[m-dev.] EDCGs and Higher Order Programming

[David Overton]

On Thu, 27 Jan, 2000 at 11:02:29AM EST, Fergus Henderson wrote:
> 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.
> > 

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

I've been having similar thoughts about this:  DCGs + record syntax
gives you most of the benefits of EDCGs, but with _much_ less added
complication to the language.

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

Why not add a simple construct similar to the proposal for embedded EDCG goals,
but using DCGs instead?  E.g.

foo -->
	( ^io -->
		write_string("blah"),
		write_int(42)
	).

would be transformed by the compiler to Fergus's code above.  This is
still a much simpler transformation than EDCGs.

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

There's no need to extract the io__state within the closure, so you
could write:

	write_strings(Strs) -->
		IO0 =^ io,
		{ list__foldl(write_string, IO0, IO) },
		^io := IO.

or, using the syntax I just proposed:

	write_strings(Strs) -->
		( ^io --> list__foldl(write_string) ).

[...]
> 
> 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).

With my proposal, there is no need for the io2p function since you
don't have to worry about converting between two different types,
`(pred)+hidden(changed(io))' and `pred(io__state, io__state)', for the
same concept.  

The p2io function can be replaced by `( ^io --> ... )'.

What do other think about this?


David
-- 
David Overton       Department of Computer Science & Software Engineering
PhD Student         The University of Melbourne, Australia
+61 3 9344 9159     http://www.cs.mu.oz.au/~dmo
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------