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:

  • Why are programmers everywhere getting excited about monads, and trying to reimplement them in their language(s) of choice?
  • Can monads be useful outside the context of Haskell's type system?
  • Are monads the most appropriate concept in Clojure for what we have been examining?

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):

  • Python took list comprehensions straight out of Haskell, but did so without specifically monadic underpinnings. Since then generator comprehensions and dictionary comprehensions have been added to the language and are important tools in the Python programmers toolbox.
  • Microsoft introduced LINQ into .Net; This is particularly relevant as it is a transplanting of monads with new syntax support. LINQ to databases is the least interesting application. LINQ to objects is a sequence monad and provides a rich comprehensions notation, and Rx is roughly the continuation monad and is intended to facilitate reactive programming.
  • Lexical closures - bread and butter for functional programming, and now central to most modern programming languages - came about via cross pollination from Algol 60 (and Pascal?) to Lisp. When this was transported to Lisp it was discovered to be immensely powerful. Emacs Lisp is now the only remaining lisp that does not support them.1

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:

  • The state of the input stream (the remainder) flows naturally through the parsers. It is also pure-functional; there is no mutable state. This is a big benefit for testing and understanding.
  • Backtracking is provided for us with no extra mechanical considerations: The call stack holds our states for us, and because its pure-functional theres no concern about a parser having messed with the stack.
  • We have parser comprehension syntax complete with guards.
  • Once we have written our primitive parsers of choice (in my case that was just get-one,eof, and 'choice') we never had to deal with the underlying abstraction again.

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