[m-dev.] EDCGs and Higher Order Programming

[Fergus Henderson]

On 26-Jan-2000, Ralph Becket <rbeck at microsoft.com> wrote:
> Thanks for the update.  Just for the record, I'm very
> uneasy about the whole EDCG thing.
> 
> It seems to me that EDCGs are a leap *away* from
> declarative programming in the sense that code using
> them can no longer be directly associated with logical
> formulae without reference to some auxiliary machinery.
> DCGs at least have { big red warning signs } indicating
> where strange things are afoot.

Well, with EDCGs you still have the `-->>' as a big red
warning sign (assuming appropriate syntax highlighting
support in your editor, of course ;-).

> The functional programming community seem to avoid the
> need for this sort of thing by having good mechanisms
> for boxing up bits of state;

I think the recent introduction of dynamically scoped
variables in Hugs/ghc suggests the opposite; the existing
mechanisms in Haskell 98 are _not_ sufficient, it seems.

> now we have the record
> syntax, surely that (plus DCGs) should be sufficient to
> achieve the same thing?

Good question.  But I don't think it works out quite so nicely.
For example, suppose you want to pass the io__state and something
else, so you put them both in a record.  Now you want to call
something simple like `io__write_string' or `io__write_int'.
To do that, you need to extract the io__state from the record,
pass it to io__write_string and/or io__write_int,
and then set the resulting io__state:

	:- type my_state ---> my_state(io :: io__state, other :: int).
	:- inst my_state = unique(my_state(unique, ground)).

	:- pred foo(my_state::di(my_state), my_state::uo(my_state)) is det.
	foo -->
		IO0 =^ io,
		{ write_string("blah", IO0, IO1) },
		{ write_int(42, IO1, IO) },
		^io := IO.

This is rather nasty: you need to do explicit argument passing
and variable numbering.  With EDCGs, you avoid both of those
in cases like this.

There would also be some difficulty with higher-order code for the
DCGs+records approach, similar to the issue with EDCGs discussed below.
Your `write_strings' example would have to look something like this:

 	write_strings(Strs) -->
 		WriteStringPred = (pred(S::in, di, uo) is det -->
			IO0 =^ io,
			{ write_string(S, IO0, IO) },
			^io := IO)
 		list__foldl(WriteStringPred, Strs).

So I don't think DCGs+records solves the problem.

> > But reusing list__foldl is more difficult.
> > For that, you would need to write something like
> > 
> > 	write_strings(Strs) -->>
> > 		WriteStringPred = (pred(S::in, A0::di, A::uo) is det :-
> > 			(io is changed(A0, A) -->> io__write_string(S))),
> > 		list__foldl(WriteStringPred, Strs, $io, $=io).
> 
> This is terrible!  I make good use of higher order
> programming and I'm hampered enough as it is by the
> mode system (the polymorphic modes extension is
> eagerly awaited) without having to jump through hoops
> like this one!

Well, you can do a little better by abstracting out the conversion
function:

	:- func io2p((pred)+hidden(changed(io))) = pred(io__state, io__state).
	:- mode io2p(in(pred)) = out(pred(di, uo) is det).
	io2p(P) = (pred(IO0::di, IO::uo) is det :-
 			(io is changed(IO0, IO) -->> P)).

Then you can write `write_strings' as

	write_strings(Strs) -->>
		list__foldl(io2p(io__write_string), Strs, $io, $=io).

You could also define a conversion function in the other direction
(`io2p'), and thus write it as

	write_strings(Strs) -->>
		p2io(list__foldl(io2p(io__write_string), Strs).

but the ", $io, $=io" notation is sufficiently concise that there is
no need.

Using conversion functions like this is in fact closer to the typical
Haskell style; the Haskell people call their equivalent of functions
like `io2p' and `p2io' "monad transformers", I believe.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------