Monads and Fauxnads : Part 2
Indefinite Scope + Dynamic Extent = Parametric Context
Diving deeper into the murky waters of Monads in Common Lisp. While Part 1 spent 1800 words beating around a rather large bush, Part 2 actually defines Monads with some rigor.
The rest of the post explores a syntactic extension for a toy Monad implementation in Common Lisp. The approach taken here utilizes dynamic rebinding of functions, some lazy evaluation, and a Haskell-esque "do" operator, and result is a bit weird.
The Cart Before The Horse
This post hacks and thrashes its way to a toy implementation of Monads in Common Lisp. By the end, you'll be making sense of programs that look like this:
> (defvar add-1
(fauxdo
(:<- current-state take)
(put (1+ current-state))))
ADD-1
> (run-state
0 ; starting state
(fauxdo
add-1
add-1
add-1))
NIL ; return value
3 ; ending state
For the intrepid reader, here is the full code listing.
Monads, Formally Speaking
The Typclassopecdia contains a somewhat austere typeclass definition, which I abridge slightly here:
(Haskell Warning)
class Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b Furthermore, the following "Monad laws" must also be respected:
return a >>= k = k am >>= return = mm >>= (\x -> k x >>= h) = (m >>= k) >>= h
Got it? Great! Now you know what Monads are! Done! Go Home!
But Seriously
What does any of that mean? Briefly, the above defines a type class -- a big set of types, all of which support a particular interface.
What it says is that a type constructor m is a Monad when the functions return and >>= are available.
The first function, return, takes a value of any type whatsoever and returns an instance of the "monadic" type. You can think of it as "injecting" a value into a monadic context.
The second function (>>=), which is sometimes called bind is a little more interesting. It is a higher-order function that combines members of a Monad to produce another such member.
Aside: A type constructor is a bit like a "type level function" - it takes a type and returns a type. In the Monad definition,
mis a type constructor that takes a variable typeaand yields a concrete typem a.
An Example With a Minimum of Moving Parts
A standard introductory example of a Monad would be a list with either zero or one member. That is, either NIL or (foo), for any value of foo. Some languages call it Maybe or Option, and it is used to represent the result of a computation that may have failed.
In what follows you define return and bind for such a Maybe Monad.
;; calling it 'ret' b/c of name conflicts
(defun ret (x)
"monadic return for a Maybe Monad.
Just wraps its argument in a list."
(list x))
(defun bind (mx x->my)
"monadic bind for a Maybe Monad.
If its first argument isn't NIL,
then it is a list with one element.
Apply the second argument to that element."
(when mx
(funcall x->my (car mx)))) Here are two examples of doing a "monadic" computation in your makeshift Maybe Monad.
> (bind (ret 10)
(lambda (x) (ret (+ x 20))))
(30)
> (bind nil
(lambda (x) (ret (+ x 20))))
NIL On the first run, you inject 10 into the Monad with (ret 10) and supply that as the first argument of bind. The second argument is a lambda that takes a number and returns that number plus 20 back into the monadic context. Notice that you get (30) as the output. That is, the number 30 inside the monadic context.
In the second case, you run the same thing except instead of a number, you pass NIL as the first argument. Predictably NIL is the result. In that way, the Maybe Monad is used to represent computations that can fail, and whose failure propagates through the rest of the computation.
The Remaining Task
Ok, so what remains to be done?
Looking back, you see that by defining bind and ret, you were able to run a simple "monadic" computation. How might the same be done for the Reader and State Monads that were obliquely discussed in Part 1?
As written, the bind and ret functions only work for one kind of Monad. Should they perhaps be turned into generic functions? Probably, but that's not what you're gonna to do!
Instead, you're going to slide down weirder path, a path that revisits the theme of dynamic variables from Part 1. This time, rather than providing contextual bindings for some "global" state, you will dynamically rebind those two Monad functions for each monadic context.
Fauxnads With DYNAMIC-FLET
DYNAMIC-FLET is a poorly conceived experimental macro for treating function definitions made with defun as special in the way that variables declared with defvar are. Check out this post for more.
To use dynamic-flet, you need functions to rebind. First, you define top-level "dummy" versions of the two Monad functions:
;; bind :: m a -> (a -> m b) -> m b
(defun bind (ma a->mb) (error "BIND Not Called In A monadic Context."))
;; ret :: a -> m a
(defun ret (a) (error "RET Not Called In A monadic Context.")) Next, you can re-implement the Maybe Monad using dynamic-flet:
(defun run-maybe (program)
(dynamic-flet
(ret (a) (list a))
(dynamic-flet
(bind (maybe-a a->maybe-b)
(when maybe-a
(funcall a->maybe-b (first maybe-a))))
(force (force program))))) ;; awkward
And this is how you'd use it:
(run-maybe
(lazy
(bind (ret 10)
(lambda (x) (ret (+ 20 x))))))
(30) How does this work? First run-maybe creates temporary bindings of the two Monad interface functions. The argument to run-maybe is a program, in this case a thunk, one that evaluates to an object of your maybe type.
You need to wrap the bind call in a lazy because, as the argument to run-maybe evaluates, bind and ret have not yet been defined. See the code listing for the implementation of lazy used here.
So far, this isn't much of a gain is it? I mean, its pretty awkward to have to use bind that way. You can fix that.
The Fauxdo Macro
Haskell includes special syntax for working with Monads, called do. (No relation to the CL do). The do syntax is mostly used to elide the >>= operator, and often results in more legible code. It looks like this:
do x <- foo1
y <- foo2
z <- foo3
return (g x y z) Which, after translating into the Lisp syntax from above, is shorthand for this unpleasant construct:
(bind foo1
(lambda (x)
(bind foo2
(lambda (y)
(bind foo3
(lambda (z)
(ret (g x y z)))))))) You see that do introduces a block and <- binds the "output" of monadic computations to a value that can be used again later on.
The fauxdo macro accomplishes the same thing, but it would be a little tedious to reproduce it here. Again, you can study its definition in the code listing.
Using fauxdo the example with Maybe becomes:
> (run-maybe
(fauxdo
(:<- x (ret 10))
(ret (+ x 20))))
(30)
And just for kicks, here's a plausibly more justified example. In this example you a define computation that can fail: you get an element from a sequence by its index, and you fail if the index is greater than the length of the sequence.
> (defun maybe-elt (n seq)
"If it exists, get the nth member
of the sequence SEQ. Fail otherwise."
(when (< n (length seq))
(ret (elt seq n))))
> (let ((xs (list 1 2 3 4 5 6)))
(run-maybe
(fauxdo
(:<- x (maybe-elt 4 xs)) ; succeeds
(ret (+ x 100)))))
(105)
> (let ((xs (list 1 2 3 4 5 6)))
(run-maybe
(fauxdo
(:<- x (maybe-elt 200 xs)) ; fails, 200 is too big
(ret (+ x 100)))))
NIL
The Return of State
To conclude Part 2, you will revisit the State Monad using the dynamic-flet approach. In Part 1, two functions were defined to get and set the state inside that fakey State Monad. Here you do the same, calling the two operations take and put.
;;; State Monad ;;;
;; take :: m s == State s s == s -> (s, s)
(defvar take
"Get the current state"
(lambda (state) (values state state)))
;; put :: s -> m () == s -> State s () == s -> (s -> ((), s))
(defun put (new-state)
"Update the state with a new value, returning nothing."
(lambda (state)
(declare (ignore state))
(values nil new-state))) Before defining the run-state context function, you can see that the state Monad is here represented as a computation that returns two values. The first value is thought of as the "output" of the computation, and the second value is the "state" that is carried along throughout the computation.
(defun run-state (init-state program)
"Run the PROGRAM with initial state INIT-STATE"
(dynamic-flet
(ret (a) (lambda (state) (values a state)))
(dynamic-flet
(bind (state-a a->state-b)
(lambda (state)
(multiple-value-bind
(result new-state) (funcall state-a state)
(funcall (funcall a->state-b result) new-state))))
(funcall (force (force program)) init-state)))) The ret function simply "injects" its argument into the "stateful world" of the State monad. That is, it produces a computation that returns its argument, leaving the state untouched.
The bind function evaluates its first argument (a stateful computation with an a as output) with the provided state, and passes the output value, along with the new state, to the second argument.
Given the above, you can run the example at the start of this post.
Why These "Monads" Are Just A Toy
One thing that makes Monads useful in a purely functional world like Haskell is that they can be embedded into one another, mapped over, and transformed. For example, you can use a Monad Transformer to combine the State and Maybe Monads together, allowing for computations that are both stateful and support failure propagation.
Mapping might actually be sort of easy to do , but it's hard to see how you might cleanly combine these "fauxnads" with one another. Perhaps this is an exercise left to the reader ;)
Hope you enjoyed yet another frivolous installment of Parenthetical Curios.
-colin
subscribe