Tail-call Optimization

from macropy.experimental.tco import macros, tco

def fact(n, acc=1):
    if n == 0:
        return acc
        return fact(n-1, n * acc)

print(fact(10000))  # doesn't stack overflow
# 28462596809170545189064132121198688901...

Tail-call Optimization is a technique which will optimize away the stack usage of functions calls which are in a tail position. Intuitively, if a function A calls another function B, but does not do any computation after B returns (i.e. A returns immediately when B returns), we don’t need to keep around the stack frame for A, which is normally used to store where to resume the computation after B returns. By optimizing this, we can prevent really deep tail-recursive functions (like the factorial example above) from overflowing the stack.

The @tco decorator macro doesn’t just work with tail-recursive functions, but also with any generic tail-calls (of either a function or a method) via trampolining, such this mutually recursive example:

from macropy.experimental.tco import macros, tco

class Example(object):

    def odd(n):
    if n < 0:
        return odd(-n)
    elif n == 0:
        return False
        return even(n - 1)

    def even(n):
        if n == 0:
            return True
            return odd(n-1)

print(Example().even(100000))  # No stack overflow
# True

Note that both odd and even were both decorated with @tco. All functions which would ordinarily use too many stack frames must be decorated.


How is tail recursion implemented? The idea is that if a function f would return the result of a recursive call to some function g, it could instead return g, along with whatever arguments it would have passed to g. Then instead of running f directly, we run trampoline(f), which will call f, call the result of f, call the result of that f, etc. until finally some call returns an actual value.

A transformed (and simplified) version of the tail-call optimized factorial would look like this

def trampoline_decorator(func):
    def trampolined(*args):
        if not in_trampoline():
            return trampoline(func, args)
        return func(*args)
    return trampolined

def trampoline(func, args):
  while True:
        result = func(*args)
        with patterns:
            if ('macropy-tco-call', func, args) << result:
                if ignoring:
                    return None
                    return result

def fact(n, acc):
    if n == 0:
        return 1
        return ('macropy-tco-call', fact, [n-1, n * acc])