The return of the monads: lessons learned about macros

[Konrad Hinsen]

A while ago I uploaded an implementation of monads in Clojure to the
group's file section. I have now replaced it by a more or less complete
rewrite. This rewrite was motivated by one serious problem with the
original implementation, plus a number of minor points that I was not
happy with. I have also integrated some ideas from Jim's alternative monad
implementation. The new implementation has replaced the original one at

http://clojure.googlegroups.com/web/monads.clj

In my original implementation, I had used keywords for the monad
operations. These keywords were replaced by their definitions inside a
given monad using a recursive symbol replacement in the form to be
evaluated. This approach has a major problem: it doesn't combine correctly
with macros. If a macro expands into a form containing monad operation
keywords, they are not replaced at all, because my symbol replacement code
sees only the original form.

The new implementation uses plain functions for the monad operations. The
with-monad form
expands into a straightforward let form that binds the operations to their
names. Generic monad operations such as lift are implemented as functions
that take the four basic monad definitions as additional parameters. These
functions are wrapped by macros that add these parameters to the argument
list. In the new implementation, all form manipulation is done by macros,
and there is much less of it: it no longer has a fundamental role, but
just provides nicer syntax.

To pursue my original idea of a replacement-based implementation, one
would need something like Common Lisp's symbol-macrolet, which is however
not trivial to implement. It requires either an integration with the
compiler's macro expansion mechanism, or a separate implementation of full
macro expansion, including subforms, of an arbitrary form.

With the new monad implementation, client modules can:
- define new monads (monad and defmonad)
- define new generic monad operations (defmonadfn)
- execute code using a monad (with-monad)
- define functions that internally use a specific monad (define the
function inside a with-monad block)
- use monad comprehension syntax (domonad)

Some minor changes:
- All monad operations have names starting with m-.
- There is a single m-lift that takes its arity as an argument.
- m-plus takes an arbitrary number of arguments and respects lazy evaluation.

Konrad.

[jim]

Konrad,

I haven't had a chance to look at this in depth but I did see two
things.

First, the function 'group' that you define seems to be the same as
Clojure's 'partition' function.

Second, when I tried to load monads, I get the following error.

java.lang.ExceptionInInitializerError (monads.clj:
165)
Caused by: java.lang.ExceptionInInitializerError
Caused by: java.lang.RuntimeException:
java.lang.ClassNotFoundException: user$m_PLUS_m_seq_PLUS_m__252
at clojure.lang.RT.readString(RT.java:1163)
at user$m_PLUS_m_map_PLUS_m__272.<clinit>(monads.clj:165)
... 26 more
Caused by: java.lang.ClassNotFoundException: user
$m_PLUS_m_seq_PLUS_m__252

(I snipped out some of the call stack.)

Looking forward to digging into this later.

Jim

[Konrad Hinsen]

Jim,

thanks for your comments!

> First, the function 'group' that you define seems to be the same as
> Clojure's 'partition' function.

Indeed. I have spent some time checking if something like this exists
already, but I didn't consider "partition" as a name!

> Second, when I tried to load monads, I get the following error.
>
> java.lang.ExceptionInInitializerError (monads.clj:
> 165)
> Caused by: java.lang.ExceptionInInitializerError
> Caused by: java.lang.RuntimeException:
> java.lang.ClassNotFoundException: user$m_PLUS_m_seq_PLUS_m__252
> at clojure.lang.RT.readString(RT.java:1163)
> at user$m_PLUS_m_map_PLUS_m__272.<clinit>(monads.clj:165)
> ... 26 more
> Caused by: java.lang.ClassNotFoundException: user
> $m_PLUS_m_seq_PLUS_m__252

The definition of m-map makes use of m-seq, which is a macro that
expands into a call to the function m+m-seq+m. It seems that this
function doesn't exist on your system. It should have been created by
the (defmonadfn m-seq...) just before.

On my system this works fine, but since I use a pretty old Clojure
version (the 20080916 release), it is possible that something
important has changed since. Unfortunately I can't easily test with
more recent SVN versions as I live behind a firewall that doesn't let
the SVN protocol pass.

Konrad.

[jim]

Konrad,

I got your code to work by doing the following:

Replaced with-monad with:

