
<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div>Whether or not you really need it, adding it to Python is a fun challenge that's worth trying.</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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<span style="-webkit-tap-highlight-color: rgba(26, 26, 26, 0.292969); -webkit-composition-fill-color: rgba(175, 192, 227, 0.230469); -webkit-composition-frame-color: rgba(77, 128, 180, 0.230469); "> 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.)</span></div><div><br>Sent from a random iPhone</div><div><br>On Jan 18, 2014, at 7:58, <a href="mailto:musicdenotation@gmail.com">musicdenotation@gmail.com</a> wrote:<br><br></div><blockquote type="cite"><div><meta http-equiv="content-type" content="text/html; charset=utf-8"><div><blockquote type="cite">On Jan 18, 2014, at 22:08, "Joao S. O. Bueno" <<a href="mailto:jsbueno@python.org.br">jsbueno@python.org.br</a>> wrote:</blockquote></div><div><br></div><blockquote type="cite"><span>You can use tail recursion elimination in Python as it is today.</span><br><blockquote type="cite"><span></span></blockquote><blockquote type="cite"><span></span></blockquote><blockquote type="cite"><span></span></blockquote><blockquote type="cite"><span></span></blockquote><blockquote type="cite"><span></span></blockquote><blockquote type="cite"><span></span></blockquote><blockquote type="cite"><span></span></blockquote><blockquote type="cite"><span></span></blockquote><blockquote type="cite"><span></span></blockquote><blockquote type="cite"><span></span></blockquote><blockquote type="cite"><span></span></blockquote></blockquote>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 <i>return</i> statement.</div></blockquote><blockquote type="cite"><div><span>_______________________________________________</span><br><span>Python-ideas mailing list</span><br><span><a href="mailto:Python-ideas@python.org">Python-ideas@python.org</a></span><br><span><a href="https://mail.python.org/mailman/listinfo/python-ideas">https://mail.python.org/mailman/listinfo/python-ideas</a></span><br><span>Code of Conduct: <a href="http://python.org/psf/codeofconduct/">http://python.org/psf/codeofconduct/</a></span></div></blockquote></body></html>