195 Advanced

Continuation-Passing Style

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Continuation-Passing Style" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Continuation-passing style (CPS) transforms functions so that instead of returning a value, they pass the result to a "continuation" callback. Key difference from OCaml: 1. **Tail call optimization**: OCaml guarantees TCO for direct tail calls and can optimize CPS; Rust does not guarantee TCO — CPS in Rust still risks stack overflow without trampolining.

Tutorial

The Problem

Continuation-passing style (CPS) transforms functions so that instead of returning a value, they pass the result to a "continuation" callback. CPS makes control flow explicit — every function knows exactly what happens next. It is the basis for compilers (CPS intermediate representations in GHC, MLton), non-local exits, and cooperative scheduling. CPS transform eliminates the call stack: tail calls to continuations never grow the stack.

🎯 Learning Outcomes

• Understand CPS as explicit control flow: every function receives a continuation parameter

• Learn to transform direct-style functions into CPS

• See how callcc (call-with-current-continuation) enables non-local exits and backtracking

• Understand how CPS relates to trampolining (example 197) for eliminating stack overflow

Code Example

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

(* Continuation-passing style (CPS): instead of returning a value,
   pass it to a continuation function 'k'. Enables:
   - Tail-call optimization for any recursion
   - First-class control flow
   - Building coroutines, generators *)

(* Direct style *)
let rec factorial_direct n =
  if n <= 1 then 1 else n * factorial_direct (n - 1)

(* CPS style: always tail recursive *)
let factorial_cps n k =
  let rec go n k =
    if n <= 1 then k 1
    else go (n - 1) (fun result -> k (n * result))
  in go n k

(* Fibonacci in CPS *)
let fibonacci_cps n k =
  let rec go n k =
    if n <= 1 then k n
    else
      go (n - 1) (fun a ->
        go (n - 2) (fun b ->
          k (a + b)))
  in go n k

(* Early exit: CPS allows "throwing" to a continuation *)
let find_cps pred lst found not_found =
  let rec go = function
    | []     -> not_found ()
    | x :: xs -> if pred x then found x else go xs
  in go lst

let () =
  Printf.printf "5! = %d\n" (factorial_direct 5);
  factorial_cps 5 (Printf.printf "CPS 5! = %d\n");
  fibonacci_cps 10 (Printf.printf "CPS fib(10) = %d\n");

  let lst = [1; 3; 5; 8; 9; 12] in
  find_cps (fun x -> x mod 2 = 0) lst
    (fun x -> Printf.printf "First even: %d\n" x)
    (fun () -> Printf.printf "No evens\n")

Key Differences

Tail call optimization: OCaml guarantees TCO for direct tail calls and can optimize CPS; Rust does not guarantee TCO — CPS in Rust still risks stack overflow without trampolining.

**callcc**: OCaml's effects provide first-class continuations; Rust lacks callcc — non-local exits use Result and ?, not continuations.

Expressiveness: Full callcc enables coroutines, backtracking, and non-local exits; Rust's CPS simulation provides only the direct sequencing benefit.

Readability: CPS code in both languages is hard to read; compilers use CPS as IR but programmers rarely write it directly.

OCaml Approach

OCaml naturally supports CPS:

let add_k a b k = k (a + b)
let factorial_k n k =
  let rec go n acc k = if n = 0 then k acc else go (n-1) (n*acc) k in
  go n 1 k

OCaml has a callcc library via setjmp/longjmp (unsafe) or via effects (OCaml 5). The delimcc library provides delimited continuations. CPS is a common intermediate representation in OCaml compilers.

Full Source

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

(* Continuation-passing style (CPS): instead of returning a value,
   pass it to a continuation function 'k'. Enables:
   - Tail-call optimization for any recursion
   - First-class control flow
   - Building coroutines, generators *)

(* Direct style *)
let rec factorial_direct n =
  if n <= 1 then 1 else n * factorial_direct (n - 1)

(* CPS style: always tail recursive *)
let factorial_cps n k =
  let rec go n k =
    if n <= 1 then k 1
    else go (n - 1) (fun result -> k (n * result))
  in go n k

(* Fibonacci in CPS *)
let fibonacci_cps n k =
  let rec go n k =
    if n <= 1 then k n
    else
      go (n - 1) (fun a ->
        go (n - 2) (fun b ->
          k (a + b)))
  in go n k

(* Early exit: CPS allows "throwing" to a continuation *)
let find_cps pred lst found not_found =
  let rec go = function
    | []     -> not_found ()
    | x :: xs -> if pred x then found x else go xs
  in go lst

let () =
  Printf.printf "5! = %d\n" (factorial_direct 5);
  factorial_cps 5 (Printf.printf "CPS 5! = %d\n");
  fibonacci_cps 10 (Printf.printf "CPS fib(10) = %d\n");

  let lst = [1; 3; 5; 8; 9; 12] in
  find_cps (fun x -> x mod 2 = 0) lst
    (fun x -> Printf.printf "First even: %d\n" x)
    (fun () -> Printf.printf "No evens\n")

Deep Comparison

OCaml vs Rust: Continuation Passing

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

Convert sum_list(list: &[i32]) -> i32 to CPS and verify it produces identical results.

Implement map_k<A, B, K: FnOnce(Vec<B>)>(list: Vec<A>, f: impl Fn(A, Box<dyn FnOnce(B)>), k: K) — CPS map over a vector.

Show how CPS factorial becomes iterative when combined with trampolining.

Open Source Repos

functional-rust

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

Rust