I was going to post this as a comment on r/lisp, but I feel it’s grown a bit too much for the platform. For one time only, this blog will host some Racket code. I apologise in advance to any Schemer reading this. I needed an easy way to play with control operators, but I’ve never really Schemed, so there’s probably a dozen issues with the code and its style.
So, why is the continuation monad the mother of all monads? The short answer is that, by enabling transparent inversion of control, it eliminates the need to sprinkle hooks for monad-specific code everywhere; normal (as much as anything involving delimited continuations can be “normal”) evaluation rules will be subverted as needed. Here’s how.
First, some boilerplate (boilerfoil may be the more appropriate term).
#lang racket (require racket/control) ; for shift/reset (define (run thunk return . arguments) (reset (return (apply thunk arguments))))
This definition is all that is needed to execute arbitrary Racket code
in a monad: the only thing to specify is how a ground value should be
moved in the monad.
bind will be defined implicitly, through the
code for monad-specific behaviour. The body of
run defines a
context to determine where to stop capturing the continuation, and
executes the form
(return (apply thunk arguments)) in that context:
the thunk is called with any argument provided, and the result is
returned into the monad.
For the sake of generalisation, I’ll start with a trivial example: the Maybe monad. First, I’ll quickly define structure types. In practice, a distinguished “nothing” value would suffice, but this way parallels Haskell more closely.
(struct Maybe ()) (struct Nothing Maybe ()) (struct Some Maybe (value))
Some also doubles as
return. In order to abort
nothing must unwind the continuation and return a
(define (nothing) (shift k (Nothing))) > (run (lambda () 42) Some) #<Some> > (Some-value (run (lambda () 42) Some)) 42
run obviously works as it should in these trivial
examples. It’s also not surprising that
nothing works, because it’s
the obvious implementation of unwinding with delimited continuations.
> (run (lambda () 42 (nothing) #t) Some) #<Nothing>
In the List monad,
return is just
run can be called with a
list as the second argument, and indeed, the result is a
normal computation that returns its value as a singleton.
> (run (lambda () (+ 4 5)) list) '(9)
The useful thing to do with the List monad is to specify multiple return values, and have the computation fork (lazily in Haskell, eagerly here, because I’m working with strict lists) on each choice. That’s a one-liner:
(define (inject-values . values) (shift k (append-map k values)))
This function captures the continuation up to
reset, unwinds the
current continuation up to that point, and binds the captured
delimited continuation to
k. Then, it passes each possible value to
the continuation, and appends the results together.
Here’s a first example:
> (run (lambda () (+ (inject-values 1 2) (inject-values 3 4))) list) '(4 5 5 6)
That is, reassuringly, the four possible sums:
1 + 3 = 4,
1 + 4 = 5,
2 + 3 = 5, and
2 + 4 = 6. The magic is that all Scheme code,
by virtue of supporting the capture (and unwind) of delimited
continuation, is now “in” the List monad. It is certainly the case
for that uninstrumented thunk. The pre-defined function
provides a more convincing example.
> (run (lambda () (map cons (inject-values '(1 2) '(4 5)) (inject-values '(3 4) '(5 6)))) list) '(((1 . 3) (2 . 4)) ((1 . 5) (2 . 6)) ((4 . 3) (5 . 4)) ((4 . 5) (5 . 6)))
I’ve taken the liberty of line-wrapping the return value, and clearly,
(map cons ...) has been called with all four pairs of lists… but
all the special monadic operations happens outside
inject-values inside the mapped function is a much stronger evidence
that arbitrary uninstrumented Scheme code is implicitly lifted in the
map is a predefined (pre-compiled even) library function.
> (run (lambda () (map (lambda (x y) ((inject-values + -) x y)) '(1 2 3) '(4 5 6))) list) '((5 7 9) ; + + + (5 7 -3) ; + + - (5 -3 9) ; + - + (5 -3 -3) ; + - - (-3 7 9) ; - + + (-3 7 -3) ; - + - (-3 -3 9) ; - - + (-3 -3 -3)) ; - - -
At each call to the mapped function, the computation explores both the branch in which the arguments are added and the one in which they are subtracted. The result, for 3 pairs of triplets, is a list of 8 triplets.
Neither of these implementations is surprising or new; I believe
they’re standard undergraduate exercises in a few universities. The
is that both
inject-values share the same structure
and can be defined in terms of the monad they help implement. Because
I dislike scrolling, their definitions are copied here.
(define (nothing) ; Maybe (shift k (Nothing))) (define (inject-values . values) ; List (shift k (append-map k values)))
Instead of returning the (monadic) value
list), both capture and unwind the delimited continuation, bind it to
k, and then do something more to the value. Some squinting reveals
that that something more is calling
bind with the continuation
as the next step. In the Maybe monad,
Nothing >>= k evaluates to
Nothing. In the List monad,
values >>= k becomes
. k)  values, which is basically
(append-map k values). The
general form for any monad is then to implement any operator that
return a value as
(define (operator ...) (shift k (bind [special stuff] k)))
As code, this gives
(define (make-operator bind operator) (lambda arguments (shift k (bind (apply operator arguments) k))))
after adding support for variadic operators. For example, choosing between multiple items in a list is
(define (list-bind x k) (append-map k x)) (define inject-values2 (make-operator list-bind list))
Some sketching on paper will show that the transformation is generic
and correct, with a proof that mostly goes through repeated
applications of the monad laws. Capturing the continuation moves the
whole stack of functions that will eventually receive results into a
single function (the continuation), and that function can then be
bind. The monad laws guarantee that this associative
reordering of nested
binds preserves the meaning of the program.
We can also mimic
do-notation more closely and implement
“anti-return”. Given that operator, not
returning a value can instead
be implemented as
joining it after the fact. One definition is
(make-operator bind identity), but I feel it’s simpler to just do it
(define (make-join bind) (lambda (value) (shift k (bind value k)))) (define join-list (make-join list-bind)) > (run (lambda () (+ 1 (join-list '(1 2 3)))) list) '(2 3 4)
Of course all this also works when
operator is equivalent to
return; it’s just pointless. The
bind dance is
then a convoluted way to demand regular Scheme evaluation rules.
And that is how the continuation monad is universal. When code is in the continuation monad (or in a language with delimited continuations), there is a mechanical way to have that code execute in almost any other monad. There are technical restrictions on the monad for the transformation to work, but I think any monad that can be implemented in (pure) Haskell qualifies.
I feel like sigfpe’s presentation was hobbled by the fact that he used the Continuation monad in Haskell, making it harder to see that the Continuation monad of the implementation is completely independent of the emulated one. Really, the idea is one of these nice insights that formalise and generalise old hacks, and seem obvious in retrospect.
The post’s title refers to the fact that delimited continuations can
themselves be implemented in terms of
(and a single mutable cell). There are many ways to interpret the
call/cc suffices to transpose code into arbitrary
monads. It certainly seems like a victory for the minimalist crowd.
On the other hand, I believe that the power of programming languages
and paradigms lies as much in what they enable as it does in what they
forbid (or make inconvenient, at least). From that point of view,
it’s not obvious whether the universality of
call/cc makes a strong
case for or against the feature.
This result also provides a tentative explanation for the low traction of monads among Lispers: perhaps many would rather directly hack the features in, with (ersatz) continuations.