Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

617 views

Skip to first unread message

Feb 17, 2004, 4:43:52 PM2/17/04

to

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

Feb 17, 2004, 5:23:48 PM2/17/04

to

In article <gNOSPAMat-170...@k-137-79-50-101.jpl.nasa.gov>,

Erann Gat <gNOS...@jpl.nasa.gov> wrote:

(snip)

>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)

Erann Gat <gNOS...@jpl.nasa.gov> wrote:

(snip)

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

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

Feb 17, 2004, 5:35:20 PM2/17/04

to

gNOS...@jpl.nasa.gov (Erann Gat) once said:

>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?

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

--

Brian M. McNamara lor...@acm.org : I am a parsing fool!

** Reduce - Reuse - Recycle ** : (Where's my medication? ;) )

Feb 17, 2004, 6:50:47 PM2/17/04

to

On Tue, 17 Feb 2004 13:43:52 -0800, Erann Gat wrote:

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

--

__("< Marcin Kowalczyk

\__/ qrc...@knm.org.pl

^^ http://qrnik.knm.org.pl/~qrczak/

Feb 17, 2004, 6:38:31 PM2/17/04

to

In article <8Zc*Du...@news.chiark.greenend.org.uk>, Mark Carroll

<ma...@chiark.greenend.org.uk> wrote:

<ma...@chiark.greenend.org.uk> wrote:

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.

Feb 17, 2004, 6:40:53 PM2/17/04

to

In article <c0u4v8$j74$1...@news-int.gatech.edu>, gt5...@prism.gatech.edu

(Brian McNamara!) wrote:

(Brian McNamara!) wrote:

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

Feb 17, 2004, 7:31:12 PM2/17/04

to

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

<qrc...@knm.org.pl> wrote:

<qrc...@knm.org.pl> wrote:

>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

Feb 17, 2004, 7:42:45 PM2/17/04

to

gNOS...@jpl.nasa.gov (Erann Gat) once said:

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.

Feb 17, 2004, 7:11:57 PM2/17/04

to

In article <gNOSPAMat-170...@k-137-79-50-101.jpl.nasa.gov>,

gNOS...@jpl.nasa.gov (Erann Gat) wrote:

gNOS...@jpl.nasa.gov (Erann Gat) wrote:

> In article <8Zc*Du...@news.chiark.greenend.org.uk>, Mark Carroll

> <ma...@chiark.greenend.org.uk> wrote:

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

Feb 17, 2004, 8:21:05 PM2/17/04

to

On Tue, 17 Feb 2004 16:11:57 -0800, gNOS...@jpl.nasa.gov (Erann Gat)

wrote:

wrote:

>The first non-trivial example is this:

>

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

>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

Feb 17, 2004, 8:44:19 PM2/17/04

to

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

>

> 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". :)

> "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).

> 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

server speak with each other:

> 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

l...@iki.fi

Feb 17, 2004, 9:24:17 PM2/17/04

to

"Erann Gat" <gNOS...@jpl.nasa.gov> wrote in message

news:gNOSPAMat-170...@k-137-79-50-101.jpl.nasa.gov...

> 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

Feb 18, 2004, 3:02:46 AM2/18/04

to

Lauri Alanko <l...@iki.fi> writes:

> Erann Gat <gNOS...@jpl.nasa.gov> wrote:

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

> 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

--

If I haven't seen further, it is by standing in the footprints of giants

Feb 18, 2004, 12:26:23 PM2/18/04

to

In article <gNOSPAMat-170...@k-137-79-50-101.jpl.nasa.gov>, Erann

Gat wrote:

>

> 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?

>

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

--

Neel Krishnaswami

ne...@cs.cmu.edu

Feb 18, 2004, 12:36:17 PM2/18/04

to

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

>

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

Feb 18, 2004, 1:01:05 PM2/18/04

to

Neelakantan Krishnaswami <ne...@cs.cmu.edu> writes:

> 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: 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

Feb 18, 2004, 1:44:30 PM2/18/04

to

Neelakantan Krishnaswami <ne...@cs.cmu.edu> writes:

>[...]

> 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. :)

>[...]

>[...]

> 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

Feb 18, 2004, 3:04:45 PM2/18/04

to

In article <m1vfm4n...@tti5.uchicago.edu>, Matthias Blume wrote:

> Neelakantan Krishnaswami <ne...@cs.cmu.edu> writes:

>>

>> 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)))

