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:
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 a
m >>= return = m
m >>= (\x -> k x >>= h) = (m >>= k) >>= h
Got it? Great! Now you know what Monads are! Done! Go Home!
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
>>= 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 type
aand yields a concrete type
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
(foo), for any value of
foo. Some languages call it
Option, and it is used to represent the result of a computation that may have failed.
In what follows you define
bind for such a
;; 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
ret, you were able to run a simple "monadic" computation. How might the same be done for the
State Monads that were obliquely discussed in Part 1?
As written, the
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.
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
(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
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 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.
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.
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
;;; 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))))
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.
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.