Possibly Pythonic Tail Call Optimization (TCO/TRE)

[Chris Angelico]

On Sun, Jul 12, 2015 at 8:20 AM, Ian Burnette <ian.burnette at gmail.com> wrote:
>
> 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 that mocks this behavior using the try/except looping method that others 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.
>

When a function is purely tail-recursive like this, it's trivial to
convert it at the source code level:

def factorial(n):
    acc = 1
    while n > 0:
        acc *= n
        n -= 1
    return acc

The cases that _can't_ be converted this trivially are the ones that
usually can't be converted automatically either - the best case I can
think of is tree traversal, where one of the calls could be tail-call
optimized:

def traverse(node, func):
    if node.left: traverse(node.left, func)
    func(node)
    if node.right: return recur(node.right, func)

(By the way, what happens if you call recur() without returning its result?)

It still needs stack space for all the left calls, so it's not really
benefiting that much from TCO. Where does the advantage show up? Why
is it worth writing your code recursively, only to have it be
implemented iteratively? Warping your code around a recursive solution
to make it into a perfect tail call usually means making it look a lot
less impressive; for instance, the 'acc' parameter in your above code
has no meaning outside of transforming the recursion into tail
recursion.

https://xkcd.com/1270/

ChrisA