>

> Neelakantan Krishnaswami <ne...@cs.cmu.edu> writes:

>>

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

> to satisfy even just the first law:

>

> to satisfy even just the first law:

>

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

> 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. :)

--

Neel Krishnaswami

ne...@cs.cmu.edu

Feb 18, 2004, 9:53:38 PM2/18/04

to

In article <slrnc3781u...@gs3106.sp.cs.cmu.edu>, Neelakantan

Krishnaswami <ne...@cs.cmu.edu> wrote:

Krishnaswami <ne...@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.

Feb 19, 2004, 3:00:29 PM2/19/04

to

Just in case: The second part of the article "Multiple values as an

effect" talks about monadic reflection and reification in Scheme:

effect" talks about monadic reflection and reification in Scheme:

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

and gives practical examples.

Feb 20, 2004, 2:21:12 PM2/20/04

to

In article <c0ug1j$rdb$1...@oravannahka.helsinki.fi>, Lauri Alanko

<l...@iki.fi> wrote:

<l...@iki.fi> wrote:

[An explanation of how a Haskell server can be written as main ::

[Response] -> [Request]]

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

Feb 22, 2004, 5:23:22 PM2/22/04

to

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.

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

Feb 24, 2004, 7:32:20 AM2/24/04

to

>>>>> "Erann" == Erann Gat <gNOS...@jpl.nasa.gov> writes:

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/

--

Cheers =8-} Mike

Friede, Völkerverständigung und überhaupt blabla

Feb 24, 2004, 9:22:25 AM2/24/04

to

In article <gNOSPAMat-200...@k-137-79-50-101.jpl.nasa.gov>,

Erann Gat <gNOS...@jpl.nasa.gov> wrote:

> One last question about this: if you actually write a server this way, how

> do you keep from running out of memory?

Erann Gat <gNOS...@jpl.nasa.gov> wrote:

> 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

l...@iki.fi

Feb 24, 2004, 1:08:39 PM2/24/04

to

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.

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)))))

Feb 24, 2004, 2:15:03 PM2/24/04

to

Andre <an...@het.brown.edu> once said:

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

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

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.

>LIST MONAD:

>----------

...

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

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!

...

>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))

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?)

Feb 24, 2004, 4:24:20 PM2/24/04

to

"Brian McNamara!" wrote:

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

> 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))

> 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

Feb 27, 2004, 4:24:55 PM2/27/04

to

Erann Gat wrote:

> In article <c0ug1j$rdb$1...@oravannahka.helsinki.fi>, Lauri Alanko

><l...@iki.fi> wrote:

>

> [An explanation of how a Haskell server can be written as main ::

> [Response] -> [Request]]

> In article <c0ug1j$rdb$1...@oravannahka.helsinki.fi>, Lauri Alanko

><l...@iki.fi> wrote:

>

> [An explanation of how a Haskell server can be written as main ::

> [Response] -> [Request]]

I think that in this situation the Haskell program is a client, and the

"world" acts as a server.

Best regards,

Tom

--

.signature: Too many levels of symbolic links

Mar 5, 2004, 1:31:04 PM3/5/04

to

Neelakantan Krishnaswami <ne...@cs.cmu.edu> writes:

>>> (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)))

>>

In article <m1vfm4n...@tti5.uchicago.edu>, Matthias Blume wrote:

>> I'm going to be more picky here, because, unfortunately, this "monad" fails

>> to satisfy even just the first law:

>>

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

Feb 4, 2020, 11:20:48 AM2/4/20

to

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"

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"

0 new messages