Monads and Fauxnads : Part 1

⃪ series back --- Parenthetical Curios --- series forward →

Indefinite Scope + Dynamic Extent = Parametric Context

In a previous post I made the disturbingly Fermat-like remark that "you can mostly simulate certain Monads, including State and Reader, with special variables in Common Lisp."

So, in order to spare generations of Lispers the burden of demonstration, I will, for posterity, present the punchline of that remark.

In the followup post, I present a novel approach to a more thoroughgoing simulation of Monads in Common Lisp, one that utilizes a dynamic-flet macro.

As ever, this installment of Parenthetical Curios contains next to nothing of practical value.

Sneaking Monads Into Your Repertoire

I should start with a pretty severe disclaimer: I am not, with any generality, going to tell you what Monads are. Offering a "plain English" explanation, or even a clever a metaphor, probably wont do any good anyway. Not to worry, you don't need to be told what Monads are in order to understand them. In fact, the chances are fair that (assuming you program computers) you have already discovered Monads yourself.

In any case, there is a good way learn to recognize Monads without being told what they are: you can see what they do. The first part of this post will not so much explain Monads as demonstrate a couple of them: Reader and State.

Setting The Compass

Let's revisit the comment that prompted this post. The claim is as follows.

[Y]ou can mostly simulate certain Monads, including Reader and State, with special variables in Common Lisp.

Now, readers whose experience includes both Haskell and Common Lisp might already understand what I was trying to say. But for anybody else, and especially for those incensed by my cavalier remark, I must advise the reader that a whole lot hinges on the word mostly. In fact, a better term might have been sort of. Okay, time to dig in.

The Absolute Minimal Punchline

If my prompting comment was a joke, here is the punchline:

     CL-USER> (defvar *env*)  
     *ENV*  
      
     CL-USER> (defun type-of-env ()  
                (type-of *env*))  
     TYPE-OF-ENV  
      
     CL-USER> (type-of-env )     ;; can't call this unless *env* is bound  
     ; Evaluation aborted on #<UNBOUND-VARIABLE *ENV* {1009A85A33}>.  
      
     CL-USER> (let ((*env* 10))  
                (type-of-env ))  
     (INTEGER 0 4611686018427387903)  
      
     CL-USER> (type-of-env )    ;; after let exits, *env* is unbound again  
     ; Evaluation aborted on #<UNBOUND-VARIABLE *ENV* {1009915843}>.  
     CL-USER>

The above is, from a hand-wavy and conceptually muddy point-of-view, an example of a Reader Monad. If waving your hands in the mud makes you dizzy, don't worry. The steady ground of rigor will follow, eventually. For now, just try to understand what the above code does.

The idea is this: You have some computation to do, in this case the function called type-of-env. This computation does not act alone! It happens inside a "context", here it's a variable called *env*. Crucially, the context is not explicitly passed to the computation as an argument. Even so, the computation can make use of that context to produce its output.

So, sorry for the let down, but that's really all I was referring to with my talk of "simulating" the "Reader Monad".

One observation to note about the above example: type-of-env might be thought of as being purely functional modulo context. That is, given the same value of *env*, the computation will always produce the same result. This thought gives us a clue as to the characteristics of Monads.

Interestingly, the Haskell programming language, where Monads play an especially important role, happens also to be purely functional. I.e. there's no mutation is allowed in Haskell, except, that is, inside a special Monad.

So, if you apply a bit of from-the-hip induction, you might surmise something about the nature of Monads: at least some of the time, Monads let purely functional code do things like access "global state".

It's a good first guess, but needs refinement and extension. Onward!

Healthy Skepticism

So at this point you might be thinking "Uhhh ok. So it's just an ordinary global variable? Aren't GLOBAL VARIABLES BAD? Monads are just functions using global variables!? I'm confused. Colin, you're doing a bad job."

Hey! Ease up! I'm doing my best. Let's take your concerns one at a time.

First, although *env* is a global variable, it is no ordinary a global variable. Actually, it's a dynamic variable. More on that momentarily.

Second, I can't disagree with you that global variables are usually bad. As I mentioned, *env* is a dynamic variable, and dynamic variables have some interesting properties that set them apart from run-of-the-mill globals - properties that make them, some of the time, less bad.

Finally, about "functions using global variables", the answer is emphatically "NO, that is definitely not, in any way, even close to what Monads are."

I can see, at this point, that your mind is looking for an answer to the question of what Monads are. Let me remind you that, at the start of this post, I abnegated my responsibility for such definitional concerns.

If you're looking for somewhere solid to stand, it might fair to say that, so far, you have simulated exactly one instance of one kind of Monad (the Reader), which behaves as if it had access to some read-only global state. You got here by taking advantage of the special powers available to dynamic variables.

