Dylan - How to use a modular monadic style with generic function?

Author

How to use a modular monadic style with generic function?

Peter Robisch

2006-06-17, 8:10 am

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

dan.doel@gmail.com

2006-06-17, 8:10 am

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.

Peter Robisch

2006-06-17, 6:59 pm

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/pub...I-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

Peter Robisch

2006-06-17, 6:59 pm

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/i...1/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

Aaron Denney

2006-06-17, 6:59 pm

["Followup-To:" header set to comp.lang.functional.]
On 2006-06-17, Peter Robisch <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/i...1/msg00804.html
>
> Neel in this message also wrote:
>
> The wikipedia writes about "Generic Function":
>
> 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
> 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
-><-

dan.doel@gmail.com

2006-06-17, 9:59 pm

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

Sponsored Links