Monads as a Design Pattern
Lately I've found monads to be more and more useful in several programming projects. For example, Harlan's type inferencer uses a monad to keep track of what variables have been unified with each other, among other things. It took me a while to really grok monads. One reason is that many of the tutorials I've seen start out with category theory and the monad laws. These things don't strike me as all that useful when I'm trying to make my code better in some way.
What I have found useful is to think of monads as a style of programming (like continuation passing style), or even a design pattern. I've found monads are really handy when you need to thread some object through a sequence of function calls. To see how this works, we're going to start with a store-passing interpreter for a small language and show how to use monads to hide the store in the cases where we don't need it.
A Store Passing Interpreter🔗
Let's start by looking at an interpreter. This is basically the first interpreter from this post, but we've added mutable references.
(define value-of/store
(lambda (e env store)
(match e
(,x (guard (symbol? x))
(cons (lookup x env) store))
(,n (guard (number? n))
(cons n store))
((λ (,x) ,e)
(cons (lambda (v store)
(value-of/store e (extend-env x v env) store))
store))
((ref ,e)
(match (value-of/store e env store)
((,v . ,store)
(let ((label (gensym)))
(cons `(ref ,label)
(cons (cons label v) store))))))
((deref ,e)
(match (value-of/store e env store)
(((ref ,label) . ,store)
(cons (cdr (assq label store))
store))))
((update ,e-ref ,e-val)
(match (value-of/store e-ref env store)
(((ref ,label) . ,store)
(match (value-of/store e-val env store)
((,val . ,store)
(cons `(ref ,label)
(cons (cons label val) store)))))))
((,rator ,rand)
(match (value-of/store rator env store)
((,rator . ,store)
(match (value-of/store rand env store)
((,rand . ,store)
(rator rand store)))))))))
There are a couple of high level changes from the standard environment
passing interpreter. First, we've added an additional store
parameter. This represents the state of the memory, as opposed to the
environment, which tracks variables on the stack. Second, since
operations such as ref and update can modify the store, in
addition to returning the value of an expression, we also have to
return a potentially updated store. We could use Scheme's support for
multiple return values, but I went with cons instead for
simplicity's sake.
The first few cases are pretty straightforward. Starting on line 4, we have the variable lookup line. This reads a value from the environment and returns it. The store is left unchanged, so we just return that as is. Likewise with the number case in line 6.
For the lambda case on line 8, we use Scheme's lambda to represent
functions in our language. There's a slight subtly here. Instead of
having the procedure only take a value argument (v), it also must
take a store. The reason is that otherwise this procedure would modify
the store that was in effect when it the procedure was created, rather
than the store in effect at the call site.
Next we have ref, deref and update. This is where the store
starts to be interesting. We've represented the store as an
association list between labels and values. We use ref to create a
new reference (think of it like new in C++ or Java), which we
implement by using gensym to create a new label, and then adding a
new label:value pair to the store. The value of a ref expression is
a value tagged as a reference, containing an address into the
store. Think of these as pointers.
For deref, we first evaluate the argument and use match to unpack
the label from the returned reference value. Once we have the label,
we use assq to look it up in the store then we return its value.
The update expression requires us to evaluate two arguments: the
destination location and the new value. We do this with two recursive
calls to value-of/store. In the interpreter from previous posts, we
could have used match's catamorphism facility to make this quite a
bit shorter, but here we need to be explicit about ordering because of
a potentially changing store. When we get around to actually updating
the store, we just prepend a new label:value pair. Because assq
returns the first match it finds, this results in whatever value was
previously there being ignored.
Finally, the application case (line 30) is similar to before. The main changes are that we need to be explicit about the order of evaluation and we pass the current store into the function we are applying.
What we have now is an interpreter for a small language with mutable
references. You'll notice we didn't use any side effects in creating
the interpreter, which is kind of cool. Still, a few things are less
than ideal. To go from a language without mutable references to one
with mutable references, we had to change basically every line in the
interpreter. Every recursive call to value-of/store needs an
additional store parameter, and every return from the interpreter has
to return a store as well. This is the case even though only ref and
update can modify the store. What we'd like is to only have to be
aware of the store for cases that interact with the store. Monads can
help us do that.
Cleaning up the Interpreter🔗
To deal with some of the shortcomings in the previous paragraph, we are going to derive a monad through a series of correctness-preserving transformations. Some of the intermediate steps will look rather ugly, but the end should look pretty nice.
The first thing we're going to do is Curry (Schönfinkel?) the store argument.
(define value-of/store
(lambda (e env)
(lambda (store)
(match e
(,x (guard (symbol? x))
(cons (lookup x env) store))
(,n (guard (number? n))
(cons n store))
((λ (,x) ,e)
(cons (lambda (v)
(lambda (store)
((value-of/store e (extend-env x v env)) store)))
store))
((ref ,e)
(match ((value-of/store e env) store)
((,v . ,store)
(let ((label (gensym)))
(cons `(ref ,label)
(cons (cons label v) store))))))
((deref ,e)
(match ((value-of/store e env) store)
(((ref ,label) . ,store)
(cons (cdr (assq label store))
store))))
((update ,e-ref ,e-val)
(match ((value-of/store e-ref env) store)
(((ref ,label) . ,store)
(match ((value-of/store e-val env) store)
((,val . ,store)
(cons `(ref ,label)
(cons (cons label val) store)))))))
((,rator ,rand)
(match ((value-of/store rator env) store)
((,rator . ,store)
(match ((value-of/store rand env) store)
((,rand . ,store)
((rator rand) store))))))))))
As I said, we're going to make things worse for a while. Curried
functions in Scheme programs are always kind of messy. The nice thing
is that now we can push the (lambda (store) ...) part inside each of
the match branches. It will become clear why we might want to do this
in a second.
(define value-of/store
(lambda (e env)
(match e
(,x (guard (symbol? x))
(lambda (store)
(cons (lookup x env) store)))
(,n (guard (number? n))
(lambda (store)
(cons n store)))
((λ (,x) ,e)
(lambda (store)
(cons (lambda (v)
(lambda (store)
((value-of/store e (extend-env x v env)) store)))
store)))
((ref ,e)
(lambda (store)
(match ((value-of/store e env) store)
((,v . ,store)
(let ((label (gensym)))
(cons `(ref ,label)
(cons (cons label v) store)))))))
((deref ,e)
(lambda (store)
(match ((value-of/store e env) store)
(((ref ,label) . ,store)
(cons (cdr (assq label store))
store)))))
((update ,e-ref ,e-val)
(lambda (store)
(match ((value-of/store e-ref env) store)
(((ref ,label) . ,store)
(match ((value-of/store e-val env) store)
((,val . ,store)
(cons `(ref ,label)
(cons (cons label val) store))))))))
((,rator ,rand)
(lambda (store)
(match ((value-of/store rator env) store)
((,rator . ,store)
(match ((value-of/store rand env) store)
((,rand . ,store)
((rator rand) store))))))))))
Notice how we have a couple of cases, such as the variable and number
case, where all we do is cons some value onto an unchanged
store. Since we repeat this pattern a few times, let's pull it into a
separate function that we'll call... return.
(define return
(lambda (v)
(lambda (store)
(cons v store))))
We can rewrite our previous interpreter using return:
(define value-of/store
(lambda (e env)
(match e
(,x (guard (symbol? x))
(return (lookup x env)))
(,n (guard (number? n))
(return n))
((λ (,x) ,e)
(return (lambda (v)
(value-of/store e (extend-env x v env)))))
((ref ,e)
(lambda (store)
(match ((value-of/store e env) store)
((,v . ,store)
(let ((label (gensym)))
(cons `(ref ,label)
(cons (cons label v) store)))))))
((deref ,e)
(lambda (store)
(match ((value-of/store e env) store)
(((ref ,label) . ,store)
(cons (cdr (assq label store))
store)))))
((update ,e-ref ,e-val)
(lambda (store)
(match ((value-of/store e-ref env) store)
(((ref ,label) . ,store)
(match ((value-of/store e-val env) store)
((,val . ,store)
(cons `(ref ,label)
(cons (cons label val) store))))))))
((,rator ,rand)
(lambda (store)
(match ((value-of/store rator env) store)
((,rator . ,store)
(match ((value-of/store rand env) store)
((,rand . ,store)
((rator rand) store))))))))))
For the first time, we've introduced a transformation that makes our program shorter! While I was at it, I also did a transformation called an eta reduction in the lambda line at lines 9-10. The result is that the first three cases in the interpreter make no mention of the store. This is real tangible progress towards our goal.
Let's look at the last case, the application case, for a bit. Here we
take a store, pass it into a call to evaluate the operator, and then
thread the resulting store into a call to evaluate operand, and then
finally we thread that store into the actual application of the
operand. In each case, we don't really care about the store; we only
care about the value of the expression. Let's see if we can write a
function that does the store-threading for us. We'll call
it... bind.
(define bind
(lambda (m f)
(lambda (store)
(match (m store)
((,v . ,store)
((f v) store))))))
Here, m is for monad, meaning it's a function that does something
when it receives a store. The f parameter is a function describing
what to do next. It expects a value and returns a new monad. We get
this value by applying a store to the m argument. We expect f to
return a function expected a new store, and we apply this function to
the updated store returned by m. It's a bit complicated, but it
simplifies our application line somewhat:
(value-of/store
(lambda (e env)
(match e
(,x (guard (symbol? x))
(return (lookup x env)))
(,n (guard (number? n))
(return n))
((λ (,x) ,e)
(return (lambda (v)
(value-of/store e (extend-env x v env)))))
((ref ,e)
(lambda (store)
(match ((value-of/store e env) store)
((,v . ,store)
(let ((label (gensym)))
(cons `(ref ,label)
(cons (cons label v) store)))))))
((deref ,e)
(lambda (store)
(match ((value-of/store e env) store)
(((ref ,label) . ,store)
(cons (cdr (assq label store))
store)))))
((update ,e-ref ,e-val)
(lambda (store)
(match ((value-of/store e-ref env) store)
(((ref ,label) . ,store)
(match ((value-of/store e-val env) store)
((,val . ,store)
(cons `(ref ,label)
(cons (cons label val) store))))))))
((,rator ,rand)
(bind (value-of/store rator env)
(lambda (rator)
(bind (value-of/store rand env)
(lambda (rand)
(rator rand)))))))))
Our interpreter just shrunk by another line. The only cases where we
see the store actually appears are ref, deref, and update, which
are exactly the cases that need to read or write memory. The rest of
the interpreter is completely oblivious to the existence of memory.
We can clean up the application line a little further. If you squint a
little, you'll noticed that the calls to bind look a little like the
traditional expansion of (let ((x e)) b) to ((lambda (x) b) e). Let's build some extra syntax to make it easier to chain lots of
calls to bind together. We'll call it... do*.
(define-syntax do*
(syntax-rules ()
((_ ((x e) rest ...) body)
(bind e (lambda (x) (do* (rest ...) body))))
((_ () body)
body)))
This macro works a little like let*, where it performs a sequence of
computations in order and names each of their results. Using this
macro, our interpreter becomes:
(define value-of/store
(lambda (e env)
(match e
(,x (guard (symbol? x))
(return (lookup x env)))
(,n (guard (number? n))
(return n))
((λ (,x) ,e)
(return (lambda (v)
(value-of/store e (extend-env x v env)))))
((ref ,e)
(lambda (store)
(match ((value-of/store e env) store)
((,v . ,store)
(let ((label (gensym)))
(cons `(ref ,label)
(cons (cons label v) store)))))))
((deref ,e)
(lambda (store)
(match ((value-of/store e env) store)
(((ref ,label) . ,store)
(cons (cdr (assq label store))
store)))))
((update ,e-ref ,e-val)
(lambda (store)
(match ((value-of/store e-ref env) store)
(((ref ,label) . ,store)
(match ((value-of/store e-val env) store)
((,val . ,store)
(cons `(ref ,label)
(cons (cons label val) store))))))))
((,rator ,rand)
(do* ((rator (value-of/store rator env))
(rand (value-of/store rand env)))
(rator rand))))))
Not bad.
We're going to cheat a little for the last few cases. We're doing to
define three new functions, create-ref, get-ref and set-ref,
which do the store manipulation for us. Here they are:
(define (create-ref val)
(lambda (store)
(let ((label (gensym)))
(cons `(ref ,label)
(cons (cons label val) store)))))
(define (get-ref ref)
(lambda (store)
(match ref
((ref ,label)
(cons (cdr (assq label store)) store)))))
(define (set-ref ref val)
(lambda (store)
(match ref
((ref ,label)
(cons ref (cons (cons label val) store))))))
These feel like cheating to me because we got these functions
basically by copying and pasting the body of the ref, deref and
update cases. But, we can think of it as defining a clean interface
to the store, which is just good software engineering. Plus, our
interpreter was actually doing two things in each case. First it had
to evaluate the arguments and then it had to access the store. Using
these helper functions makes that separation clearer.
Using these functions in the interpreter completes our transition over to monads.
(define value-of/store
(lambda (e env)
(match e
(,x (guard (symbol? x))
(return (lookup x env)))
(,n (guard (number? n))
(return n))
((λ (,x) ,e)
(return (lambda (v)
(value-of/store e (extend-env x v env)))))
((ref ,e)
(do* ((val (value-of/store e env)))
(create-ref val)))
((deref ,e)
(do* ((ref (value-of/store e env)))
(get-ref ref)))
((update ,e-ref ,e-val)
(do* ((ref (value-of/store e-ref env))
(val (value-of/store e-val env)))
(set-ref ref val)))
((,rator ,rand)
(do* ((rator (value-of/store rator env))
(rand (value-of/store rand env)))
(rator rand))))))
Our interpreter is now a whole 11 lines shorter than where we started! Granted, we've moved some of the functionality into helper functions, so the total length of the program may be longer. Still, this program seems much better factored to me. The interpreter itself shows how to evaluate different language forms, and things like order of evaluation are very clear. The details of how to manipulate the store-related data structures are all hidden in the monad.
Conclusion🔗
I've found that thinking of deriving monads through a series of program transformations has helped them make a lot more sense to me. In functional programming it's common to simulate stateful things by threading extra arguments around. This quickly gets tedious. Monads help you keep this hidden when you don't care about it and cleanly expose it in cases where you do.
Another benefit of this style of programming that I've found is that
once your program is written in terms of return, bind and do*,
you can modify the monad without having to change the rest of your
program. In rewriting the Harlan type inferencer, there were a few
times I realized I had some more information to thread through the
inferencer. In the old style, I would have had to change many lines of
code to do this. Since the type inferencer was written monadically,
however, I could modify a handful of functions while leaving the bulk
of the code unchanged.