Quick Recap

In the last post, I went through the zipIndex example from RĂșnar’s paper. The example, zipIndex, is implemented in functional style Scala, but it has a huge problem — it is not stack safe. If the input list is too long, zipIndex will throw StackOverflowError.

Trampoline

So how do we get around the stack problem? Is there a way to avoid creating stack frames? At this point, the paper introduces a technique called trampoline. The idea is to “trade stack for heap”.

Trampoline
1 2 3 4 5 6 7 8 9 10 11
sealed trait Trampoline[+A] { @tailrec (1) final def runT: A = this match { case More(k) => k().runT case Done(v) => v } } case class More[+A](k: () => Trampoline[A]) extends Trampoline[A] case class Done[+A](result: A) extends Trampoline[A]
1 Tell the Scala compiler to apply tail-call optimisation. As such, no new stack frame will be created when runT calls itself.

Trampoline is an ADT that captures the steps of a computation. In order words, given a computation that will return a value of type A (correspond to the covariant type variable, A, of the above Trampoline ADT), that computation can be represented as either More or Done. A Done signifies that computation is finished, and the value inside Done will be used as the return value. A More indicates that there is a least one more step to perform for the computation. So go ahead and perform the step inside More, then see what the next step will be.

Trampoline in Haskell

As an aside, I much prefer the Haskell syntax; it is much more concise. Below is the implementation of runT and the Trampoline ADT in Haskell.

data Trampoline a = More (() -> Trampoline a)
                  | Done a

runT :: Trampoline a -> a
runT (Done a) = a
runT (More k) = runT (k ())

Trampoline Example: Odd and Even

After introducing the Trampoline ADT, the paper shows a simple example on how to use it. The odd and even functions do as their names say. They call each other mutual recursively — meaning at the last step of odd it calls even and vice versa. Since we are using Trampoline to represent the odd and even computations and both of those computations return Boolean, the return types for odd and even will be Trampoline[Boolean].

Let’s see the code!

1 2 3 4 5 6 7 8 9 10 11 12 13
def even[A](ns: List[A]): Trampoline[Boolean] = (1) ns match { case Nil => Done(true) case x :: xs => More(() => odd(xs)) (2) } def odd[A](ns: List[A]): Trampoline[Boolean] = (1) ns match { case Nil => Done(false) case x :: xs => More(() => even(xs)) (2) } even(List(1,2,3)).runT // -> False (3)
1 Return Trampoline[Boolean] rather than just Boolean.
2 Mutual recursion.
3 Run the computation.

After calling even(List(1,2,3)), we get a value of type Trampoline[Boolean]. The value represents all the steps in the even computation. So in order to get the Boolean value out, we will need to run those steps. Hence, we need to call runT on the return value of even. This is why we are trading stack for heap. The return value of even contains all the computational steps.

Normally, if even and odd mutually call each other and they return Boolean values, the invocation of even(List.fill(4000)(1)) will overflow the stack. That is because at the end of even, before it can return, it calls odd. Thus, creating a new stack frame for every single element in the input list. By utilizing Trampoline, instead of having even calls odd, even just returns a step (More). The last step is to ‘get’ the boolean value out of Trampoline. To do that, we call runT. Since runT is tail recursive, it is not allocating new stack frames.

Why Is It Called Trampoline?

By using Trampoline, the control flow has changed. Originally, even passing its control to odd, then odd passes its control to even, in the process, allocates a new stack frame for even. The back and forth goes on until it reaches the end of the input list. When Trampoline is used as the return value, even just returns a value of type Trampoline. It is up to the runT method of Trampoline to call the next step. So the control flow bounces from a function to Trampoline, then to another function, then back to Trampoline and so on. Every time when the control bounces back to runT, the stack frame gets deallocated. So there is no risk of overflowing the stack.

Applying Trampoline

The logical next step is to apply the Trampoline technique to the zipIndex example introduced in the first post. And that is what we will see in the next post.