# 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 a`

`m >>= return = m`

`m >>= (\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,

`m`

is a type constructor that takes a variable type`a`

and yields a concrete type`m 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