595 Advanced

Trampoline Pattern

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Trampoline Pattern" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Deep recursion causes stack overflow. Key difference from OCaml: 1. **TCO availability**: OCaml guarantees TCO for direct tail calls; Rust does not — trampolines are necessary for stack

Tutorial

The Problem

Deep recursion causes stack overflow. Rust's default stack is 8MB — a recursive function that calls itself millions of times will overflow. Languages with tail-call optimization (OCaml, Scheme, Haskell) eliminate this through compiler transformation. Rust does not guarantee TCO. The trampoline pattern provides a library-level solution: instead of calling recursively, return a thunk (deferred computation). A loop runs the trampoline by repeatedly calling the thunk until Done. This converts O(n) stack depth to O(1) stack depth with O(n) heap allocation.

🎯 Learning Outcomes

• What a trampoline is: a loop that evaluates thunks until a final value is produced

• How Bounce<T> { Done(T), More(Box<dyn FnOnce() -> Bounce<T>>) } models the trampoline

• How to convert a recursive function to trampoline style

• The tradeoff: O(1) stack, O(n) heap allocation for the thunk chain

• Where trampolines are used: stack-safe interpreters, Scala's TailCalls, Haskell's Cont monad

Code Example

enum Bounce<T> {
    Done(T),
    More(Box<dyn FnOnce() -> Bounce<T>>),
}

