Thunks, Trampolines and Continuation Passing

Here is a thunk, a kind of delayed apply that takes a function and arguments but, rather than calling the function right away returns another function that, when called, will call the first function with the arguments originally given.

thunk = lambda name, *args: lambda: name(*args)

Here is a trampoline that basically unwraps nested thunks until a result is found.

def _trampoline(bouncer):
    while callable(bouncer):
        bouncer = bouncer()
    return bouncer

Here is a useful wrapper function that turns a function into a trampolined version.

trampoline = lambda f: lambda *args: _trampoline(f(*args))

Now let's just define one more ingredient, an identity function.

identity = lambda x: x

Now we can write factorial in continuation-passing style:

_factorial = lambda n, c=identity: c(1) if n == 0 else thunk(_factorial, n - 1, lambda result: thunk(c, n * result))

and trampoline it:

factorial = trampoline(_factorial)

We now have a factorial function that doesn't have stack limitations. You can say

print factorial(100000)

and (a couple of minutes later) Python will happily display the result :-)

I did consider currying thunk:

thunk = lambda name: lambda *args: lambda: name(*args)

so the CPS factorial would be:

_factorial = lambda n, c=identity: c(1) if n == 0 else thunk(_factorial)(n - 1, lambda result: thunk(c)(n * result))

UPDATE: Sorry to the first few commentors, due to a cute-and-paste SNAFU I was using the curried version of thunk for the first definition of _factorial. Now fixed.