[Python-Dev] Explicit Tail Calls

[Adam Olsen]

On 10/12/07, Shane Hathaway <shane at hathawaymix.org> wrote:
> Hello,
>
> I'm interested in seeing a good way to write tail calls in Python.  Some
> algorithms are more readable when expressed using tail recursion.
>
> I know tail call optimization has been discussed before [1], but I would
> like to consider a different approach.  The previous discussion centered
> on implicit tail call optimization, which incurs the risk of changing
> the behavior of currently working code.  (For example, is it safe to
> optimize tail calls within try...finally blocks?  Probably not.  And I
> generally want all stack frames to appear in tracebacks, unless I say
> otherwise.)
>
> I would like to suggest an explicit form of tail calls.  A new built-in
> exception type called "Return" will be added, and it will be used like this:

So long as you're willing to make it explicit (which I strongly
encourage), you can accomplish nearly anything you'd like with
decorators and functions.  There doesn't seem to be strong enough use
cases to get anything into the core language anyway.

If you don't like the existing decorator recipes I can help you come
up with a better one in private, off the list.


> def fact2(n, v):
>     if n:
>         raise Return(fact2, n-1, v*n)
>     else:
>         return v

I hope your use cases are better than this. ;)


> The interpreter will catch Return exceptions and use them to call
> something else.  The caller of a function that uses "raise Return" will
> see the result of the tail call as the returned value, rather than the
> Return exception.  I am not yet considering implementation details.
>
> Not all algorithms are good candidates for this.  I used the fact2
> example only because it's readily available.  I know there are other
> people interested in tail call optimization in Python [2] [3]; perhaps
> some of them are watching and can provide better examples.
>
> Furthermore, there might be some explicit syntax that converts "return
> f(...)" statements to "raise Return(f, ...)", such as a decorator.
> However, I'm less interested in the syntax and more interested in the
> basic capability.
>
> Shane
>
> [1] http://mail.python.org/pipermail/python-dev/2004-July/046150.html
> [2] http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/474088
> [3] http://www.voidspace.org.uk/python/weblog/arch_d7_2007_09_22.shtml#e833
> _______________________________________________
> Python-Dev mailing list
> Python-Dev at python.org
> http://mail.python.org/mailman/listinfo/python-dev
> Unsubscribe: http://mail.python.org/mailman/options/python-dev/rhamph%40gmail.com
>


-- 
Adam Olsen, aka Rhamphoryncus