for review: EDCGs

[Peter Nicholas MALKIN]

Hello,

I have not included the DIFF in this mail because it is over 5000 lines
long. If you really do wish to view it, it is in my home directory;

~pnmalk/MERCURYDEVELOPERS/DIFF
~pnmalk/MERCURYDEVELOPERS/edcg.m 	% This file is a new module.

~pnmalk/MERCURYDEVELOPERS/calculator.m  % This is an example file.
					% It is an EDCG version of
					% mercury/samples/calculator.m

Peter.

I hope to include the following explanation of EDCGs in the
reference manual.


-------------- next part --------------
Description of Extended Definite Clause Grammers (EDCGs).
=========================================================

A hidden argument represents a single variable, but not always the same 
variable, that can be used within the body of a clause without explicitly 
listing the variable in the head argument list of the clause or in any 
predicate call within the body of the clause.

Each hidden argument has a type associated with it, the type of the variable
it represents. The type of a hidden argument is declared in an `:- htype' 
declaration. An htype declaration is required for each hidden argument 
occurring in the relevant module.

The htype declaration is of the following form:

:- htype(HiddenName, Type).

Where Type is a Mercury type, the type associated with Hidden.

If a hidden argument is to be used within the clause of a predicate then it
must be declared within the `:- pred' declaration for that predicate. Each
hidden argument can only be declared once within a predicate declaration.
Predicate declarations are extended with an optional hidden part:

:- pred PredName(VisibleArgs)[+hidden(HiddenArgs)].

where `+' and `hidden' are required syntactic elements and HiddenArgs is a
comma-separated enumeration of HiddenArg's. A HiddenArg can be of one of
four forms: 

	changed(HiddenName)
	passed(HiddenName)
	produced(HiddenName)
	consumed(HiddenName)

where HiddenName is the name of a hidden argument declared in an htype
declaration. The same hidden argument can be used in different forms in
different predicates.

For each HiddenArg the predicate declaration is extended with two (changed)
or one (passed, produced or consumed) additional argument, in the order the
hidden arguments are listed. The additional argument(s) have the
Mercury type, as specified in the corresponding htype declaration for
HiddenName. 

Each hidden argument has associated with it a "state". A hidden argument can
be either be in one of two main states (referred to as liveness); 
(i) 	"dead" 			(not associated with a variable). 
(ii) 	"alive: Variable"	Variable being the variable that the hidden
					argument currently represents.

If it is alive then it can be in one of two states;
(i)	"constant"	can represent only one variable.
(ii)	"changing"	can represent different variables 
					(not at the same time).

The state of a clause head, body or goal within the body is a map from all 
hidden arguments defined in the module to their states.

Two states are considered to match when the corresponding hidden arguments in 
the two states have the same state. They can also have different variables 
assigned to the same hidden argument, which is resolved by unifying the 
variables that are different. At present no exception for matching states is 
made when one of the states the is post-state of a goal with determinism error 
or fail. Two states not matching when required is an error.

The form in which a hidden argument is declared in a predicate 
declaration determines what the pre-state and post-state of the hidden
argument is in the head of any clause for that predicate:

changed(Hidden): 
	pre-state: changing alive: OldVariable
	post_state: changing alive: NewVariable

passed(Hidden): 
	pre-state: constant alive: Variable
	post_state: constant alive: Variable

consumed(Hidden): 
	pre-state: constant alive: OldVariable
	post_state: dead

produced(Hidden): 
	pre-state: dead
	post_state: constant alive: NewVariable

The pre-state of the clause head is the map of hidden arguments to their
pre-states as defined by their form declarations or by default to a pre-state
of dead. The post-state of the clause head is defined similarly.

The pre-state of the clause body is equal to the pre-state of the clause head.
The post-state of the clause body should match the post-state of the clause
head.

The pre-state of the second conjunct is the post-state of the first conjunct. 
The post-state of the conjuntion is the post-state of the second conjunct.

The pre-states of all disjuncts in a disjunction are the same as that of the
disjunction. The post-states of all the disjuncts should match to give the
post-state of the disjunction. 

The pre-state of the `if' and `else' parts of if-then-else goals are same. 
The pre-state of the `then' part of an if-then-else is the post-state of the 
`if' part. The post-states of the `then' and `else' parts should match to
give the post-state of the if-then-else goal.

The pre-state and post-state of a hidden argument for a predicate call 
depends on the form it was declared in for that predicate. The state of the
hidden argument before the call is expected to match the required pre-state
of the predicate call as defined for that predicate. The post state is the 
same as the pre-state for all hidden arguments that are not declared for the 
predicate.

changed(Hidden): 
	pre-state: changing alive: OldVariable
	post_state: changing alive: NewVariable
			OR
	pre-state: constant alive: OldVariable
	post_state: constant alive: NewVariable

passed(Hidden): 
	pre-state: constant alive: Variable
	post_state: constant alive: Variable
			OR
	pre-state: changed alive: Variable
	post_state: changed alive: Variable

consumed(Hidden): 
	pre-state: constant alive: OldVariable
	post_state: dead

produced(Hidden): 
	pre-state: dead
	post_state: constant alive: NewVariable

The head argument lists of a clauses and calls to a predicates are expanded
with extra arguments corresponding to the hidden arguments used by the
predicates. The variables added are taken form the pre-state and post-state
of the hidden arguments declared for that predicate.

There are four primitive operations used to handle hidden arguments:

  changing:	`Hidden <+ NewValue'
  producing:	`Hidden <. InitValue'
  consuming:	`Hidden >. FinalValue'
  accessing:	`Hidden >: IntermediateValue'

In no other way can the hidden arguments be handled explicitly.

These built-ins can be viewed as single argument predicate calls. The
current state of the hidden argument must match the required pre-state of the
operations (given below):
  
  changing: `Hidden <+ NewValue' becomes `NewVar = NewValue'
	pre-state: changing alive: OldVar 
	post-state: changing alive: NewVar

  producing: `Hidden <. InitValue' becomes `NewVar = InitValue'
	pre-state: dead
	post-state: constant alive: NewVar
	
  consuming: `Hidden >. FinalValue' becomes `OldVar = FinalValue'
	pre-state: constant alive: OldVar
	post-state: dead

  accessing: `Hidden >: IntermediateValue' becomes `Var = IntermediateValue'
	pre-state: constant alive: Var 
	post-state: constant alive: Var
		OR
	pre-state: changing alive: Var 
	post-state: changing alive: Var

Every clause that uses hidden arguments must have the functor '-->>' instead 
of ':-', to symbolize that the order of the goals in the body of the clause 
is significant. This is the case even when the clause head possesses no 
hidden arguments.

Each hidden argument must have an hmode declaration specifying the mode
of the hidden argument. Only here can the mode of a hidden argument be 
specified.

The hmode declaration is of the following form:

:- hmode(Hidden, [changed(Mode, Mode),] [passed(Mode),] 
			[consumed(Mode),] [produced(Mode)]).

Where Mode is a Mercury mode.

A single mode is associated with the forms passed, produced and consumed.
Two modes with the form changed, the first mode is the 'In' mode and the 
second the 'Out' mode. The mode declarations for the different hidden forms 
do not need to appear in the above order. A form only needs a mode 
declaration if the hidden argument is called in that form, otherwise it can 
be left out. Only one mode declaration can be given for each form of a 
hidden argument. Only one hmode declaration is allowed for any particular
hidden argument.

Hidden argument modes cannot be declared in normal predicate mode 
declarations. When a predicate has a hidden argument then its mode
declaration will be expanded later on to include the mode(s) of the hidden 
argument's form in which it is called (in the order they are listed in the 
pred declaration).