869 Expert

869-continuation-monad — Continuation Monad

Functional Programming

Tutorial

The Problem

Continuation-passing style (CPS) is a program transformation where every function, instead of returning a value, accepts an extra "continuation" argument — a callback representing the rest of the computation. This transform makes control flow explicit and enables features that are otherwise impossible in a direct-style language: early exit, coroutines, and delimited continuations. Scheme pioneered first-class continuations with call/cc. The continuation monad wraps this pattern as a composable abstraction with the type Cont r a = (a -> r) -> r, fundamental to compiler intermediate representations and effect-system implementations.

🎯 Learning Outcomes

• Understand continuation-passing style and how it makes control flow explicit

• Implement the Cont monad type in Rust using Box<dyn Fn>

• Recognize CPS factorial as the canonical tail-recursive transformation

• Understand how callcc enables early exit from nested computations

• Compare Rust's heap-allocated closures with OCaml's uniform closure representation

Code Example

#![allow(clippy::all)]
/// Continuation Monad — Delimited Continuations in Rust
///
/// The continuation monad wraps computations that pass their result to a callback.
/// type Cont r a = (a -> r) -> r

pub struct Cont<R, A> {
    run: Box<dyn Fn(Box<dyn Fn(A) -> R>) -> R>,
}

impl<R: 'static, A: 'static> Cont<R, A> {
    pub fn new(f: impl Fn(Box<dyn Fn(A) -> R>) -> R + 'static) -> Self {
        Cont { run: Box::new(f) }
    }

    pub fn run_cont(self, k: impl Fn(A) -> R + 'static) -> R {
        (self.run)(Box::new(k))
    }
}

/// Wrap a pure value in Cont: \k -> k(a)
pub fn cont_return<R: 'static, A: Clone + 'static>(a: A) -> Cont<R, A> {
    Cont::new(move |k: Box<dyn Fn(A) -> R>| k(a.clone()))
}

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

    #[test]
    fn test_cps_add() {
        let result = (|a: i32, b: i32, k: &dyn Fn(i32) -> i32| k(a + b))(3, 4, &|x| x);
        assert_eq!(result, 7);
    }

    #[test]
    fn test_factorial_cps() {
        fn fact(n: i32, k: &dyn Fn(i32) -> i32) -> i32 {
            if n <= 1 {
                k(1)
            } else {
                fact(n - 1, &|r| k(n * r))
            }
        }
        assert_eq!(fact(5, &|x| x), 120);
    }

    #[test]
    fn test_cont_return() {
        let c = cont_return::<i32, i32>(42);
        assert_eq!(c.run_cont(|x| x), 42);
        let c2 = cont_return::<i32, i32>(10);
        assert_eq!(c2.run_cont(|x| x * 2), 20);
    }
}

(* Example 070: Continuation Monad *)
(* CPS: continuation-passing style *)

(* Approach 1: Basic CPS transforms *)
let add_cps x y k = k (x + y)
let mul_cps x y k = k (x * y)
let square_cps x k = k (x * x)

(* Chain: (3 + 4) * 2 *)
let example1 k = add_cps 3 4 (fun sum -> mul_cps sum 2 k)

