Trampolining

In essence, trampolining is replacing recursive function calls with objects representing these calls. This way the recursive computation is built up in the heap instead of the stack, and it is possible to represent much deeper recursive calls just because of the bigger size of the heap.

The Scala util.control.TailCalls implementation provides a ready-to-use abstraction for trampolined recursive calls. Remember that we have two general cases in recursion that break down to three concrete cases? These are:

• The base case
• The recursive case, which can be:
  • Head recursion
  • Tail recursion

The representation reflects them by following three protected case classes:

case class Done[A](value: A) extends TailRec[A]
case class Call[A](rest: () => TailRec[A]) extends TailRec[A]
case class Cont[A, B](a: TailRec[A], f: A => TailRec[B]) extends TailRec[B]

As these are protected, we can't use them directly, but are expected to use special helper methods instead. Let's take a look at them by re implementing our Ackerman function:

import util.control.TailCalls._

def tailA(m: BigInt, n: BigInt): TailRec[BigInt] = {
  if (m == 0) done(n + 1)
  else if (n == 0) tailcall(tailA(m - 1, 1))
  else tailcall(tailA(m, n - 1)).flatMap(tailA(m - 1, _))
}
def A(m: Int, n: Int): BigInt = tailA(m, n).result

We wrap our recursive calls into the tailcall method, which creates an instance of a Call. The recursive call is a bit more complex than the base case because we first need to recursively wrap the internal call and then use the flatMap method provided by the TailRec to pass the result into the outer recursive call.

The A is just a helper method to unlift the result of the calculation from the TailRec. We're using BigInt to represent the result because now, as the implementation is stack safe, it can return quite huge numbers:

scala> Trampolined.A(4,2).toString.length

Now, as we've seen how to represent recursive functions as objects, it is time to reveal another truth about Scala functions.