[Python-ideas] Tail recursion elimination

[Steven D'Aprano]

On Sun, Jan 19, 2014 at 12:01:00PM -0800, Andrew Barnert wrote:
> From: Steven D'Aprano <steve at pearwood.info>
[...]
> > 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).

But if TCE becomes opt-in, say by the proposed "return from" syntax, 
then you can keep your cake and eat it too. I can decide at *edit* time, 
"this function should have TCE enabled", and leave the rest of my code 
to have the "normal" behaviour.

If the choice was "TCE everywhere" versus "TCE nowhere", I would choose 
nowhere too. But it need not be that choice.


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

Yes, you got me. It was throw away code, which I've since thrown away, 
but if I recall correctly one of the three functions was tail-recursive. 
I was more concerned with making the rhetorical point that sometimes the 
only part of the traceback you care about is the bit that actually 
fails, at which point the rest of the traceback is noise and you might 
choose to prefer performance over a more detailed traceback.


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

I work with one of those guys :-(


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

You seem to be assuming that bugs in deep algorithms only manifest 
themselves in sufficiently deep data sets that turning TCE off will 
cause a recursion error before the true bug manifests, thus masking the 
bug you care about by mere lack of resources.

I don't believe that is the case for all bugs, or even a majority. If it 
is true for some bugs -- of course it will be -- then a solution is to 
add enough temporary debugging code (e.g. logging, or even just good ol' 
print) to see enough of what is going on that you can identify the bug, 
stacktrace or no stacktrace. Chances are you would have to write some 
temporary debugging code regardless of whether the algorithm was 
iterative or recursive, TCE or no TCE.



-- 
Steven