🎬 How Rust Iterators Work Lazy evaluation, chaining, collect(), and zero-cost abstractions.

📝 Text version (for readers / accessibility)

• Iterators are lazy — .map(), .filter(), .take() build a chain but do no work until consumed

• .collect() triggers evaluation, transforming the chain into a Vec, HashMap, or other collection

• Zero-cost abstraction: iterator chains compile to the same machine code as hand-written loops

• .iter() borrows, .into_iter() consumes, .iter_mut() borrows mutably

• Chaining replaces nested loops with a readable, composable pipeline

099: CPS — Continuation-Passing Style

Difficulty: 3 Level: Advanced Instead of returning a value, pass a callback that receives the result — giving you total control over what happens next.

The Problem This Solves

You write a recursive function. It works perfectly for small inputs. Then someone calls it with a deeply nested tree or a large number, and you get a stack overflow. The Rust default stack is 8MB, and deep recursion will eat through it fast. The usual fix is to rewrite the recursion as a loop. But sometimes — for tree traversal, parsers, interpreters — that rewrite is painful. You lose the clarity of the recursive structure while adding complex state management. CPS (Continuation-Passing Style) is a systematic transformation that fixes this. Instead of a function that returns a value, you write a function that calls a callback with the value. That callback — the "continuation" — represents "what happens next." With CPS, every call becomes a tail call, which means the stack stays constant. There's a deeper payoff: once you hold "what happens next" as a first-class value, you can manipulate it. You can skip it (early exit). You can store it (suspending a computation). You can call it multiple times (backtracking). This is how async, generators, and coroutines work under the hood — and it's all CPS. This example exists to teach you that pattern.

The Intuition

Normal functions: compute result → return it to whoever called you. CPS functions: compute result → pass it to a callback you were given.

// Normal style: returns the value
fn double(x: i32) -> i32 {
 x * 2
}

// CPS style: calls the callback with the value  
// k is the "continuation" — pronounced "what to do next"
fn double_cps<R>(x: i32, k: impl Fn(i32) -> R) -> R {
 k(x * 2)  // instead of returning, we CALL k
}

// Using it:
let result = double(5);                    // normal: result = 10
double_cps(5, |result| println!("{}", result)); // CPS: callback receives 10

The big insight for recursion: with CPS, you build up the "pending work" in the callback chain instead of on the call stack. The stack stays flat; the heap grows instead.

// Normal factorial — stack grows with n (can overflow!)
fn factorial(n: u64) -> u64 {
 if n == 0 { 1 } else { n * factorial(n - 1) }
 //                      ^--- each call waits here, stack frame stays alive
}

// CPS factorial — each call is a TAIL CALL (no waiting)
fn factorial_cps(n: u64, k: Box<dyn FnOnce(u64) -> u64>) -> u64 {
 if n == 0 {
     k(1)  // base case: call continuation with 1
 } else {
     // Recursive call is LAST thing we do — tail call!
     // The "multiply by n" is wrapped into the continuation
     factorial_cps(n - 1, Box::new(move |result| k(n * result)))
 }
}

How It Works in Rust

Direct recursion (not stack-safe):

fn factorial(n: u64) -> u64 {
 if n == 0 { 1 } else { n * factorial(n - 1) }
 // Stack frame for each call! Depth 100_000 → stack overflow
}

CPS transformation:

fn factorial_cps(n: u64) -> u64 {
 fn go(n: u64, k: Box<dyn FnOnce(u64) -> u64>) -> u64 {
     if n == 0 {
         k(1)  // done: call the continuation with 1
     } else {
         // Pass a new continuation that wraps "multiply by n"
         go(n - 1, Box::new(move |result| k(n * result)))
     }
 }
 go(n, Box::new(|x| x))  // identity continuation to start
}

Note: in OCaml, this is truly stack-safe because the compiler does Tail Call Optimization (TCO). Rust does NOT guarantee TCO, so in Rust, CPS alone doesn't prevent stack overflow — you also need a trampoline (see example 197). But CPS is the essential first step. CPS for early exit — two continuations:

