Continuation-Passing Mnemonics

Learning to construct continuations can be tough. It’s easy to state how they work: they facilitate tail recursion by recursively passing the remainder of a computation. But it can be a lot harder to actually get one working from scratch. I won’t discuss continuations further here; there are lots of good discussions online and in books. What I want to show here is a simple mnemonic block of code I use to remember how to write a continuation. It can help prevent that “deer in the headlights” look when asked for a continuation example by a friend, at a job interview, or when staring into the monitor at 1 a.m., lol.

Most of the examples one sees involve using a continuation to provide tail recursion to a function requiring some operation on the results from two recursive calls. It’s probably because this covers the many of the simplest real life cases for which continuation-passing is needed. For example, here is the commonly-seen continuation-passing version of a function which computes a Fibonacci number. (As always, presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

let fib n =

  let rec f n cont =

    match n with

    | 0 -> cont 0

    | 1 -> cont 1

    | n -> 

      f (n-2) (fun n2-> 

        f (n-1) (fun n1->

          cont(n1+n2)))

  f n (fun x->x)

But even this simple example can be a little intimidating, and a little difficult to remember, given that writing continuation-passing functions is not typically a frequent task. It is worthwhile committing the Fibonacci example to memory, but I’ve got an even simpler example that I can even use as a mnemonic to recall the Fibonacci (or tree, etc.) examples.

Here is my simpler example: computing the sum of the numbers from 1 to n. Of course, this a task for which continuation-passing, and even recursion, is not actually required; I use it as an example only because it is so simple to remember!

For reference, here is a naïve recursive implementation:

let rec sum0 = function

  | 1 -> 1

  | n -> n+(sum0 (n-1))

This one shows a typically-constructed continuation-passing version:

let sum1 n =

  let rec f n cont =

    match n with

    | 1 -> cont 1

    | n -> f (n-1) (fun n1->cont(n+n1))

  f n (fun x->x)   

And this one, the one I memorize, shows a continuation-passing version with the parameters in reverse order from that usually seen. For some reason I find it easier to understand this way; probably some psychological thing related to the recursive and continuation functions being side-by-side. (That, and the currying and use of the “function” construct make it look cleaner.)

let sum2 =

  let rec f cont = function

    | 1 -> cont 1

    | n -> f (fun n1->cont(n+n1)) (n-1) 

  f (fun x->x)   

Tests will show that the naïve version will overflow the stack past a certain value of n, while the other two do not. (As always when testing tail recursion, remember that tail call optimization is turned off in debug mode, so perform the tests in release mode.)

Remembering this simple example can make it easier to construct the more complex cases where continuation-passing is actually needed. In my ongoing parlance, this version, being simpler, appears more “fluent.” And it’s often easier when coding to first write a simple function or program, and then change it into a complex one incrementally, even if the initial, simple example bears little resemblance to the end result.

-Neil