[Python-ideas] Tail recursion elimination

[Andrew Barnert]

From: Steven D'Aprano <steve at pearwood.info>

Sent: Saturday, January 18, 2014 4:45 PM


> On Sat, Jan 18, 2014 at 10:29:46AM -0800, Andrew Barnert wrote:
> 
>>  Whether or not you really need it, adding it to Python is a fun 
>>  challenge that's worth trying.
> 
> "Need" is a funny thing.

Which I why I made that point. It's not a completely objective question, and it may be hard for the OP (or you, or anyone else) to convince anyone that he "needs" it even though he does (or, more importantly, convince people that _they_ need it). If so, he doesn't have to let that stop him from writing and sharing an implementation. It may turn out that, once people have a chance to play with it, that will convince everyone better than any abstract argument he could make. If not, at least he's had fun, learned about CPython internals, and, most importantly, produced a fork that he can maintain as long as he thinks he needs it. Depending on your time and resources, that may not be worth doing, but that's the same decision as any other development project; there's nothing actually stopping anyone from doing it if it's worth their while, so anyone who wants this should consider whether it's worth their while to do it.

> You can go a long way without recursion, or only shallow recursion. In 
> 15 years + of writing Python code, I've never been in a position that I 
> couldn't solve a problem because of the lack of tail recursion. But 
> every time I manually convert a recursive algorithm to an iterative one, 
> I feel that I'm doing make-work, manually doing something which the 
> compiler is much better at than I am, and the result is often less 
> natural, or even awkward. (Trampolines? Ewww.)


But the same is true for converting a naive recursive algorithm to tail-recursive. It's unpleasant make-work, just like converting it to iteration. In a language like Common Lisp, it's about the same amount of work, but the tail-recursive version often ends up looking more natural. In a language like Python, where we typically deal in iterables rather than recursive data structures, I believe it would often be _more_ work rather than the same amount, and end up looking a lot less natural rather than more. I'm sure there would be exceptions, but I suspect they would be rare.

>>  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, 
> 
> What makes you say that it is "non-pythonic"? You seem to be assuming 
> that *by definition* anything written recursively is non-pythonic.

Not at all. There's plenty of code that's naturally recursive even in Python—and much of that code is written recursively today. For a good example, see os.walk.

However, the main driver for TCE is the ability to write looping constructs recursively, which is not possible without it (unless the thing you're looping over is guaranteed not to be too big). Look at any tutorial on tail recursion; it's always recursing over a cons list or something similar. And looping that way in Python will almost always be non-pythonic, because you will have to drive the iterable manually. Again, there are surely exceptions, but I doubt they'd be very common.

> In fact, in some cases, I *would* willingly give up *non-useful* 

> tracebacks for the ability to write more idiomatic code. Have you seen 
> the typical recursive traceback?

But if you eliminate tail calls, you're not just eliminating recursive tracebacks; you're eliminating every stack frame that ends in a tail call. Which includes a huge number of useful frames.

If you restrict it to _only_ eliminating recursive tail calls, then it goes from something that can be done at compile time (as I showed in my previous email) to something that has to be done at runtime, making every function call slower. And it doesn't work with mutual or indirect recursion (unless you want to walk the whole stack to see if the function being called exists higher up—which makes it even slower, and also gets us back to eliminating useful tracebacks).

> py> a(7)
> Traceback (most recent call last):
>   File "<stdin>", line 1, in <module>
>   File "./rectest.py", line 2, in a
>     return b(n-1)
>   File "./rectest.py", line 5, in b
>     return c(n-1) + a(n)
>   File "./rectest.py", line 2, in a
>     return b(n-1)
>   File "./rectest.py", line 5, in b
>     return c(n-1) + a(n)
>   File "./rectest.py", line 2, in a
>     return b(n-1)
>   File "./rectest.py", line 5, in b
>     return c(n-1) + a(n)
>   File "./rectest.py", line 2, in a
>     return b(n-1)
>   File "./rectest.py", line 5, in b
>     return c(n-1) + a(n)
>   File "./rectest.py", line 2, in a
>     return b(n-1)
>   File "./rectest.py", line 5, in b
>     return c(n-1) + a(n)
>   File "./rectest.py", line 2, in a
>     return b(n-1)
>   File "./rectest.py", line 5, in b
>     return c(n-1) + a(n)
>   File "./rectest.py", line 9, in c
>     return 1/n
> ZeroDivisionError: division by zero
> 
> The only thing that I care about is the very last line, that function c 
> tries to divide by zero. The rest of the traceback is just noise, I 
> don't even look at it.

Your example is not actually tail-recursive.

I'm guessing you know this, and decided that having something that blows up fast just to have an example of a recursive traceback was more important than having an example that also fits into the rest of the discussion—which is perfectly reasonable. 

But it's still worth calling that out, because at least half the blog posts out there that say "Python sucks because it doesn't have TCE" prove Python's suckiness by showing a non-tail-recursive algorithm that would blow up exactly the same way in Scheme as in Python. 

> Now, it's okay if you disagree, or if you can see something useful in 

> the traceback other than the last entry.

Sure. Unless that line in b is the only place in your code that ever calls c, I think it would be useful to know how we got to c and why n is 0. If that isn't useful, than _no_ tracebacks are ever useful, not just recursive ones.

> I'm not suggesting that TCE 
> should be compulsary. I would be happy with a commandline switch to 
> turn it on, or better still, a decorator to apply it to certain 
> functions and not others. I expect that I'd have TCE turned off for 
> debugging.

But the primary reason people want TCE is to be able to write functions that otherwise wouldn't run. Nobody asks for TCE because they're concerned about 2KB wasted on stack traces in their shallow algorithm; they ask for it because their deep algorithm fails with a recursion error. So, turning it off to debug it means turning off the ability to reproduce the error you're trying to debug.

>>  but even if you don't solve this, you can always 

>>  maintain a fork the same way that Stackless has been doing.
> 
> Having to fork the entire compiler just to write a few functions in 
> their most idiomatic, natural (recursive) form seems a bit extreme, 
> wouldn't you say? 


Not necessarily.

The whole reason Stackless exists is to be able to write some algorithms in a natural way that wasn't possible with mainline CPython. At least early on, it looked at least plausible that Stackless would eventually be merged into the main core, although that turned out not to happen. There are some core language changes that were inspired by Stackless. Someone (Ralf Schmidt, I think?) was able to extract some of Stackless's functionality into a module that works with CPython, which is very cool. But even without any of that, people were able to use Stackless when they wanted to write code that required its features. That's surely better than not being able to write it, period.

And a TCE fork could go the same way. It might get merged into the core one day, or it might inspire some changes in the core, or it might turn out to be possible to extract the key functionality into a module for CPython—but even if none of that happens, you, and others, can still use your fork when you want to.

If you prefer to call it a patch or a branch or something else instead of a fork, that's fine, but it's basically the same amount of work either way, and there's nothing stopping anyone who wants it from doing it.