[Python-ideas] A Continuations Compromise in Python

[John Graham]

Your comment on the iterative solution also erasing the stack trace is
a good one.  Insofar as the specific problem, I've always thought
maybe ... notation could capture recursive stack traces easier...

Traceback (most recent call last):
 File "<stdin>", line 1, in <module>
 File "<stdin>", line 3, in spam
 ...
 File "<stdin>", line 2, in spam
 ValueError: Nobody expects the Spanish Inquisition!

although I believe that particular syntax is used in Doctest (although
would it be incorrect in this case?).  The same could be used in a
'continue' statement, indicating the first one or two functions and
the last one or two functions, similar to sequences described in math
(1,2,...,n-1,n).  Anywho, I'm no expert on stack traces so if someone
else had a better idea I'm all ears.

I'd also like to agree with your statement that TCO is not just about
execution speed.  In fact, to clear up this whole argument, lets go
ahead and claim that TCO code will never be faster than the iterative
version of things.  TCO will prevent things from blowing the stack.
And despite many of the cases presented, there are some things that
CAN'T be done iteratively, simply, as the commenters to the post you
linked to pointed out.  Mutual recursion is one, as the iterative
solution to that begins to grow in size and use some more complex
looping logic.  Actual continuation style, where you're making
tail-calls to OTHER functions, can only be represented by a
trampoline.  Which, as I've stated before, is hardly a simpler
solution.  The complexity of the iterative solution simply goes up
from there.

I want to clarify that the original suggestion was never to implement
TCO 'implicitly'.  I don't want to have to 'write my function just
right' to get TCO to work.  This is why the keyword was suggested, as
it'd be an explicit way to tell the interpreter 'this is a tail-call'.
 If it's not, then throw an exception.  Otherwise, there's no
optimizations going on behind the scenes that I'm not aware of, which
is the case in languages that just turn tail calls optimized behind
the scenes.  I agree completely with Guido that this can confuse
newcomers.

So to clarify (and don't get me wrong, this is a very interesting
conversation :), the proposal is to add explicit and unambiguous
support for the elimination of tail calls (via the use of a keyword),
rather than an implicit, confusing optimization behind the scenes, and
to do so not to increase runtime performance (per say) but instead to
allow techniques which currently blow the stack to work.




On Sun, May 3, 2009 at 10:29 AM, Steven D'Aprano <steve at pearwood.info> wrote:
> 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
> _______________________________________________
> Python-ideas mailing list
> Python-ideas at python.org
> http://mail.python.org/mailman/listinfo/python-ideas
>