pulley.monad Readme

What is pulley?

pulley is the Positronic utility libraries. It is a collection of relatively small, simple libraries developed by Positronic Solutions, LLC. It is our pleasure to make them available to the public.

What is pulley.monad?

pulley.monad is part of the pulley collection of libraries. It provides a generic library for working with monads in Clojure. Instead of working directly with different types of monads, users of pulley.monad are encouraged to use a single monad type as much as possible — the “Generic” monad.

The Generic monad represents a description of a computation. This computation can be run with a set of concrete monad operators to yield a concrete result.

pulley.monad is licensed under the GNU Lesser General Public License (LGPL).

Status

pulley.monad is currently in the experimental stage. In particular, the idea of a generic monad is very much experimental and subject to change.

It is hoped that this approach will enable the ability to delay the details of a computation, and in turn provide many interesting opportunities. However, if this approach proves to be unsatisfactory, pulley.monad may undergo a complete redesign or even be abandoned.

Relation to Other Libraries

There are other monad libraries for Clojure, most notably algo.monads. pulley.monad differs from these mainly in its emphasis on a generic monad. In other libraries, the monad used is fixed when bind or return are called. In pulley.monad, the top-level bind and return operators operate over a single monad type (the Generic monad).

The Generic monad is very similar in spirit to the Free monad, in that the Generic monad expresses a generic computation that may then be interpretted in a variety of manners. However, while the Free monad turns functors into monads, the Generic monad turns monads into monads.

Usage

To use pulley.monad in your project, include the following dependency in your project.clj:

[com.positronic-solutions/pulley.monad "0.1.0"]

Now, you can

