197 Advanced

Trampoline

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Trampoline" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Rust (and OCaml without tail-call optimization) stack-overflows on deeply recursive functions. Key difference from OCaml: 1. **TCO guarantee**: OCaml guarantees TCO for direct tail calls; Rust does not — trampolining is always required for stack

Tutorial

The Problem

Rust (and OCaml without tail-call optimization) stack-overflows on deeply recursive functions. A trampoline converts stack recursion into heap iteration: instead of calling the next step recursively, return a thunk (a suspended computation). The trampoline loop executes thunks iteratively on the heap, never growing the call stack. This enables "infinite" recursion and mutual recursion on arbitrary inputs without stack overflow.

🎯 Learning Outcomes

• Understand why stack overflow occurs in recursive functions

• Learn the trampoline pattern: return Done(value) or More(thunk) instead of recursing

• See how trampolining converts stack depth into heap allocation

• Understand the trade-off: heap allocation per step vs. stack frame per step

Code Example

#![allow(clippy::all)]
// Stub — awaiting conversion from OCaml source.

(* Trampoline: convert deep recursion to a loop by returning thunks.
   Each step either returns a value (Done) or a thunk to continue (Bounce). *)

type 'a trampoline =
  | Done   : 'a -> 'a trampoline
  | Bounce : (unit -> 'a trampoline) -> 'a trampoline

let done_ x = Done x
let bounce f = Bounce f

(* Run the trampoline loop — O(1) stack! *)
let run t =
  let rec loop = function
    | Done x    -> x
    | Bounce f  -> loop (f ())
  in loop t

(* Even/odd without stack overflow via mutual recursion + trampoline *)
let rec is_even_t n =
  if n = 0 then done_ true
  else bounce (fun () -> is_odd_t (n - 1))
and is_odd_t n =
  if n = 0 then done_ false
  else bounce (fun () -> is_even_t (n - 1))

(* Factorial via trampoline *)
let factorial_t n =
  let rec go n acc =
    if n <= 1 then done_ acc
    else bounce (fun () -> go (n - 1) (n * acc))
  in run (go n 1)

let () =
  Printf.printf "is_even 1000000 = %b\n" (run (is_even_t 1_000_000));
  Printf.printf "is_odd  999999  = %b\n" (run (is_odd_t  999_999));
  Printf.printf "10!     = %d\n"         (factorial_t 10);
  Printf.printf "No stack overflow on deep recursion\n"

Key Differences

TCO guarantee: OCaml guarantees TCO for direct tail calls; Rust does not — trampolining is always required for stack-safe deep recursion in Rust.

Mutual recursion: Neither language's standard TCO handles mutual tail recursion (between two different functions); trampolining handles this in both.

Heap cost: Each trampoline step allocates a Box<dyn FnOnce>; OCaml's TCO reuses the stack frame — zero allocation.

Readability: Trampolined code is harder to read than direct recursion; the transformation is mechanical and can be automated with a macro.

OCaml Approach

OCaml guarantees tail call optimization for direct tail calls:

let rec factorial n acc = if n = 0 then acc else factorial (n-1) (n*acc)

This is already stack-safe in OCaml. Trampolining is only needed in OCaml for mutually recursive functions that the compiler cannot prove are tail-recursive. OCaml's tailcall ppx annotation forces TCO and warns if it fails.

Full Source

#![allow(clippy::all)]
// Stub — awaiting conversion from OCaml source.

(* Trampoline: convert deep recursion to a loop by returning thunks.
   Each step either returns a value (Done) or a thunk to continue (Bounce). *)

type 'a trampoline =
  | Done   : 'a -> 'a trampoline
  | Bounce : (unit -> 'a trampoline) -> 'a trampoline

let done_ x = Done x
let bounce f = Bounce f

(* Run the trampoline loop — O(1) stack! *)
let run t =
  let rec loop = function
    | Done x    -> x
    | Bounce f  -> loop (f ())
  in loop t

(* Even/odd without stack overflow via mutual recursion + trampoline *)
let rec is_even_t n =
  if n = 0 then done_ true
  else bounce (fun () -> is_odd_t (n - 1))
and is_odd_t n =
  if n = 0 then done_ false
  else bounce (fun () -> is_even_t (n - 1))

(* Factorial via trampoline *)
let factorial_t n =
  let rec go n acc =
    if n <= 1 then done_ acc
    else bounce (fun () -> go (n - 1) (n * acc))
  in run (go n 1)

let () =
  Printf.printf "is_even 1000000 = %b\n" (run (is_even_t 1_000_000));
  Printf.printf "is_odd  999999  = %b\n" (run (is_odd_t  999_999));
  Printf.printf "10!     = %d\n"         (factorial_t 10);
  Printf.printf "No stack overflow on deep recursion\n"

Deep Comparison

OCaml vs Rust: Trampoline

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement trampolined mutual recursion: is_even(n) and is_odd(n) using Trampoline with no stack growth.

Write a macro trampoline! that transforms a recursive function into its trampolined equivalent automatically.

Measure the performance difference between trampolined vs. iterative Fibonacci for n=100,000.

Open Source Repos

functional-rust

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

Rust