3 ms·

> 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.

by shiro 17y ago

> 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.

Daniel_Newby 17y ago
> 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.
- shiro 17y ago
  > 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.)

by shiro 17y ago

Daniel_Newby 17y ago

> 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.

shiro 17y ago
> 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.)