fn find_cps<T: Copy>(
 pred: &dyn Fn(T) -> bool,
 list: &[T],
 found: &dyn Fn(T) -> Option<T>,      // called when found
 not_found: &dyn Fn() -> Option<T>,   // called when exhausted
) -> Option<T> {
 if list.is_empty() {
     not_found()          // nothing matched: take this branch
 } else if pred(list[0]) {
     found(list[0])       // found one: take this branch immediately
 } else {
     find_cps(pred, &list[1..], found, not_found)
 }
}
// Two continuations = two possible outcomes = early exit for free!

The idiomatic Rust way (for most cases): avoid CPS entirely, use iterators.

// This does the same as CPS find, with zero overhead:
let first_even = nums.iter().find(|&&x| x % 2 == 0);

What This Unlocks

Stack safety: Combine CPS with a trampoline (example 197) and you get infinite recursion depth with O(1) stack.
Control flow superpowers: Async/await is CPS. `?` operator is CPS. Generators are CPS. Once you see this, you see it everywhere in Rust code.
Interpreter and compiler writing: CPS is the standard intermediate representation in optimizing compilers (used by GHC, MLTON, and others). Understanding it makes compiler papers readable.

Key Differences

Concept	OCaml	Rust
CPS is tail-recursive?	Yes — OCaml guarantees TCO	No — needs trampoline too
Continuation type	`'a -> 'b` (lightweight)	`Box<dyn FnOnce(A) -> B>` (heap)
Closure allocation cost	Near-zero (GC stack)	One heap alloc per continuation
Practical recommendation	CPS is viable	Use iterators; CPS = educational
The `?` operator	`result >>= continuation`	CPS in disguise!

//! # CPS — Continuation-Passing Style
//!
//! Transform recursive functions to pass "what to do next" as a function argument.
//! This makes them tail-recursive in OCaml; in Rust, closures still allocate on heap.

// ---------------------------------------------------------------------------
// Approach A: Direct recursion (not tail-recursive)
// ---------------------------------------------------------------------------

pub fn factorial(n: u64) -> u64 {
    if n == 0 { 1 } else { n * factorial(n - 1) }
}

// ---------------------------------------------------------------------------
// Approach B: CPS with boxed closures
// ---------------------------------------------------------------------------

pub fn factorial_cps(n: u64) -> u64 {
    fn go(n: u64, k: Box<dyn FnOnce(u64) -> u64>) -> u64 {
        if n == 0 {
            k(1)
        } else {
            go(n - 1, Box::new(move |result| k(n * result)))
        }
    }
    go(n, Box::new(|x| x))
}

// ---------------------------------------------------------------------------
// Approach C: Iterative (idiomatic Rust — no CPS needed)
// ---------------------------------------------------------------------------

pub fn factorial_iter(n: u64) -> u64 {
    (1..=n).product()
}

// ---------------------------------------------------------------------------
// Tree sum — CPS vs direct
// ---------------------------------------------------------------------------

#[derive(Debug)]
pub enum Tree {
    Leaf(i64),
    Node(Box<Tree>, Box<Tree>),
}

pub fn tree_sum(t: &Tree) -> i64 {
    match t {
        Tree::Leaf(x) => *x,
        Tree::Node(l, r) => tree_sum(l) + tree_sum(r),
    }
}

pub fn tree_sum_cps(t: &Tree) -> i64 {
    fn go(t: &Tree, k: Box<dyn FnOnce(i64) -> i64 + '_>) -> i64 {
        match t {
            Tree::Leaf(x) => k(*x),
            Tree::Node(l, r) => {
                go(l, Box::new(move |sl| go(r, Box::new(move |sr| k(sl + sr)))))
            }
        }
    }
    go(t, Box::new(|x| x))
}

