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.¹

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 open².

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:

• Some brief discussion on the relevance of Monads to Clojure — You’ll need to dig around a bit there sorry.

Footnotes

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.

Ghosts in the Machine

This is the second (and final) part of my examination of the State monad and its variations. If you are unfamiliar with the basic concepts surrounding the State monad, you may wish to read the first part before continuing.

Backtracking State

One of the features of the State monad worth looking at is how it implements a simple interpreter. Our current interpreter lets us write any sort of procedural code we needed, though it might get rather unwieldy (only one register and one memory location). While interesting, its not especially useful.

Recall my claim that State is the basis of more interesting monads. We are going to look at a modification to the code from state-m that lets us backtrack if the computation fails to the last choice point.

The paragraph above introduces the three new features we need to provide:

• A way to define choice points
• A way to define computation failure
• A mechanism to handle backtracking.

The two former points happily coincide with the interface for monad plus monads. Specifically the function m-zero will represent our failure mode, and m-plus will represent choice points. The last case (backtracking) will be implemented in m-bind and m-plus.

Before we go any further, here is an implementation I have cooked up based on the previously defined state-m1 monad.

(use 'clojure.contrib.monads)

(defmonad backtrack-state
    [m-result (fn [value]
                  (fn [state]
                      [value state]))

     m-bind (fn [computation func]
                (fn [state]
                    (when-let [[value new-state] (computation state)]
                              ((func value) new-state))))

     m-zero (fn [new-state] nil)

     m-plus (fn [left right]
                (fn [state] 
                    (if-let [result (left state)] 
                            result 
                            (right state))))])

Note that m-plus is a function that returns a function with the same type as m-bind and m-result. However, m-zero is strictly a value, which happens to be a function that always returns nil.

m-zero is our first hint at how this backtrack-state is constructed. A failure is nil, a successful computation returns the familiar [value state] pair from the regular state-m.

A small change has been made to m-bind. In particular, where state-m1 would just use a let to destructure the result of (computation state), backtrack-state uses when-let. This form fuses when and let so that when the lets binding-form’s source is also the test for when. If the test returns a truthy value (in our case not nil) then the body of the form is evaluated and returned. Otherwise nil is returned.

An alternative formulation is presented here for clarity

(when (computation state) 
    (let [[value new-state] (computation state)]
         ((func value) new-state)))

This means that if ‘computation’ fails the result will be failure without having to evaluate ‘func’.

The remaining logic is in m-plus. This function takes two arguments, both potential computations to perform, and returns a state consuming function. if-let is a cousin to when-let, and provides a failure branch rather than just returning nil.

Lastly, the implementations of get-state and put-state are identical to the versions from state-m1

To illustrate the expressive power of this new monad we have written, we are going to look at a small library built on top of it. There are two parts to this, first is a basic set of parser tools, and then there is the specific parser we are going to write. At the end we will have a little parser that will take a string representing a number and return a pair of either :int or :float depending if there is a decimal component. If anything else is found, it will fail returning only nil. So, the parser library:

(with-monad backtrack-state
    (defn run-parser
        "run-parser takes a top level parser and a string or seq'able
         to run the parser on"
        [parser input]
        (parser (lazy-seq input)))

    ;; primatives
    (defn get-one []
        "Gets the next item from the input and returns it"
        (domonad [input (get-state)
                  _ (put-state (rest input))]
            (first input)))

    (def eof
        (domonad [remaining (get-state)
                  :when (= (count remaining) 0)]
            nil))

    ;; simple parsers
    ;;
    ;; These parser's are built on top of the primatives above
    (defn one-satisfying [p]
        "This is the most basic matching parser. It tests the next
         item in the sequence against the predicate provided. If 
         true, then it is returned, otherwise fails."
        (domonad [one (get-one)
                  :when (p one)]
              one))

    (defn one-of [any-of]
        "Matches any one item in the provided collection or string"
        (one-satisfying (set any-of)))

    (defn not-one-of [none-of]
        "Matches any one item not in the provided collection or string"
        (let [none-of (set none-of)]
        (one-satisfying #(not (none-of %)))))

    ;; combinators    
    ;;
    ;; These parsers combine other parsers into new parsers
    (defn choice [& parsers]
        "Choice takes one or more parsers (in order) and returns a new 
         parser that tries each one in turn until one matches. If 
         all fail, then choice fails"
        (reduce m-plus parsers))

    (defn many [p]
        "Many matches the same parser 0 or more times until it it fails, 
         then it returns a sequence of the match results"
        (choice (domonad [r p
                          rs (many p)]
                      (cons r rs))
                 (m-result '())))

    (defn many1 [p]
        "Many1 is like many, but must match at least 1 item"
        (domonad [r p
                  rs (many p)]
            (cons r rs)))

    (defn optional 
        "This parser matches 0 or 1 of some parser. Optionally may take
         a default result"
        ([p] (optional p nil))
        ([p default] (choice p (m-result default)))))

If you have never used a parser combinator library before, this might seem a bit strange. Possibly the most surprising thing initially is that there is no lexical analysis step. Next, you have infinite lookahead. If parsing fails, we just fail back too the last m-plus point. Lastly, we build parsers by combining simpler parsers programmatically. The toolkit provides the simplest parsers and the basic parser combinators (parsers that are built by combining other parsers).

To put two parsers into sequence, we can just use m-bind. This means we can leverage monad comprehensions (i.e. the domonad form) to specify that one parser.

Looking at the functions in this little library you could come to the conclusion that its effectively a regular expression engine written verbosely. Certainly we have all the same primitives (one-of, many, many1, optional). The difference is that we have the full power of the host language (in this case Clojure) to call one. We’ll come back to this later with a small hypothetical parser.

This library also has one very nice feature: it is completely data agnostic, nowhere in it does it care if its processing a string of characters, a vector of ints or anything else. As long as it can be converted into a sequence, and the items in that sequence are comparable it’s good.

One last note about this particular implementation. Besides being tied to our backtracking-state monad it also suffers from a very flawed implementation of many. In particular, our implementation is elegant but relies on recursion. Remember that domonad will transform our code into a heavily nested set of function calls, and you can see that this fundamental combinator would quickly cause our whole parser to blow stack.

So with this basic set of tools in hand, lets look at the specific parser implementation:

(with-monad backtrack-state
    (def parse-digit (one-of "0123456789"))
    (def parse-digits (many1 parse-digit))
    (def parse-sign (one-of "+-"))
    (def parse-dot (one-of "."))

    (def parse-integer 
        (domonad [digits parse-digits]
            [:int digits]))

    (def parse-float
        (domonad [whole-digits parse-digits
                  _ parse-dot
                  decimal-digits parse-digits]
            [:float (concat whole-digits "." decimal-digits)]))

    (def parse-number 
        (domonad [sign (optional parse-sign "+")
                  [type digits] (choice (domonad [int parse-integer
                                                  _ eof]
                                              int) 
                                        (domonad [float parse-float
                                                  _ eof]
                                            float))]
             [type (apply str (cons sign digits))])))

This parser is very simple. It only has 2 backtracking points; the optional for parse-sign and the choice for digits. Both of these backtracking points only use m-plus indirectly, and you might have noticed that get-state and put-state are never needed outside the primitive get-one.

To run this parser, we’ll pass it and an input into run-parser:

(map #(run-parser parse-number %) ["123" 
                                   "" 
                                   "123.123" 
                                   "0" 
                                   "0.0"
                                   "-1"
                                   "1 2"])
;; => ([[:int "+123"] ()] nil [[:float "+123.123"] ()] [[:int "+0"] ()] [[:float "+0.0"] ()] [[:int "-1"] ()] nil)

You can see that each string we have parsed has returned a pair or nil. nil indicates a failure (no match), the pair is the complete parsed result containing the result of the parser and the remaining tokens to parse. Because we specified an eof in our parse-number parser we never have any remaining input.

Just as an illustration of how this style of parser is so expressive, here is a hypothetical that parses an xml element:

(with-monad backtracking-state
    (defn open-tag []
        (domonad [_ (one-of "<")
                  name (elem-name) 
                  attrs (attributes)
                  _ (one-of ">")]
            [name attrs]))

    (defn xml-element 
        []
        (domonad 
            [[name attrs] (open-tag)
             children (many xml-node)
             _ (close-tag name)]
            [:element name attrs children])))

Obviously, this is a very simplified ideal of xml, but you can see how leveraging the host language allows us to provide recursive parsers (xml-node will eventually try xml-element again), and pass information through (e.g. name from open-tag is passed to close-tag).

Nondeterministic State

After backtrack-state the step to nondeterministic-state is very small. Conceptually, we want to evaluate the computation for ever possible choice we encounter. Once again we will use monad plus to define choice points and failure. Unlike backtrack-state we will need to change the type of data returned by the state machine from a single value (a pair or nil) to a collection of value-state pairs.

The choice of collection proves interesting. There are two obvious candidates: vector and set. The difference is small but significant. A vector will result in every result including any duplicates. This will be useful if you are searching for the total possible solutions. However if you only care for every unique result then the set makes more sense as it will reduce the total computation in the case of repetition. We will come back to this decision in the last section (Transformations).

Heres the code for a set based nondetermistic-state monad.

(use 'clojure.contrib.monads)
(use 'clojure.set)

(defmonad nondeterministic-state
    [m-result (fn [value]
                  (fn [state]
                      #{[value state]}))

     m-bind (fn [computation func]
                (fn [state]
                    (let [results (computation state)
                          result-sets (map (fn [[value new-state]] 
                                                ((func value) new-state))
                                            results)]
                        (apply union result-sets))))

     m-zero (fn [new-state] #{})

     m-plus (fn [left right]
                (fn [state] 
                    (union (left state) (right state))))])

(defn nd-get-state 
    [] 
    (fn [state] #{[state state]}))

(defn nd-put-state 
    [state] 
    (fn [_] #{[nil state]}))

The changes here are all fairly straight forward. Places we added logic for backtracking now find the union of sets, and m-zero returns a empty set rather than nil. The final change is that we have to use a new version of get-state and put-state that handles the set wrapper.

A simple example of this monad in action is the quadratic formula; square root fails for negative numbers, and returns both positive and negative values for any positive number. The follow implementation is a little rough but demonstrates the concept:

(defn sqrt [v]
    (with-monad nondeterministic-state
       (if (> v 0) 
           (m-plus (m-result (Math/sqrt v)) (m-result (* -1 (Math/sqrt v))))
           m-zero)))

(defn quadratic 
    [a b c]
    ((domonad nondeterministic-state
        [roots (sqrt (- (* b b) (* 4 a c)))]
        (/ (+ (- b) roots) (* 2 a))) nil))

Here it is in action with some sample inputs:

(quadratic 1 20 4)
; => #{[-0.20204102886728847 nil] [-19.79795897113271 nil]}
(quadratic 1 2 4)
; => #{}

Transformations

We have looked at three variations of the State concept. Recall that I mentioned there is a relationship between the simple monads: Identity, Maybe and Set. The type signatures for the Haskell equivalents make this particularly clear

newtype State s a = State { runState :: (s -> (a,s)) } 

newtype BTState s a = BTState { runBRState :: (s -> Maybe (a,s)) } 

newtype NDState s a = NDState { runNDState :: (s -> [(a,s)]) }
   -- Note the use of list/seq instead of set, but provides similar behaviour

Since we started with state-m1 as our base, it is fairly obvious that this is going to relate to the Identity monad. backtracking-state relates to the Maybe monad, and nondeterminstic-state relates to the Set monad, alternatively it is possible to implement a nondetermistic-state on top of a Sequence / List monad.

This idea that one monad can wrap another is interesting. Without going into too much detail, it is possible to write a function that takes a monad type as its argument (the inner monad), and wraps it up in another monad that has been written in terms of the standard monadic operations.

This idea is know as a monad transformer. The transformer is the function that transforms (or decorates) the inner monad. The Clojure monad library provides a macro for defining transforms called (unsurprisingly) monad-transformer. We can shortcut all the hard work above with a couple of one liners!

(def backtrack-m (state-t maybe-m)) ; you might also see this called parser-m

(def nondeterministic-m (state-t set-m))

You could also choose to use sequence-m in place of set-m for the nondeterministic-m. It is important to realise that the order of the wrapping makes a significant difference with regard to the semantics of the generated Monad.

The specific implementation details of creating a transformer are left to the reader to explore if they are interested. Jim Duey’s second monad’s tutorial covers transformers in more detail. Personally I think this is one area where Clojure’s monad support is superior to Haskell’s as we don’t have to appease such a strict type system. This also makes Haskell based Monad Transformer tutorials a lot more complex.

Wrapping up

We have now looked at three related monads in some detail, seen how they can be used to write some amazingly expressive code, and encountered the tools to make these sorts of operations much easier to wield.

The parser library provided here has an elegant interface but has a very naïve implementation. Recursion will cause problems with the implementation of many, and the astute reader will have noticed that the design causes it to hold onto the head of the input sequence. To convert it from a generic backtracking monad to a specialized parser monad is an interesting project well worth exploring. Another exercise would be implementing a non-determistic monad without a state component.

Finally, a big thanks to Matt and Steven for their help proof reading these posts.

Discuss this post on the Hacker News thread

Welcome to the Machine

Today I’m going to dive into the deep end and take a look at the State monad¹, with an implementation in Clojure. This will be done using Konrad Hinsen’s clojure.contrib.monads API, but I will be providing my own specific monad implementations for continuity. You should use the API versions of any of these monads in the real world however.

The first question to ask is “why use a State monad in Clojure; there is already great support for state management in the language”. My answer is “because the State Monad is the foundation of more interesting monads.” In particular we will be looking at Backtracking State and Nondeterministic State monads. You might use Backtracking to build a parser combinator library². The Nondeterministic state allows you to find all the solutions that fit some problem. A simple example might be an implementation of the Quadratic Formula.

We’ll look at these monads in turn, and then wrap up with a quick high level look at the role Monad Transformers could play, and the relationships between these variations on State and some other monads you may have already encountered: Identity, Maybe and Set.

State

First thing to consider about the state monad is what it is. Ignore the more academic answers to that question, the state monad is a way of building a state machine. It does not hold some state in it, instead it is a series of functions which a state is threaded through. Haskell has a curious looking type for State

newtype State s a = State { runState :: (s -> (a,s)) }

State is a wrapper type that contains a single value. This value is a function from type s to a pair of type a and type s. The curious thing about this definition is it uses the record syntax in Haskell to call the value runState. It does this so that you can unpack the state and apply it to the initial state in one step. Eg:

(runState myStateMachine) initialState  --  parens are for clarity

In Clojure land, we are going to not concern ourselves with a concrete wrapping type. Instead our monad will just return a function. The last thing to think about is what s and a represent. s is the state, and a is the value that that function returns. In our clojure code this will look like a function of one argument (the initial state) that returns a vector of two items: the value and the new state.

Before we go any further, lets have a quick look at the code for this state-m monad. I’ve called it state-m1 to avoid clashing with the state-m in the monad library.

(use 'clojure.contrib.monads)

(defmonad state-m1 
    [m-result (fn [value]
                  (fn [state]
                      [value state]))

     m-bind (fn [computation func]
                (fn [state]
                    (let [[value new-state] (computation state)]
                         ((func value) new-state))))])

While all the interesting behavior happens inside m-bind, m-result is indicative of the nature of the monad. Haskell calls this function return which sufficiently confuses many people, and I like to call it introduce because it introduces a new value into the computation. As is mentioned above, the State is a function from initial state to a value and new state, and as you can see m-result takes a value and returns a function. In this function, the value is constant, and the state is whatever state that gets passed through it.

m-bind provides the guts of the monad. And, because it does a whole lot of function wrangling, it can be a little difficult to wrap your brain around at first. Because this is key to understanding the rest of the monad, and the derivative monads, we will examine this one slowly.

First thing to notice is that like m-result, m-bind returns a new function that takes a state and returns a value-state pair. Second thing is the names of the arguments to m-bind. I have called them computation and func. computation is the existing state-machine and func is the function to use as the next step in the state-machine. In the same way that a linked list is a head and tail, and cons stitches them together, m-bind stitches together func and computation, the big difference is the facing. computation is the many unit, and func is the singular unit³.

Lets look at a very simple (and contrived) example. We’ll look at how you set would write some code to use it, and then have a look at what that transforms into. This is going to introduce a value into the computation, increment it, and return that new value, all the while ignoring the state that the caller has specified.

 (def my-state-machine (domonad state-m1 
      [my-val (m-result 1)
       my-val2 (m-result (inc my-val))]
       my-val2)) 

 (my-state-machine "state") ;; -> [2 "state"]

If this looks like a strange way to write a let form to you, you would be right. We currently have no easy way to deal with the state in our state machine, we can only thread the value through. Before we do that though, lets unwind that expression.

First up is (m-result 1). This creates a function as we can see from the definition of state-m1. Specifically it produces

(fn [state] [1 state])

This becomes our computation for the first bind⁴:

(m-bind (fn [state] [1 state]) 
        (fn [my-val] (m-result (inc my-val))))

Lets do a straight forward reduction here to see what we get. I’ve copied the body of m-bind from above, and where it says computation I’m replacing it with (fn [state] [1 state]) and whenever it says func I’m replacing it with (fn [my-val] (m-result (inc my-val))):

(fn [state]
    (let [[value new-state] ((fn [state] [1 state]) state)]
         (((fn [my-val] (m-result (inc my-val))) value) new-state)))

Lastly we have a bind to get my-val2 out of the big computation. This is once again a fairly straight forward reduction, only with a larger computation.

(fn [state]
    (let [[value new-state] ((fn [state]
                                 (let [[value new-state] ((fn [state] [1 state]) state)]
                                      (((fn [my-val] (m-result (inc my-val))) value) 
                                       new-state))) state)]
         (((fn [my-val2] (m-result my-val2)) value) new-state)))

So thats the basic transformation from the domonad notation. You can see how the various expressions have been stitched into the state-machine. Next we’ll do another set of reductions so you can see how the state is threaded through the stages of the machine. As above the string “state” be passed through.

Reducing the state-machine

Note: If you are comfortable with how this reduces down, skip on to the next section

First the argument to the machine is replaced (see the end of the second last line):

(let [[value new-state] ((fn [state]
                             (let [[value new-state] ((fn [state] [1 state]) state)]
                                  (((fn [my-val] (m-result (inc my-val))) value) 
                                   new-state))) "state")]
     (((fn [my-val2] (m-result my-val2)) value) new-state))

Next that function in can be reduced down. This time the string “state” has moved to the end of the first line.

(let [[value new-state] (let [[value new-state] ((fn [state] [1 state]) "state")]
                            (((fn [my-val] (m-result (inc my-val))) value) new-state))]
     (((fn [my-val2] (m-result my-val2)) value) new-state))

And again. Note that the function producing the pair has been replaced with the specific pair.

(let [[value new-state] (let [[value new-state] [1 "state"]]
                            (((fn [my-val] (m-result (inc my-val))) value) new-state))]
     (((fn [my-val2] (m-result my-val2)) value) new-state))

At this point we can remove the top let, destructuring the pair we just created into value and new-state:

(let [[value new-state] (((fn [my-val] (m-result (inc my-val))) 1) "state")]
     (((fn [my-val2] (m-result my-val2)) value) new-state))

Now we can reduce down function. Recall that this function was introduced by the first m-bind.

(let [[value new-state] (((m-result (inc 1))) "state")]
     (((fn [my-val2] (m-result my-val2)) value) new-state))

This time we can increment 1 and replace the m-result with the result of that function.

(let [[value new-state] ((fn [state] [2 state]) "state")]
     (((fn [my-val2] (m-result my-val2)) value) new-state))

The reduction should be starting to look familiar. “state” will be used to reduce the result of that m-result.

(let [[value new-state] [2 "state"]]
     (((fn [my-val2] (m-result my-val2)) value) new-state)))

Once more destructuring out the let form

(((fn [my-val2] (m-result my-val2)) 2) "state")

Reduce the inter function

((m-result 2) "state")

Expand out m-result

((fn [state] [2 state]) "state")

And finally reduce that down.

[2 "state"]

That looks like a lot of work, but it is actually straight forward. Still, its not very useful if it just provides a complicated version of the let form.

Manipulating the state

The most obvious state managing functions will be two primitives get-state which returns the current value of the state, and put-state which updates the current state⁵. To get handle on whats going on at this stage, I like think of the value as something like a register in the state-machine, and state as the sole memory location.

(defn get-state [] 
    (fn [state] [state state]))

(defn put-state [new-state]
    (fn [_] [nil new-state]))

These functions follow the familiar form indicated by m-result. The return a function that takes an initial state and returns a pair of value and current state.

get-state returns a function that takes the state value and places it in the value ‘register’, and leaves it in the state as well. In contrast, put-state takes a new state as its argument and the returns a function that ignores the current state, obliterates the value ‘register’ and updates the state.

So how would you go about using these two functions? Here is another contrived example that increments the current state, and returns the original value:

((domonad state-m1
    [v (get-state)
     _ (put-state (inc v))]
    v) 1) ;; -> [1 2]

I’ll leave reductions of this to the more eager reader.

Wrapping up

So that’s the basic State monad. It’s likely you won’t use this very often (ever?) in Clojure, but understanding it is very useful.

In the second (and final) part we’ll take a look at a couple of variations on this concept, including looking at some small example programs that make use of them.

Discuss this on the Hacker News thread.

Footnotes

1. If you are unfamiliar with monads I would suggest you look else where. The api documentation provides links to a set of tutorials that are a good resource for Clojure programmers. You might also find my post Functions of functions useful.
2. Parser Combinators are a way of describing a recursive decent parser using combinations of functions. These parsers can trivially have infinite lookahead, and the full expressive power of the host language. The canonical example of this idea is Parsec in Haskell, but the concept has been ported to many languages. In languages other than Haskell, they are often implemented using tricks other than monads, but Parsec is still the most elegant example.
3. This is actually a simplification. In reality it might could be considered closer to two trees being joined as the leaves of a new tree.
4. I am assuming you understand how bind is rewritten into nested function application from its domonad form.
5. Once you are comfortable with how this simplistic implementation works, I would urge you to explore the code in clojure.contrib.monads.clj as it provides a much more sophisticated API, and uses some nice tricks. In contrast I have chosen to implement the canonical get and put.

A couple of lists

From Python to Clojure.

In the last post I talked about factors that have caused myself and others to look around for languages to move on to from Python. I noted that a number of languages that expat pythonistas are looking at are more recent entries in the Functional Programming space. After dabbling in a number of languages over the last two years I have settled on Clojure. This post examines the tradeoffs from my perspective.

When I first came to Python it was around 2002. With a background in Java from university Python provided an appealing language to get things done. As a quick summary:

• The syntax is clean and clear, including strong support for iteration (something that was “in the future” for Java at the time). Generator comprehensions were in the future meta-package at the time I believe.
• Dynamic exploratory development with an excellent REPL is easy.
• Access to foreign code from C-land has always been good¹.
• Great built in collections and literal support for the core ones. Lists, dictionaries, tuples, sets are all out of the box.
• Simple and expressive Object Orientation.
• Great range of libraries. Some particular worthy ones include Twisted, Django, WSGI, SciPy.
• Comprehensive namespace and packaging tools.
• Cross platform.

The big obvious tradeoff was speed but, as has been noted many times by many people, this isn’t a huge impediment for a large class of programs. Not so obvious is the GIL and the problems it brings to multi-threaded programs but I don’t want to go into that debate here.

Another problem that comes to the surface after extended use is packaging third party library code. Tools like virtualenv and pip etc have helped a lot in recent years, but its certainly not Python’s strength.

I’ve had the chance to work on some really cool projects with Python. I built a skinnable, scriptable media player with webservice integration for my internship, extracted a nice little parser combinator library from this site with some friends, I worked on a Django based financial application full time and a many more small projects.

Any language I move to has to feel as expressive as the experience I get with Python (sans learning curve difficulty). This brings us to Clojure.

I’ve been following Clojure since mid 2008, dabbling in it and writing little toy applications. The functional style has been appealing to me more and more. So what features does Clojure bring to the table for me?

• It is a lisp, so the syntax is nearly nonexistant. However, it has more literals for data and these are used in the special forms. Clojure has (to a new-lisper) much nicer special forms, the obvious example is let compared to Common Lisp².
• Namespaces and modules support is solid. The differing rules for Clojure imports and Java imports tripped me up at first, but makes sense.
• Dynamic exploratory development with the REPL. The REPL is a bit more raw than Python’s but is improving dramatically.
• As mentioned above, there is a good set of literals for data. The built in data-structures are really good. Lists, vectors, maps (dictionaries), sorted maps, sets, sorted sets. This is an area Clojure really shines; not only are there all the basic collections I want, they are super fast and persistent (immutable), which sets things up well for concurrent operations.
• Functional Programming is front and center, but supports mutability and state clearly.
• Support for Java and Objects is solid. The inter-op / foreign function interface to Java-land is a core feature of Clojure.
• “Clojure has objects but isn’t oriented around them.” — Chris Houser.
• Cross Platform
• Builds on Java’s code distribution tools like jar files, and Maven repos with Leiningen.
• Fast. Type hints allow you to avoid reflection in many cases, and it compiles to the JVM.

One obvious lack for Clojure is (native) libraries that are as comprehensive as some of the ones for Python. There isn’t a web framework that competes with Django in terms of feature set and breadth for example. The language is very young (just over 2 years) and it is developing rapidly, but you might still find yourself building (or wrapping java) what you could have got from the toolbox in Python.

Secondly, if Object Orientation is key to how you design code, you will be out of luck. Same goes for JVM: If you have no love for the JVM platform, Clojure won’t be the right choice for you.

There is a lot of overlap between the two lists. Neither list covers all the great things about either language, just the things that spring to mind about why I like each.

So what makes Clojure more appealing than other Functional (or Hybrid OO/FP) languages? One key differentiator is that as a pragmatically designed language, IO and state considerations are clearly part of the plan. Not only this, the role of state, identity and time with regard to concurrency has been considered throughout the language’s and core library’s design.

Unlike Python (and other contemporaries like Java), Clojure does not provide mutability or identity to all data or variables. Instead, data is immutable, and the core data-structures are designed with that in mind. Secondly explicit reference types are provided. The programmer is expected to write core logic in a pure functionally mode where possible, and then use the reference types to maintain identity where needed. This will be familiar to anybody who has seen the buzz around functional programming and concurrency. Unlike in the C family, where pointers merely address memory, each reference type provides additional semantics. These semantics allow Clojure to provide managed statefulness; this is analogous to managed memory. A lot has been written about Clojure’s concurrency features, and by smarter people than me, so I won’t say any more.

One consideration with the current state of Clojure is that the planned 1.2 release is bringing two new constructs: Types and Protocols. These correspond roughly to Classes and Interfaces in Java. The current release (1.1) provides a Structs feature that uses dynamic maps as types, but this feature is due to be deprecated with 1.2. This places new users in an awkward position, but is a necessary change and will only be good in the long run.

The features that made Python a great choice in 2002 are no longer just the domain of so called ‘Scripting’ languages. Switching to Clojure does have trade-offs but it feels like the right choice for me.

Note: Discussion on the Hacker News thread.

Postscript

“Show Us The Code!” I’m not going to for this post. Snippets could be manufactured in situations that show each language as ‘better’. If you would like to see a small piece of Clojure written by a relative beginner, check out Caponia. This is an ultra light weight, in memory, full text index library that Matt and I designed during lunch and he implemented over the following day.

In contrast to this rather fluffy post, the next two will be looking at state and evaluation semantics in Clojure, chock full of code snippets. Update: The first half is now up.

See also

1. hga on Hacker News provides a link dump of Clojure material. A great place to get started.

Footnotes

1. These days its excellent with the ctypes library
2. No doubt Common Lisp has good reasons for how it does things, but from the outside its opaque and frankly not as nice as Clojure. Clearly a subjective judgement, but I’m allowed to make those when I’m evaluating a language for my own use.

On iteration

A Python programmer discovering the magic of itertools is three months from looking for a new language that better supports the functional style.

There is an observable trend in Python programmers that results in a reasonable section of them moving to functional programming languages. This trend is encouraged by the Python language, and has a couple of temporal considerations.

Firstly the language. Python has strong support for describing operations over aggregates. Most programmers coming to Python are coming from other procedural and OO languages, and these languages at best may support a for each style loop¹. The iterations of understanding (and understanding of iterations) follow a familiar path:

The new Python programmer will begin by writing programs that use the familiar for loop to process collections. At some point the syntax for List Comprehensions will be discovered. He will begin to write more and more code in this form. Following List Comprehensions are Generator Comprehensions, and perhaps Generator functions and the yield keyword.

Eventually he will stumble across itertools. This module becomes many Python programmers’ favorite standard library component. This is the beginning of the end for his interest in Python. Why? Two key reasons:

1. Python’s design and leadership prefer procedural and OO to the functional programming style. While the language can facilitate it, the library and syntax don’t support it naturally.
2. Generators are a poor substitute for real lazy data structures. You can do a lot with them, but you hit the pain points fairly quickly.

Secondly the temporal considerations. Python is currently going through a major version change. This fixes many warts and problems in the language, but requires projects to be ported to the newer, cleaner Python 3.

Concurrently, Functional Programming has come to the fore in geekdom as an answer to difficulties with concurrency and expression. Two languages in particular are well positioned to be an easy jump for an experienced Python programmer: Clojure, and F#. Haskell is also a popular choice with more academically minded over F#. Scala may be preferred by those who still have a strong attachment to mixing OO and Functional styles.

F# provides the familiar whitespaced based syntax. It has syntax blocks for statement based-procedurally oriented programming, and a class syntax that feels very familiar to expat Pythonista.

Clojure is the other contender. As a modern lisp for the JVM it provides a familiar development enviroment. Clojure also provides a large palette of tools for concurrent programming — a particular pain point for Pythonistas³ — and is capable of running very fast.

Python’s ease of development has been matched by these more recent languages. They provide features that the experienced Pythonista wishes he had, and without sacrificing speed or expression. The choice will be dictated by the enviroment and personal choice, but there are clear choices beyond Python.

Note: Discussion on the Hacker News thread.

See also

• The evolution of a Python programmer
• Zero, One and Many - The only three numbers in computing

Footnotes

1. This is changing with C# providing LINQ (to objects in particular).
2. Along with Smalltalk, recent C#s, Ruby, and other OO languages
3. Via the Global Interpreter Lock, mutability as a default and a lack of primatives.