Skip to main content

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

Comments

shi said…
Another way to avoid blowing the stack in the case of your memoized function is to gradually fill the memoization table:

def fib_wrapper(n):
....for c in xrange(n):
........fib(c)
....return fib(n)

fib_wrapper(1000)

Popular posts from this blog

Procedural music with PyAudio and NumPy

Combining two of my favorite pastimes, programming and music... This is the hacky "reduced to it's basic components" version of a library I've been working on for generating music and dealing with music theory.

Tweaking the harmonics by changing the shape of the harmonic components and ratios can produce some interesting sounds. This one only uses sine waveforms, but a square / saw generator is trivial with numpy.

It takes a second to generate, so don't turn your volume up too loud in anticipation (it may be loud).

import math
import numpy
import pyaudio
import itertools
from scipy import interpolate
from operator import itemgetter


class Note:

NOTES = ['c','c#','d','d#','e','f','f#','g','g#','a','a#','b']

def __init__(self, note, octave=4):
self.octave = octave
if isinstance(note, int):
self.index = note
self.note = Note.NOTES[note]
elif isinstance(note, st…

Build a Feed Reader in Python (Parts 7-9)

Part 07 Adding Jinja2 templates to a flask web application.

 Part 08 Adding static files so we can serve some CSS to style our app.

Part 09 Adding a background task to continuously update the articles while the application is running.

Write a Feed Reader in Python

I just started a new video tutorial series. This time it'll cover the entire process of writing an RSS feed reader in Python from start to finish using the feedparser module, flask, and SQLAlchemy. Expect to see about 3-4 new videos a week until this thing is finished!
Click to watch