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.
#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
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
(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
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
fail function to see just how many times it gets called as the program searches for a path that doesn't call
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.