There have been lots of demonstrations of monads in dynamically-typed languages before; notably, Oleg’s article on monads in Scheme. However, I haven’t yet (Update: see below) seen one that smoothly allows for return-type polymorphism.
This post introduces (1) coercions between monad representations and (2) “undecided” quasi-monadic placeholder values. Taken together, these give a Haskell-like feel for monads in a dynamically-typed language.
The techniques are illustrated using Racket, but aren’t specific to Racket.
How can we write monadic programs like this, where monad types are implicit, just as they are in comparable Haskell programs?
The overall computation uses
do-notation at IO type, while the
evens list uses
do-notation at List type.
Simple monomorphic monads are easy. Here’s the List monad in Racket:
Let’s add some simple
Now we can write list comprehensions. For example, let’s select the odd numbers from a list, and multiply each by two:
Let’s define another monad! How about for Racket’s lazy streams?
This is a fine definition, as far as it goes, but we’ve just run into the first problem:
Monads behave differently at different types
bind as functions won’t work.
We need some kind of dynamic method dispatch. Haskell does this by
But there’s a deeper problem, too:
Monads don’t learn their types until it’s too late
How should we choose which dictionary to use? It’s easy with
because the specific monad being bound is always given as
first argument. The
bind implementation can be a method on the
This doesn’t work for
fail. When they’re called, they
don’t know what kind of monad they should produce. That only becomes
clear later, when their results flow into a
Haskell uses the type system. We have to do it at runtime, on a case-by-case basis.
To address these problems, we explicitly represent the dictionary we need:
binder methods correspond to the monad
operations we met above, but
coercer is new. It lets us dynamically
reinterpret a monad at a different monadic type. We’ll see its use
Now we can define our List monad class:
not-coercable function is for use when it’s not possible to
reinterpret the type of a monad, which is the overwhelmingly common
case. It checks to make sure we’re already at the expected type, and
raises an exception if we’re not.
We need some way of learning which dictionary to use for a given monad instance. It’s here that Racket’s generics come in:
This declares a new generic interface,
gen:monad, with a single
monad->monad-class. It supplies implementations of
gen:monad for the builtin types
pair?, in each case
List monad-class when asked.
Now we can implement
coerce, not just for a single monad, but for all
monad->monad-class to find the relevant dictionary, extract
the right method from the dictionary, and delegate to it.
bind dispatches on its first argument, while
dispatches on its second argument: monad instances get to decide how
they are bound and how (or if!) they are to be interpreted at other
Next, we introduce neutral quasi-monad instances for when
fail don’t know which monad type to use. Because we might
such a quasi-monad before it collapses into a particular type, we need
to define a quasi-monad to represent
binds in superposition, too.
Return method dictionary looks very similar to the
implementation of the
with the addition of a
return-struct box around the carried value:
There are two interesting things to note here:
The bind implementation is a direct statement of one of the monad laws,
return x >>= f ≡ f x
The coerce implementation rebuilds the monad using the
returnimplementation from the target monad.
Return coerce implementation gives us the equivalent of
return-type polymorphism, letting us avoid sprinkling monad type
annotations throughout our code.
Bind are implemented similarly: 1
coerce method for an undetermined failure calls the new
failer method to produce the correct representation
for the final monad.
coerce for a
binds its parameters, after first coercing
them into the now-known monad.
You might have noticed a call to
coerce in the
This is necessary because
f might simply
(return 1), which is one
of these neutral quasi-monad instances that needs to be told what kind
of thing it should be before it can be used. On the other hand,
might have returned
(list 1), in which case
List’s coercer method
will notice that no conversion needs to be done.
The IO Monad
Racket is an eager, imperative language, and so doesn’t need an IO monad the way Haskell does. But we can define one anyway, to see what it would be like.
It’s also useful as a template for implementing unusual control structures for monadic embedded domain-specific languages.
Values in the IO type denote sequences of delayed actions. We’ll
represent these using two structure types, one for
return and one
Lifting Racket’s primitive input/output procedures into our IO type is straightforward:
Finally, we need a way to actually execute a built-up chain of actions:
Revisiting the Challenge Problem
We now have all the pieces we need to run the challenge program given above.
The challenge comes from the end of Oleg’s article on monadic programming in Scheme. His example uses many different types of monad together, using the monomorphic technique he developed:
With our polymorphic monads, we are able to use the generic
do-notation macro defined above, and write instead
which compares favourably to the Haskell
A somewhat fleshed-out implementation of these ideas is available here:
prop:procedure, making monad-classes directly callable and allowing
(coerce List foo)to be written as
It uses the double-dispatch pattern to let monad instances flexibly adapt themselves to each other in coercions. For example, lists, streams and sets can all be considered interconvertible.
It uses Racket’s built-in exception type to represent pending failures instead of the simple structure sketched above. This way, failures may carry stack traces and an informative error message.
It includes a simple
I based this work on some experiments I ran back in 2006 in writing a monadic library for Scheme. Racket offers much better support for object-oriented/generic programming (among many other things!) than vanilla Scheme does, which makes for smoother integration between my monad library and the rest of the language.
Ben Wolfson pointed me to his
monad library for clojure in a
about this post. It seems to be using a very similar approach, with
“neutral” carriers for monadic values that stay neutral until a later
point in the program. The main difference seems to be that with my
approach, no “run” step is needed for some monads, since monadic
values carry their
bind implementation with them. Ben’s library
supplies the bind implementation at “run” time instead.
Update, 20150127: Paul Khuong pointed me to
his Scheme monad implementation
this twitter conversation.
It doesn’t have dynamic-dispatch for automatically determining the
bind implementation, but I suspect it could be added;
perhaps in his
join operator, which makes an interesting contrast to
the technique explored in this post. The really nice thing about the
delimited continuation approach to monads is that the
implicit. You never mention
return explicitly in monadic code.
That makes a big difference, because return-type polymorphism is only
needed to handle explicit
returns! By placing the
next to the appropriate
run operation, the delimited continuation
technique neatly sidesteps the problem.
return is generic: it injects a value into any monad at
all. Which specific monad is used depends on the context. This is
impossible to directly implement in general without static analysis.
Lacking such static analyses in dynamically-typed languages, achieving
the equivalent of Haskell’s
return is challenging, even though
implementing particular monomorphic variations is straightforward.
The trick is to make
return produce a kind of superposition which
doesn’t collapse to a specific monad type until it touches a monad
that already knows what type it is.
In this post, I’ve shown how this kind of monad “coercion” works well to give the kind of return-type polymorphism we need to make monads feel in Racket similar to the way they do in Haskell.
No implementations are given for their
returnermethods, since they are only quasi-monad classes, and it’s not possible for user code to ever be in the