[m-dev.] EDCGs

[Ralph Becket]

> From: Peter Nicholas MALKIN [mailto:pnmalk at cat.cs.mu.OZ.AU]
> 
> I would like to see the expansion rules if it is not too much trouble.

The basic idea is to rename all of the variables in the atomic subgoals
of a goal, keeping track of which renamings are for `input' versions
(let's call them `unprimed') and which are for `output' versions (which
I'll call primed).  The atomic subgoals are then grouped together by
supplying the appropriate unifications to join the `outputs' of the
left hand side to the `inputs' of the right hand side.  Other unifications
have to be added to make disjunctions and conditional goals work.  The
use of primed variables indicates that the lexical order of the source
code dictates the order of operations on the named `bit of state'.

Sticking with my original syntax for now, which I acknowledge would have 
to be changed, consider the following goal (I've labelled the subgoals
A and B):

A	io__print("Hello, World!", IO, IO`),
B	io__nl(IO, IO`).

If G is a goal then G* is G after transformation, in(G, X) is the name of
the input renaming of var X in G and out(G, X) is the output renaming.  G*
is G where all unprimed instances of X have been replaced with in(G, X)
and all primed instances of X have been replaced with out(G, X).

We have, then,

	in(A, IO) = IO0		% I've picked IO0, IO1, ... as renamings
	out(A, IO) = IO1
	A* = io__print("Hello, World!", IO0, IO1)

and

	in(B, IO) = IO2
	out(B, IO) = IO3
	B* = io__nl(IO2, IO3)

A and B are combined to give

	in((A,B), IO) = IO0
	out((A,B), IO) = IO3
	(A,B)* =
		io__print("Hello, World!", IO0, IO1),
		IO2 = IO1,
		io__nl(IO2, IO3)

Notice the added conjunct connecting the output version of IO in A* to
the input version of IO in B*.  The compiler can optimize away all the
unnecessary unifications.

Here are the rules in more detail (newvar stands for a fresh variable
name each time it appears):

* Atomic Case (A is an atomic goal)

for all free vars X or X` occurring in A,
	in(A, X) = newvar
	out(A, X) = { newvar	if X` occurs in A
			{ in(A, X)	otherwise

* Conjunctive Case ((L,R) is a conjunctive goal)

for all free vars X or X` occurring in (L,R),
	in((L,R), X) =  { in(L, X)	if X occurs in L
			    { in(R, X)	otherwise
	out((L,R), X) = { out(R, X)	if X occurs in R
			    { out(L, X)	otherwise
	(L,R)* = (L*, U, R*)				
		where U is a conjunction of unifications
		such that Y = Z in U iff out(L, X) = Z
		and in(R, X) = Y

* Disjunctive Case ((L;R) is a disjunctive goal)

Here we ensure that the input versions of each variable in each disjunct
are the same and similarly for the output versions.  That is, for all
free vars X occurring in the disjunction, in(L, X) = in(R, X) and
out(L, X) = out(R, X).  This is achieved by extending L* and R* with
appropriate unifications to get (L,R)*.

* Conditional Case ((if C then Y else N) is a conditional goal)

Similar to the disjunctive case, except that we have in((C,Y)*, X) = in(N,
X)
and out((C,Y)*, X) = out(N, X) for all X occurring in the compound goal.

* Finishing up.

A clause body is augmented with unifications to ensure that the input
versions of variables mentioned in the head are the same as the input
version in the clause body and similarly for the output versions.

This sounds complicated, and does need some slightly careful book-keeping,
but the programmer need not worry about the rewriting at all - one just has
to put on the imperative-programming hat and treat X, X` combinations as
abbreviations for destructive update, which is exactly what we're mimicking.
Indeed, the whole transformation can be seen as transforming imperative code
featuring destructive update into `equivalentish' code using
single-assignment
only.

Cheers,

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