Devils and Angels, via Monads
Jim Bender
"Programming with Continuations". That paper used call/cc and mutable state (via
"set!") to describe an "exercise", which they called "devils and angels". This "exercise"
has little practical point, per se: it is really the illustration of the combination
of state and first-class continuations which was important.
That "exercise" provides three operations: milestone, which provides a "marker";
devil, which transfers control back to the last milestone; and angel, which transfers
control "forward" to the last devil. In other words, tracing a "devils and angels"
program is "tricky".
This note shows an alternative implementation: in terms of monads: a state monad
lifted into a continuation monad. This is not new: such an implementation is shown
in Chalmers's "Advance Functional Programming" course--in Haskell, of course:
http://www.cs.chalmers.se/~augustss/AFP/problems/devils-n-angels/
What this note does is to show an implementation, not in terms of the standard
implementation of monads, but rather one based on Andrzej Filinski's paper
"Representing Monads". That paper shows how a "monadic" program may be written
in direct style--i.e. how to add "effects" to an Scheme/ML program without completely
transforming that program into the normal monadic style. Shift and reset--delimited
continuations-- are used to achieve this.
However, where Filinski represents _monads_ using shift and reset (via his
reflect and reify operators), this note represents _monad transformers_, specifically,
the top-most monad transformer. This is relevant because, as noted, this
implementation of "Devils and Angels" applies a continuation monad transformer
to a state monad (consisting of a pair of "continuation" stacks).
[Certainly this approach must be compared with Filinski's later paper,
"Representing Layered Monads". Read on ;)]
The foundation of my implementation is the state monad, where "state"
consists of a "past" stack and a "future" stack.
We first provide a stack implementation:
> (define (make-stack) '())
> (define (empty-stack? s) (null? s))
> (define (pop s def)
> (if (empty-stack? s)
> (values def '())
> (values (car s) (cdr s))))
> (define (push s v) (values v (cons v s)))
We give below the definition of a standard state monad:
> (define stateM@
> (unit/sig monad^ (import)
> (define (return v) (lambda (past future) (values v past future)))
> (define (bind m w)
> (lambda (past_ future_)
> (let-values (((val past future) (m past_ future_)))
> ((w val) past future))))
> (define (run m)
> (let-values (((a s1 s2) (m (make-stack) (make-stack)))) a))))
[It is worth noting that, where Filinski's paper uses SML's functors
to compose SML structures which implement the monad(s), I use PLT's
signed units (unit/sig). Essentially, I use unit/sig as a stand-in
for the composable SML modules.]
This state monad is given operations to push and pop from each of the stacks:
the past and future stacks.
> (define stateMOps@
> (unit/sig stateMOps^ (import monad^)
> (define (popPastSt def)
> (lambda (past future)
> (let-values (((v new-s) (pop past def)))
> (values v new-s future))))
> (define (popFutureSt def)
> (lambda (past future)
> (let-values (((v new-s) (pop future def)))
> (values v past new-s))))
> (define (pushPastSt v)
> (lambda (past future)
> (let-values (((v new-s) (push past v)))
> (values v new-s future))))
> (define (pushFutureSt v)
> (lambda (past future)
> (let-values (((v new-s) (push future v)))
> (values v past new-s))))))
The next step is to provide a continuation "monad transformer": the code which
will enable lifting of the state monad into a continuation monad.
> (define monadT@
> (unit/sig monadT^ (import represent^ (base : monad^))
> (define (lift m) (lambda (k) (base:bind m k)))
> (define (return v) (lift (base:return v)))
> (define (bind m w) (lambda (k) (m (lambda (v) ((w v) k)))))
> (define (run t) (base:run ((reify t) base:return)))))
We now provide both an implementation of the callcc operator and
the lifted "state" operations:
> (define ctrlStOps@
> (unit/sig ctrlStOps^ (import represent^ monadT^ stateMOps^)
> (define (popPast def) (reflect (lift (popPastSt def))))
> (define (popFuture def) (reflect (lift (popFutureSt def))))
> (define (pushPast v) (reflect (lift (pushPastSt v))))
> (define (pushFuture v) (reflect (lift (pushFutureSt v))))
> (define (callcc f)
> (reflect (lambda (k)
> ((reify (lambda () (f (lambda (v) (jump k v))))) k))))
> ; not exported--this is embeded in the "continuation" passed to "f" by callcc
> (define (jump k v)
> (reflect (lambda (_)
> (k v))))))
In both the contination monad transformer (the "run" function) and the here
in the various operations, we see the use of reify and run. These are Filinski's
monadic reflection operators:
> (define represent@
> (unit/sig represent^ (import monad^)
> (define (reflect m) (shift k (bind m k)))
> (define (reify t) (reset (return (t))))))
It is these operations that actually alleviate the need to express the "devils
and angels" _operations_, and programs which use those operations, in the standard
monadic notation: i.e. a systematic use of bind and unit, throughout the program
which is a _client_ of the monad(s). Filinski gives us the detailed math on _why_
these operations work.
We have noted that Filinski "represents" _monads_ using reflect and reify. Here,
we seem to be representing a monad _transformer_ with reflect and reify. In essence,
this works because a monad plus a transformer *is* a new monad. What is interesting,
however, is that the client of this "represented" monad (transformer) does not need
to be away of the "lifting" which has occurred in the background.
Finally, we give the implementation of the milestone, devil, and angel operations:
> (define (milestone x) (callcc (lambda (k) (pushPast k)
> (define (devil x)
> (callcc (lambda (k) (pushFuture k)
> ((popPast return) x))))
> (define (angel x) ((popFuture return) x))
What is most interesting about this implementation of these three operators from
the Friedman puzzle, is that the implementation is actually identical to that given
in the original paper: despite a monadic implementation behind the scenes, the
direct style implementation of these three operations (which are _clients_ of the
state+continuation monads) is identical to the more imperative implementation in the
original paper. (Friedman, et al. implemented the pair of stacks in terms of set!.)
To link everything together, we use the following compound-unit:
> (define-values/invoke-unit/sig
> ((open ctrlStOps^) (open monadT^))
> (compound-unit/sig
> (import)
> (link (ST : monad^ (stateM@))
> (STOPS : stateMOps^ (stateMOps@ ST))
> (REPRESENTATION : represent^
> (represent@ (MT : monad^)))
> (MT : monadT^ (monadT@ REPRESENTATION ST))
> (CTRL : ctrlStOps^ (ctrlStOps@ REPRESENTATION MT STOPS)))
> (export (open CTRL) (open MT))))
Finally, we give an example "devils and angels" program:
> (run (lambda ()
> (let ((x (milestone 1))) ; point "A"
> (if (= x 1)
> (+ (devil 2) 100) ; point "B"
> (angel (+ 3 x))))))
This example is due to the Chalmers course mentioned above. Quoting
their explanation:
"This example will first come to point A with value 1 bound to x.
The devil will jump back to A, but now x will have value 2.
This means that we end up in the else-branch, where the angel will jump
forward to the latest devil position, which was B, with the value 3+x.
Finally, the example returns 3+x+100."
The answer, by the way, is 105.
We have earlier mentioned Filinski's other paper "Representing Layered Monads".
In the methodology of that paper, the state and continuation monads would be
implemented separately, both in terms of (separate instances of) reify and reflect.
Finally, these two separate monads would be chained together, in effect, via a
tower of CPS terms (well, a tower of shift/resent terms).
I claim that this is often a perfectly viable method. But it is also more subtle:
far more subtle than the implementation of a single monad in terms of reify/reflect.
As well, implementation of the layering via monad transformers may be more accessible
(at least to those familiar with Haskell), and such an implementation provides
more fine-grained control over the transformation of the base monad that does
Filinski's "layered monad" scheme.
Are these techniques practical? In a separate post, I will illustrate the implementation
of an "Abstract CPS" monad via Filinski's reify/reflect--in order to provide a usable,
though pedagogical, implementation of a library of delimited continuation operations
(a la Queinnec's "A Library of High-Level Control Operators", which was implemented as
an _interpreter_). And soon, on the WebIt! mailing list, I will post an example of
an XML transformation which uses these techniques. The first is, strictly, only an
example of the techinique of Filinski's "Representing Monads" paper.
The second will provide a practical illustration of "representing" monad transformers.
I have earlier, on the WebIt! list, posted examples of XML transformations that use
monads; these used the more standard implementation of monads--and required the
entire "stylesheet" to be expressed in monadic style. This new example does not
require such a transformation.
Jim Bender