[OskarS]

I find that argument very unpersuasive: the optimization is tail CALL elimination, not tail RECURSION elimination, and the call to f(x-1) is certainly a tail call. I see no reason you couldn't optimize away that stack frame. "Tail recursion" is a technique in functional programming, that depends crucially on tail call elimination, but the tail call itself absolutely does not have to be recursive (it just has to be in tail position), it's just that it happens to be so in a tail recursive algorithm.

Incidentally: I don't believe that is a violation of lexical scoping. f is scoped globally, inside itself f is not defined, so f(x-1) refers to the globally scoped f. When it's reassigned, you reassign the global f. Nothing here violates lexical scoping, since f is never scoped anywhere other than globally (note that the blog post never claims it is, either)

I don't disagree with Guido's larger point, though, Python probably shouldn't use TCO. The debugging/stack trace point is very true, and also it's just not Pythonic to write algorithms TCO style. You just don't need to, in Python.

[wk_end]

It’s somewhat unclear, but in this case Guido is responding directly to a particular - broken - attempt to add TCO to self-tail calls to CPython in the fashion described. I assume, having not read the linked article, that the author must have done that as a quick hack - because CPython’s bytecode must allow arbitrary jumping within a function body but doesn’t have the means to express a true tail call. I guess.

He goes on, later in the post, to describe how he’d go about adding tail calls - although this treatment is also confused.

[JulianChastain]

Well I mean the reason you can't optimize away the stack frame is that at any point during runtime f can be redefined to be a different function. In the above example, do you agree that any tail call elimination would result in the wrong evaluation of `g(5) = 0` instead of the correct `g(5) = 4`?

And your understanding of why python doesn't permit TCE is because functions are globally scoped with indefinite extent?

[OskarS]

> In the above example, do you agree that any tail call elimination would result in the wrong evaluation of `g(5) = 0` instead of the correct `g(5) = 4`?

No, I very much do not agree: it is still a tail call, and can use tail call optimization. When it calls f(x-1), regardless of whether f has been reassigned or not, you have to resolve what f is, because it COULD have been reassigned. The Python interpreter has to do this regardless, the fact that it's recursive is irrelevant.

You do that, and you get the function value you need to call (it could be the original value assigned to f, it could be the new value, it doesn't matter). At that point, nothing that is remaining on the stack frame except the arguments and return address is needed anymore, so you can reuse it for the the call to f(x-1). That is what tail call elimination is.

I'll grant that it's entirely possible that I've misunderstood this whole thing and that Guido is correct (he's a much smarter fella than me), but if so, I have no idea why I'm wrong.

> And your understanding of why python doesn't permit TCE is because functions are globally scoped with indefinite extent?

No, not at all, that was just a side note about why you were wrong to say it violated lexical scoping (it doesn't). My understanding of why Guido didn't do this is because he didn't think tail call elimination is a very useful feature for Python, and it destroys stack traces. Both of which I agree with. I just don't buy the other technical reason.