Neelakantan Krishnaswami (Neel) once wrote to comp.lang.dylan:
> Honestly, my Dylan code is more functional than my Ocaml code.
> This is because I find it easier to write in a state-passing
> or monadic style in Dylan than in Caml.
> I find Dylan nicer for writing state-passing code because of
> a nasty habit: I care about memory allocation.
> Dylan's multiple return values can be stack allocated, whereas
> using a tuple won't be. Even though I *know* that I shouldn't
> care, I do. :)
> The combination of generic functions makes a modular monadic
> style almost ridiculously easy to do. I tend to cheat a bit,
> and use macros to eliminate the overhead of a monadic style, too.
Can someone explain
* How the combination of generic functions makes a modular monadic
style almost ridiculously easy to do.
and give an example.
Also I appreciate an explanation for
* How to use macros to eliminate the overhead of a monadic style
and an example.
I read some monad papers, but I did not graps how to use them in a
practical way. (As you can see from my questions.)
Peter
--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
On Fri, 16 Jun 2006 07:52:32 +0000, Peter Robisch wrote:
> Can someone explain
> * How the combination of generic functions makes a modular monadic
> style almost ridiculously easy to do.
> and give an example.
Well, back when I was trying to explain threads to myself it was easiest
for me, for whatever reason, to think them as a monad with subtypes that
described the state of a computation. Generic functions made it easy to
compartmentalize the action going on in the subtypes:
(in-package :concur)
;;;;a simple, preemptive thread trampoline implemented as a monad
(defparameter *schedule-quantum* 20)
;;;this is a thin wrapper around defclass that automatically generates
;;;constructors, etc.
(def-datatype thread
(done (val t))
(running (thunk function))
(receiving (message-queue queue)
(cont function))
(sending (thunk function)
(message-queue queue)
(message thread))
(thread-pair (thread1 thread)
(thread2 thread)))
(defmethod unit ((type (eql 'thread)) val)
(done val))
(defun thread-reduce (thread)
(declare (type running thread))
(funcall (thunk thread)))
;;;give runnable threads their time in the sun
(defgeneric ticker (thread count)
(:method ((thread thread) count)
(step-thread thread)))
(defmethod ticker :around ((thread running) (count fixnum))
(if (> count 1)
(ticker (call-next-method) (1- count))
(call-next-method)))
(defmethod ticker :around ((thread sending) (count fixnum))
(if (> count 1)
(ticker (call-next-method) (1- count))
(call-next-method)))
;;give us some (quasi) indeterminacy
(defun step-threads (thread1 thread2)
(if (zerop (random 2))
(let ((t1 (ticker thread1 *schedule-quantum*)))
(values t1 (ticker thread2 *schedule-quantum*)))
(let ((t2 (ticker thread2 *schedule-quantum*)))
(values (ticker thread1 *schedule-quantum*) t2))))
;;; thread -> thread
(defgeneric step-thread (thread)
(:method ((thread running))
(thread-reduce thread))
;;in async channels, send should never block
;;of course you could run out of space :)
(:method ((thread sending))
(let ((queue (message-queue thread)))
(push-val queue (message thread))
(running (thunk thread))))
;;receive blocks if there are no pending messages
(:method ((thread receiving))
(let ((queue (message-queue thread)))
(if (empty-p queue)
thread
(let ((message (pull queue))
(cont (cont thread)))
(running
#'(lambda ()
(funcall cont message)))))))
;;heart of the stepper
(:method ((thread thread-pair))
(let ((thread1 (thread1 thread))
(thread2 (thread2 thread)))
;;should both be halted before a return?
(if (and (done-p thread1) (done-p thread2))
thread1
(multiple-value-bind (thread1 thread2)
(step-threads thread1 thread2)
(thread-pair thread1 thread2)))))
;;we're done with this branch of the evaluation
(:method ((thread done))
thread))
;;;allows stepwise evaluation
;;;each step in the evaluation gets wrapped in
;;;another thunk
(defmethod bind ((monad-val running) next)
(let* ((thunk (thunk monad-val))
(new-thunk #'(lambda ()
(let ((val (funcall thunk)))
(bind val next)))))
(running new-thunk)))
;;;nothin' to do
(defmethod bind ((monad-val done) next)
(let ((val (val monad-val)))
(running #'(lambda ()
(funcall next val)))))
;;;tack another pending operation onto the continuation
(defmethod bind ((monad-val receiving) next)
(let* ((old-cont (cont monad-val))
(new-cont #'(lambda (m-val)
(bind (funcall old-cont m-val)
next))))
(receiving (message-queue monad-val) new-cont)))
;;;tack another pending operation onto the continuation
(defmethod bind ((monad-val sending) next)
(let* ((old-thunk (thunk monad-val))
(new-thunk #'(lambda ()
(bind (funcall old-thunk)
next))))
(sending new-thunk (message-queue monad-val) (message monad-val))))
;;;tack another pending operation onto the thread that will
;;;eventually return a value (thread1)
(defmethod bind ((monad-val thread-pair) next)
(let* ((old-thread (thread1 monad-val))
(new-thread (running #'(lambda ()
(bind old-thread
next)))))
(thread-pair new-thread (thread2 monad-val))))
;;;go get 'em boys
(defmethod run ((monad-val thread))
(run (step-thread monad-val)))
;;;we're all done, return the result
(defmethod run ((monad-val done))
(val monad-val))
;;;some macrology to make it less ugly
(defmacro fork-threads (&rest exprs)
(reduce #'(lambda (current rest)
`(fork2 ,current ,rest))
exprs
:from-end t))
(defmacro fork2 (exp1 exp2)
`(thread-pair (running #'(lambda () ,exp1))
(running #'(lambda () ,exp2))))
(defmacro send-msg (message-queue message)
`(sending #'(lambda () (unit 'thread nil))
,message-queue
(unit 'thread ,message)))
(defmacro recv-msg (message-queue)
`(receiving ,message-queue
#'identity))
Of course, it's not completely functional (the message-queue), and the
style has a bit of overhead in the large amount of consing it does.
A good example of using macros to trim monadic style code is the
implementation of a subset of the Kanren logic language in "The
Reasoned Schemer"
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Peter Robisch wrote:
> Can someone explain
> * How the combination of generic functions makes a modular monadic
> style almost ridiculously easy to do.
> and give an example.
Since you posted this to comp.lang.lisp, I thought I'd try to write
some monadic code in lisp. But I got snagged up when I tried to
implement a generic version of "return". Here's my attempt so far...
;;; list monad
(defmethod >>= ((a sequence) f)
(mapcan f a))
(defmethod list-return (a)
(list a))
;;; maybe monad
(defclass Just ()
(val))
(defun just (x)
(let ((y (make-instance 'Just)))
(setf (slot-value y 'val) x)
y))
(defmethod print-object ((a Just) stream)
(format stream "Just ~A" (slot-value a 'val)))
(defmethod >>= ((a Just) f)
(funcall f (slot-value a 'val)))
(defclass Nothing () ())
(defmethod >>= ((a Nothing) f)
(make-instance 'Nothing))
(defmethod maybe-return (a)
(just a))
...where I had to use specific instances of "return" instead of a
generic one. So something like this works fine...
(defun foo-list (x)
(>>= x #'(lambda (a) (list-return (1+ a)))))
(defun foo-maybe (x)
(>>= x #'(lambda (a) (maybe-return (1+ a)))))
...but it would be better to have...
;(defun foo-generic-monad (x)
; (>>= x #'(lambda (a) (monad-return (1+ a)))))
...where "monad-return" works for any monad. The problem is that the
type for "return" in Haskell is...
return :: (Monad m) => a -> m a
...which means we'd need to do dispatch on the result type, instead of
just argument types. So I'd also be interested in what the lisp idiom
would be to enable generic monadic programming.
> Also I appreciate an explanation for
> * How to use macros to eliminate the overhead of a monadic style
> and an example.
Maybe Haskell-like do-notation?...
(defmacro do-monad (&rest x)
(labels ((helper (x &rest xs)
(if (null xs)
x
`(>>= ,(cadr x) (lambda (,(car x))
,(apply #'helper xs))))))
(apply #'helper x)))
(print
(do-monad (a '(1 2 3))
(b '(4 5 6))
(list-return (+ a b))))
From: Matthew D Swank
Subject: Re: Dispatch on return type (was: How to use a modular monadic style with generic function?)
Date:
Message-ID: <pan.2006.06.16.21.55.15.866722@c.net>
On Fri, 16 Jun 2006 12:24:25 -0700, Greg Buchholz wrote:
> ;(defun foo-generic-monad (x)
> ; (>>= x #'(lambda (a) (monad-return (1+ a)))))
>
> ...where "monad-return" works for any monad. The problem is that the
> type for "return" in Haskell is...
>
> return :: (Monad m) => a -> m a
>
> ...which means we'd need to do dispatch on the result type, instead of
> just argument types. So I'd also be interested in what the lisp idiom
> would be to enable generic monadic programming.
Well, there maybe other ways, but the two lisp-y ways that come to mind
are special-vars:
(defvar *return* #'identity)
(defun monad-return (val)
(funcall *return* val))
(defmacro with-return (ret &body body)
`(let ((*return* ,ret))
,@body))
But this can get you into trouble when the monad is a closure, or when you
are using monad transformers.
Another technique is to use an eql specifier:
(defgeneric monad-return (type val))
(defmethod monad-return ((type (eql 'list)) ;we agree this is the return
;type
val)
...stuff for lisp)
(defmethod monad-return ((type (eql 'maybe))
val)
...stuff for maybe)
This of course runs into inheritance issues, but that might even be
solvable with some macrology (a la Seibel's binary class lib, my current,
favorite, accessible extension to CLOS-- just enough to be cool yet
compact, but not so big that you have to grok a large, special purpose
interpreter just to understand it).
>
>> Also I appreciate an explanation for
>> * How to use macros to eliminate the overhead of a monadic style
>> and an example.
>
> Maybe Haskell-like do-notation?...
>
> (defmacro do-monad (&rest x)
> (labels ((helper (x &rest xs)
> (if (null xs)
> x
> `(>>= ,(cadr x) (lambda (,(car x))
> ,(apply #'helper xs))))))
> (apply #'helper x)))
It think that's more sugar than overhead elimination. The big thing is
reduce the amount of closures and structure instances the machinery has to
create.
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Peter Robisch wrote:
> Can someone explain
> * How the combination of generic functions makes a modular monadic
> style almost ridiculously easy to do.
> and give an example.
I'm not quite sure what is meant by this exactly, however:
> Also I appreciate an explanation for
> * How to use macros to eliminate the overhead of a monadic style
> and an example.
For examples of this, look into Haskell. It doesn't have macros
(although there is an extension to the language which adds them), but
it does have special syntax to make monadic programming easy (it
basically looks like imperative programming).
For example, Haskell uses monads for I/O. Say you want to write a
program that reads a character and prints it back to the screen.
Without special syntax, that would look something like this:
main = getChar >>= \c ->
putChar c
However, with the special syntax (do-notation, as it's called), you can
instead write that as:
main = do c <- getChar
putChar c
The transformations Haskell does are a little more general than simply
converting the lower to the upper form, but that's the basic idea.
P. Abate of www.anu.edu.au wrote:
Consider this ocaml code:
---------------------
let return x = [x]
let bind m f = List.flatten ( List.map f m )
let mzero = []
let mplus = List.append
let guard b = if b then return () else mzero
let rec select = function
|[] -> mzero
|a::x -> mplus (return (a,x)) (bind (select x) ( fun (b,x') -> return
(b,a::x') ))
let notin q l = not(List.mem q l)
let range n =
let rec aux i l =
if i = 0 then l else i::(aux (i-1) l)
in List.rev ( aux n [] )
let rec place i rs d1 d2 = match i with
|0 -> return []
|i ->
bind (select rs) (fun (q,rs') -> (* select one queen *)
let q1 = q - i in
let q2 = q + i in
bind (guard (notin q1 d1)) (fun r1 ->
bind (guard (notin q2 d2)) (fun r2 ->
bind (place (i-1) rs' (q1::d1) (q2::d2)) (fun qs ->
(return (q::qs))))))
let queen n = place n (range n) [] []
-------------------
This example is a bad translation in ocaml from this paper:
[1] http://www.cs.uni-bonn.de/~ralf/publications/IAI-TR-96-9.ps.gz
This was one of the motivating examples for me on how to use mondads in
a practical way. And other good example is to write a small
interpreter...
At the top, I've give a monad (plus) in terms of lists. In ocaml lists
are not lazy as in haskell, and therefore the backtracking here is
expensive. Substituting the for operation on the top with a lazy version
allows you to add this feature in a modular way. If you were writing the
same example in haskell, you could have add IO by transforming the
initial monad in a state monad (I think). If you want both, you could
use a monad transformer to combine a state monad and a backtracking
monad... and so on so forth.
Question: A friend told me that monad transformers are dead ... Is this
true ? I've tried to write a library of monad transformers in ocaml from
[1], but I got stuck (maybe because the ocaml type system doesn't have
\forall type quantifiers ??? while haskell does).
Do you people use these transformers or you write each and all your new
monads from scratch ?
Reg macros and friends you might want to have a look at this camlp4
extension: http://www.cas.mcmaster.ca/~carette/pa_monad/
:)
--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
From: Matthew D Swank
Subject: Re: How to use a modular monadic style with generic function?
Date:
Message-ID: <pan.2006.06.17.20.33.10.4146@c.net>
On Sat, 17 Jun 2006 20:22:33 +0000, Peter Robisch wrote:
> P. Abate of www.anu.edu.au wrote:
>
> Consider this ocaml code:
>
...
And you are posting this follow-up to comp.lang.lisp because...?
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Peter Robisch wrote:
> Question: A friend told me that monad transformers are dead ... Is this
> true ?
I must admit, my haskell experience so far has been mostly paper
reading and doing small experiments with the concepts presented in said
papers. However, monad transformers seem useful to me. For instance, in
the case of parser combinators, in:
http://www.cs.nott.ac.uk/~gmh/monparsing.ps
It's pointed out that the parser monad is equivalent to:
type Parser a = StateT String [] a
And you can add parser position tracking (for the offside rule) by
wrapping that in a ReaderT.
I've also been playing around trying to make an Erlang-alike syntax for
discrete message-passing processes, and what I came up with wraps the
IO monad with the ReaderT transformer to implicitly pass around a
channel in each process.
In any case, the Haskell libraries come with a bunch of monad
transformers (reader, writer, state, cps, list...), so they can't
exactly be 'dead.'
I feel more comfortable in Dylan (as in Haskell or Ocaml). In my posting
I quoted this comp.lang.dylan message:
http://people.csail.mit.edu/gregs/info-dylan-archive-html-2001/msg00804.html
Neel in this message also wrote:
> What I really miss in Dylan [...] the parametric polymorphism (Dylan uses
> dynamic typing plus I guess parts of a metaobject protocol to simulate
> this. It works fine, but I miss the compile-time guarantees.)
The wikipedia writes about "Generic Function":
> In certain systems for object-oriented programming such as the Common Lisp
> Object System and Dylan, a generic function is an entity made up of all
> methods having the same name. [...] An other, completely separate
> definition of generic function is a function that uses parametric
> polymorphism. This is the definition used when working with a language
> like OCaml.
So Ocalm and Haskell on one side and Dylan on the other (seems to)
distinguish a little bit in their understanding of the term "generic
function".
As one of the repliers wrote
> ps: I know anything about Dylan or Haskell...
Could you transfer your example to Dylan? :-)
Otherwise I will try it and hope on your comments.
pet-ro
--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
From: Aaron Denney
Subject: Re: How to use a modular monadic style with generic function?
Date:
Message-ID: <slrne98u75.ek5.wnoise@ofb.net>
["Followup-To:" header set to comp.lang.functional.]
On 2006-06-17, Peter Robisch <·············@gmx.net> wrote:
> I feel more comfortable in Dylan (as in Haskell or Ocaml). In my posting
> I quoted this comp.lang.dylan message:
>
> http://people.csail.mit.edu/gregs/info-dylan-archive-html-2001/msg00804.html
>
> Neel in this message also wrote:
>> What I really miss in Dylan [...] the parametric polymorphism (Dylan uses
>> dynamic typing plus I guess parts of a metaobject protocol to simulate
>> this. It works fine, but I miss the compile-time guarantees.)
>
> The wikipedia writes about "Generic Function":
>> In certain systems for object-oriented programming such as the Common Lisp
>> Object System and Dylan, a generic function is an entity made up of all
>> methods having the same name. [...] An other, completely separate
>> definition of generic function is a function that uses parametric
>> polymorphism. This is the definition used when working with a language
>> like OCaml.
>
> So Ocalm and Haskell on one side and Dylan on the other (seems to)
> distinguish a little bit in their understanding of the term "generic
> function".
>
> As one of the repliers wrote
>> ps: I know anything about Dylan or Haskell...
> Could you transfer your example to Dylan? :-)
>
> Otherwise I will try it and hope on your comments.
"generics" is a bit of an overloaded term. The best definition I've
heard is "the type of polymorphism that your language doesn't (yet)
have."
--
Aaron Denney
-><-