Continuations—what are they?

17 Nov 2022

I had a friend ask me what continuations are, and why they're useful. There's a ton of literature about continuations; this is just a simple example meant to showcase something small and hopefully grokkable.

You will need to understand a little bit of Racket, but if you know any Scheme, that should be good enough. If you just want a quick primer, check out Learn X in Y minutes for Racket.

#lang racket

;;; Export these symbols
(provide fail pick non-deterministic-factor)

;;; Global stack of choices (only visible to this module)
(define *choices* '())

;;; Pop a value off of the alternate choices stack
(define (fail)
  (if (null? *choices*)
      #f
      (let ([next-choice (car *choices*)])
        (set! *choices* (cdr *choices*))
        (next-choice))))

This next function pick is where we capture the continuation. I've named it return-from-pick to illustrate that when you call this function, it will jump back to the point in the code where pick returns. However, this works even if you use the continuation after the thing the called pick itself has returned.

Internally, the continuation is basically stack + program counter. It answers the question "where does this value go to when I return it?"

We "install" the continuation by calling it like a function. It's a first-class value, though, so we can save it in a closure on a stack and call it as many times as we want.

(define (pick vals)
  (if (null? vals)
      (fail)                            ; fallback if there's nothing to choose
      (let ([my-choice (car vals)])     ; pick something

        (let/cc return-from-pick        ; capture the continutation right here!

          ;; Push the rest of the options into the *choices* stack
          (for ([other-choice (cdr vals)])
            (set! *choices* (cons (λ () (return-from-pick other-choice)) *choices*)))

          ;; This is how we return from the `pick' function with a particular value.
          (return-from-pick my-choice)))))

Now we have to use our operator. Let's write a factoring function that non-deterministically picks a factor. We test it to make sure that the one we picked works, and if it did, we return it. Otherwise, we tell the computer that we fail ed.

(define (non-deterministic-factor n)
  ;; Pick some factor, dunno which
  (let ([some-factor (pick (range 2 n))])
    ;; Did we pick a factor?
    (if (zero? (modulo n some-factor))
        some-factor                     ; yes we did!
        (fail))))                       ; oops, that was the wrong one

If you save those snippets into a file called amb.rkt and try running it, you should see something like:

$ racket -it amb.rkt
> (non-deterministic-factor 42)
2
> (fail)
21
> (fail)
14
> (fail)
7
> (fail)
6
> (fail)
3
> (fail)
#f
> (fail)
#f
,quit
$

Moral of the story: we just implemented McCarthy's non-deterministic/ambiguous amb operator which picks some value, tries it out, then seemingly backtracks no matter the code to the point where the value gets picked if the fail function is ever invoked. Moreover, this was all implemented in userland: no special compiler constructs, no macros, no nuffin'.

In reality, what we did was we saved the stack and program counter just before we returned from pick with our choice. When we call fail, we reinstantiate that stack frame but return a different value. The program proceeds as if we had returned with that value in the first place. (Though note that changes on the heap or the file system, etc. will not be reverted. It's only in side-effect free code that the illusion of time travel will be complete. You could stick a print statement in the fail function to see just how many times it gets called as the program searches for a path that doesn't call fail.)

Continuations can also be used to implement cooperative threading, job queues, and exception handling if you language doesn't support those. In each case, you can extend the language with continuations and functions without the rest of the code having to worry about it. It's a very powerful, robust, and non-leaky abstraction.