Several good reasons. Firstly, Python is sufficiently dynamic that you cannot easily tell at compile time which function will be called at run time: the code can call a function that rewrites the name space as a side effect. That's generally a terrible idea, but somebody is probably doing it. EDIT: Actually, it is not a bad idea. Consider an object that plugs a worker method into itself (self.worker = some_function) and then calls it on the object, like self.worker( self ). This is pretty reasonable for Python code, but it would be hard to analyze sufficiently at compile time to eliminate tail calls.
Secondly, it is difficult to deal with a tail recursive call inside a try-catch block. Consider a multithreaded recursive tree manipulation algorithm that locks nodes as it descends into them, using finally blocks to guarantee lock release during exception unwind. The core algorithm can undergo tail call elimination, possibly releasing references to numerous large data structures. Yet the exception handling variables must remain on a stack, and some references to core algorithm variables may need to be retained. It is possible to do a hybrid stack elimination, but not easy. And the exception backtrace would have bizarre gaps where variables were eliminated, complicating debugging.
> you cannot easily tell at compile time which function will be called at run time: the code can call a function that rewrites the name space as a side effect.
I think you don't need to know which function will be called at compile time to do tail call elimination, in general. As far as the compiler can see a function call, and can see the caller has nothing to do except returning the result of the call, then the compiler doesn't need to know which function is called (It doesn't even matter if the callee has some "wrappers" like decorators. The caller can just jump to the wrapper entry).
Is there something peculiar about Python that makes it difficult? (I don't understand how your self.worker example prevents tail call elimination, but maybe that's because I don't know enough about Python.)
> Secondly, it is difficult to deal with a tail recursive call inside a try-catch block.
A call made inside try-catch block is not a tail call, almost by definition. The compiler may perform something clever, but from the programmers POV, it's sufficient to regard them as non-tail calls.
> I don't understand how your self.worker example prevents tail call elimination, ...
If some_function calls a bunch of random functions, it is very, very hard to tell if those calls will execute "self.worker = some_other_function" as a side effect. This happens because everything in Python can be changed on the fly; languages with true constants don't have this problem.
> A call made inside try-catch block is not a tail call, almost by definition.
Right, and since Python makes wide use of exceptions, true tail call elimination is often impossible. The best you can get is partial elimination, and it is a PITA.
> If some_function calls a bunch of random functions, it is very, very hard to tell if those calls will execute "self.worker = some_other_function" as a side effect.
I still don't see, since changing self.worker at runtime does not matter at all. Whether a call is at tail position or not can be determined only looking at the caller code. If self.worker(self) appear at the tail position, compiler can generate code sequence something like this:
discard caller's frame.
push the value of 'self' as argument.
retrieve value of 'worker' attribute.
jump to the method pointed by the value.
The value of worker attribute may be different every time this code is executed, but that's totally fine.
The only construct I can think of so far that prevents compile-time tail call elimination is first class macros, since with them the compiler cannot determine a call is tail position or not. It is the extreme end of dynamism. But even with them, you can do runtime tail call elimination. It might not be as efficient, though.
> Right, and since Python makes wide use of exceptions, true tail call elimination is often impossible.
Wait... are we talking about the same thing?
What I mean by tail call elimination is converting tail calls to jumps. It has nothing to do with non tail calls, hence wide use of try-catch block has nothing to do with "true tail call elimination".
What you can argue is something like: because try-catch block is so abundant in Python code that tail call elimination won't add much value to typical Python programs. I don't know if it's true or not, but it's plausible. (E.g. C++ has to run destructors when stack-allocated objects goes out of scope, which makes most of calls non-tail calls, hence effects of tail call elimination will be limited.)
Secondly, it is difficult to deal with a tail recursive call inside a try-catch block. Consider a multithreaded recursive tree manipulation algorithm that locks nodes as it descends into them, using finally blocks to guarantee lock release during exception unwind. The core algorithm can undergo tail call elimination, possibly releasing references to numerous large data structures. Yet the exception handling variables must remain on a stack, and some references to core algorithm variables may need to be retained. It is possible to do a hybrid stack elimination, but not easy. And the exception backtrace would have bizarre gaps where variables were eliminated, complicating debugging.