196 Expert

Delimited Continuations

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Delimited Continuations" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. Full continuations (`callcc`) capture the entire remaining computation. Key difference from OCaml: 1. **Native support**: OCaml 5's effect system is built on delimited continuations; Rust requires simulation or `unsafe` code.

Tutorial

The Problem

Full continuations (callcc) capture the entire remaining computation. Delimited continuations capture only the computation up to a "delimiter" — a prompt that marks the boundary. This makes them composable and less dangerous than full continuations. Delimited continuations are the foundation of effect handlers (OCaml 5), generators, and async/await. Understanding them reveals how all these features share a common computational model.

🎯 Learning Outcomes

• Understand the difference between full and delimited continuations

• Learn reset (sets the delimiter) and shift (captures the delimited continuation)

• See how delimited continuations generalize generators, exceptions, and async

• Understand why OCaml 5's effect handlers are implemented via delimited continuations

Code Example

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

(* Delimited continuations: capture only part of the call stack.
   OCaml 5 effects give us delimited continuations naturally. *)
effect Shift : ('a -> 'b) -> 'a

let reset f =
  match f () with
  | v -> v
  | effect (Shift k) handler -> handler k

let shift f = perform (Shift f)

(* Classic: list of successes (nondeterminism) *)
let choose lst =
  shift (fun k -> List.concat_map k lst)

let () =
  (* Pythagorean triples up to 10 *)
  let triples =
    reset (fun () ->
      let a = choose [1;2;3;4;5;6;7;8;9;10] in
      let b = choose [a;a+1;a+2;a+3;a+4;a+5;a+6;a+7;a+8;a+9;a+10] in
      let c = choose [b;b+1;b+2;b+3;b+4;b+5] in
      if a*a + b*b = c*c then [(a,b,c)] else [])
  in
  List.iter (fun (a,b,c) -> Printf.printf "(%d,%d,%d)\n" a b c) (List.filteri (fun i _ -> i < 5) triples)

Key Differences

Native support: OCaml 5's effect system is built on delimited continuations; Rust requires simulation or unsafe code.

Multi-shot: OCaml's continue k can be called multiple times (non-determinism, backtracking); Rust's FnOnce and Box<dyn FnOnce> are single-shot only.

Stack frames: OCaml captures actual stack frames as continuations — zero-copy; Rust's simulation copies data into closures.

Composability: Delimited continuations in OCaml compose via nested match_with; Rust's simulation composes poorly beyond simple cases.

OCaml Approach

OCaml 5 implements delimited continuations natively:

let () =
  match_with (fun () ->
    let k = perform (Shift (fun k -> k)) in  (* capture delimited cont *)
    Printf.printf "resumed\n";
    perform (Resume k)  (* resume it *)
  ) () { ... }

The delimcc library (for older OCaml) provides new_prompt, push_prompt, and shift0 / control0 as the full delimited continuation API.

Full Source

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

(* Delimited continuations: capture only part of the call stack.
   OCaml 5 effects give us delimited continuations naturally. *)
effect Shift : ('a -> 'b) -> 'a

let reset f =
  match f () with
  | v -> v
  | effect (Shift k) handler -> handler k

let shift f = perform (Shift f)

(* Classic: list of successes (nondeterminism) *)
let choose lst =
  shift (fun k -> List.concat_map k lst)

let () =
  (* Pythagorean triples up to 10 *)
  let triples =
    reset (fun () ->
      let a = choose [1;2;3;4;5;6;7;8;9;10] in
      let b = choose [a;a+1;a+2;a+3;a+4;a+5;a+6;a+7;a+8;a+9;a+10] in
      let c = choose [b;b+1;b+2;b+3;b+4;b+5] in
      if a*a + b*b = c*c then [(a,b,c)] else [])
  in
  List.iter (fun (a,b,c) -> Printf.printf "(%d,%d,%d)\n" a b c) (List.filteri (fun i _ -> i < 5) triples)

Deep Comparison

OCaml vs Rust: Delimited Cont

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 a generator using the delimited continuation simulation: yield_value shifts, next_value resets.

Implement simple backtracking: amb([1, 2, 3]) tries all options using multi-shot continuation semantics.

Write a reset/shift combination that implements Result propagation — shift throws an error, reset catches it.

Open Source Repos

functional-rust

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

Rust