[m-dev.] EDCGs and Higher Order Programming

[Fergus Henderson]

On 26-Jan-2000, Ralph Becket <rbeck at microsoft.com> wrote:
> I'm slightly uneasy about how well EDCGs, which
> it seems are going to be part of the Mercury
> world, will mesh with higher order programming,
> especially in the light of the discussion about
> disallowing expanded (i.e. non-EDCG) calls to
> EDCG predicates.
> 
> Can someone reassure me about this one? 

We just had a long meeting here on Tuesday discussing EDCGs in detail
and addressing higher-order support in particular.

The current implementation of EDCGs does not support higher-order code.
But the upshot of Tuesday's meeting is that although
we plan to commit the current EDCG implementation into the main
development branch soon, so that we can get some experience with it,
we will continue working on a new implementation of EDCGs
that supports type inference, higher-order programming, and
perhaps has more extensive support for overload resolution
(the last point is somewhat contraversial).
The new implementation will achieve this by performing the
EDCG transformation after type-checking rather before type-checking.

> For example, say I want to do something like
> the following:
> 
> write_strings(Strs) -->
> 	list__foldl(io__write_string, Strs).
> 
> What would happen in the EDCG version of the world?

Ah, now that is a good question -- one that we did not specifically
address in Tuesday's meeting.

If we don't allow punning between the EDCG form and the expanded form,
then it seems like code reuse will be a little more difficult.
When we support higher-order EDCGs, then you will be able
to write

	write_strings(Strs) -->
		io__foldl(io__write_string, Strs).

where io__foldl is defined as

	:- pred io__foldl(pred(T) + hidden(changed(io)), list(T))
		+ hidden(changed(io)).
	:- mode io__foldl(pred(in) is det, in) is det.

	io__foldl(_P, []) -->> [].
	io__foldl(P, [X|Xs]) -->> P(X), io__foldl(P, Xs).

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

Note that calling an ordinary predicate like list__foldl from within
an EDCG is easy -- just add `$io, $=io' at the end of the argument list.
But converting an EDCG higher-order term into an ordinary predicate
higher-order term requires using a rather complicated lambda expression
as a wrapper.

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