[Python-ideas] Tail recursion elimination

[Steven D'Aprano]

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. There's nothing you can do with a for-loop that 
you can't do with a while-loop, but that doesn't mean we don't "need" 
for-loops. Certain algorithms and idioms are simply better written in 
terms of for-loops, and certain algorithms are simply better written in 
terms of recursion than looping.

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


> 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. I do 
not subscribe to that view.

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? They're a great argument for "less is 
more". What normally happens is that you get a RuntimeError and the 
traceback blows away your xterm's buffer with hundreds of identical or 
near-identical lines. But even in the case where you didn't hit the 
recursion limit, the traceback is pretty much a picture of redundancy 
and noise:


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.

Now, it's okay if you disagree, or if you can see something useful in 
the traceback other than the last entry. 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 perhaps not -- it's not like Haskell and Scheme 
programmers are unable to debug their recursive code.

The point is that tracebacks are not sacrosanct, and, yes, I would like 
the choice between writing idiomatic recursive code and more extensive 
tracebacks. Trading off speed for convenience is perfectly Pythonic -- 
that's why we have the ability to write C extensions, is it not?


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



-- 
Steven