Chapter 7 Programming with continuations

Writing Functions in CPS

Functions written in continuation passing style never return their results directly, instead they always pass call the continuation with them.

Let’s consider the factorial function as an example. I’m using pseudocode which differs from OCaml used in the source article.

fn fact(n):
	if n == 0 then 1
	else n * fact(n-1)

If this were written in CPS style, it’ll take a continuation argument too:

fn cps_fact(n, k):
	if n == 0 then k(1)
	else cps_fact(n - 1, (v) => k(v * n))

Note how the function written in CPS style is tail-recursive. The data that was stored in the stack in the first function is now stored in different lambda objects on the heap. This might be beneficial for languages where the stack size is limited but heap is available.

It is tempting to write the else branch above as k(n * cps_fact(n-1, k)), but remember that cps_fact doesn’t return anything, it just passes the result to the continuation passed to it. So we need to do the multiplication of n in the continuation we supply.

Iterators

Consider that we have a binary tree

enum Tree[T] =
	Leaf |
	Node(Tree, T, Tree)

Now we can write a function iterating over it as:

fn tree_iter (f: T -> ()) (t: Tree[T]):
	case t in
		Leaf => ()
		Node(left, val, right) => tree_iter(f, left); f(val); tree_iter(f, right)

We can rewrite this in CPS as:

fn tree_iter (f: T -> (() -> T2) -> T2) (t: Tree[T]) (k: () -> T2):
	case t in
		Leaf => k()
		Node(left, val, right) => tree_iter f left (() => f val (() => tree_iter right k))

The function f is also written in CPS here where it not only takes an element of the tree, it also takes a continuation which encodes what part of the iteration is left.

We can use continuations to implement Python-style generators:

fn tree_generator (t: Tree[T]) -> (() -> T):
	let next = () => (
		tree_iter (x => k => next = k; x) t (() => raise StopIteration)
	);
	(() => next())

Aysnchronous & Concurrent Programming

Functions can do some work and then store the continuation supplied to them along with the generated value in a scheduler queue to be run later.

fn foo ... k:
	// ... perform computation ...
	yield (() => foo ... k)

The yield function is supplied with a function that does the rest of the work. It can then run other functions and schedule this functino later.