EDCGs

[Peter Nicholas MALKIN]

Here are some possible improvements to the proposed edcg syntax by Peter
Szeredi and Martin Kosa. First I will suggest a few improvements on the
proposed syntax presented then I will present my completely different
version for edcgs which I believe to correspond more closely to the
current mercury style as well as including these improvements.

1)
There is of course Zoltan's suggestion that any edcg should involve the
functor -->> instead of :-.

A complication arises in that if a predicate or function does not have
hidden arguments but some of the goals in its body have hidden arguments
then again the order of the goals is important. Since the reason for using
-->> as Zoltan said was to indicate clearly that the order of the clauses
was important then the -->> notation should be used if a functor has
goals that deal with hidden arguments in its body, even if itself does not
have hidden arguments. This error would be easy to locate, just look for
uses of the operators >. <. >: <+.

2)
An alteration to occasionally avoid having to use the -->> notation is to
enable functors with hidden arguments to be called in the usual fashion
with the hidden arguments expressed in the head of the goal after
the visual arguments. For identification the name of the hidden argument
should be attached to the appropriate parameter.

This means that if a functor does not have hidden arguments and one or
more of its goals do however and the scope of all hidden arguments is
confined to the goal using the hidden arguments, then order is not
important and the goal can be called using conventional notation and the
functor -->> need not be used.

This extra syntax option means that a functor involving hidden arguments
need not be called as an EDCG rule, hence making the hidden argument
notation entirely optional, as with DCG's, which is nice.

3)
A complication arises with the proposed notation if a predicate is
called, and there are hidden arguments initiated, then the predicate MUST
use them. However a situation may arise where you wish some of the hidden
argument(s) to skip this predicate but remain active after. For this to be
done, the unusefull arguments must be killed with their values stored, new
arguments created, the predicate called, and then the new ones destroyed
and the old ones reinstated.

Expressing hidden arguments in the argument list of a goal should be made
to restrict the scope of the hidden variable to the goal hence making it
is possible to override existing hidden arguments for the duration
of a goal easily and hence preventing the before said excessive code.
Restricting the scope means less scope violations and also information
hiding.

4)
I deem that the accumulator hidden argument notation is redundant.
Given;

:- acc(AccName, AccPred).

Whenever the notation AccName <+ [X] occurs, it is replaced by
AccPred(X, Sin, Sout), where Sin and Sout are the accumulator before and
after respectively. Why bother? AccName is just an alias for the predicate
AccPred. Instead define a predicate AccPred to have two hidden arguments
and the same functionality as before. Hence instead of writing
AccName <+ [X], write AccPred(X). This means that EDCG code resembles
conventional code more precisely. This also does away with determinism
problems with the accumulator predicate.

I cannot see a situation where doing this would be a problem or not have
all the features of the other method. I am just going straight to the
expansion of Accname, which requires no extra code, about the same in fact
and it is more precise.

5)
The proposed version does not support polymorphism between hidden
arguments and other arguments either hidden or not.

This can be cured by attaching an argument to htype definitions, as in
normal type definitions.

:- htype(Hidden[(...)], Type[(...)]).

For example;

:- htype(accumulator(T), list(T)).

Allowing for;

:- pred predicate(T)+hidden(changed(accumulator(T))).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% My EDCG Notation %%%%%%%%%%%%%%%%%%%%%%%%%%

I designed this notation with an aim to keep it simple and use a
programming style as close to the current mercury style as possible.

If a variable is to be hidden it must be declared with an 'htype'
declaration. The hidden variable is considered and dealt with in much the
same way as any normal data constructor. Each hidden variable must have an
'htype' declaration.

The 'htype' declaration is almost the same as the standard 'type'
declaration.

Syntax;

:- htype hidden_type_name[(...)] --->   hidden_constructor_name(...).

Hidden type names and data constructors must be uniquely named with
respect to other hidden type names and data constructors respectively to
prevent ambiguity.

Equivalence types may not be used because of ambiguities.

On expansion of the EDCGs the hidden data constructor would be broken up
into it constituent parts and hence only one data constructor is allowed
for a hidden argument. Since types within the data constructor may have
more than one data constructor this places no restriction ultimately on
the data structures that can be used as hidden arguments.

It is pointless to have a single data constructor with no arguments so the
data constructor is required to have arguments.

Allowing data constructors means that arguments that are never passed
separately can be grouped together hence simplifying code further.