(require '[com.positronic-solutions.pulley.monad :as m])

Building and Running a Simple Computation: return and bind

The essence of monads is the composition of computations. With pulley.monad, we describe computations using a single monad — the Generic monad.

The return operator is used to construct a computation from a value. I.e., return constructs a computation which, when executed, yields the value it was given. For example, the following describes a computation which yields the value 3.

(m/return 3)

Note that we use return without specifying a particular monad to use. (m/return 3) returns a generic computation. To actually use it, we must use run to convert the generic computation into a concrete monad type.

For example, we can run the above computation in the Identity monad:

(m/run m/identity-m
  <<v1:expr>>)

This expression yields the value 3.

We can also run the same computation in the List monad:

(m/run m/list-m
  <<v1:expr>>)

This yields the value (3) (i.e., a singleton list conataining 3).

We chain computations via bind. bind takes a “monadic value” mv (i.e., generic computation) and a function f. bind returns a computation which first executes mv to extract its result, then applies f to the extracted value. f must return a monadic value / generic computation.

(m/bind <<v1:expr>>
        (fn [v]
          (m/return (inc v))))

This epxresses a computation that first yields 3 then increments it to yield a final result of 4.

(m/run m/identity-m
  <<t1:expr>>)
;; => 4

>>= and >>

bind takes exactly two arguments. However, sometimes you will find yourself writing code like this:

(m/bind (m/bind <<v1:expr>>
                (fn [x]
                  (m/return (inc x))))
        (fn [x]
          (m/return (* x 2))))

This is similar to

(-> 3
    inc
    (* 2))

It would be convenient if we could pass both functions in a single call to bind. pulley.monad provides >>= as a variadic version of bind:

(m/>>= <<v1:expr>>
       (comp m/return inc)
       (comp m/return (partial * 2)))

We see here that >>= is somewhat similar to Clojure’s threading macros (e.g., ->). Also, we use higher-order functions to construct the binding functions. However, we could have just as easily used the previous fn forms.

Sometimes we are interested in executing an effectual computation solely for its effect. In these cases, we don’t care about the result. The >> function takes one or more computations and composes them into a single computation which, when executed, executes the given computations in order, discarding the result of every computation except the last.

m-let

Consider the following computation:

(m/>>= <<v1:expr>>
       (fn [x]
         (m/>>= <<v2:expr>>
                (fn [y]
                  (m/return (+ x y))))))

Even though all this does is add 3 and 2, it requires an annoying amount of nesting. Although this is probably not how you would actually go about adding two constants together, composing computations often involves a high degree of nesting.

Fortunately, in Clojure it’s easy to obviate the need for nesting with a little syntactic sugar. The m-let macro provides this sugar. With m-let, we can write the above example as:

(m/m-let [x <<v1:expr>>
          y <<v2:expr>>]
  (m/return (+ x y)))

This m-let version is equivalent to the previous version, but involves a much lower degree of nesting. Furthermore the level of nesting remains constant, regardles of the number of bindings.

m-do

m-let provides a significant portion of the convenience of Haskell’s ”do-notation”. However, there are some patterns that are not so convenient with m-let.

m-do provides a more complete approximation of do-notation that allows more computations to be expressed as a single “flat” expression. m-do takes one or more expressions. In addition to Clojure expressions that evaluate to Generic monad values, the following forms are also supported:

• Exressions of the form :let <x> <value> denote a “pure let” expression. <value> must be a Clojure expression that evaluates to a “pure” value. The remainder of the expressions given to m-do are carried out with <x> bound to the value produced by evaluating <value>.
• Expressions of the form :bind <x> <value> denote a “monadic let” expression. In this case, <value> must be a Clojure expression that evaluates to a “mondaic” value. The remainder of the expressions given to m-do are carried out with <x> bound to the value yielded when <value> is run.

In both cases, <x> can be a simple variable or a destructuring expression — any form that can validly be used in a Clojure let binding can be used.

m-do allows us to mix pure and monadic expressions in a single “flat” expression. For example, suppose we have functions m-read-line and m-println which are monadic counterparts of Clojure’s read-line and println. With m-do, we can write:

(m-do :bind x  (m-read-line)
      :let  x' (str "First line: " x)
      (m-println x')
      :bind y  (m-read-line)
      :let  y' (str "Second line: " y)
      (m-println y')
      (m/return [x' y']))

Expressing this computation using m-let is only a little more difficult. In fact, with a little “cleverness”, we can express it as a flat expression as well — we simply wrap the <value> portion of each pure :let expression with m/return and bind the IO actions to a bogus variable (e.g., _):

(m-let [x  (m-read-line)
        x' (m/return (str "First line: " x))
        _  (m-println x')
        y  (m-read-line)
        y' (m/return (str "Second line: " y))
        _  (m-println y')]
  (m/return [x' y']))

However, with m-do it remains clear which expressions are “pure”, which expressions are “monadic”, and which expressions are executed purely for side-effects.

when-run / when-run*

Clojure uses eager evaluation. Unless we explicitly delay an expression, it will be evaluated when it is encountered.

Sometimes, though, it is necessary to delay execution of an expression until a later time. Fortunately, this is easy to do — we simply wrap the expression in a lambda (fn) expression. When we need the result, we simply call the function.

Unfortunately, a function of no arguments is not a valid Generic monad value. Other options, such as delay, suffer the same fundamental problem. So we need another solution.

For this purpose, pulley.monad provides the when-run macro. Given an expression, when-run wraps that expression in a monadic computation which evaluates the expression precisely when the computation is run.

It should be noted that when-run should not be used with IO, or simlar side-effecting actions. Use io instead. Even though it is functionally similar, io is semantically very different. (This is a general rule, and exceptions might be made in certain cases. For example, it might be considered acceptable to use when-run for logging debug messages.)

The primary use-case for when-run is recursive expressions.

For example, consider the following function that implements a monad-style version of if:

(defn m-if [pred true-branch false-branch]
  (m/m-do :bind pred? pred
          (if pred?
            true-branch
            false-branch)))

Now let’s say we want to use m-if to construct a recursive function:

(defn m-while [pred action]
  (m-if pred
        (>> action
            (m-while pred action))
        (m/return "done")))

The intent here is to implement a while-loop construct. However, it doesn’t matter what we pass to m-while — the result will always be a StackOverflowError. The reason for this is that both m-if and >> are functions, so their arguments are always evaluated prior to invoking the function. This means that the recursive call to m-while is unconditionally evaluated!

Fortunately, this is easy to fix with when-run:

(defn m-while [pred action]
  (m-if pred
        (>> action
            (m/when-run (m-while pred action)))
        (m/return "done")))

This version delays the recursive call to m-while, so all the arguments to m-if terminate. Since m-while is a function, we still need to be careful about the arguments to m-while itself (i.e., we might need to wrap them with when-run), but at least m-while itself will terminate. (The computation returned by m-while might not terminate, but the function call itself will always terminate in constant time.)

when-run* is the functional analog of when-run. Rather than transforming an expression, when-run* accepts a thunk and returns a monadic computation that invokes the thunk precisely when the computation is run.

For example, we could re-write m-while in terms of when-run*:

(defn m-while [pred action]
  (m-if pred
        (>> action
            (when-run* (fn []
                         (m-while pred action))))
        (m/return "done")))

io / io*

IO operations (and other non-functional effects) are very sensitive to when they are evaluated. Running them at the wrong time can lead not only to bugs, but wreak havoc on the entire system. Therefore, it is imperative to properly control such effects.

Although the timing issue can be solved via when-run, there is a large difference semantically between simply delaying evaluation of a pure functional expression and performing an action that affects the state of the “world”. The former is the domain of when-run / when-run*, while io / io* are intended for the latter.

There is also a slight difference in interface: io expects the given expression evaluate to a “pure” value (whereas when-run expects the given expression to return a monadic value).

Here’s an example of where io is necessary:

(def say-hello (m/return (println "hello")))

The above code prints hello immediately, during the definition of say-hello. (m/run m/identity-m say-hello) would not print anything. We can correct both problems by using io:

(def say-hello (m/io (println "hello")))

You can also give io multiple expressions. In this case, all expressions will be executed in sequence and the value of the last expression will be return‘ed

(def say-hello-and-goodby
  (m/io (println "hello")
        (println "goodbye")))

Constructing Custom Monad Types

run’s first argument is a map containing monad operations. This map must contain the following:

::m/return

Function implementing the monadic return operator.

::m/bind

Function implementing the monadic bind operator.

For example, we can construct the identity monad as:

(def identity-m
  {::m/return (fn [v]
                v)
   ::m/bind (fn [mv f]
              (f mv))})

Now we can use identity-m with run:

(m/run identity-m
  <<t1:expr>>)

Examples

You can find more examples under the examples directory.

Source Code

pulley.monad is written in a “Literate Programming” format. All the source code is contained in Emacs Org files. The code blocks from these files need to be extracted and assembled to form the Clojure source files.

All the source code for the library is contained in the Implementation Guide. To extract the source code, simply open Implementation Guide.org in Emacs and run the =org-babel-tangle= command. The default key binding for this command is C-c C-v C-t.

Contributing

Any and all comments are welcome and appreciated. If you run into any bugs or have a feature request, please report them in the GitHub issue tracker. If you change the source code, this should be done in the Org files.