/// Stack-based tree sum — truly iterative, no recursion
pub fn tree_sum_stack(t: &Tree) -> i64 {
    let mut stack = vec![t];
    let mut sum = 0;
    while let Some(node) = stack.pop() {
        match node {
            Tree::Leaf(x) => sum += x,
            Tree::Node(l, r) => {
                stack.push(l);
                stack.push(r);
            }
        }
    }
    sum
}

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

    #[test]
    fn test_factorial() {
        assert_eq!(factorial(10), 3628800);
        assert_eq!(factorial_cps(10), 3628800);
        assert_eq!(factorial_iter(10), 3628800);
    }

    #[test]
    fn test_factorial_zero() {
        assert_eq!(factorial(0), 1);
        assert_eq!(factorial_cps(0), 1);
    }

    #[test]
    fn test_tree_sum() {
        let t = Tree::Node(
            Box::new(Tree::Node(Box::new(Tree::Leaf(1)), Box::new(Tree::Leaf(2)))),
            Box::new(Tree::Node(Box::new(Tree::Leaf(3)), Box::new(Tree::Leaf(4)))),
        );
        assert_eq!(tree_sum(&t), 10);
        assert_eq!(tree_sum_cps(&t), 10);
        assert_eq!(tree_sum_stack(&t), 10);
    }

    #[test]
    fn test_tree_leaf() {
        let t = Tree::Leaf(42);
        assert_eq!(tree_sum(&t), 42);
        assert_eq!(tree_sum_cps(&t), 42);
    }

    #[test]
    fn test_factorial_large() {
        assert_eq!(factorial_iter(20), 2432902008176640000);
    }
}

fn main() {
    println!("{:?}", factorial(10), 3628800);
    println!("{:?}", factorial_cps(10), 3628800);
    println!("{:?}", factorial_iter(10), 3628800);
}

(* Direct style - not tail recursive *)
let rec factorial n =
  if n = 0 then 1 else n * factorial (n - 1)

(* CPS style - tail recursive *)
let factorial_cps n =
  let rec go n k =
    if n = 0 then k 1
    else go (n - 1) (fun result -> k (n * result))
  in
  go n Fun.id

(* CPS tree sum *)
type 'a tree = Leaf of 'a | Node of 'a tree * 'a tree

let sum_cps t =
  let rec go t k = match t with
    | Leaf x -> k x
    | Node (l, r) -> go l (fun sl -> go r (fun sr -> k (sl + sr)))
  in go t Fun.id

let () =
  Printf.printf "%d\n" (factorial_cps 10);
  let t = Node (Node (Leaf 1, Leaf 2), Node (Leaf 3, Leaf 4)) in
  Printf.printf "%d\n" (sum_cps t)

📊 Detailed Comparison

Comparison: CPS — OCaml vs Rust

Core Insight

CPS trades stack frames for heap-allocated closures. OCaml's GC makes this trade cheap — closures are first-class and lightweight. Rust's ownership model makes CPS verbose: each continuation needs `Box<dyn FnOnce>`, and nested closures fight the borrow checker. The lesson: Rust prefers explicit iteration (`for`, `fold`, explicit stack) over CPS.

OCaml

🐪 Show OCaml equivalent

let factorial_cps n =
let rec go n k =
 if n = 0 then k 1
 else go (n - 1) (fun result -> k (n * result))
in go n Fun.id

Rust — CPS

pub fn factorial_cps(n: u64) -> u64 {
 fn go(n: u64, k: Box<dyn FnOnce(u64) -> u64>) -> u64 {
     if n == 0 { k(1) }
     else { go(n - 1, Box::new(move |result| k(n * result))) }
 }
 go(n, Box::new(|x| x))
}

Rust — Idiomatic (iterative)

pub fn factorial_iter(n: u64) -> u64 {
 (1..=n).product()
}

Comparison Table

Aspect	OCaml	Rust
Closure cost	GC-managed, cheap	`Box<dyn FnOnce>` heap alloc
Identity fn	`Fun.id`	`\	x\	x` or `std::convert::identity`
Tail call opt	Yes (CPS enables it)	No TCO guarantee
Idiomatic alt	CPS is idiomatic	Iterators / explicit stack
Tree traversal	CPS avoids stack overflow	Explicit `Vec` stack

Learner Notes

No TCO in Rust: Even with CPS, Rust doesn't guarantee tail call optimization, so stack overflow is still possible
`FnOnce` vs `Fn`: CPS continuations are called exactly once — `FnOnce` is the right trait (takes ownership)
Explicit stack pattern: `let mut stack = vec![root]; while let Some(node) = stack.pop()` — Rust's idiomatic "CPS"
`(1..=n).product()`: For simple cases, iterators make CPS entirely unnecessary
OCaml's advantage: CPS is a fundamental FP technique that feels natural in OCaml — it's a core teaching tool