[Python-ideas] A Continuations Compromise in Python

[Steven D'Aprano]

On Mon, 4 May 2009 12:34:53 am Steven D'Aprano wrote about removing 
tail-recursion:

> In this case, the speed-up could (in principle) be by up to a factor
> of five or so, not a mere couple of percent. 

Sorry, that "factor of five" is probably bogus. I got that for some 
comparisons between recursion and iteration, but the speed difference 
is probably not relevant to the sort of tail call optimizations we're 
discussing. I will *not* defend my suggestion of 5x faster, however, on 
the basis of my Towers of Hanoi test, I think 2x faster is conceivable.


I found Guido's recent blog post of tail call optimization:

http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

Worthwhile reading. Also read the commenters: they make some interesting 
points, such as that tail call optimization is a general technique 
applicable to more than just recursion.

Guido's largest objection to TCO is that it ruins nice stack traces when 
you get an exception. I must admit I've never understood this argument. 
Perhaps I'm missing something, but I've never considered the stack 
trace you get in recursive functions useful. Here's an example:

>>> def spam(n=0):
...     if n == 10: raise ValueError(
...     'Nobody expects the Spanish Inquisition!')
...     spam(n+1)
...
>>> spam()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 3, in spam
  File "<stdin>", line 3, in spam
  File "<stdin>", line 3, in spam
  File "<stdin>", line 3, in spam
  File "<stdin>", line 3, in spam
  File "<stdin>", line 3, in spam
  File "<stdin>", line 3, in spam
  File "<stdin>", line 3, in spam
  File "<stdin>", line 3, in spam
  File "<stdin>", line 3, in spam
  File "<stdin>", line 2, in spam
ValueError: Nobody expects the Spanish Inquisition!

To me, all those identical "line 3, in spam" lines are just noise. They 
get in the way of a nice stack trace! What is Guido seeing that I'm 
not? Hopefully he isn't counting them by hand to see how deep he got 
into the recursion!

I wish there was a way to tell Python to just throw that white noise 
away and give me the sort of stack trace I get from a loop function. 
(It's not so bad when there only ten lines, but when there's 1000, you 
might very well fill your xterm's buffer and lose valuable history.)

>>> def ham(n=0):
...     while n < 0:
...             n += 1
...     raise ValueError('Nobody expects the Spanish Inquisition!')
...
>>> ham()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in ham
ValueError: Nobody expects the Spanish Inquisition!

Which of course illustrates the point that Guido's recommendation to 
re-write the recursion as an iterative loop by hand will have the same 
effect on the stack trace as iteration already does. I haven't heard 
anyone argue that stack traces in a while or for loop should show you 
the entire history of the loop, so I wonder why recursive calls should 
be treated as sacrosanct?

(I have nothing to say about Guido's other arguments against TCO at this 
point, but my silence should not be interpreted as agreement.)



-- 
Steven D'Aprano