Tail-call Optimization

from macropy.experimental.tco import macros, tco

@tco
def fact(n, acc=1):
    if n == 0:
        return acc
    else:
        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):

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

    @tco
    def even(n):
        if n == 0:
            return True
        else:
            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.

Trampolining

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):
  _enter_trampoline()
  while True:
        result = func(*args)
        with patterns:
            if ('macropy-tco-call', func, args) << result:
                pass
            else:
                if ignoring:
                    _exit_trampoline()
                    return None
                else:
                    _exit_trampoline()
                    return result

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