Stackless Scala, Part 2: Trampoline
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”.
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 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.