The ups and downs of trampolining

With CoffeeScript

I really enjoy programming solutions that are elegant and short. I also really like to keep the functions I write as pure as possible. This often leads me to want to implement recursive solutions to problems. Recursion allows iteration without mutation. It also allows for beautifully succinct tree traversal. The problem with recursive functions, however, is that each recursive step takes up stack space; and stack space is limited. The time complexity of our recursive algorithm may be alright, but our space complexity is totally off kilter if it is linear or worse. Because of this, our recursive algorithms will typically cause a stack overflow given some arbitrary problem size. This is not acceptable.

Luckily, there are a couple of solutions to this problem! Some compilers for some languages support tail call optimization. That is great for them. Unfortunately, I rarely get to program in those languages. Another method that we can utilize in any language that supports first class functions is trampolining.

Before we start talking about trampolining, I will need to explain the concept of a thunk. Thunks are very simple things. They are simply a function call that has been wrapped in an anonymous function. Thunks are used for delayed execution. Lets see an example of this:

Say we have some function that takes in some parameters and performs some operations based on that input:

add = (a,b) -> a+b

We can thunk some given invocation of this function like so:

add_thunk = -> add(1,2)

Now we have a thunk that will add one and two once invoked at some later time. This is how thunks can be used for delayed execution!

#do some other stuff… 
x = add_thunk()
# x now holds the value 3

This seems perfectly useless doesn’t it? However, this simple mechanism is the solution to our recursion problems. We can use thunks to easily make linearly recursive functions have constant space complexity, thus solving our stack overflow issues.

So, here is an extremely simple linearly recursive function:

countDown = (n) -> 
  console.log(n)
  if n > 0 countDown(n-1)
  else "DONE!"

This function will just count down from the number it is given to zero and return the string “DONE!” once it is finished. If we give this function some value n > 10000 or so, we will likely get a “maximum call stack size exceeded” error or something like that. With a tiny, simple change we can make this function not cause that error for any arbitrarily large input. We just need to make it return a thunk of its recursive call rather than invoking the recursive call itself.

countDown = (n) ->
 console.log(n) 
 if n > 0 -> countDown(n-1)
 else “DONE!”

Now when we call countDown, it gives us a thunk that will execute the next recursive step in the process:

>thunk = countDown(10)
 10
>thunk = thunk()
 9
>thunk = thunk()
 8

The secret sauce here is that we are now performing each recursive step while keeping a constant call stack depth. We keep calling a single function, which gets added to the call stack, that function just returns a thunk of the next function call and then is removed from the call stack! After going up and down like this n times, we will get our “DONE!” string! But we’re still not done yet. We really don’t want to have to keep calling thunk after thunk every time we want to use this function do we? This looks pretty ridiculous:

>countDown(10)()()()()()()()()()()
 => “DONE!”

So lets define a function that does this for us:

trampoline = (fun, args...) ->
  result = fun(args...)
  while typeof result is 'function'
    result = result()
  result

This function will just keep on calling thunks that our recursive function returns until it gets something other than a thunk indicating that we are done. So now we can just pass our function into trampoline and let it go!

trampoline(countDown, 1000000)
#wait a while…
 => “DONE!”

If we tried to call our non-thunking countDown function with n = 1000000, we would most likely get a stack overflow error. Our trampolining, thunking implementation handles it just fine!

So, for this implementation of trampoline, recursive functions are only “trampolinable” when they return thunks of their next recursive step. This does turn out to be a prohibitive constraint in some cases.

The sad thing about trampolining is that it doesn’t make our lives very easy when we are writing non-linear recursive functions. It think it is totally possible to implement a non-linear recursive function that is “trampolinable.” It just seems to make things really complicated for some problems (like non-trivial tree traversal).