Languages that don’t support tail-call elimination out of the box can make people think twice about using recursion. Ever received a SystemStackError when doing something like this?

Ok, the example’s contrived, but you’ve no doubt come across cases where you’d like to avoid using an iterative solution even if it’s just for the sake of elegance. Luckily in Ruby this can be easily fixed by:

  1. Having your method return a thunk rather than a direct tail-call
  2. Using a trampoline to avoid growing the stack

A thunk is essentially just the suspended application of a function. Taking our example, it’s just a matter of transforming the tail call like so:

The trampoline implementation is equally trivial. It takes a thunk as an argument and iteratively calls it until something other than a continuation is returned:

So now if we start the ball rolling with our trampoline call:

We can run increment as long as we like without blowing the stack. As there’s no base case it’ll continue indefinitely- a worst-case example. Using continuation-passing here trades a time-penalty in higher-order function calls for the advantage of not increasing the amount of space needed to perform the computation. Not too hard really, is it?

Alternatively we could use Kernel#callcc to replay the computation until we have a return value. Here we get a continuation object to use with callcc { … }, give @k the correct execution context by reassigning the thunk as before, then call it until we’re done:

If you want to get a proper grasp of CPS you could do a lot worse than get hold of Dybvig’s book and go through all the call/cc examples.