Trampoline: Deep Recursion in a Loop
Hold each step as data and run them in one loop, so deep recursion costs heap, not stack.
| Models | A recursive computation held as steps, which run() works through one at a time |
| Replaces | A recursive method that overflows the stack, or a loop that keeps its own stack of work |
| Effect Path | TrampolinePath |
| Instances | Functor, Applicative, Monad |
| Choose it when | Recursion can go thousands of calls deep, or two functions call each other; otherwise keep the plain recursion or loop you have, or compare every type in Choosing a Type |
- Explain why a recursive sum overflows the stack, and what sets the depth it reaches
- Hold the same recursion as steps on a
TrampolinePath, and run it a million calls deep - Turn each kind of call into a step: a base case, a tail call, and a call whose result you combine
- Run two functions that call each other in one loop
- Traverse a long list under
IOwithout nesting a call for each element
The code on this page is TrampolineBook.java: the page includes it, so the build compiles and runs it. TrampolineBookTest.java holds what the page says each method does.
A sum that overflows
The sums on this page use plain numbers, since the depth of the recursion is what matters. The code on this page uses these imports:
import static org.higherkindedj.hkt.instances.Witnesses.io;
import static org.higherkindedj.hkt.io.IOKindHelper.IO_OP;
import java.util.List;
import java.util.stream.IntStream;
import org.higherkindedj.hkt.Kind;
import org.higherkindedj.hkt.effect.Path;
import org.higherkindedj.hkt.effect.TrampolinePath;
import org.higherkindedj.hkt.instances.Instances;
import org.higherkindedj.hkt.io.IO;
import org.higherkindedj.hkt.io.IOKind;
import org.higherkindedj.hkt.trampoline.Trampoline;
import org.higherkindedj.hkt.trampoline.TrampolineUtils;
Each call to this sum waits for the deeper call it makes to return, so each holds a frame on the thread's stack:
// Each call waits for the deeper call it makes, so each adds a frame to the stack
static long sum(long n) {
if (n <= 0) {
return 0;
}
return n + sum(n - 1);
}
sum(1_000) gives 500500, but sum(1_000_000) throws StackOverflowError. A thread's stack has a fixed size, 1 MB by default: 5,000 of these frames fit, and 100,000 do not. Where between the two it overflows depends on whether the JIT has compiled the method yet. The JVM never reuses a frame for a call in tail position, so rewriting the method as a tail call does not help. You can catch the error, but the sum is lost.
The same sum, held as steps
A TrampolinePath holds the recursion instead of making it. Path.trampolineDefer holds the deeper call as a step to take later, and map holds what to do with that call's result:
// The same sum, held as steps: defer the deeper call, then map its result
static TrampolinePath<Long> sumPath(long n) {
if (n <= 0) {
return Path.trampolineDone(0L);
}
return Path.trampolineDefer(() -> sumPath(n - 1)).map(deeper -> n + deeper);
}
run() works through the steps in one loop. Each pending addition waits on a list on the heap, so the stack stays flat:
long total = sumPath(1_000_000).run();
// 500000500000
The name comes from the loop. Each step bounces back to it with the next step to take, where a plain recursion would go one frame deeper:
Plain recursion On a trampoline
sum(5) run():
sum(4) +--> sum(5): defer sum(4), then add 5
sum(3) | |
sum(2) | v
sum(1) +--> sum(4): defer sum(3), then add 4
sum(0) | |
return 0 | v
return 1 +--> ...
return 3 | |
return 6 | v
return 10 +--> sum(0) is done: 0
return 15 then the held additions:
0 + 1 + 2 + 3 + 4 + 5 = 15
Stack grows with n Stack stays flat; additions wait on the heap
Higher-Kinded-J's trampoline grew out of Scott Logic's blog post Recursion, Thunks and Trampolines with Java and Scala. The post builds the same idea from two cases, Done for a result and More for a step still to take, run by one loop. Higher-Kinded-J adds a third case, FlatMap, for sequencing, and an instance, so a Trampoline takes part in code written for any monad.
Each kind of call, as a step
A recursive method becomes a trampolined one call by call:
| In the recursive method | On a trampoline |
|---|---|
The return type T | Trampoline<T>, or TrampolinePath<T> |
A base case, return value | Trampoline.done(value) |
A tail call, return f(x) | Trampoline.defer(() -> f(x)) |
A call whose result you combine, return n + f(x) | Trampoline.defer(() -> f(x)).map(r -> n + r) |
Two calls, return f(x) + f(y) | Trampoline.defer(() -> f(x)).flatMap(a -> f(y).map(b -> a + b)) |
map and flatMap are what keep a combined call safe: defer alone would leave the addition outside the trampoline. When the running total can travel with the call, a tail call needs only defer:
// A tail call: the running total travels with the call, so only defer is needed
static Trampoline<Long> sumTail(long n, long total) {
if (n <= 0) {
return Trampoline.done(total);
}
return Trampoline.defer(() -> sumTail(n - 1, total + n));
}
long sameTotal = sumTail(1_000_000, 0).run();
// 500000500000
Two functions that call each other
Two functions that call each other overflow the stack as fast as one deep function. They are awkward to merge into one loop by hand, since the loop must track which function it is in. On a trampoline, each stays as it is written, and defers to the other:
// Two functions that call each other, each kept as it is written
static Trampoline<Boolean> isEven(long n) {
return n == 0 ? Trampoline.done(true) : Trampoline.defer(() -> isOdd(n - 1));
}
static Trampoline<Boolean> isOdd(long n) {
return n == 0 ? Trampoline.done(false) : Trampoline.defer(() -> isEven(n - 1));
}
boolean even = isEven(1_000_001).run();
// false
A long list under IO
traverse runs a function that returns an effect on each element of a list, and gathers the results into one effect holding a list, as Foldable and Traverse explains. Under a lazy applicative such as IO, a traverse that combines the elements one after another nests one call per element, so running the result for a long list can overflow. TrampolineUtils.traverseListStackSafe combines them as a balanced tree instead, and sequenceStackSafe does the same for a list of effects:
List<Integer> lines = IntStream.rangeClosed(1, 100_000).boxed().toList();
// Combines the IO steps as a balanced tree, so the nesting grows with the log of the length
Kind<IOKind.Witness, List<String>> labelled =
TrampolineUtils.traverseListStackSafe(
lines, n -> IO_OP.widen(IO.delay(() -> "line " + n)), Instances.monad(io()));
int labels = IO_OP.narrow(labelled).unsafeRunSync().size();
// 100000
They sit beside Trampoline in its package, but need no trampoline, since the tree's nesting grows with the log of the list's length.
A trampoline always gives a value
Nothing runs until run(). A trampoline always gives a value, so done(null) throws NullPointerException, as A Task Always Gives a Value sets out for every lazy type.
Creating instances
Path.trampolineDone(value) and Path.trampolineDefer(supplier) start a TrampolinePath, and Path.trampoline(trampoline) wraps a Trampoline. Trampoline.done(value) and Trampoline.defer(supplier) build a Trampoline directly.
Methods
| Method | What it does |
|---|---|
defer(supplier) | Holds a step to take later |
map(f), flatMap(f) | Hold what to do with the result; on a TrampolinePath, flatMap is via |
zipWith(other, f) | Combines two trampolines' results, on a TrampolinePath |
run() | Works through every step in a loop, and gives the result |
toTrampoline(), toIOPath(), toLazyPath() | Turn a TrampolinePath into a Trampoline, an IOPath or a LazyPath |
Working with Kind
Generic code takes Trampoline through its Monad, from Instances.monad(trampoline()), which is TrampolineMonad.INSTANCE. Its flatMap holds the step as Trampoline.flatMap does, so a deep chain built through the instance runs in the loop too. TRAMPOLINE.widen and TRAMPOLINE.narrow, from TrampolineKindHelper, convert between a Trampoline and its Kind.
When to use Trampoline
| You need | Use |
|---|---|
| Recursion that can go thousands of calls deep, such as a walk over a deep tree | Trampoline, or TrampolinePath |
| Two functions that call each other | Trampoline: each stays as it is written |
A traverse of a long list under IO or another lazy applicative | TrampolineUtils |
| Recursion that stays a few hundred calls deep | Plain recursion |
| A loop that is already a loop | The loop: a trampoline adds an object per step |
Benchmarks: TrampolineBenchmark measures building and running trampolines, and deep recursion against plain recursion. Benchmarks & Performance says how to run it.