To declare the modes of the types within the hidden data constructor one
uses the 'hmode' declaration, which is equivalent to a predicate mode
declaration. The same modes in an 'hmode' declaration apply to all
predicate or function calls using the hidden argument unless otherwise
stated in the predicate or function declaration.

Syntax;

:- hmode hidden_constructor_name(mode, ...).

The 'htype' and 'hmode' declaration can be combined;

:- htype hidden_type_name[(...)] 
	---> hidden_constructor_name(type::mode, ...).


Example;

:- htype stuff
        ---> stuff(int::in, int::in, int::out).

Or

:- hmode stuff(in, in, out).

Or

:- mode predicate(in, stuff(in, in, out)).

Or

:- pred predicate(int::in, stuff(in, in, out)).


If the default values are to be used then a predicate type and mode
declaration would look like so;

:- pred predicate(int::in, stuff).

:- mode predicate(in).

Hidden arguments can appear anywhere within the list of arguments in any
order, provided they are listed after all nonhidden arguments. Removing
this restriction brings an added restriction to the naming of hidden data
constructors, in that they do not have the same functor as an existing
nonhidden data constructor. I also feel that this way promotes 
readability.

Accessing, and instantiating hidden arguments;
Hidden arguments can be used in the head of a predicate or function call
as per normal. With this use their is no distinction of use between hidden
and nonhidden variables. With the exception that hidden arguments do not
have to be in place or in order except that they should appear after
nonhidden arguments and that a hidden argument cannot be unified with a
single variable for identification reasons.

If a hidden argument needs to be altered outside a clause head then the
hidden argument's data constructor is called like a predicate, and acts
like a simple unification predicate. By unification predicate I mean one
that unifies itself with the current version of the hidden argument.

Any predicate involving hidden predicate notation should involve the
functor -->> instead of :-. This is to indicate that the order of the
predicates is important.

For example (using the previous example's declarations);

predicate(..., stuff(X,Y,Z)) -->>
        stuff(A, 3, 4),
        ... .

is expanded to;

predicate(..., stuff(X,Y,Z)):-
        stuff(A,3,4) = stuff(X,Y,Z),
        ... .

One extra point to address is the scope of hidden argument. When
implementing EDCGs I will keep a list of current (live) hidden arguments
and their current terms being either variables or ground terms. To make a
hidden become live it needs to be included in the head of a clause, or in
predicate notation. A hidden variable appearing in the head of a clause
has scope only within that clause. A hidden variable using predicate
notation has scope of its present location until the end of the body of
the clause it appears or it is ended by the programmer. To end the scope
of a hidden variable prematurely the notation is simply;

hidden_data_constructor

This cannot be confused with a unification because the data constructor
must have at least one argument.

Any scope violations should be picked up as either mode errors because a
hidden variable has been unduely passed on, or predicate errors where the
wrong number of arguments is given because a hidden variable has not been
passed on.

Good programming practice would be to try not to use the predicate
notation as much as possible, therefore reducing the scope of the hidden
arguments which is information hiding.


The advantages of this method over the proposed method are;
1)
It retains the declarative style of mercury. The proposed style is
distinctly procedural because of the use of the operators >. <. >: and <+.

2)
The only new notation is 'htype', 'hmode', and overall the notation is
simple.

3)
'htype' and 'hmode' closely follow existing type and mode declarations and
hence the concept of them is not new. Therefore mercury programmers will
quickly pick up the EDCG coding style since it so closely resembles the
current style.

4)
Since there is no real change in coding style this will allow significant
compiler code reuse in programming EDCGs.

5)
Predicates can be called in the usual style, whereas in the proposed
method they cannot.

6)
In the proposed method one cannot declare a hidden variable to have a
scope only within the calling predicate, since it must be initialized
outside the call. Leading to possible scope violations and an overuse of
the -->> functor.

7)
My method retains all of the functionality of the proposed method but
without extensive notation.

8)
My method supports polymorphism between hidden arguments and other
arguments either hidden or not.

9)
Overriding live hidden arguments is easily done (because of the scope
rules) if the hidden arguments that need overriding are given in the
predicate header.

10)
My notation does not involve unnecessary accumulator functions.

11)
It is easy to clump together hidden arguments that are only called in the
same functions. It is possible to do this in the proposed notation except
that they must all be put into ungamely data structures that are
partially instantiated in some cases.


Disadvantages over proposed method;
ANY SUGGESTIONS?

For more examples see the directory ~pnmalk/edcg/ and view any files with
.e as the suffix.


Peter Malkin