# 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.

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.