Possibly Pythonic Tail Call Optimization (TCO/TRE)

[Ian Burnette]

Hi there,

First, please forgive me if this is the wrong venue to be suggesting this
idea-- I'm just following the PEP workflow page
<https://www.python.org/dev/peps/pep-0001/#pep-workflow>.

I've recently been playing around with Clojure, and I really like the way
they've overcome the JVM not supporting TRE. The way Clojure solves this
problem is to have a built in "recur" function that signals to the Clojure
compiler to convert the code to a loop in the JVM. In python we could do
something similar by having a *recur(*args, **kwargs)* function that
removes its parent from the stack and then runs the parent function again
with the given arguments. It would look something like this:

def factorial(n, acc=1):

if n == 0:

return acc

else:

return recur(n-1, acc=(acc*n)) #signals to the interpreter to trigger TRE


# Doesn't overflow the stack!

factorial(30000)


I've also created a plugin
<https://github.com/blackfedora/recur.py/blob/master/recur.py> that mocks
this behavior using the try/except looping method that others
<http://code.activestate.com/recipes/474088/> have utilized to implement
TCO into python. Of course, my plugin still requires a decorator and the
overhead of transmitting information through an exception. Implementing
recur with interpreter support should lead to much better performance.

I've read Guido's reasoning against dynamic TCO
<http://neopythonic.blogspot.co.uk/2009/04/tail-recursion-elimination.html>,
but I believe many of his concerns can be boiled down to "I don't want the
interpreter doing things the user didn't expect, and I just don't think
this is important enough to affect everyone's experience". This recur
approach solves that by giving functional python users the ability to
explicitly tell the interpreter what they want without changing how other
users interact with the interpreter. Guido also notes that TRE removes
removes stack trace data. While a more subtle garbage collection scheme
would help alleviate this problem, there's really no avoiding this. My only
defense is that this solution is at least explicit, so users should know
that they're implementing code that might produce a completely unhelpful
stack trace.

Thank you for your time and consideration; I hope this was at least
interesting!

All the best,
Ian Burnette

*Ian Burnette*
Python/Django Developer
Cox Media Group
P: 843.478.5026
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20150711/302cf465/attachment.html>