Monads in Scheme?

[Erann Gat]

I've been following with interest the discussion on how to explain Monads
to people. The thing I seem to get hung up on the most is notation. Most
of the explanations are rendered in Haskell, which I am not familiar
with. I understand the general concepts, but not the details of the
syntax, which makes the explanations and examples hard to parse.

My question is: is it possible to render and/or explain the concept of a
monad in Scheme? And if not, why not? Is it because Scheme has no type
system, and types are part and parcel of what monads are? Or can the
essence of monads be divorced from type theory?

Thanks,
Erann

[Mark Carroll]

In article <gNOSPAMat-***@k-137-79-50-101.jpl.nasa.gov>,
Erann Gat <***@jpl.nasa.gov> wrote:
(snip)

Post by Erann Gat
of the explanations are rendered in Haskell, which I am not familiar
with. I understand the general concepts, but not the details of the
syntax, which makes the explanations and examples hard to parse.

(snip)

FWIW a really nice explanation of Haskell's monad syntax is in
http://citeseer.nj.nec.com/578595.html sections 2.2 and 2.3.

-- Mark

[Erann Gat]

Post by Mark Carroll
(snip)

Post by Erann Gat
of the explanations are rendered in Haskell, which I am not familiar
with. I understand the general concepts, but not the details of the
syntax, which makes the explanations and examples hard to parse.

(snip)
FWIW a really nice explanation of Haskell's monad syntax is in
http://citeseer.nj.nec.com/578595.html sections 2.2 and 2.3.

Thanks, that's a nice pointer. But just for the record, it's not monad
syntax that I have trouble with, it's Haskell syntax. For example, in the
following link suggested by Brian MacNamara:

http://www.engr.mun.ca/~theo/Misc/haskell_and_monads.htm

presumably targeted at beginners, you find the following example code:

(>>=) :: StateTrans s a ->
(a -> StateTrans s b) ->
StateTrans s b

p >>= k = \s0 -> let (s1, a) = p s0
q = k a
in q s1

What on earth does that mean? Do the parens in the first line mean the
same thing as the parens in the fourth line? What's that backslash doing
there?

No need to answer; these are rhetorical questions.

E.

[Erann Gat]

Post by Erann Gat

Post by Mark Carroll
FWIW a really nice explanation of Haskell's monad syntax is in
http://citeseer.nj.nec.com/578595.html sections 2.2 and 2.3.

Thanks, that's a nice pointer.

I take that back. This paper is horribly confusing.

The first non-trivial example is this:

main :: [Response] -> [Request]

This seems backwards. A server-like program does not take responses as
input and produce requests as output, it does exactly the opposite. At
first I thought this was just a mistake, but reading on makes it clear
that no, this is really what they meant:

"There has to be some clever footwork to deal with the fact that the
function has to be applied to a list of responses before there are any
responses in the list, but that isn't a problem in a lazy setting."

On behalf of confused monad studiers everywhere let me say that there has
to be more than just fancy footwork. There has to be an *explanation* of
how laziness allows you to work the miracle of writing a function whose
results exist before its input parameters do.

This one is not a rhetorical question: can someone please explain to me
what the florp is going on here?

Thanks,
E.

[Ben Rudiak-Gould]

Post by Erann Gat
main :: [Response] -> [Request]

This is an example of the bad old days before monads were introduced
to Haskell. The IO monad model replaces the [Response] -> [Request]
model with something much clearer. So you don't need to understand the
old model if you don't want to.

Post by Erann Gat
On behalf of confused monad studiers everywhere let me say that there has
to be more than just fancy footwork. There has to be an *explanation* of
how laziness allows you to work the miracle of writing a function whose
results exist before its input parameters do.

This sort of thing happens a lot in non-strict languages. On a low
level, the input to the function is calculated incrementally as it's
demanded. As long as the function produces an initial request which
doesn't depend on any of the responses, then a second request which
depends only on the response(s) to the first one, and so on,
everything will work fine (which it not to say it isn't very
confusing).

You can see the same thing in action in this definition of the stream
of fibonacci numbers:

(define fibs (cons-stream 1
(cons-stream 1
(stream-map + fibs (stream-cdr fibs)) )))

This works because it never consumes more of itself than has been
produced so far.

-- Ben

[Lauri Alanko]

Post by Erann Gat
main :: [Response] -> [Request]
This seems backwards. A server-like program does not take responses as
input and produce requests as output, it does exactly the opposite.

It's just a matter of perspective. A program gets data from the
outside world as input, and sends data back to the outside world as
output. Some of the input depends on previous output, since in the
outside world there are systems that communicate with the program. We
usually say that a "response" is a communication that depends on a
previous "request", but it is quite common that the next request
depends on the previous response, so there's no clear distinction.

People also often find it unintuitive that the thing that's running on
a workstation is the "X server", and the actual applications that are
running remotely are "clients". :)

Post by Erann Gat
"There has to be some clever footwork to deal with the fact that the
function has to be applied to a list of responses before there are any
responses in the list, but that isn't a problem in a lazy setting."
On behalf of confused monad studiers everywhere let me say that there has
to be more than just fancy footwork. There has to be an *explanation* of
how laziness allows you to work the miracle of writing a function whose
results exist before its input parameters do.

You may want to play with the "interact" function.

All right, here's a quick look. Suppose both requests and responses
are just ints, and we're running a "server" that returns the square of
the request. Moreover, suppose the "client" begins by sending 2, and
then always sends the previous response modulo 19 (this is all off the
top of my head).

Post by Erann Gat
server :: [Int] -> [Int]
server (x:xs) = x * x : server xs
client :: [Int] -> [Int]
client input = 2 : client' input
client' (x:xs) = x `mod` 19 : client' xs

So here we have two separate "processes" which take a lazy list as
input and produce as output another lazy list that depends on the input.

To get the actual requests and responses, we just let the client and

Post by Erann Gat
requests :: [Int]
requests = client responses
responses :: [Int]
responses = server requests

Unholy, wicked, vicious, evil, eh? :)

It actually works out all right. In the beginning we know only the
first request and no responses:

req: [2,...] resp: [...]

To get the next request, we need the first response. To get the first
response we need to know the first request, which we thankfully
already have:

