DCG's compared to Haskell monads
Alan Baljeu
They're useful in pure functional languages where they
effectively accumulate changes which can be serialized to
some output. I'm probably not explaining them quite correctly.
The list datatype is an example of a monad.
DCG's are are tool for serializing computation, and making
implicit the building up of a list. However, the concept
can be generalized to implicitly collecting any kind of data.
I'm just wondering how close this is to the monad concept.
What's the relation between these, and can DCG style be
used to implicitly manage side-effecty code in prolog, like
monads do for Haskell?
Alan
Fergus Henderson
>can DCG style be used to implicitly manage side-effecty code in prolog, like
>monads do for Haskell?
Yes. This approach is used in Mercury <http://www.cs.mu.oz.au/mercury/>,
where the state-of-the-world is represented as an implicit DCG parameter.
However, this approach also relies on Mercury's unique mode support
(which is essentially a directional linear type system -- it is similar
to unique types in Clean) to ensure that there is only one reference to
the state-of-the-world at any point in time. It also relies on Mercury's
support for determinism analysis, to ensure that "side-effecty" code won't
fail and can't be backtracked over. Mercury's determinism analysis in
turn also depends on Mercury's type and mode systems. (Other approaches
to determinism are possible, though, some of which do not rely on mode
analysis -- for example see the language TEL, which is described in
Gert Smolka's PhD thesis.)
--
Fergus Henderson <f...@cs.mu.oz.au> | "I have always known that the pursuit
The University of Melbourne | of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
Jamie Andrews
Fergus has mentioned some constructs in Mercury. Also,
Peter van Roy worked on various variations of the DCG concept a
number of years ago, IIRC. They are the same kind of thing in a
loose sense: a way of getting state into a declarative
computation in a declaratively principled way.
However, the monad concept refers to something very
specific: a data object with some specific operations that do
specific things, which (in a principled functional setting) are
accomplished by making the data object a fairly complex
expression involving lots of lambdas. The only way you could do
that in a declaratively principled way in logic programming is
with a higher order LP language, like Lambda Prolog or Twelf.
The DCG idea is essentially sophisticated syntactic sugar for
extra parameters, which is a different kind of thing.
In Googling to see if anyone had actually worked on this
area, I see that our own Paul Tarau (with Yves Bekkers) has
a paper called "Monadic Constructs for Logic Programming",
available on the Web. I haven't looked at the paper closely,
but it does seem to use Lambda Prolog. Paul, are you reading
this thread and can you comment?
--Jamie. (nel mezzo del cammin di nostra vita)
andrews .uwo } Merge these two lines to obtain my e-mail address.
@csd .ca } (Unsolicited "bulk" e-mail costs everyone.)