(* Approach 2: Cont monad *)
type ('a, 'r) cont = Cont of (('a -> 'r) -> 'r)

let run_cont (Cont f) k = f k
let return_ x = Cont (fun k -> k x)
let bind (Cont m) f = Cont (fun k ->
  m (fun a -> run_cont (f a) k))
let ( >>= ) = bind

(* callcc: capture the current continuation *)
let callcc f = Cont (fun k ->
  run_cont (f (fun a -> Cont (fun _ -> k a))) k)

(* Approach 3: Early exit with callcc *)
let find_first_negative xs =
  callcc (fun exit ->
    List.fold_left (fun acc x ->
      acc >>= fun _ ->
      if x < 0 then exit (Some x)
      else return_ None
    ) (return_ None) xs
  )

let safe_div_cont x y =
  callcc (fun exit ->
    if y = 0 then exit (Error "Division by zero")
    else return_ (Ok (x / y))
  )

let () =
  (* Basic CPS *)
  example1 (fun result -> assert (result = 14));
  square_cps 5 (fun result -> assert (result = 25));

  (* Cont monad *)
  let result = run_cont (
    return_ 5 >>= fun x ->
    return_ (x * 2) >>= fun y ->
    return_ (y + 1)
  ) Fun.id in
  assert (result = 11);

  (* callcc: early exit *)
  let result = run_cont (find_first_negative [1; 2; -3; 4]) Fun.id in
  assert (result = Some (-3));

  let result = run_cont (find_first_negative [1; 2; 3]) Fun.id in
  assert (result = None);

  let result = run_cont (safe_div_cont 10 2) Fun.id in
  assert (result = Ok 5);
  let result = run_cont (safe_div_cont 10 0) Fun.id in
  assert (result = Error "Division by zero");

  Printf.printf "✓ All tests passed\n"

Key Differences

Closure representation: Rust requires Box<dyn Fn> for heap-allocated dynamic closures; OCaml closures are uniformly heap-allocated values.

callcc: Full callcc is not expressible in safe Rust; OCaml (and Scheme) support it natively via the runtime stack.

Lifetime of continuations: Rust must carefully manage 'static bounds on captured values; OCaml's GC handles lifetime automatically.

Composition: OCaml's >>= operator chains continuations cleanly; Rust requires explicit method calls or helper functions.

OCaml Approach

OCaml represents Cont as a GADT-free algebraic type type ('a, 'r) cont = Cont of (('a -> 'r) -> 'r). The bind function composes two continuations, and callcc captures the current continuation, enabling early exit from List.fold_left. OCaml's let* syntax makes monadic chains readable. The OCaml version shows find_first_negative using callcc to exit the fold immediately when a negative is found — a pattern impossible with plain fold.

Full Source

#![allow(clippy::all)]
/// Continuation Monad — Delimited Continuations in Rust
///
/// The continuation monad wraps computations that pass their result to a callback.
/// type Cont r a = (a -> r) -> r

pub struct Cont<R, A> {
    run: Box<dyn Fn(Box<dyn Fn(A) -> R>) -> R>,
}

impl<R: 'static, A: 'static> Cont<R, A> {
    pub fn new(f: impl Fn(Box<dyn Fn(A) -> R>) -> R + 'static) -> Self {
        Cont { run: Box::new(f) }
    }

    pub fn run_cont(self, k: impl Fn(A) -> R + 'static) -> R {
        (self.run)(Box::new(k))
    }
}

/// Wrap a pure value in Cont: \k -> k(a)
pub fn cont_return<R: 'static, A: Clone + 'static>(a: A) -> Cont<R, A> {
    Cont::new(move |k: Box<dyn Fn(A) -> R>| k(a.clone()))
}

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

    #[test]
    fn test_cps_add() {
        let result = (|a: i32, b: i32, k: &dyn Fn(i32) -> i32| k(a + b))(3, 4, &|x| x);
        assert_eq!(result, 7);
    }

    #[test]
    fn test_factorial_cps() {
        fn fact(n: i32, k: &dyn Fn(i32) -> i32) -> i32 {
            if n <= 1 {
                k(1)
            } else {
                fact(n - 1, &|r| k(n * r))
            }
        }
        assert_eq!(fact(5, &|x| x), 120);
    }

    #[test]
    fn test_cont_return() {
        let c = cont_return::<i32, i32>(42);
        assert_eq!(c.run_cont(|x| x), 42);
        let c2 = cont_return::<i32, i32>(10);
        assert_eq!(c2.run_cont(|x| x * 2), 20);
    }
}

(* Example 070: Continuation Monad *)
(* CPS: continuation-passing style *)

(* Approach 1: Basic CPS transforms *)
let add_cps x y k = k (x + y)
let mul_cps x y k = k (x * y)
let square_cps x k = k (x * x)

(* Chain: (3 + 4) * 2 *)
let example1 k = add_cps 3 4 (fun sum -> mul_cps sum 2 k)

(* Approach 2: Cont monad *)
type ('a, 'r) cont = Cont of (('a -> 'r) -> 'r)

let run_cont (Cont f) k = f k
let return_ x = Cont (fun k -> k x)
let bind (Cont m) f = Cont (fun k ->
  m (fun a -> run_cont (f a) k))
let ( >>= ) = bind

(* callcc: capture the current continuation *)
let callcc f = Cont (fun k ->
  run_cont (f (fun a -> Cont (fun _ -> k a))) k)

(* Approach 3: Early exit with callcc *)
let find_first_negative xs =
  callcc (fun exit ->
    List.fold_left (fun acc x ->
      acc >>= fun _ ->
      if x < 0 then exit (Some x)
      else return_ None
    ) (return_ None) xs
  )

let safe_div_cont x y =
  callcc (fun exit ->
    if y = 0 then exit (Error "Division by zero")
    else return_ (Ok (x / y))
  )

let () =
  (* Basic CPS *)
  example1 (fun result -> assert (result = 14));
  square_cps 5 (fun result -> assert (result = 25));

  (* Cont monad *)
  let result = run_cont (
    return_ 5 >>= fun x ->
    return_ (x * 2) >>= fun y ->
    return_ (y + 1)
  ) Fun.id in
  assert (result = 11);

  (* callcc: early exit *)
  let result = run_cont (find_first_negative [1; 2; -3; 4]) Fun.id in
  assert (result = Some (-3));

  let result = run_cont (find_first_negative [1; 2; 3]) Fun.id in
  assert (result = None);

  let result = run_cont (safe_div_cont 10 2) Fun.id in
  assert (result = Ok 5);
  let result = run_cont (safe_div_cont 10 0) Fun.id in
  assert (result = Error "Division by zero");

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_cps_add() {
        let result = (|a: i32, b: i32, k: &dyn Fn(i32) -> i32| k(a + b))(3, 4, &|x| x);
        assert_eq!(result, 7);
    }

    #[test]
    fn test_factorial_cps() {
        fn fact(n: i32, k: &dyn Fn(i32) -> i32) -> i32 {
            if n <= 1 {
                k(1)
            } else {
                fact(n - 1, &|r| k(n * r))
            }
        }
        assert_eq!(fact(5, &|x| x), 120);
    }

    #[test]
    fn test_cont_return() {
        let c = cont_return::<i32, i32>(42);
        assert_eq!(c.run_cont(|x| x), 42);
        let c2 = cont_return::<i32, i32>(10);
        assert_eq!(c2.run_cont(|x| x * 2), 20);
    }
}

Exercises

Implement cont_bind that sequences two Cont<R, A> values (monadic bind / >>=).

Implement a CPS Fibonacci that is stack-safe by expressing it as a continuation chain.

Use the continuation monad to implement a depth-limited tree search that exits early when the depth limit is reached.

Open Source Repos

functional-rust

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

Rust