Monads in Scheme?
Andre
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!
>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?)
--
Brian M. McNamara lor...@acm.org : I am a parsing fool!
** Reduce - Reuse - Recycle ** : (Where's my medication? ;) )
Andre
> 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