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
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.
The original post had 9 comments I'm in the process of migrating over.