Re: Language Design

["Daan Leijen" <daan@cs.uu.nl>]

> Thanks. Now, somewhere linked to the Haskell web site,
> is an article about 'Arrows', which explains why it was found
> Monads are inadequate. I recall the issue was related
> to interfacing to CGI scripts and preserving state between
> interactions. Sorry I don't have URL handy :-(

Hello John,

The excellent article about arrows was written by John Hughes:
http://www.cs.chalmers.se/~rjmh/

I don't think that the article says that "Monads are inadequate"
(since monads are more general than arrows) but you can say
that Arrows are sometimes a better choice than monads depending
on your problem domain.

I think that in general Monads are easier to use (and understand) than arrows
and would urge you to try the monadic way first.  I believe that there are
only 2 significant reasons why one should prefer arrows over monads.

*The first reason is about control over evalutation time. Let me elaborate
this with an example of an arrow-style parser (1) and a monadic style parser (2).
The main operators of the monadic parser are return and bind:

return :: a -> Parser a
(>>=) :: Parser a -> (a -> Parser b) -> Parser b

The main operators of the arrow style parser are also a return (succeed) and some flavor of bind:

succeed :: a -> Parser a
(<*>)    :: Parser a -> Parser (a->b) -> Parser b

Now, from the type of the monadic bind, it becomes clear that a program can never access the
second parser (Parser b) until you have executed the first one, since the second one depends on
the returned runtime value 'a'.  Not so for the arrow style combinator. Allthough you still have to
execute the parsers to get the runtime values, it is possible to do something with the "Parser x"
data type before actually parsing anything.
This is exactly what Doaiste Swierstra does in his paper (1) to construct parse tables before
running the parser.

Arrow style parser can only parse context-free grammars  (since a parser cannot depend on the result
of another parser) whereas Monadic style parsers can parse any (even a context-sensitive) grammar.

The second reason for choosing arrow style combinators is for finer control about life-times.
I will elaborate on this using the CGI example. The example of John Hughes is something
like this:

test = arr (\z -> "give the question ?") >>> ask >>>
         (arr id &&& ask) >>>
         arr (\(q,a) -> "The answer to '" ++ q ++ "' is " ++ a)

it first sends the string "give the question" over to the client (ask), the response is kept in two
places (&&&), one just to send it to the third action (arr id) and one where the response is
immediately send to the client (ask), the result of this ((q,a)) is then printed.

Note that the lifetime of each value is kept within the function in the 'arr' combinator. (=
succeed).
That is why we need to explicitly thread the response through the second action with the "arr id"
expression,
in order to get it finally in the "q" of the last action. By being so explicit about the lifetimes,
it is possible
to only save the minimal state necessary between client/server interactions in the CGI problem
domain.

With monads, each time we bind a value, the values will be accessible by all following actions. The
same
CGI example in monadic style looks easier in my opinion:

test   = do{ question <- ask "what is the question ?"
                ; answer   <- ask question
                ; return ("the answer to '" ++ question ++ "' is " ++ answer)
                }

The same techniques to implement the CGI server work also with the monadic style, the only
difference is
that we now always save the entire set of values that could be accessed, instead of a more minimal
set.
For example, we don't have to thread the value of "question" around, it can be immediately accessed
on the third action.  (I have a small example implementation of both a monadic and arrow style CGI
framework
that works with Hugs, if you are interested in the different approaches it might be interesting to
look at it,
just send me an email)


 Pheew, I hope this helps you in determining the best implementation technique.
For now, I would advise you to stick with monads and adapt later if necessary.

All the best,
    Daan.

(1) Doaitse Swierstra and Luc Duponcheel. (1996)
Deterministic, Error-Correcting Combinator Parsers.
Advanced Functional Programming. LNCS 1129: 185-207.
http://www.cs.uu.nl/groups/ST/Software.

(2) Graham Hutton and Erik Meijer. (1996)
Monadic Parser Combinators.
Technical report NOTTCS-TR-96-4. Department of Computer Science, University of Nottingham.
http://www.cs.nott.ac.uk/Department/Staff/gmh/monparsing.ps.
(this article is highly recommended :-)



> --
> John (Max) Skaller, mailto:skaller@maxtal.com.au
> 10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
> checkout Vyper http://Vyper.sourceforge.net
> download Interscript http://Interscript.sourceforge.net
>
>