 Representing Monads
started 3/24/2003; 8:06:12 AM - last post 3/27/2003; 9:07:54 AM
|
|
Ehud Lamm - Representing Monads 
3/24/2003; 8:06:12 AM (reads: 2386, responses: 5)
|
|
| Representing Monads |
|
Andrzej Filinski. Representing monads. In Conference Record of POPL '94: 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Portland, Oregon, pages 446--457
We show that any monad whose unit and extension operations are expressible as purely functional terms can be embedded in a call-by-value language with "composable continuations".
Another way of stating this result is to say that any monadic effect whose definition is itself experssible in a functional language can be synthesize from just two "impure" constructs: first-class continutations and a storage cell. Thus languages like Scheme and ML are, in fact, "monadically complete" in the sense that any program expressible in the somewhat contorted monadic style can also be written direct style.
This is a rather technical paper, that discusses the connection between monads, CPS, and composable continutations.
Posted to functional by Ehud Lamm on 3/24/03; 8:15:46 AM
|
|
|
|
Frank Atanassow - Re: Representing Monads
3/25/2003; 4:32:35 AM (reads: 668, responses: 4)
|
|
|
This paper (actually, I think I read his thesis) is, indeed, very surprising and interesting. What's cool about it is that it shows how you can take any ML program and change its behavior without even touching the program. For example, you could add non-determinism to a program by lifting it over a backtracking monad.
It's sort of amazing that no one has ever taken advantage of this capability (so far as I know).
|
|
Ehud Lamm - Re: Representing Monads
3/25/2003; 5:06:15 AM (reads: 710, responses: 3)
|
|
|
by lifting it over a backtracking monad.
I wonder how many people in the world understand this expression...
|
|
Frank Atanassow - Re: Representing Monads
3/26/2003; 4:44:54 AM (reads: 728, responses: 2)
|
|
|
I wonder how many people in the world understand this expression...
For example, you could write a program which finds one root of a polynomial, and without any changes transform it into a program which finds all roots of a polynomial.
|
|
Ehud Lamm - Re: Representing Monads
3/26/2003; 11:31:50 AM (reads: 744, responses: 1)
|
|
|
I am sure most people here understand what backtracking means, and understand the discussion about the Screamer implementation. I was wondering about the (more arcane) expression "lifting over a monad."
|
|
Frank Atanassow - Re: Representing Monads
3/27/2003; 9:07:54 AM (reads: 755, responses: 0)
|
|
|
I meant, given a monad transformer t, the operation of transforming an expression in some language with semantics given by a monad m, to an expression in the language over with semantics given by a monad (t m).
For example, transforming
f t
to
\ fm -> \ tm -> do { f <- fm; t <- tm; return (f t) }
See:
Sheng Liang, Paul Hudak and Mark Jones.
Monad Transformers and Modular Interpreters,
Proc. POPL '95.
(CiteSeer)
|
|
|
|