[Python-ideas] Tail recursion elimination

musicdenotation at gmail.com musicdenotation at gmail.com
Sat Jan 18 15:52:17 CET 2014


On April 22, 2009, Guido van Rossum wrote:
> First, as one commenter remarked, TRE is incompatible with nice stack traces: when a tail recursion is eliminated, there's no stack frame left to use to print a traceback when something goes wrong later. This will confuse users who inadvertently wrote something recursive (the recursion isn't obvious in the stack trace printed), and makes debugging hard. Providing an option to disable TRE seems wrong to me: Python's default is and should always be to be maximally helpful for debugging.
What are "nice" stack traces? If you mean stack traces that record every function call then it is not nice and helpful at all given their length. Do loops have nice stack traces as you mean it? No. When something goes wrong in a loop, you don't get to see every iteration in the stack trace. You debug loops by examining the values of variables in the iteration it goes wrong. Likewise you debug a tail recursive function by examining the arguments that went into the function call that blows up. And if you don't want to turn on TRE by default, you can turn it off and offer an option to enable.
> Second, the idea that TRE is merely an optimization, which each Python implementation can choose to implement or not, is wrong. Once tail recursion elimination exists, developers will start writing code that depends on it, and their code won't run on implementations that don't provide it: a typical Python implementation allows 1000 recursions, which is plenty for non-recursively written code and for code that recurses to traverse, for example, a typical parse tree, but not enough for a recursively written loop over a large list.
Yes, it is more of a language feature than an implementation feature. But once CPython implements it, I think other implementations will follow suit or Python developers will not write code that uses TRE just like JavaScript developers don't use Mozilla-specific extensions like let keyword.
> Third, I don't believe in recursion as the basis of all programming. This is a fundamental belief of certain computer scientists, especially those who love Scheme and like to teach programming by starting with a "cons" cell and recursion. But to me, seeing recursion as the basis of everything else is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool.

This isn't a valid argument. That something isn't fundamental is almost never an argument to leave it out. (Except for Scheme.)
> Of course, none of this does anything to address my first three arguments. Is it really such a big deal to rewrite your function to use a loop? (After all TRE only addresses recursion that can easily be replaced by a loop. :-)

It isn't a big deal, yes. But why restrict programmers? Python is a multi-paradigm language anyway: you can write imperative or functional code with(out) object orientation. "There should be one – and only one – obvious way to do it"? You are misinterpreting it. It is about having only one obvious way to do things, but you have removed another obvious way to do certain things because certain problems are better expressed using recursion rather than looping (traversing a tree, for example). I think the most obvious way to do something is how it is defined. If there was really one way to do anything, there should be no for-loops, list comprehensions, or even object orientation at all in Python. Remember that recursion is either something lower- or higher-level than looping. And if you don't like abstractions over primitive concepts, you should be coding in machine code right now.





 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20140118/0ac6789e/attachment.html>


More information about the Python-ideas mailing list