One Big Aside On Dynamic Variables

(Skip this if you care to.)

Dynamic variables are so-called because their bindings have indefinite scope and (wait for it ...) dynamic extent. What follows is a primer on what these terms mean.
An entity has indefinite scope when it can be referred to anywhere in the code. Scope, generally speaking, is about where a variable is allowed to be written down in some code. In the above, the *env* variable appeared inside a function of zero arguments and you did not need to pass it in as a parameter first. Standard global variables also have indefinite scope.
Entities with dynamic extent can only be referenced in a period of runtime between the "establishment" and "disestablishment" of the entity. That is, extent is about the "lifetime" of some data. In the example, the bindings of *env* only "lived" as long as the code inside the let form was running. Once a let block exited, the current binding of *env* "disestablished".
Normally a global becomes a nuisance when more and more code in an application relies on it . When this happens, testing becomes difficult and, consequently, the application as a whole more fragile. Think about it, with a global you have this single junction in your program where some function called in one module can effect the behavior of some other function called in a totally different place, perhaps a place you've never personally seen.
Dynamic variables are different, and allow you to run functions in a totally different contexts without worrying about how they affect other functions that might literally refer to the same "global" variable. Each time a dynamic variable is bound with a let expression, it creates its own private world that wont effect any other computations relying on the same variables unless they're also being called in the same "private world". To make this concrete consider this example with nested lets:

     CL-USER> (let ((*env* 10))  
                (format t "*ENV* is ~s which has type ~a~%"  
                        *env*  
                        (type-of-env))  
                (let ((*env* "hello"))  
                  (format t "But now it's ~s and has type ~a~%"  
                          *env*  
                          (type-of-env)))  
                (format t "Back to being ~s which has type ~a~%"  
                        *env*  
                        (type-of-env)))  
     *ENV* is 10 which has type (INTEGER 0 4611686018427387903)  
     But now it's "hello" and has type (SIMPLE-ARRAY CHARACTER (5))  
     Back to being 10 which has type (INTEGER 0 4611686018427387903)

Keeping The Joke Going: Mutation

Briefly, here is how you might adapt the above to enable your "Monadic computations" to both read AND write state (gasp!).

     CL-USER> (defvar *state*)  
     *STATE*  
     CL-USER> (defun get-state () *state*)  
     GET-STATE  
     CL-USER> (defun set-state (new)  
                (assert (boundp '*state*)) ;; only run set-state if bound  
                (setf *state* new))  
     SET-STATE  
     CL-USER> (defun add-to-state (&rest numbers)  
                (dolist (n numbers (get-state))  
                  (set-state (+ n (get-state)))))  
     ADD-TO-STATE  
     CL-USER> (add-to-state)   ;; must call inside a binding of *state*  
     ; Evaluation aborted on #<UNBOUND-VARIABLE *STATE* {1004BCD8E3}>.  
      
     CL-USER> (let ((*state* 0))  
                (add-to-state 1 2 3))  
     6  
     CL-USER> (let ((*state* 0))  
                (add-to-state 1 2 3)  
                (let ((*state* 100))  
                  (add-to-state 1 2 3 4)  
                  (print (list :inner-state (get-state))))  
                (print (list :outer-state (get-state)))  
                :done)  
      
     (:INNER-STATE 110)  
     (:OUTER-STATE 6)  
     :DONE

This, it turns out, is pretty close to what you can do with the State Monad.

Here you can see the now familiar ideas at work. First, you have this special dynamic variable, *state*, that you control access to through an interface. This time the interface consists of two functions: one to get the "context" and one to update it.

Using that interface you can run some computations that only make sense inside the "Monadic context". Also, just like the first example, rebinding the dynamic variable makes a whole new "context" that doesn't interact with the outside context, even in the presence of mutations to the state.

Likewise, these computations that refer to the *state* through its interface are referentially transparent modulo the context. The example above doesn't qualify as purely functional because it calls print, which has the side effect of printing some data to a stream. Even so, given same context, the computations produce the same output from the same inputs.

Unkept Promises

So far you have seen how dynamic variables enable you to define computations (functions) that evaluate in a parametric context. Hence the tag line of this post:

Indefinite Scope + Dynamic Extent = Parametric Context

Using parametric contexts, you were able to simulate the behavior of two Monads, the Reader and the State. If you had to guess about what makes some comptuation "Monadic", based on what you've seen here, you could say that it has something to do with these contextual computations. This guess is, it turns out, a good way to think about Monads some of the time.

This post was way too long for the basicness of its content. In Part 2 I make good on my promise to offer some rigor. The theme of "Dyanmic Variables" is revisted, this time in the context of functions, where dynamically rebindable function names are used define to honest-to-goodness Monads. It is a strange approach, but sort of cool.

Cheers.