[Python-ideas] Tail recursion elimination

[Andrew Barnert]

Whether or not you really need it, adding it to Python is a fun challenge that's worth trying.

The first problem is that CPython makes a C function call for every Python function call, and C doesn't eliminate tail calls; the only way to do it manually is with longjmp. So, you probably want to add it to either Stackless or PyPy instead.

Second, detecting tail recursion to eliminate it is pretty hard, and you have to do a runtime check to detect that the function being called is already on the stack, which potentially slows down every function call. Fortunately, eliminating _all_ tail calls instead of just recursive ones is a lot easier in Python, and it's better in just about every way.

Third, eliminating tail calls means the aren't on the stack at runtime, which means there's no obvious way to display useful tracebacks. I don't think too many Python users would accept the tradeoff of giving up good tracebacks to enable certain kinds of non-pythonic code, but even if you don't solve this, you can always maintain a fork the same way that Stackless has been doing.

Meanwhile, it will be a lot easier to do this in steps: First add a tail statement that's like return except that its expression must be a Call; instead of compiling to a return bytecode it replaces the call_function* with a tail_function*, which you can initially fake by doing a call and return. Next, write a real implementation of tail_function* that jumps instead of calling and returning. Next, write a simple keyhole optimizer that converts any call_function* followed immediately by return into a tail_function*, which makes your custom syntax unnecessary, so you can revert it. Finally, solve the traceback problem in some way. (Maybe you could do something tricky here: Split the stack frame object into the bit needed for tracebacks and the bit needed for actual calling; tail call elimination takes care of the second one, and a different optimization to detect and run-compress loops takes care of the first one. Making that fast enough so that it doesn't slow down every call unacceptable probably means keeping around a dict mapping some kind of "position" record to frames.)

Sent from a random iPhone

On Jan 18, 2014, at 7:58, musicdenotation at gmail.com wrote:

>> On Jan 18, 2014, at 22:08, "Joao S. O. Bueno" <jsbueno at python.org.br> wrote:
> 
> 
>> You can use tail recursion elimination in Python as it is today.
> I have seen many "implementations" of tail-call optimization, and their common problem is that they all require special syntax to work. I need a solution that is directly usable with Python's orrdinary return statement.
> _______________________________________________
> Python-ideas mailing list
> Python-ideas at python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20140118/4b25ec3a/attachment-0001.html>