composing monads
David A. Herman
using continuations and monads because... well, because I can. I'm
learning lots in the process.
I read the chapter on `amb' in SICP and it took my breath away. The
implementation in t-y-scheme is instructive but the use of set! is not so
pretty for my purposes. Since a particular evaluation might not exhaust
all possibilities before terminating, the next call to amb will continue
where it left off; it doesn't flush the cached failure continuation. And
of course it can't, because the framework doesn't know when you're "all
done". So you end up having to sandwich your code between calls to reset
the failure procedure.
It seems I should use a monad to carry along the failure procedure. A
parser needs to be able to make use of this in various ways; imagine an
"alt" pattern ("x or y or z") or a "seq" pattern ("x then y then z")
taking some number of patterns and a success and failure continuation:
alt(x,y,z)<KS,KF> = x -- KS seq(x,y,z)<KS,KF> = x -- KF
| |
y -- KS y -- KF
| |
z -- KS z -- KF
| |
KF KS
For alt, any single success is an overall success, and for seq any single
failure is an overall failure.
But I already have a monad that passes along the state of the parse --
since my goal is a pure-functional parser, the "cursor" is implemented as
a monad. This should be great for backtracking, too, because jumping
backwards in the computation is totally safe without mutable state.
What I'm unsure of is how to compose monads: I've got the one monad that
passes along the state of the input, and now I want another one that
passes along the state of the computation, specifically, the current
failure procedure. Do I overload the single unit/bind procedures to handle
both of those? Since some of the high-level procedures have to produce
"answers" of the monad's type, this seems like a violation of an
abstraction boundary. So I think I need to compose the two frameworks, so
that the backtracking monad is invisible to the parsing monad. Am I on the
right track? (no pun intended)
Dave
prunes...@attbi.com
> I'm writing a pure-functional, backtracking, recursive-descent parser
> using continuations and monads because... well, because I can.
>
> [snip]
>
> What I'm unsure of is how to compose monads: I've got the one monad that
> passes along the state of the input, and now I want another one that
> passes along the state of the computation, specifically, the current
> failure procedure. Do I overload the single unit/bind procedures to handle
> both of those? Since some of the high-level procedures have to produce
> "answers" of the monad's type, this seems like a violation of an
> abstraction boundary. So I think I need to compose the two frameworks, so
> that the backtracking monad is invisible to the parsing monad. Am I on the
> right track? (no pun intended)
I believe that the usual technique is to overload the unit/bind
procedures.
Have you made progress?
David A. Herman
> procedures.
>
> Have you made progress?
I haven't had much time to work on this lately, but a helpful response
pointed me to David Espinosa's PhD thesis on "Semantic Lego," which from
what I've read so far seems to be exactly what I was looking for (chapter
2.4 is called "Monads don't compose" and chapter 2.5 is called "Monads do
compose").
The problem Espinosa tackles is that denotational semantics are not
modular, so you can't construct them as easily as computer programs.
Semantic Lego, AFAICT, is a module system for denotational semantics --
so, for example, you can plug an exception monad and a store monad into an
interpreter as independent building blocks.
At least, that's what I've gleaned so far. Now the real trick will be
reading and (gulp) understanding his thesis.
Dave