(defmacro with-monad
[name & exprs]
(let [bind-sym 'm-bind
result-sym 'm-result
zero-sym 'm-zero
plus-sym 'm-plus]
`(let [~bind-sym (:m-bind ~name)
~result-sym (:m-result ~name)
~zero-sym (:m-zero ~name)
~plus-sym (:m-plus ~name)]
(do ~@exprs))))

And in defmonadfn changed

(list ~fn-name '~'m-bind '~'m-result '~'m-zero '~'m-plus ~@args))

to

(list '~fn-name '~'m-bind '~'m-result '~'m-zero '~'m-plus ~@args))

I'll probably have some more comments after I dig into the code.

Jim

[jim]

Konrad,

I've looked over your monad code and I like it, FWIW.

The macro programming will twist your mind if you don't have
experience writing Lisp style macros, but the resulting syntax seems
pretty clean.

I would make some minor changes in two places. I would write with-
monad as:

(defmacro with-monad
"Evaluates an expression after replacing the keywords defining the
monad operations by the functions associated with these keywords
in the monad definition given by name."
[name & exprs]
`(let [~'m-bind (:m-bind ~name)
~'m-result (:m-result ~name)
~'m-zero (:m-zero ~name)
~'m-plus (:m-plus ~name)]
(do ~@exprs)))

And I would write m-lift as

(defmacro m-lift
"Converts a function f of n arguments into a function of n
monadic arguments returning a monadic value."
[n f]
(let [expr (take n (repeatedly #(gensym "x_")))
vars (vec (take n (repeatedly #(gensym "mv_"))))
steps (vec (interleave expr vars))]
(list `fn vars (monad-expr steps (cons f expr)))))

This removes the creation of the 'syms' list which you immediately
tear apart to generate the other lists.

All in all, a fine piece of code that I'll be using whenever I want to
use monads in Clojure.

I've also modified my parser combinator monad and uploaded a new
version at:

http://groups.google.com/group/clojure/web/monad-parser%20%282%29.clj

Jim

[Konrad Hinsen]

Jim,

> I would make some minor changes in two places. I would write with-
> monad as:

Obviously this is a better version.

> And I would write m-lift as

I like that one as well.

I have uploaded a new version that integrates your improvements.
Another one is that the monad operations are now named functions (a
feature I discovered by accident), which helps in debugging.

> I've also modified my parser combinator monad and uploaded a new
> version at:
>
> http://groups.google.com/group/clojure/web/monad-parser%20%282%29.clj

That looks like a good opportunity to look at monadic parsers...

Konrad.

[jim]

Konrad,

I did some more work from the paper the parser combinator is based
on. From that I built what I think is a state monad transformer:

(defn stateT [m]
(monad [m-result (fn [v]
(fn [s]
((:m-result m) (list v s))))
m-bind (fn [stm f]
(fn [s]
((:m-bind m) (stm s)
(fn [[v ss]]
((f v) ss)))))
m-zero (when (:m-zero m)
(fn [s]
(:m-zero m)))
m-plus (when (:m-plus m)
(fn [& stms]
(fn [s]
(apply (:m-plus m)
(map #(% s) stms)))))
]))

This function takes a monad and wraps it inside a state monad,
producing a new monad with a combination of characteristics from both.

I also rewrote the maybe monad as:

(defmonad maybe
"Monad describing computations with possible failures. Failure is
represented by an empty vector, success by a vector with a single
element, the resulting value."
[m-zero []
m-result (fn [v]
[v])
m-bind (fn [vs f]
(into [] (mapcat f vs)))
m-plus (fn [& mvs]
(let [first-valid (first (drop-while empty? mvs))]
(if (nil? first-valid)
m-zero
first-valid)))
])

(notice the change to the bind function).

This let me write the parser monad as:

(def parser-m (stateT maybe))

If that stateT function isn't actually a monad transformer, it still
is a slick way of combining the two monads.

Jim

[jim]

Also, I came across set-state and fetch-state being implemented in
terms of update-state.

(defn set-state [s]
(update-state (fn [x] s)))

(defn fetch-state []
(update-state identity))

Jim

[Konrad Hinsen]

On Dec 14, 2008, at 23:16, jim wrote:

> Also, I came across set-state and fetch-state being implemented in
> terms of update-state.

Indeed, those are the implementations I had in my first monad
implementation. I replaced them by manually inlining update-state
when I wanted to get rid of monad-operation substitution at monad
creation time. In the current version, these clearer implementations
can be used again.

Konrad.

[Konrad Hinsen]

Jim,

you were quicker than me in implementing monad transformers! What I
had in mind is exactly what you did: a monad transformer would be
implemented as a function taking a monad as an argument. That's in
fact why I defined the monad macro in addition to defmonad.

> I did some more work from the paper the parser combinator is based
> on. From that I built what I think is a state monad transformer:

That's exactly what it is. In fact, it looks like a translation of
the Haskell implementation.

There is one aspect of your implementation that I don't like: it
exposes the internal representation of monads as maps. This can be
avoided by using "with-monad m" in the definition of the monad
operations:

(defn stateT [m]
(monad [m-result (with-monad m
(fn m-result-state-t [v]
(fn [s] (m-result (list v s)))))

m-bind (with-monad m
(fn m-bind-state-t [stm f]
(fn [s]
(m-bind (stm s)
(fn [[v ss]]
((f v) ss))))))

m-zero (with-monad m
(when m-zero
(fn [s] m-zero)))

m-plus (with-monad m
(when m-plus
(fn m-plus-state-t [& stms]
(fn [s] (apply m-plus (map #(% s) stms))))))
]))

It should also be possible to write m-bind as a monad comprehension
in the inner monad:

m-bind (with-monad m
(fn m-bind-state-t [stm f]
(fn [s]
(domonad
[[v ss] (stm s)]
((f v) ss)))))

This looks clearer to me, but I didn't test if it actually works.

> I also rewrote the maybe monad as:

...

Why did you do this? Did you just want a more concise implementation,
or is there a difference in behaviour? As far as I can see, your
version of m-bind does exactly the same as mine for all input values
that can occur in the given context. Yours would also do something
useful given a vector of more than one value, but that should never
happen in the maybe monad.

Konrad.

[jim]

Konrad,

Glad to know we were on the same page about monad transformers.

That transformer was indeed a translation from the Haskell
implementation. Using 'with-monad' does clean it up.

I'll have to take a look at your implementation of m-bind.

I did prefer the conciseness and the fact that it would handle a
vector of more than one value. But the behavior is identical, so it
seems it's more a matter of taste.

> > I also rewrote the maybe monad as:
> ...
>
> Why did you do this? Did you just want a more concise implementation,
> or is there a difference in behaviour? As far as I can see, your
> version of m-bind does exactly the same as mine for all input values
> that can occur in the given context. Yours would also do something
> useful given a vector of more than one value, but that should never
> happen in the maybe monad.

I've got some more thinking to do about transformers, when I get a
chance.

Jim