A Lazy Sequence

Monads: redux

The discussion from Welcome to the Machine on Hacker News raised some interesting points. There is one in particular I would like to focus on:

“Personally, I don't see why every language is trying to copy Haskell's monads. A monad is not some deeply important concept, it's just an abstraction that happened to be very useful in the context of Haskell's type system. Without Haskell's type system, it is not quite as useful, and it's possible that other abstractions would be better.” — Jonathan Rockway

There are a few questions in this quote I would like to consider:

There is one question I would not like to consider: “Can monads exist in a dynamically typed language?”. This argument was thrashed in the above discussion thread.

Firstly then, why copy monads? There has been a lot of buzz about them as Haskell has become more popular. Underneath all the hype and confusion surrounding the concept is a simple concept: Function composition of which monads are a particular form with a set of laws. Haskell's syntax and type system is particularly well suited to using monads to express abstraction.

New ideas spread through computing by cross pollination. If we weren't experimenting with trying to implement another languages interesting features in our own language of choice, the growth and development would be much slower. Some anecdotes (none sourced):

I'm sure everyone could produce many more examples.

Wholesale aggregation of features doesn't really help. We need to evaluate if the concept being experimented with is worth inclusion. As Rockway says above, it is possible that there is a better abstraction that suits Clojure better than monads. This brings us to the second and third questions raised.

Can monads be useful outside of Haskell's type system? In the context of Clojure, I would say that yes they can. Are they necessarily optimal? In a lot of cases no; Clojure provides reference types for managing state and because the language isn't lazy we always have sequenced operations anyway. That is two reasons you might use a monadic construction in Haskell.

Whats left for us is the value of monads for providing abstractions over expression. We could see this with the backtracking and nondeterministic monads from Ghosts in the Machine. One of the key features of Clojure's monads library is the Monad Comprehension form known as domonad. It allows us to implement these useful forms without having to step straight to writing macros. The downside is the need to be explicit about the monad we are using, and the onus on the user to understand what is going on.

In the last post I claimed that using monads to construct a parser combinator was an interesting and expressive model. What I want to look at now is what that monad provides for us, and what other features of Clojure could be brought to bear against this problem. Now for a caveat; I am still a novice with Clojure, so this section will be left open2.

Firstly, the biggest features we get from the parser monad:

How would we reproduce these requirements (tracking state, tracking branch points at the state at the time, a convenient notation, and abstracting users away from the mechanics)?

The first and second points are closely tied together, lets consider the second (the backtracking stack) first. As the parser walks the input stream, it is going to have to keep modifying the top most element on the stack. Each time we encounter a choice, we need to create a new top of stack to remember the old choice and provide a way to continue from where we left off with the old value and state of the input.

We need a mechanism to maintain this stack and allow the primitives to mutate it. Clojure's provides 4 core reference types to maintain state: Vars, Refs, Agents, Atoms. The later three are specifically concerned with concurrent activity. Vars are intended to allow per-thread local rebinding. This sounds most like what we want. We can use a binding form inside run-parser to create a nested binding, and then our primitive parsing operations can use set! to update the state. The use of binding also means we can safely call a second (completely distinct) parser inside the first without fear of it destroying our backtrack stack. This is similar to using a thread local variable in another language.

That covers points one and most of two, but at the cost of loosing our pure-functional expression. We have however gained primitives that do not need to expose a monadic interface. From a complexity perspective this appears to be a mixed bag.

So we can now manage the state of the parser stack, but we don't have a mechanism to signal failure. The most obvious choice here would be to throw an exception. Some developers are not keen to use exceptions to manage flow control, but I cannot think of a replacement.

Parser comprehensions? well, we can now just use straight functions and let forms. We don't have a guard notation any longer, but we can plug that gap with a 'fail' primitive, potentially passing additional information into it. If we need a more sophisticated form, we could always write a macro on top of these building blocks.

Lastly, we should still be able to write parser combinators in terms of a small set of abstractions, so both approaches appear to are equal on this count.

This brings us to the last question raised at the start; are monads the most appropriate tool for job in Clojure? This is hard to answer, because monads are such an abstract concept. As I noted above, a number of the reasons you would use monads in Haskell are redundant in Clojure, however, there are still situations that could warrant their usage. Indeed, the parser combinators case we examined is a mixed bag for both solutions.

Using monads lets us have a pure functional solution, at the cost of some transparency, especially for developers less experienced in monadic logic, while a ref type based approach uses some inelegant tactics to reproduce the system at the cost of pure-functionality.

So, monads do have a place, but that place is more restricted in Clojure than in Haskell. You could comfortably get by without knowing about them, but there are situations where they will help. This sort of experimentation is a vital part of the growth of languages, and of developers individual skills.

See Also:

  1. I read this story very recently but can no longer find the source. If somebody knows what it is I will update this to point to it. In the mean time, treat it as highly apocryphal.
  2. More experienced opinions and alternatives are greatly valued here.
15 February 2010