099 Advanced

099 — Continuation-Passing Style (CPS)

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "099 — Continuation-Passing Style (CPS)" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Transform recursive functions to CPS by passing a continuation — "what to do next" — as an explicit function argument. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Transform recursive functions to CPS by passing a continuation — "what to do next" — as an explicit function argument. Implement factorial in direct, CPS, and iterative styles. Show CPS on a binary tree sum. Compare with OCaml where CPS provides genuine tail recursion versus Rust where CPS uses boxed closures but does not eliminate stack use.

🎯 Learning Outcomes

• Understand CPS: every call passes a function that receives the result

• Implement factorial_cps(n, k) where k accumulates pending multiplications

• Recognise that go(n-1, move |result| k(n * result)) builds a closure chain on the heap

• Understand that Rust CPS with Box<dyn FnOnce> does not achieve true tail recursion

• Map Rust's boxed CPS to OCaml's natively tail-recursive CPS

• Prefer (1..=n).product() — the idiomatic iterative alternative

Code Example

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))
}

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

Key Differences

Aspect	Rust	OCaml
Continuation type	`Box<dyn FnOnce(u64) -> u64>`	`int -> int` (polymorphic)
Tail recursion	No (stack still grows)	Yes (TCO to loop)
Heap allocation	One `Box` per step	Closure captured on OCaml heap
Practical version	`(1..=n).product()`	`let rec fold` or `Stdlib.fold_left`
Verbosity	High	Low
Educational value	Shows closure mechanics	Shows genuine TCO

CPS is primarily a transformation technique for compilers and theoretical study. In practice, Rust solves the stack-overflow problem with iterative solutions and the Iterator protocol; OCaml uses tail-call optimisation. Understanding CPS helps with async/await, callback-based APIs, and compiler intermediate representations.

OCaml Approach

OCaml's go n k is let rec go n k = if n = 0 then k 1 else go (n-1) (fun result -> k (n * result)). Because go is tail-recursive (the last operation in each branch is the call to go or k), OCaml optimises this to a loop with O(1) stack. The sum_cps tree version shows nested CPS: go l (fun sl -> go r (fun sr -> k (sl + sr))).

Full Source

#![allow(clippy::all)]
//! # 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);
    }
}

(* 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)

✓ Tests Rust test suite

#[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);
    }
}

Deep 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

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

Exercises

Implement fib_cps(n: u64) -> u64 in CPS style and verify it matches the direct recursive version.

Convert tree_sum to use an explicit Vec-based stack instead of CPS — the standard iterative tree traversal technique in Rust.

Implement a trampolining version: instead of Box<dyn FnOnce>, return an enum Step::Done(u64) | Step::Bounce(Box<dyn FnOnce() -> Step>) and loop in a driver.

In OCaml, implement map_cps : ('a -> 'b) -> 'a list -> 'b list in CPS and verify tail recursion.

Explore Rust's async/await as a form of CPS desugaring: sketch how async fn f() resembles a continuation-passing transformation.

Open Source Repos

functional-rust

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

Rust