type 'a bounce = Done of 'a | Bounce of (unit -> 'a bounce)

Key Differences

TCO availability: OCaml guarantees TCO for direct tail calls; Rust does not — trampolines are necessary for stack-safe recursion in Rust.

Stack vs heap: OCaml TCO uses O(1) stack AND O(1) heap per step; Rust trampolines use O(1) stack but O(n) heap for the thunk chain.

Mutual recursion: OCaml's TCO handles mutually tail-recursive functions; Rust requires explicit trampolining for mutual tail recursion.

Ergonomics: OCaml tail-recursive code reads like normal recursive code; Rust trampoline code is more verbose with explicit Bounce wrapping.

OCaml Approach

OCaml has TCO for tail calls — trampolines are unnecessary for simple tail-recursive functions:

(* OCaml with TCO — no stack overflow: *)
let rec fact_acc n acc = if n <= 1 then acc else fact_acc (n-1) (n * acc)

(* If needed, OCaml also has trampolines: *)
type 'a bounce = Done of 'a | More of (unit -> 'a bounce)
let rec run = function Done v -> v | More f -> run (f ())

OCaml's run function itself uses a tail call and is therefore stack-safe.

Full Source

#![allow(clippy::all)]
//! # Trampoline Pattern
//!
//! Stack-safe recursion using trampolines to convert recursive calls to iteration.

/// Trampoline type - either done with a value or needs another step.
pub enum Bounce<T> {
    Done(T),
    More(Box<dyn FnOnce() -> Bounce<T>>),
}

/// Run a trampolined computation to completion.
pub fn run<T>(mut b: Bounce<T>) -> T {
    loop {
        match b {
            Bounce::Done(v) => return v,
            Bounce::More(th) => b = th(),
        }
    }
}

/// Stack-safe factorial using trampoline.
pub fn fact_t(n: u64, acc: u64) -> Bounce<u64> {
    if n == 0 {
        Bounce::Done(acc)
    } else {
        Bounce::More(Box::new(move || fact_t(n - 1, n * acc)))
    }
}

/// Factorial entry point.
pub fn factorial(n: u64) -> u64 {
    run(fact_t(n, 1))
}

/// Stack-safe even check using mutual recursion.
pub fn even_t(n: u64) -> Bounce<bool> {
    if n == 0 {
        Bounce::Done(true)
    } else {
        Bounce::More(Box::new(move || odd_t(n - 1)))
    }
}

/// Stack-safe odd check.
pub fn odd_t(n: u64) -> Bounce<bool> {
    if n == 0 {
        Bounce::Done(false)
    } else {
        Bounce::More(Box::new(move || even_t(n - 1)))
    }
}

/// Check if a number is even (stack-safe).
pub fn is_even(n: u64) -> bool {
    run(even_t(n))
}

/// Check if a number is odd (stack-safe).
pub fn is_odd(n: u64) -> bool {
    run(odd_t(n))
}

/// Stack-safe countdown.
pub fn count_t(n: u64) -> Bounce<u64> {
    if n == 0 {
        Bounce::Done(0)
    } else {
        Bounce::More(Box::new(move || count_t(n - 1)))
    }
}

/// Sum using trampoline.
pub fn sum_t(n: u64, acc: u64) -> Bounce<u64> {
    if n == 0 {
        Bounce::Done(acc)
    } else {
        Bounce::More(Box::new(move || sum_t(n - 1, acc + n)))
    }
}

pub fn sum_to(n: u64) -> u64 {
    run(sum_t(n, 0))
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_factorial() {
        assert_eq!(factorial(0), 1);
        assert_eq!(factorial(5), 120);
        assert_eq!(factorial(10), 3_628_800);
    }

    #[test]
    fn test_is_even() {
        assert!(is_even(0));
        assert!(is_even(100));
        assert!(!is_even(101));
    }

    #[test]
    fn test_is_odd() {
        assert!(!is_odd(0));
        assert!(!is_odd(100));
        assert!(is_odd(101));
    }

    #[test]
    fn test_deep_recursion() {
        // This would stack overflow without trampoline
        assert_eq!(run(count_t(50_000)), 0);
    }

    #[test]
    fn test_sum_to() {
        assert_eq!(sum_to(10), 55);
        assert_eq!(sum_to(100), 5050);
    }
}

(* Trampoline in OCaml *)
type 'a bounce = Done of 'a | Bounce of (unit -> 'a bounce)

let run t =
  let rec go = function
    | Done v    -> v
    | Bounce th -> go (th ())
  in go t

let rec fact_t n acc =
  if n <= 0 then Done acc
  else Bounce (fun () -> fact_t (n-1) (n*acc))

let rec even_t n =
  if n = 0 then Done true
  else Bounce (fun () -> odd_t  (n-1))
and odd_t n =
  if n = 0 then Done false
  else Bounce (fun () -> even_t (n-1))

let () =
  Printf.printf "100! > 0: %b\n" (run (fact_t 100 1) > 0);
  Printf.printf "even 100: %b\n" (run (even_t 100));
  Printf.printf "even 101: %b\n" (run (even_t 101))

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_factorial() {
        assert_eq!(factorial(0), 1);
        assert_eq!(factorial(5), 120);
        assert_eq!(factorial(10), 3_628_800);
    }

    #[test]
    fn test_is_even() {
        assert!(is_even(0));
        assert!(is_even(100));
        assert!(!is_even(101));
    }

    #[test]
    fn test_is_odd() {
        assert!(!is_odd(0));
        assert!(!is_odd(100));
        assert!(is_odd(101));
    }

    #[test]
    fn test_deep_recursion() {
        // This would stack overflow without trampoline
        assert_eq!(run(count_t(50_000)), 0);
    }

    #[test]
    fn test_sum_to() {
        assert_eq!(sum_to(10), 55);
        assert_eq!(sum_to(100), 5050);
    }
}

Deep Comparison

OCaml vs Rust: Trampoline Pattern

Trampoline Type

OCaml

type 'a bounce = Done of 'a | Bounce of (unit -> 'a bounce)

Rust

enum Bounce<T> {
    Done(T),
    More(Box<dyn FnOnce() -> Bounce<T>>),
}

Runner

OCaml

let run t =
  let rec go = function
    | Done v    -> v
    | Bounce th -> go (th ())
  in go t

Rust

fn run<T>(mut b: Bounce<T>) -> T {
    loop {
        match b {
            Bounce::Done(v) => return v,
            Bounce::More(th) => b = th(),
        }
    }
}

Why Trampolines?

Rust doesn't have tail call optimization. Deep recursion will stack overflow. Trampolines convert recursion to iteration:

Return Done(value) for base case

Return More(thunk) for recursive case

run loops until Done

Key Differences

Aspect	OCaml	Rust
TCO	Often available	Not guaranteed
Closure boxing	Implicit	Explicit `Box<dyn FnOnce>`
Run loop	Recursive go	Iterative loop

Exercises

Fibonacci trampoline: Convert the naive recursive Fibonacci to trampoline style using an accumulator pair — verify it handles fib(1_000_000) without stack overflow.

Mutual trampoline: Implement mutually tail-recursive is_even and is_odd using the trampoline pattern where each returns More(Box::new(|| other(n-1))).

Cont monad: Implement the Continuation monad as a struct Cont<A, R>(Box<dyn FnOnce(Box<dyn FnOnce(A) -> R>) -> R>) and show how it relates to the trampoline.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust