[m-dev.] Fw: Replacement syntax for DCGs

Ralph Becket rafe at cs.mu.OZ.AU
Mon Nov 26 14:11:27 AEDT 2001

Here's yet another DCG-replacement suggestion.  I think it's simpler
and more elegant than EDCGs (see http://www.cs.mu.oz.au/research/mercury/mailing-lists/mercury-developers/mercury-developers.9912/0114.html ), but
EDCGs have the advantage of having been implemented, but not
integrated into the compiler.

Anyway, comments welcome.

Problem 1: DCG syntax is ugly and puts the cart before the horse (it's
very common to see the majority of a DCG clause { escaped } with only a
few unescaped goals.)

Problem 2: DCGs are weak because they only support a single threaded

Suggestion: some alternative syntax:

Rather than writing

foo -->
	{ p(...) },
	{ q(...) },
	{ r(...) },

we would make ! an infix binary operator and write

io ! foo :-
	io ! io__print(...),
	io ! io__print(...).

There is nothing special about the symbol `io' - it could be anything -
it's just used to name a threaded argument.

The syntactic transformation is straightforward: we just remove the
`io !' from the head and any goals with it as a prefix, wrap { } around
all the other goals, change the :- to a --> and carry out the usual DCG

I claim this is an elegant answer to problem 1 that does not problems
in situations where the majority of goals in a DCG clause are unescaped.

Problem 2 can be handled by allowing chaining.  For example:

io ! array ! foo :-
	array ! p(...),
	io ! array ! array__foldl2(...),
	io ! io__print(...).

This would be expanded in two stages.  First we go to

(array ! foo) -->
	{ array ! p(...) },
	{ q(...) },
	array ! array__foldl2(...),
	{ r(...) },

and perform DCG expansion (I'm extending the DCG expansion to handle the
head properly) giving

array ! foo(IO0, IO) :-
	array ! p(...),
	array ! array__foldl2(..., IO0, IO1),
	io__print(..., IO1, IO).

We see that the head is still not in standard form, so we continue with

foo(IO0, IO) -->
	{ q(...) },
	array__foldl2(..., IO0, IO1),
	{ r(...) },
	{ io__print(..., IO1, IO) }.

perform DCG expansion and finish up with

foo(IO0, IO, Array0, Array) :-
	p(..., Array0, Array1),
	array__foldl2(..., IO0, IO1, Array1, Array),
	io__print(..., IO1, IO).

It is an error if any goal in the body has the form (_ ! _) when the
head does not.

This solves problem 2.

The chaining expansion does impose an order on the argument pairs (e.g.
here io argument pairs must come before array argument pairs.)  This
doesn't seem like a big deal, but if it is, we can just make the
obvious change to the algorithm rather than using simple DCG expansion.

If we want to access the values of the threaded parameters we can
use the existing DCG notation:

	array ! =(X)	% Unifies X with the current array value.

	array ! :=(X)	% Sets the current array value to X.

1. Any show stoppers in there?
2. Is it worth it?
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

More information about the developers mailing list