Trampolining for recursion...

In essence, CPS (continuation passing style) is a method of calling functions where instead of returning a value, you pass the results to another function (the continuation) provided as an argument. I wont go too deep into the reasoning behind this, as it's usually not used directly but rather as a middle representation of programming languages by some compiler/interpreter (read more on the wikipedia link).

The big downside is that you're bombarding the stack with function frames for every call, going deeper and deeper, but never returning (you just keep passing what would be the return value to another function).

One nifty method of avoiding this is to use a trampoline. A trampoline resembles a stream/lazy-list to anyone who's read SICP. Essentially, instead of calling functions from within another function, you return a bounce "call" to the trampoline which makes the call for you, doing the same with the return value of that call until it gets a land (a non-bounce return). This avoids the use of the stack for function calls, but allows you to use function closure as a means of saving state.

That being said, here is a simple trampoline implementation in Python showing a recursive fibonacci function implemented in CPS:

class Call:
  def __init__(self, fn, *args, **kwargs):
    self.call = lambda: fn(*args, **kwargs)

def trampoline(obj):
  while isinstance(obj, Call):
    obj = obj.call()
  return obj

def fibonacci(k, n):
  if n < 2:
    return Call(k, n)
  def with_a(a):
    def with_b(b):
      return Call(k, a + b)
    return Call(fibonacci, with_b, n - 1)
  return Call(fibonacci, with_a, n - 2)

call = fibonacci(lambda x: x, 20)

print trampoline(call)

Here is a normal fibonacci function, memoized, that fails due to exceeding Pythons recursion limit. The problem being, of course, that you have to recurse down deep enough to use the leaf calls to accumulate to the trunk:

def memoized(func):
  cache = {}
  def decorator(*args):
    if args not in cache:
      cache[args] = func(*args)
    return cache[args]
  return decorator

@memoized
def fibonacci(n):
  if n < 2:
    return n
  return fibonacci(n - 2) + fibonacci(n - 1)
print fibonacci(1000)

Here, however, is essentially the same function (memoized) implemented using a trampoline. The trampoline allows it to "recurse" all the way to the leaf calls because the calls are actually being made external to the function and state is being preserved in the with_a/with_b closures:

def kmemoized(func):
  cache = {}
  def decorator(k, *args):
    if args in cache:
      return Call(k, cache[args])
    def with_value(value):
      cache[args] = value
      return Call(k, value)
    return Call(func, with_value, *args)
  return decorator

@kmemoized
def fibonacci(k, n):
  if n < 2:
    return Call(k, n)
  def with_a(a):
    def with_b(b):
      return Call(k, a + b)
    return Call(fibonacci, with_b, n - 1)
  return Call(fibonacci, with_a, n - 2)

Practical for typical application development? Probably not...

A neat concept to play around with (or an interesting strategy at generating Python code)? Definitely!

(Somewhat) related wikipedia articles: continuation, functional-programming, tail-call-optimization, thunk, closure