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 =

lambdaname, *args:lambda: name(*args)

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

def_trampoline(bouncer):whilecallable(bouncer): bouncer = bouncer()returnbouncer

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

trampoline =

lambdaf:lambda*args: _trampoline(f(*args))

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

identity =

lambdax: x

Now we can write factorial in continuation-passing style:

_factorial =

lambdan, c=identity: c(1)ifn == 0elsethunk(_factorial, n - 1,lambdaresult: 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 =

lambdaname:lambda*args:lambda: name(*args)

so the CPS factorial would be:

_factorial =

lambdan, c=identity: c(1)ifn == 0elsethunk(_factorial)(n - 1,lambdaresult: 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.

Tweet

The original post was in the categories: python algorithms but I'm still in the process of migrating categories over.

The original post had **9 comments** I'm in the process of migrating over.