req: [2,...] resp: [4,...]

Now we have all we need for the second request:

req: [2,4,...] resp: [4,...]

The second response depends on the second request which we now have, so:

req: [2,4,...] resp: [4,16,...]

Etc.

req: [2,4,16,...] resp: [4,16,...]
req: [2,4,16,...] resp: [4,16,256,...]
req: [2,4,16,9,...] resp: [4,16,256,...]

Each request only depends on the previous response, and each
response only depends on the previous request, so there are no cycles
here. Thanks to lazy evaluation, elements are evaluated only as they
are needed.

This is not really much of a miracle. It's pretty much the same thing
you get when you pipe two processes to each other.


Lauri Alanko
***@iki.fi

[Ketil Malde]

Post by Erann Gat

Post by Erann Gat
main :: [Response] -> [Request]
This seems backwards. A server-like program does not take responses as
input and produce requests as output, it does exactly the opposite.

requests :: [Int]
requests = client responses
responses :: [Int]
responses = server requests

Doesn't that still make "main" the *client*, rather than the server?
(Or am I just confused also?)

-kzm

[Erann Gat]

In article <c0ug1j$rdb$***@oravannahka.helsinki.fi>, Lauri Alanko
<***@iki.fi> wrote:

[An explanation of how a Haskell server can be written as main ::
[Response] -> [Request]]

Post by Lauri Alanko
Unholy, wicked, vicious, evil, eh? :)

Actaully, I find it a bit reminiscent of prolog. (Which is not to say
that your description is wrong ;-)

Thanks for the explanation.

One last question about this: if you actually write a server this way, how
do you keep from running out of memory?

E.

[Lauri Alanko]

Post by Erann Gat
One last question about this: if you actually write a server this way, how
do you keep from running out of memory?

It gets garbage collected. No surprise there. :) You just have to make
sure that you don't actually bind the entire response and request
lists to any variables (that would keep them alive), but rather
consume and produce them "on the fly".


Lauri Alanko
***@iki.fi

[Tomasz Zielonka]

Post by Erann Gat
[Response] -> [Request]]

I think that in this situation the Haskell program is a client, and the
"world" acts as a server.

Best regards,
Tom

[Brian McNamara!]

Post by Erann Gat
My question is: is it possible to render and/or explain the concept of a
monad in Scheme? And if not, why not? Is it because Scheme has no type
system, and types are part and parcel of what monads are? Or can the
essence of monads be divorced from type theory?

You can do it; see for example
http://www.cs.indiana.edu/~jsobel/Parsing/explicit.html
which discusses a particular instance of using monads (for parsing) in
Scheme.

I think maybe the "main issue" you have to deal with when translating
monads to a dynamically-type language is that, in order to write
"generic" functions which work for multiple monads, you need to provide
a way to dispatch to the particular monad you're in. That is, whereas
a Haskell function might just mention "return" and ">>=" and use the
type inferencer to resolve the overloading, in a dynamically-typed
language, you'd probably have to make all the "(Monad m)=>" functions
take an extra parameter (the dictionary of monad methods).

Note that this issue is not dealt with in the paper at the URL above;
in much of the expository writing on monads, the writer either (1)
assumes you will only be working in one monad (as above), or (2)
provides differently-named operations for each monad (e.g. unitA/bindA
for monad A, unitB/bindB for monad B, etc.).

That's my take, anyway; I don't use dynamically-typed languages very
often, so I may be off.

[Erann Gat]

Post by Brian McNamara!
I think maybe the "main issue" you have to deal with when translating
monads to a dynamically-type language is that, in order to write
"generic" functions which work for multiple monads, you need to provide
a way to dispatch to the particular monad you're in.

What about doing it in CLOS then? Would that work better?

E.

[Brian McNamara!]

Post by Erann Gat

Post by Brian McNamara!
I think maybe the "main issue" you have to deal with when translating
monads to a dynamically-type language is that, in order to write
"generic" functions which work for multiple monads, you need to provide
a way to dispatch to the particular monad you're in.

What about doing it in CLOS then? Would that work better?

I am no CLOS expert, but I think no.

CLOS has nice stuff for automagically doing dispatch based on the
datatypes of arguments. However the "type information" associated with
a monad in Haskell often comes from context (inferred based on stuff
outside the current expression), rather than arguments.

In a previous post, someone (Marcin?) just explained in detail how you
can pass the monad dictionaries around in Scheme. This is the
straightforward way to do things.

