James Tauber

journeyman of some

blog > 2008 > 03 > 30 >

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.

Categories:
prev « python » next
prev « algorithms

Comments (9)

Juan Manuel Gimeno on March 30, 2008:

I think your definition of _factorial has a problem: thunk must be given both the function and the arguments of the delayed call (if needed).

So the definition should be:

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

Thanks for your nice article from and old schemer

Juan Manuel Gimeno

James Bennett on March 30, 2008:

Yes, but can it jump off the Empire State Building? ;)

Dave Kirby on March 30, 2008:

With the original code I got a syntax error. With Juan's change I got "maximum recursion depth exceeded" for factorial(1000).

Incidentally is there any advantage of this approach over:

def factorial(x): return reduce(operator.mul, xrange(1, x+1))

It has always puzzled me why factorial is always used as an example of functional/recursive programming, when the iterative approach is invariably faster and simpler.

Lawrence Oluyede on March 30, 2008:

PyPy has also a thunk mode: http://codespeak.net/pypy/dist/pypy/doc/objspace-proxies.html#the-thunk-object-space

Nice trick btw

James Tauber on March 30, 2008:

@Juan sorry, I cut-and-paste the version of _factorial that used the curried thunk both times. My original code is now back in place.

Your code still has a problem. You need to thunk the continuation.

James Tauber on March 30, 2008:

@James: I haven't grokked that approach yet, but nice reference.

James Tauber on March 30, 2008:

@Dave my code should be fixed now. I pasted the wrong version of the code.

Regarding the iterative approach. I don't think the CPS approach has any advantage.

I only wrote it to learn about CPS :-)

Dave Kirby on March 30, 2008:

I just saw this and thought it relevant to this post - the evolution of a Haskell programmer:

http://www.willamette.edu/~fruehr/haskell/evolution.html

Juan Manuel Gimeno on March 31, 2008:

@James: You're right, I missed to thunk the continuation.

Tanks,

Juan Manuel
Created: March 30, 2008
Last Modified: March 30, 2008
Author: jtauber