Trampolining turns a deeply chained computation into repeated steps driven by one interpreter loop. Each step returns control to that loop instead of growing the call stack. section 13.3.1 section 13.3.2
Why direct composition fails
Composing 100,000 identity functions as ordinary Int => Int values can produce a StackOverflowError when the resulting function runs. Reifying each step as TailRec[Int] and interpreting it with run preserves predictable stack usage, although the trampoline can be slower than direct calls. section 13.3.2
scala> val f = (x: Int) => x val f: Int => Int = <function1> scala> val g = List.fill(100000)(f).foldLeft(f)(_ compose _) #1 val g: Int => Int = <function1> scala> g(42) java.lang.StackOverflowError
Compare ordinary function composition with the stack overflow it can trigger. section 13.3.2
A trampolined computation is represented as data constructors such as Return, Suspend, and FlatMap. The interpreter repeatedly evaluates one constructor, then resumes the next step. Nested FlatMap values can be reassociated before interpretation, keeping execution tail-recursive. section 13.3.1 section 13.3.2
enum TailRec[A]:
case Return(a: A)
case Suspend(resume: () => A)
case FlatMap[A,B](sub: TailRec[A],
k: A => TailRec[B]) extends TailRec[B]
def flatMap[B](f: A => TailRec[B]): TailRec[B] =
FlatMap(this, f)
def map[B](f: A => B): TailRec[B] =
flatMap(a => Return(f(a)))
@annotation.tailrec final def run: A = this match #1
case Return(a) => a
case Suspend(r) => r()
case FlatMap(x, f) => x match
case Return(a) => f(a).run
case Suspend(r) => f(r()).run
case FlatMap(y, g) => y.flatMap(a => g(a).flatMap(f)).run
Inspect a TailRec representation and its tail-recursive run interpreter. section 13.3.2
Apply the technique by:
- Changing a function’s return type from B to TailRec[B]. section 13.3.2
- Wrapping function calls in Suspend and composing results with flatMap. section 13.3.2
- Running the resulting value through an interpreter such as run or result. section 13.3.2
scala> import scala.util.control.TailCalls.*
scala> val f = (x: Int) => done(x)
val f: Int => scala.util.control.TailCalls.TailRec[Int] = ...
scala> val g = List.fill(10000)(f).foldLeft(f)((a, b) =>
| x => tailcall(a(x).flatMap(b)))
val g: Int => scala.util.control.TailCalls.TailRec[Int] = ...
scala> val x1 = g(0).result
x1: Int = 0
scala> val x2 = g(42).result
x2: Int = 42
See the equivalent implementation using scala.util.control.TailCalls, including done, tailcall, and result. section 13.3.2