There is another way (which I've been experimenting with in C++); I'm
not sure if it's better or worse. The idea is, rather than clutter all
your monad computation with an explicit extra 'm' parameter, make it
implicit. That is, you can apply the same idea of the state monad to
the implementation of monads themselves, and have all of your monad
computations actually return "unary functions" (rather than "monadic
values"), where the function takes the monad-dictionary parameter as an
argument and then returns the monadic value for that monad. The result
of all this is that, rather than passing "m" around everywhere, you can
effectively just pass it in once at the "top" of the computation. It
sounds better "in theory" than "in practice", I think, though. More
experimentation is necessary.

[Marcin 'Qrczak' Kowalczyk]

Post by Erann Gat
My question is: is it possible to render and/or explain the concept of a
monad in Scheme?

Implementing them would be significantly more verbose than in Haskell,
because Haskell has a powerful static type system which can substitute
appropriate versions of overloaded operations - not only basing on the
types of their arguments, but also on the expected type of the result,
on context of their usage.

In particular monadic "return" is an example of an opeartion dispatched on
the expected type. The canonical translation of Haskell classes into the
dynamically typed world is analogous to what a Haskell compiler typically
does - materializing class dictionaries into explicitly passed objects.

A monad is thus a record of two fields, called "bind" and "return", which
are implicitly associated with a format of values, called actions of this
monad. "Bind" is a function of two arguments: an action to be performed
first, and a function which - when applied to the result produced by the
first action - returns an action to be performed next. "Bind" returns the
compound action. "Return" has one argument, some value, and returns an
action which produces the value as the result, while otherwise having no
observable behavior.

The meaning of terms like "action", "produces" and "next" depend on the
monad. In particular they can imply funny control flow, e.g. introducing
exceptions, non-determinism or continuations. This is similar to using CPS
manually (instead of using the builtin call/cc).

A monad is also accompanied with a set of primitive operations specific
to the monad, usually functions returning actions or actions. "Bind" and
"return" only provide generic plumbing. For example in the exception monad
the operations can be "throw" and "catch" (with some appropriate interface).

In essence a monad provides an evaluation model, or capabilities of the
control flow, i.e. whether it supports continuations, or an implicit
mutable state, or an implicit sink of values which are collected to a list
available "outside" the monad.

In Haskell "bind" is an infix binary operator written ">>=", and "return"
is an unary function. In Scheme extraction of a record field would be
probably composed with applying it (as it's a function), so "bind" is a
ternary function, taking the monad record, the action, and the function;
and "return" is a binary function. In monad-specific code you can also
explicitly call specialized variants of "bind" and "return" instead of
taking them from a record (where the record instance would be known
statically anyway).

Haskell passes the class dictionary (i.e. the monad record) implicitly
when the type system says so. Scheme would pass it explicitly. E.g. this
Haskell function, generic monadic version of map (where "\y -> ..." is
a lambda):

mapM :: Monad m => (a -> m b) -> [a] -> m [b] -- optional type signature
mapM f [] = return []
mapM f (x:xs) =
f x >>= \y ->
mapM f xs >>= \ys ->
return (y:ys)

would be literally translated like this:

(define (map-m m f l) ; Note the extra argument m
(if (null l)
(return m '())
(bind m (f (car l)) (lambda (y)
(bind m (map-m m f (cdr l)) (lambda (ys) ; Note passing m to map-m
(return m (cons y ys)))))))) ; Hope I counted the parens right

When mixing monad-generic and monad-specific code, we must be careful
to know when to pass m (calling a monad-generic function from a
monad-generic function), when not to pass (calling a monad-specific
function from a monad-specific function), or when to pass a specific
record like exception-monad as the m (calling a monad-generic function
from a monad-specific function). There are more complex cases in
implementing monad transformers when we construct a monad records from
other monad records, and many possibilities to get lost with generic monad
transformers, with operations like "make an action throwing an exception,
in the sense of any monad which has the exception capability" where there
are records containing other operations in addition to monad plumbing,
and a few different monad records are used in one expression.

The monadic style tends to use many higher order functions, and static
typing is very helpful in detection of confusions of an action and a
result of an action, or actions of different monads.

Static typing also helps for performance. In Scheme the generated code
would need to extract a field from a record quite often and call
statically unknown functions. A Haskell compiler can often inline calls
to ">>=" after a generic monadic code is specialized, and there are lots
of opportunities of inlining of those anonymous functions.

Back to the syntax. Haskell's binary operators, and the syntax of lambda
which can be written without parentheses after a binary operator, makes
monadic code writable and readable directly - but even Haskell provides
a syntactic sugar after the "do" keyword which makes it more pretty:

mapM f [] = return []
mapM f (x:xs) = do
y <- f x
ys <- mapM f xs
return (y:ys)

In Scheme monadic code would be awful when written directly - it needs to
open 2 levels of parentheses for each statement, to be closed after the
whole sequence of statements! Some macros would be essential. They would
still not free from passing the monad records explicitly (because when to
pass them depends on the types), but they would turn these applications of
"bind" and lambdas into something manageable.

Of course a Scheme programmer has less temptation to use monads than a
Haskell programmer, because the evaluation model of Scheme has some common
monadic features built-in or implementable in terms of one another:
mutable state (but only in the explicit references sense, like Haskell's
non-standard IO extensions, not in the sense of an implicit single state,
like Haskell's classic State monad), continuations, exceptions,
non-determinism. Haskell can't have them implicit in function application
because of laziness, so it must differentiate between applying a function
to the result of a function
f (g x)
from an action applying a pure function to the result produced by another
imperative action
g x >>= liftM f
g x >>= (return . f)
g x >>= \tmp -> return (f tmp)
do tmp <- g x; return (f tmp)
or an action performing an action resulting from the application of a
function to the result produced by another action
g x >>= f
do tmp <- g x; f tmp
while all this corresponds to (f (g x)) in Scheme, because a function can
also perform actions like writing into variables or capturing continuations.

[Ben Rudiak-Gould]

On Wed, 18 Feb 2004 00:50:47 +0100, Marcin 'Qrczak' Kowalczyk

Post by Marcin 'Qrczak' Kowalczyk
Implementing them would be significantly more verbose than in Haskell,
because Haskell has a powerful static type system which can substitute
appropriate versions of overloaded operations - not only basing on the
types of their arguments, but also on the expected type of the result,
on context of their usage.
In particular monadic "return" is an example of an opeartion dispatched on
the expected type. The canonical translation of Haskell classes into the
dynamically typed world is analogous to what a Haskell compiler typically
does - materializing class dictionaries into explicitly passed objects.

There's a way around this for the specific case of the Monad
typeclass. Introduce two data types, a "monadic value" and a "unit
value". A monadic value contains a monad tag and private data specific
to the monad. A monad tag is a dictionary (a definition of unit and
bind for that monad). Monad tags support a "same monad" equivalence
relation. A unit value is just a boxed Scheme value.

The return function makes a unit value out of its argument. The >>=
function does the following: if its first argument is a unit value, it
applies its second argument to the (unboxed) first argument. This is
legal by the monad law "return x >>= f == f x". If its first
argument is a monadic value, it calls the associated bind function to
do the rest of the work.

With this technique, you can use monads in Scheme exactly as in
Haskell, and new monads can be dynamically defined and used. It
doesn't extend easily to arbitrary typeclasses, though, or to dynamic
definition of typeclasses.

I was actually planning on designing a referentially transparent,
dynamically-typed Scheme dialect based on this idea, but I haven't had
time recently to work on it. I thought it might be useful for teaching
pure functional programming without Haskell's steep learning curve.

-- Ben

[Display Name]

Post by Erann Gat
My question is: is it possible to render and/or explain the concept of a
monad in Scheme?

Of course. For simple examples, see

http://groups.google.com/groups?selm=22df0133.0311051847.4812a67f%40posting.google.com

and

http://okmij.org/ftp/Scheme/monad-in-Scheme.html

Andre

[John Atwood]

Post by Display Name

Post by Erann Gat
My question is: is it possible to render and/or explain the concept of a
monad in Scheme?

Of course. For simple examples, see
http://groups.google.com/groups?selm=22df0133.0311051847.4812a67f%40posting.google.com
and
http://okmij.org/ftp/Scheme/monad-in-Scheme.html
Andre

For a more elaborate example, see chapter 13 of Sperber's Lula thesis:
http://w210.ub.uni-tuebingen.de/dbt/volltexte/2001/266/pdf/lula-thesis.pdf

also: Ganz and Friedman's "A Modular Interpreter In Scheme With Objects"
http://citeseer.nj.nec.com/ganz00modular.html

and every schemer should be aware of Steele's pseudomonads:
http://citeseer.nj.nec.com/steele94building.html
especially sections 15 and 16, "Why Haskell" and "Why Monads"

Also germane is Shutt's remark in
"Monads for Programming Languages" (2003):

4 Concluding note
The original objective of this work was to relate the abstract
mathematical concept of monads to the applied area of programming
languages. My overall assessment is that the mechanical form of
monads has inspired extensive (more-or-less ad hoc) work in
programming languages, while thus far no strong relation has been
demonstrated between the mathematical concept itself and the
applied area.



John

[Neelakantan Krishnaswami]

Post by Erann Gat
My question is: is it possible to render and/or explain the concept
of a monad in Scheme? And if not, why not? Is it because Scheme
has no type system, and types are part and parcel of what monads
are? Or can the essence of monads be divorced from type theory?

It's possible, but not the most fun thing in the world. Monads arise
from category theory, which is an inherently typeful branch of
mathematics, and there are very close links between category theory
and typed lambda calculi. Of course, you can do it in Scheme, but it
will be somewhat harder to understand, since you have to keep more of
the program in your head and less in your source code.

But I'll give it a shot -- I've been meaning to write down what I know
in order to solidify it, and you give me a good excuse. :)

o Q: What is a monad?

A: Monads are a concept from category theory, which functional
programmers have adapted to create a useful design pattern for
combinator libraries.

o Q: So all they are is a design pattern for higher order functions?

A: Yeah, basically. It's one of the key unifying ideas in
programming language semantics, but for hackers it's basically
a design pattern.

o Q: So what's the frequency, Kenneth?

A: Um, right. Every monad consists of four things:

1. A type constructor M, which sends a type 'a' to a
types 'M[a]'.

These types should not be thought of as the Scheme types like
string? or procedure?; instead think of them more like as the
types Scheme programmers use to specificy the arguments to
functions (eg, "a list of integers").[1] You can read 'a' as
"the type a", and 'M[a]" as "the type of computations of type
a".

2. A function 'unit', which has type 'a -> M[a]'. That is, it
takes a value of type a, and injects it into the monadic
type.

3. A function 'bind', of type '(M[a], a -> M[b]) -> M[b]'.
bind is a function taking two arguments -- the first is a
monadic value of type M[a], and the second is a function that,
given an a, returns a monadic value of type M[b]. It then
returns a value of type M[b].

Intuitively, you take the computation M[a] and perform it,
getting a value of type a (plus whatever computational stuff
performing the computation did). Then, you pass that value of
type a into the second argument, and get back a new
computation of type M[b].

4. There are the three algebraic laws that bind and unit have to obey.
In Scheme, these equivalences are:

(bind (unit x) f) == (f x)

(bind M unit) == M

(bind (bind M f) g) == (bind M (lambda (x) (bind (f x) g)))

o Q: Give me an example?

A: Sure! Here's the simplest possible monad -- the identity monad.

(define (unit x) x)
(define (bind m f) (f m))

I'll leave checking that bind and unit obey the monad laws as
an exercise.

o Q: That was too trivial to be helpful. How about a less useless
example?

A: Picky, picky. Here is the option or maybe monad, which represents
computations that can either return a value, or fail with an
error.

(define fail (vector 'fail)) ; fail is not eq? to anything else

(define (unit x) x)

(define (bind m f)
(if (eq? m fail)
fail
(f m)))

Again, I'll leave checking the monad laws to you, the reader.

o Q: Can you explain why I'd want to use this?

A: Okay. Suppose you have three functions foo, bar, and baz, each
of which takes a value (with fail not in the domain), and either
return or fail by returning fail. Now, suppose you want to compose
these three functions, with any failure causing the composition
to fail. So you write:

(define (foo-bar-baz x)
(let ((foo-val (foo x)))
(if (eq? foo-val fail)
fail
(let ((bar-val (bar foo-val)))
(if (eq? bar-val fail)
fail
(baz bar-val))))))

Then you look at this code, and sigh, because it is ugly, and
doesn't match the simple concept you had in your head:

(define (concept-of-foo-bar-baz x) (baz (bar (foo x))))

But, since you're a functional programmer, you know you can use
the power of higher order functions:

(define (compose* f x)
(if (eq? x fail)
fail
(f x)))

(define (foo-bar-baz x) (compose* baz (compose* bar (foo x))))

That's much better. But wait! The function compose* is precisely
the bind operation of the maybe monad!

o Q: Pretty nice. But you added fail to this API in a pretty ad-hoc
way. Do you have to do that with all monads?

A: Of course, all monads need to have some operations specific
to whatever thing you are using the monad for. But in the case
of the option monad, fail is an instance of a very common
pattern called "monads with zeros". A monad with a zero has
two extra elements to its API:

1. A value 'zero', of type 'M[a]'.

2. A function 'plus', of type '(M[a], M[a]) -> M[a]'

3. plus and zero must obey the following algebraic laws:

(plus m zero) == (plus zero m) == m

(bind m (lambda (x) zero)) == zero

(bind zero f) == zero

So for the maybe monad, we can write

(define zero (vector 'Fail)) ; just a rename from 'fail' to 'zero'

(define (plus a b)
(if (eq? a zero)
b
a)

The maybe monad's plus should be a very familiar pattern to a
Scheme programmer; it's exactly how the or special form works,
except that its zero value is #f. This is why it's so pleasant to
use APIs that return #f in case of failure, and a useful return
value otherwise.

o Q: Are there any other monads with zero? It's not safe to generalize
from one example.

A: Sure. Lists form a monad with a zero, too. Look:

(define (unit x) (list x))

(define (bind m f) (apply concatenate (map f m))

(define zero '())

(define (plus a b) (append a b))

Verify the monad and zero laws!

o Q: Options and lists are nice, sure. But what's all this I hear
about using monads to treat state in a pure way?

A: Let's start with an example. Suppose that you want to write
a function that will take a binary tree, and then number the
leaves. To do this with imperative state, you can do a tree
walk and increment a counter at each leaf:

(define state 0)

(define (number-tree tree)
(if (pair? tree)
(let* ((left-subtree (number-tree (car tree)))
(right-subtree (number-tree (cdr tree))))
(cons left-subtree right-subtree))
(let ((n state))
(set! state (+ state 1))
n)))

This works, but doesn't let us renumber two trees starting from
the same number. So if we try to do this purely, we need to write
your loop in "state-passing style", and thread a counter through
the program.

(define (number-tree tree state)
(if (pair? tree)
(let-values ((lft state-1) (number-tree (car tree) state))
(let-values ((rgt state-2) (number-tree (cdr tree) state-1))
(values (cons lft rgt) state-2)))
(values (+ state 1) (+ state 1))))

That's rather nasty looking, and it would suck to accidentally use
the wrong updated state. However, we can use a monad to automate the
plumbing, and get the benefit of both approaches.

; The type constructor M[a] = state -> (a, state)

(define (unit x) (lambda (state) (values x state)))

; all bind does is thread the state through some calls.

(define (bind m-a f)
(lambda (state)
(let-values ((a state*) (m-a state))
((f a) state*))))

; get takes a state and returns it as a value

(define (get state) (values state state))

; set takes a state, and returns a monadic value that replaces
; the old state with the new state

(define (set new-state) (lambda (state) (values #f new-state)))

; run will take a monadic state value, and then run it with an
; initial state to get an actual value.

(define (run m state) (m state))

Now, I'll define the number-tree program using a state monad. To
make it readable, I'll use a very eccentric indentation:

(define (number-tree tree)
(if (pair? tree)
(begin (bind (number-tree (car tree)) (lambda (left-subtree)
(bind (number-tree (cdr tree)) (lambda (right-subtree)
(unit (car left-subtree right-subtree)))))))
(begin (bind get (lambda (n)
(bind (set (+ n 1)) (lambda (dont-care)
(unit n))))))))

Compare this to the imperative definition:

(define (number-tree tree)
(if (pair? tree)
(let* ((left-subtree (number-tree (car tree)))
(right-subtree (number-tree (cdr tree))))
(cons left-subtree right-subtree))
(let ((n state))
(set! state (+ state 1))
n)))

We are using bind + lambda to simulate using let*. There is a
1-to-1 correspondence between the monadic and imperative code!
At this point, the eccentric indentation of the monadic code
suggests that it would be worthwhile to define a macro to
simplify things. (This macro is one I stole from an Oleg
article.)

(define-syntax do
(syntax-rules (def)
((do (v <- expr) rest) (bind expr (lambda (v) rest)))
((do expr) expr)
((do expr expr) (bind (set expr) (lambda (dummy) expr)))
((do expr expr* ...) (do expr (do expr* ...)))))

This emulates Haskell's do-notation, which we can use as
follows:

(define (number-tree tree)
(if (pair? tree)
(do (left-subtree <- (number-tree (car tree)))
(right-subtree <- (number-tree (cdr tree)))
(unit (cons left-subtree right-subtree)))
(do (n <- get)
(set (+ n 1))
(unit n))))

Cool, huh?

o Q: Very cool. So a Haskell compiler takes programs using the purely-
functional state monad and optimizes it internally into a program
using mutation?

A: Exactly.

o Q: What else can monads do?

A: You can also turn programs in continuation passing style into
monadic form. In fact, it's a significant result (due to Andrezj
Filinski) that all imperative programs using call/cc and state
can be translated into a monadic style, and vice versa. So
exceptions, nondeterminism, coroutines, and so on all have a
monadic expression.

o Q: Why do Haskell descriptions of monads focus so heavily on this
weird "typeclass" stuff?

A: Typeclasses are just overloading on steroids, and each of the monads
in this article had its own bind and unit operation. So
Haskellers overload bind and unit (which they call >>= and
return) for every monad they write, so that their monadic code
commits as little as possible to a specific monad. It's just
good, solid, software engineering practice.

This would be hard to do in Lisp (eg, with CLOS), because of the
unit operation -- you would need to select the appropriate unit
operation based on the expected *return* type, and that's
something that inherently needs a static type system to work.

[Matthias Blume]

Post by Neelakantan Krishnaswami
4. There are the three algebraic laws that bind and unit have to obey.
(bind (unit x) f) == (f x)
(bind M unit) == M
(bind (bind M f) g) == (bind M (lambda (x) (bind (f x) g)))

[...]

Post by Neelakantan Krishnaswami
o Q: That was too trivial to be helpful. How about a less useless
example?
A: Picky, picky. Here is the option or maybe monad, which represents
computations that can either return a value, or fail with an
error.
(define fail (vector 'fail)) ; fail is not eq? to anything else
(define (unit x) x)
(define (bind m f)
(if (eq? m fail)
fail
(f m)))
Again, I'll leave checking the monad laws to you, the reader.

I'm going to be more picky here, because, unfortunately, this "monad" fails
to satisfy even just the first law:

(define (f x) (if (eq? x fail) "got you!" "who cares"))

(bind (unit fail) f) --> fail
(f fail) --> "got you!"

BTW, this nicely demonstrates what's wrong with the common practice of
using "some distinguished value" to represent failure (or the absence
of a value) in untyped languages...

Cheers,
Matthias

[Neelakantan Krishnaswami]

Post by Matthias Blume

Post by Neelakantan Krishnaswami
A: Picky, picky. Here is the option or maybe monad, which represents
computations that can either return a value, or fail with an
error.
(define fail (vector 'fail)) ; fail is not eq? to anything else
(define (unit x) x)
(define (bind m f)
(if (eq? m fail)
fail
(f m)))

I'm going to be more picky here, because, unfortunately, this "monad" fails
BTW, this nicely demonstrates what's wrong with the common practice
of using "some distinguished value" to represent failure (or the
absence of a value) in untyped languages...

Yow, you're right! Let me try fixing that.

; An option monad in Scheme

(define (unit x) (car 'maybe x))

(define (bind m f)
(if m
(f (cdr m))
#f))

(define zero #f)

(define (plus a b)
(or a b))

The relationship between 'or' operator and monadic plus is even
clearer than in the original, too, so better and better. :)

[Vasile Rotaru]

This is my take on $subj. Some time ago I have expressed the opinion
that monads are "smart let"-s, which do some more work than just binding names to values, and here you have a let/maybe macro which
emulates the Maybe monad from Haskel.

data Maybe a = Just a | Nothing

in my code Nothing translates to #f, and everything else is Just a.

(define-syntax let/maybe
(syntax-rules ()
((_ ((res f arg) ...) body ... )
(let ((res (if arg (f arg) #f)) ...) body ...))))

testing it (with mzscheme)

(let/maybe ((see-it (lambda (x) 1) #f)) see-it)

#f

(let/maybe ((see-it (lambda (x) 1) 'hukares)) see-it)
1

Since I have never before used syntax-rules (and I'm new to scheme too) I'm not sure it will work for anything more complex than see-it.

Regards,
vasha

[Lex Spoon]

Post by Matthias Blume

Post by Neelakantan Krishnaswami
(define fail (vector 'fail)) ; fail is not eq? to anything else
(define (unit x) x)
(define (bind m f)
(if (eq? m fail)
fail
(f m)))

I'm going to be more picky here, because, unfortunately, this "monad" fails
BTW, this nicely demonstrates what's wrong with the common practice
of using "some distinguished value" to represent failure (or the
absence of a value) in untyped languages...

Actually, it's an excellent technique in dynamically typed (ahem!)
languages such as Scheme. It can make the code a little smoother
because you don't have to deconstruct the value so often. In ML, you
would lose some static checking if you use a distinguished value
instead of a variant datatype; however, there is no such loss in
Scheme, so why pay the price of more code? Use the language that's in
front of you.

If you use the technique, though, you should either (a) use lexical
scoping to prevent outsiders from using the distinguished value, or
(b) name the value so that people know they aren't supposed to use it.
In this case, (a) can be accomplished, among other ways, by adding the
following four lines:

(define (is-failed m) ; the client needs a way to check
(eq? m fail))

(define fail nil) ; hide the binding


I assumed these lines were left out just to keep the example short.
They don't add anything to the presentation.



-Lex

PS -- great article, Neel! I hope it gets posted on the web somewhere.

[Matthias]

Post by Neelakantan Krishnaswami
[...]
But I'll give it a shot -- I've been meaning to write down what I know
in order to solidify it, and you give me a good excuse. :)
[...]

Thanks for this excellent explanation!

Matthias

[Erann Gat]

In article <***@gs3106.sp.cs.cmu.edu>, Neelakantan
Krishnaswami <***@cs.cmu.edu> wrote:

[The best explanation of Monad's I've seen yet.]

Thanks! That's just what I was looking for!

And thanks to everyone who responded in this thread. All of these
responses have been very helpful.

E.

[o***@pobox.com]

Just in case: The second part of the article "Multiple values as an
effect" talks about monadic reflection and reification in Scheme:

http://google.com/groups?selm=7eb8ac3e.0310211211.3c684996%40posting.google.com

and gives practical examples.

[Michael Sperber]

Erann> My question is: is it possible to render and/or explain the concept of a
Erann> monad in Scheme? And if not, why not? Is it because Scheme has no type
Erann> system, and types are part and parcel of what monads are? Or can the
Erann> essence of monads be divorced from type theory?

The natural formulation of monads just looks very different in Scheme,
as a monadic framework is already built into the language by virtual
of CALL-WITH-CURRENT-CONTINUATION.

Check out:

Andrzej Filinski: Representing Monads. In Proceedings of the 21st ACM
SIGPLAN-SIGACT Symposium on Principles of Programming Languages,
pp. 446-457, Portland, Oregon (January 1994).

and

Andrzej Filinski: Representing Layered Monads. In Conference Record of
POPL '99: The 26th ACM SIGPLAN-SIGACT Symposium on Principles of
Programming Languages, pp. 175-188, San Antonio, Texas (January 1999).

Both are available on Andrzej Filinski's homepage under:

http://www.diku.dk/~andrzej/papers/

[Andre]

The Filinski encoding of monads in Scheme is really interesting and
easy to use. Its main advantage is that programs using monads
in Scheme can be expressed in a more concise direct style instead
of the usual monadic style.

Since the literature may be a bit forbidding, here are
some simple examples:

The two primitives that we use are *reflect* and *reify*. They
use the monad operations *unit* and *bind*, which we will supply
individually for each monad. The precise definitions of *reflect*
and *reify* are at the end of this message but are not needed to
understand their use.

LIST MONAD:
----------

Our first example is the List monad. Supplying the definitions

(define (unit x) (list x))
(define (bind l f) (apply append (map f l)))

we can now write the Haskell

do x <- [1, 2]
y <- [5, 6]
return (x, y)

in Scheme as

(reify (let* ((x (reflect '(1 2)))
(y (reflect '(5 6))))
(cons x y)))

==> ((1 . 5) (1 . 6) (2 . 5) (2 . 6))

We see the following features:

* We use *reify* to delimit a computation
and return the result as a monadic value (like do ... return).
* The role of <- is played by *reflect*, which extracts an ordinary
value from the monad.
* For explicit sequencing, we can use Scheme's native let*.

So far there seems to be little difference between the Haskell and the
Scheme encodings. However, we can take advantage of the implicit evaluation
order of Scheme to rewrite it in direct style (*), avoiding the need
for the intermediate variables x and y!

(reify (cons (reflect '(1 2))
(reflect '(5 6))))

==> ((1 . 5) (1 . 6) (2 . 5) (2 . 6))

We'll see more examples of this below.


THE MAYBE MONAD:
---------------

To use the maybe monad, we simply supply:

(define (unit x) (list x))

(define (bind m f)
(if m
(f (car m))
#f))

(define fail #f)

(define (either a b)
(or a b))

Let us now define some procedures that may throw an exception:

(define (foo x) (if (= x 0)
(reflect fail) ; exception
(/ 1 x)))

(define (bar x) (+ x x))

(define (baz x) (if (= x 0)
(reflect fail)
(/ 1 x)))

In Haskell, we could then compose them as follows:

do y <- foo 0
z <- bar y
return (baz z)

which translates directly to Scheme as before:

(reify (let* ((y (foo 0))
(z (bar y)))
(baz z)))

==> #f

However, we can also write this in the equivalent,
more concise direct style:

(reify (baz (bar (foo 1)))) ==> 1/2
(reify (baz (bar (foo 0)))) ==> #f

What a nice, concise abstraction! Certainly much better
than writing it all out as follows!

(let ((foo-val (foo x)))
(if foo-val
(let ((bar-val (bar (car foo-val))))
(if bar-val
(baz (car bar-val))
#f))
#f))

Just for fun, *either* is used to do backtracking on failure
as in the following example:

(reify (baz (bar (reflect (either (reify (foo 0))
(reify (foo 1))))))) => 1/2


THE STATE MONAD:
----------------

Let's do Neel Krishnaswami's state monad example. Once
again, all we have to do is specify:

(define (unit x) (lambda (state) (values x state)))

(define (bind m-a f)
(lambda (state)
(let-values (((a state*) (m-a state)))
((f a) state*))))

(define (get state) (values state state))

(define (set new-state) (lambda (state) (values #f new-state)))

(define (run m state) (m state))

Now the Haskell-like example given by Neel

(define (number-tree tree)
(if (pair? tree)
(do (left-subtree <- (number-tree (car tree)))
(right-subtree <- (number-tree (cdr tree)))
(unit (cons left-subtree right-subtree)))
(do (n <- get)
(set (+ n 1))
(unit n))))

can be straightforwardly, if a little verbosely (so far)
written in terms of reify and reflect as

(define (number-tree tree)
(if (pair? tree)
(reify
(let* ((left-subtree (reflect (number-tree (car tree))))
(right-subtree (reflect (number-tree (cdr tree)))))
(cons left-subtree right-subtree)))
(reify
(let ((n (reflect get)))
(reflect (set (+ n 1)))
n))))

(run (number-tree '((a . b) . c))
0)
==> ((0 . 1) . 2)

Once again, we can make it a little more concise. Let's define

(define (get*) (reflect get))
(define (set* v) (reflect (set v)))

We'll also rewrite the let* in direct style and factor out
the reify's. This then gives the following concise version:

(define (number-tree tree)
(if (pair? tree)
(cons (number-tree (car tree))
(number-tree (cdr tree)))
(let ((n (get*)))
(set* (+ n 1))
n)))

(run (reify (number-tree '((a . b) . c)))
0)
==> ((0 . 1) . 2)

The usefulness of the Filinski encoding has been underappreciated in
the wider Scheme community, probably in part due to its lack of
accessibility. Hopefully
these examples will help fill the gap for those who are interested.

Regards
Andre

(*) Caveat - in Scheme the order of evaluation of arguments is
undefined, so the translation from let* to direct style in
some of these examples is not strictly correct. Depending
on the problemm, this may or may not matter.



Code follows for reify and reflect in terms of shift and reset:

;=================================================================
; Shift and reset (see Gasbichler and Sperber)

(define-syntax reset
(syntax-rules ()
((_ ?e) (*reset (lambda () ?e)))))

(define-syntax shift
(syntax-rules ()
((_ ?k ?e) (*shift (lambda (?k) ?e)))))

(define *meta-continuation*
(lambda (v)
(error "You forgot the top-level reset...")))

(define *abort
(lambda (thunk)
(let ((val (thunk)))
(*meta-continuation* val))))

(define *reset
(lambda (thunk)
(let ((mc *meta-continuation*))
(call-with-current-continuation
(lambda (k)
(begin
(set! *meta-continuation*
(lambda (v)
(set! *meta-continuation* mc)
(k v)))
(*abort thunk)))))))

(define *shift
(lambda (f)
(call-with-current-continuation
(lambda (k)
(*abort (lambda ()
(f (lambda (v)
(reset (k v))))))))))

(define-syntax reset
(syntax-rules ()
((_ ?e) (*reset (lambda () ?e)))))

(define-syntax shift
(syntax-rules ()
((_ ?k ?e) (*shift (lambda (?k) ?e)))))

(define *meta-continuation*
(lambda (v)
(error "You forgot the top-level reset...")))

(define *abort
(lambda (thunk)
(let ((val (thunk)))
(*meta-continuation* val))))

(define *reset
(lambda (thunk)
(let ((mc *meta-continuation*))
(call-with-current-continuation
(lambda (k)
(begin
(set! *meta-continuation*
(lambda (v)
(set! *meta-continuation* mc)
(k v)))
(*abort thunk)))))))

(define *shift
(lambda (f)
(call-with-current-continuation
(lambda (k)
(*abort (lambda ()
(f (lambda (v)
(reset (k v))))))))))


;-------------------------------------------------------
; Monads from shift and reset (from Filinski, POPL '94)

(define (reflect meaning)
(shift k (bind meaning k)))

(define-syntax reify
(syntax-rules ()
((reify exp)
(reset (unit exp)))))

[Brian McNamara!]

Post by Andre
The Filinski encoding of monads in Scheme is really interesting and
easy to use. Its main advantage is that programs using monads
in Scheme can be expressed in a more concise direct style instead
of the usual monadic style.
Since the literature may be a bit forbidding, here are
The two primitives that we use are *reflect* and *reify*. They
use the monad operations *unit* and *bind*, which we will supply
individually for each monad. The precise definitions of *reflect*
and *reify* are at the end of this message but are not needed to
understand their use.

This is helpful. I'd previously read about reify/reflect in a paper by
Sobel et al. at
http://www.cs.indiana.edu/~jsobel/Parsing/explicit.html
and didn't understand them at all. With your examples, I have a
slightly better understanding, but I'm still missing a lot.

Post by Andre
----------

...

Post by Andre
we can now write the Haskell
do x <- [1, 2]
y <- [5, 6]
return (x, y)
in Scheme as
(reify (let* ((x (reflect '(1 2)))
(y (reflect '(5 6))))
(cons x y)))
==> ((1 . 5) (1 . 6) (2 . 5) (2 . 6))
* We use *reify* to delimit a computation
and return the result as a monadic value (like do ... return).
* The role of <- is played by *reflect*, which extracts an ordinary
value from the monad.
* For explicit sequencing, we can use Scheme's native let*.

As a static typer, it would help me greatly if I knew the (Haskell) type
signature of reify and reflect. I'm not sure if that's a reasonable
question though, since one or both are defined as macros.

In any case, when I was trying to understand the Sobel paper, it seemed
like reflect was merely the identity function. Surely that can't be
right. Help!

...

Post by Andre
(reify (let* ((y (foo 0))
(z (bar y)))
(baz z)))
==> #f
However, we can also write this in the equivalent,
(reify (baz (bar (foo 1)))) ==> 1/2
(reify (baz (bar (foo 0)))) ==> #f
What a nice, concise abstraction! Certainly much better
than writing it all out as follows!
(let ((foo-val (foo x)))
(if foo-val
(let ((bar-val (bar (car foo-val))))
(if bar-val
(baz (car bar-val))
#f))
#f))

With this example, I grok "what" is going on, but have no idea about
"how". Admittedly I have almost no understanding of shift/reset/
continuations; else I would figure it out from the source code at the
end of your message.

I am also curious how a computation that isn't "totally nested" would
turn out. That is, if "qux" took two arguments, and I did something
like

(reify (qux (bar (foo 1))
(bar (foo 1))) )

What happens with regards to evaluation order? (I saw you mentioned
this briefly in your message; I don't recall enough Scheme to know
if/what is the evaluation order for let* and/or for multiple arguments
to a function. Is this related to commutative operations in monads?)

[Andre]

Post by Brian McNamara!
As a static typer, it would help me greatly if I knew the (Haskell) type
signature of reify and reflect. I'm not sure if that's a reasonable
question though, since one or both are defined as macros.

Reify and reflect both contain control operations. You can reason about
them as follows. First, the definition of reify is

reify exp = reset (unit exp)

You can think of *reset* as marking a "control point" in
the code so that any *reflect* evaluated in its scope will behave as
follows:

(reset ...code... (reflect exp) ...morecode...)
^^^^^^^^^^^^^

--> reset (bind exp
(lambda (x) (...code... x ...morecode...)))

In other words, *reflect* will grab its continuation up to the
nearest enclosing *reset* and use that as the second argument to bind.
The continuation is denoted here by (lambda (x) (...a... x ...b...)).

Here bind : (M a) -> (a -> M b) -> (M b) is the same as >>= in Haskell
and unit : a -> M a is the same as return in Haskell.

There is one more evaluation rule that we will need:

(reset value) --> value
^^^^^^^^^^^^^

EXAMPLE:
-------

To see how to use these rules, let's evaluate:

(reify (cons (reflect '(1))
(reflect '(5 6))) ==> ((1 . 5) (1 . 6))

At each stage I will underline the piece that is getting reduced.
Remember that Scheme evaluates arguments before applying functions,
and I am assuming a left-to-right order of evaluation for simplicity.

(reify (cons (reflect '(1)) (reflect '(5 6)))

= (reset (unit (cons (reflect '(1)) (reflect '(5 6))) by definition
^^^^^^^^^^^^^^ of reify

--> reset (bind '(1)
(lambda (x) (unit (cons x (reflect '(5 6))))))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

--> reset (apply append (map (lambda (x) (unit (cons x (reflect '(5 6)))))
'(1)))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

--> reset (apply append (unit (cons 1 (reflect '(5 6)))))
^^^^^^^^^^^^^^^^

--> reset (bind '(5 6)
(lambda (y) (apply append (unit (cons 1 y))))))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

= reset (map (lambda (y) (apply append (unit (cons 1 y))))
'(5 6))
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

= reset '((1 . 5) (1 . 6))
^^^^^^^^^^^^^^^^^^^^^^^^

= '((1 . 5) (1 . 6))

Post by Brian McNamara!
I am also curious how a computation that isn't "totally nested" would
turn out. That is, if "qux" took two arguments, and I did something
like
(reify (qux (bar (foo 1))
(bar (foo 2))) )
What happens with regards to evaluation order? (I saw you mentioned
this briefly in your message; I don't recall enough Scheme to know
if/what is the evaluation order for let* and/or for multiple arguments
to a function. Is this related to commutative operations in monads?)

Officially, argument evaluation order in Scheme is undefined (although
all arguments of a function have to be evaluated before the function
itself is evaluated). So in your example, either (bar (foo 2)) or
(bar (foo 1)) may be evaluated first. To sequence evaluation order,
you may use let*, which evaluates top to bottom.

So strictly speaking, the expression

(reify (qux (bar (foo 1))
(bar (foo 2))) )

is only correct if the monad is commutative. Also, strictly speaking
the expression

(reify (cons (reflect '(1 2))
(reflect '(5 6)))

is incorrect for the List monad but would be correct for the Set monad,
which is commutative (i.e., using union instead of append). For the List
monad, we should really have used let*.

So the unspecified argument evaluation order in Scheme
gives a nice way for expressing commutative monads
(it seems that there has been some soul-searching among
Haskellers regarding whether the do-notation is really
optimal for commutative monads). On the other hand, there is no
mechanism enforcing correct use in Scheme...

Regards
Andre

[Maciek Godek]

I see that the thread is almost two decades old but...

a while ago I wrote an explanation of monads that exploits the syntax of Lisp:

https://www.quora.com/How-would-you-explain-a-concept-of-monads-to-a-non-CS-person/answer/Panicz-Godek

One could say that it uses a pure subset of Scheme, or "Cambridge Polish notation lambda-caluclus"