[m-rev.] EDCG implementation

[Peter Nicholas MALKIN]

Hi,

Estimated Hours Taken: >100

Implementation of the EDCG syntax. The transformation from code with EDCGs to
code without, is done after purity checking.

The diff will be stretched over the next few emails.

See below for a description of EDCGs.

Files modified:

compiler/edcg.m
	Main file. Contains predicates to infer edcg forms, and predicates to
	expand edcgs.
compiler/equiv_type.m
	Expand edcg arguments types.
compiler/goal_util.m
	Utility predicates.
compiler/hlds_goal.m
	edcg data structures.
compiler/hlds_module.m
	edcg data structures.
compiler/hlds_out.m
	Output edcg arguments.
compiler/hlds_pred.m
	edcg data structures.
compiler/make_hlds.m
	Convert edcg goals to hlds.
compiler/mercury_compile.m
	Added edcg compiler pass. Occurs after purity checking.
compiler/mercury_to_mercury.m
	Output edcg arguments.
compiler/module_qual.m
	Qualify edcg arguments.
compiler/prog_data.m
	Parse edcg arguments.
compiler/prog_io.m
	Parse edcg arguments.
compiler/prog_io_goal.m
	Parse edcg arguments.
compiler/prog_util.m
	Utility predicates
compiler/purity.m
	During purity checking predicates are checked to see whether they need
	an EDCG transformation performed upon them. This needs to be performed
	after typecheck before predicate call overloading needs to be resolved.
compiler/quantification.m
	Quantify edcg goals
compiler/typecheck.m
	Typecheck edcg arguments
library/list.m
	Added predicate list__remove_dups/3
library/ops.m
	Added operators `$', `$=' and `-->>'

The following files all have trivial changes. The changes are the result of
changes to the hlds data structure.

compiler/accumulator.m
compiler/add_trail_ops.m
compiler/assertion.m
compiler/bytecode_gen.m
compiler/clause_to_proc.m
compiler/code_aux.m
compiler/code_gen.m
compiler/code_util.m
compiler/common.m
compiler/context.m
compiler/cse_detection.m
compiler/dead_proc_elim.m
compiler/deforest.m
compiler/dependency_graph.m
compiler/det_analysis.m
compiler/det_report.m
compiler/dnf.m
compiler/excess.m
compiler/follow_code.m
compiler/follow_vars.m
compiler/goal_path.m
compiler/higher_order.m
compiler/inlining.m
compiler/intermod.m
compiler/lambda.m
compiler/lco.m
compiler/live_vars.m
compiler/liveness.m
compiler/magic.m
compiler/magic_util.m
compiler/mark_static_terms.m
compiler/mercury_to_goedel.m
compiler/ml_code_gen.m
compiler/mode_util.m
compiler/modecheck_unify.m
compiler/modes.m
compiler/modules.m
compiler/options.m
compiler/pd_cost.m
compiler/pd_term.m
compiler/pd_util.m
compiler/polymorphism.m
compiler/post_typecheck.m
compiler/prog_io_dcg.m
compiler/prog_io_typeclass.m
compiler/prog_rep.m
compiler/rl_exprn.m
compiler/rl_gen.m
compiler/rl_key.m
compiler/saved_vars.m
compiler/simplify.m
compiler/store_alloc.m
compiler/stratify.m
compiler/switch_detection.m
compiler/table_gen.m
compiler/term_traversal.m
compiler/unify_proc.m
compiler/unique_modes.m
compiler/unneeded_code.m
compiler/unused_args.m


Description of Extended Definite Clause Grammars (EDCGs).
=========================================================

EDCGs are as their name implies are similar to DCGs, except more variation is
allowed in the way arguments are passed. Like DCGs, EDCGs do not change the
semantics of the language. They are similar to DCGs, in that the compiler
performs a source to source transformation of the EDCG code. 

EDCGs are a way of implicitly using variables (through `edcg references') that
can be used within the body of a clause without explicitly listing the variable
in the head argument list or in any predicate call argument list within the body
of the clause. An `edcg reference' refers to a variable, but not necessarily
always the same variable. Each edcg reference has associated with it a name
(edcg references are module qualified) that must be distinct from all other edcg
reference names.

There are two types of references to edcg references:
(i) USED: An edcg reference is USED if the variable it points to is
referenced.
(ii) CHANGED: An edcg reference is CHANGED if the variable which it points to
changes and the new variable is referenced.

The way in which an edcg reference is used within a predicate is called its
`form'. An edcg reference can be used in different forms for different
predicates. There are four forms for an edcg reference:
(i) nothing: not USED and not CHANGED
	- in the body of all clauses of the predicate, and in the body of all
	  clauses of predicates called from the predicate, there is no use
	  of the edcg reference.
(ii) passed: USED and not CHANGED
	- in the body of all clauses of the predicate, and in the body of all
	  clauses of predicates called from the predicate, the edcg reference
	  is only USED.
(iii) produced: not USED and CHANGED
	- in the body of all clauses of the predicate, and in the body of all
	  clauses of predicates called from the predicate, the edcg reference
	  is first CHANGED before it is USED.
(iv) changed: USED and CHANGED
	- in the body of at least one clause of the predicate, and in the body
	  of at least one clauses of predicates called from the predicate, the
	  edcg reference is first USED and then later CHANGED.

A simple example:

:- etype(char_list, list(char)).
:- emode(char_list, changed(in, out)).

	% append(CharList)
	%	append Charlist onto the edcg reference char_list.
:- pred append(list(char)) +edcg(changed(char_list)).
:- mode append(in) is det.

append([]).
append([Char | Rest]) -->>
	append(Rest),
	$=char_list = [Char | $char_list].

This is transformed to:

:- pred append(list(char), list(char), list(char)).
:- mode append(in, in, out) is det.

append([], EDCG_char_list0, EDCG_char_list2).
append([Char | Rest], EDCG_char_list0, EDCG_char_list2) :-
	append(Rest, EDCG_char_list0, EDCG_char_list1),
	EDCG_char_list2 = [Char | EDCG_char_list1].


Declarations
============

Type Declarations
-----------------
Each edcg reference must be declared using an `etype' declaration. Each edcg
reference has a type associated with it, the type of the variable it refers to.

The etype declaration is of the following form:

:- etype(EDCGRef, Type).

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

Predicate Declarations
----------------------
If an edcg reference is to be referenced within the head and body of a clause of
a predicate then it must be declared within the `pred' declaration for that
predicate. 

Predicate declarations are extended with an optional edcg part:

:- pred PredName(VisableArgs)[+edcg(EDCGArgs)].

Where `+' and `edcg' are required syntactic elements and EDCGArgs is a
comma-separated enumeration of EDCGVar's. An EDCGVar can be one of
three forms: 

	changed(EDCGRef)
	passed(EDCGRef)
	produced(EDCGRef)

where EDCGRef is the name of an edcg reference declared in an `etype'
declaration. The same edcg reference can be used in different forms in
different predicates.

NB: The form nothing is assumed if the edcg reference is not listed.

Each edcg reference can only be declared once within a predicate 
declaration. 

For each EDCGVar the predicate declaration is extended with two (changed) or
one (passed or produced) additional arguments, in the order the edcg references
are listed.  The additional argument(s) have the Mercury type, as specified in
the corresponding etype declaration for EDCGRef.

Two different predicates are not allowed to be defined with the same functor 
and the same "visual" arity (the number of arguments not including edcg 
arguments), even if the number of edcg arguments differ in any way. Two
different predicates are not allowed to be defined with the same functor and the
same "total" arity (edcg plus visual arity).

The declared forms of edcg arguments refers to the way in which they are
reference within the clauses of the predicate.

If the form of use of an edcg reference in a predicate does not match the
declaration then an error is given. Unless the forms are being inferred and
there are no declared forms. By giving the compiler the option `--infer-edcgs'
the forms of usage of the EDCG refences are inferred for all predicates (using
fixed point iteration). If a predicate does not have any forms declared but does
not forms inferred then the inferred forms are used to perform an EDCG
transformation on the predicate.

A warning is given if the declared form of
the edcg reference is not as strict as possible. For instance: an edcg reference
is declared changed but is not used and changed, hence it could have been
declared as produced.

Mode Declarations
-----------------
Each edcg reference must have an `emode' declaration specifying the mode(s)
of the edcg reference. Only here can the mode of an edcg reference be 
specified.

The emode declaration is of the following form:

:- emode(EDCGRef, [changed(Mode, Mode),] [passed(Mode),] [produced(Mode)]) 

Where EDCGRef is the name of an edcg reference declared in an `etype'
declaration and Mode is a Mercury mode.

A single mode is associated with the form passed and two modes with the form
changed. The mode declarations for the different edcg forms do not need to
appear in the above order. A form only needs a mode declaration if the edcg
argument is called in that form, otherwise it can be left out. Only one mode
declaration can be given for each form of an edcg reference (this is not
necessary and can be extended). Only one emode declaration is allowed for any
particular edcg reference.

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

NB: The form of the edcg reference is in no strict way related to its mode.
There are no restrictions upon which mode(s) can be assigned to which form.


Clauses
=======
Every clause that refers to edcg references must have the functor '-->>' instead
of ':-', to symbolise that the order of the goals in the body of the clause may
be significant. The reference to an edcg reference can be direct or indirect
(i.e within a predicate called within the clause).

A reference is in scope (can be referred to) for any entire clause of any
predicate for which the edcg reference was declared for.

When performing the EDCG transformation the clause head is expanded to included
EDCG arguments.

If EDCGRef is an edcg reference declared as:

(i) passed: The variable that EDCGRef refers to initially is added to the
	clause head in the appropriate place.

(ii) produced: EDCGRef initially refers to a free variable. The variable that 
	EDCGRef refers to at the conclusion of the goal is added to the clause
	head in the appropriate place.

(iii) changed: The variable EDCGRef initially refers to and the variable that
	EDCGRef refers to at the conclusion of the goal are both added to the
	clause head in the appropriate place.

Goals
=====

EDCG Operators
--------------
There are two primitive operators to manipulate edcg references. The operators
can be used in predicate calls or unifications.

(i) `$' current:  `$EDCGRef' -> `Var'
Where EDCGRef is an edcg reference and Var is the variable that EDCGRef
currently refers to. The edcg reference continues to represent the same
variable. This can be used with edcg references that are in either
form (passed or changed).

(ii) `$=' next:  `$=EDCGRef' -> `NewVar'
Where EDCGRef is an edcg reference and NewVar is the next variable that
EDCGRef refers to (the previous variable is now inaccessible).
This can be used only with edcg references that are in changed form.

Each occurence of an operator has scope of one atomic goal, and each operator
can occur more than once within a single atomic goal. In other words, the
variables refered to by the current operator ($) and the next operator ($=) are
the same throughout the atomic goal. The order in which they appear within the
atomic goals is irrelevant (however the order of the atomic goals is relevant).

If the next operator is used within an atomic goal, then the variable it refers
to becomes the current variable in the next atomic_goal.

For example the following two atomic goals are equivalent:
	(i) $=EDCGReference = a_functor(A, B, C, $EDCGReference)
	(ii) a_functor(A, B, C, $EDCGReference) = $=EDCGReference 

However these following goals are not equivalent. In the first instance the
operators refer to the same variable. In the second they refer to different
variables:
	(i) $=EDCGReference = Var, Var = a_functor(A, B, C, $EDCGReference)
	(ii) a_functor(A, B, C, $EDCGReference) = Var, Var = $=EDCGReference 

EDCG Predicate Calls (not higher order)
---------------------------------------
Predicates with edcg arguments can be called in three forms:

(i) Implicit EDCG argument predicate call:
	The edcg arguments are not listed at all and the edcg source to source
	transformation will append the appropriate arguments to the predicate
	call.

	If the EDCG reference EDCGRef was declared as for the called predicate
	then:

	(i) If EDCGRef was declared as changed for the called predicate then
	the variables $EDCGRef and $=EDCGRef will be added to the predicate's
	argument list in the appropriate place.

	(ii) If EDCGReference was declared as passed for the called predicate
	then the variable $EDCGRef will be added to the predicate's argument
	list in the appropriate place.

	(iii) If EDCGReference was declared as produced for the called
	predicate then the variable $=EDCGRef will be added to the predicate's
	argument list in the appropriate place.

	For example:
	Given that,
	`:- pred P +edcg(produced(EDCGRef1), passed(EDCGRef2),
			changed(EDCGRef3)).'
	and that the references EDCGRef1, EDCGRef2 and EDCGRef3 are currently
	in scope then;
		P -> P($=EDCGRef1, $EDCGRef2, $EDCGRef3, $=EDCGRef3)

(ii) Explicit EDCG argument predicate call:
	The edcg arguments are listed explicitly at the predicate call.

	Predicate([Arg1 [, Arg2 ...]])+edcg(EDCGArgs)

	Where EDCGArgs is a comma separated enumeration of either:

	(i) EDCGRef(Var): 
		EDCGRef was declared as passed or produced for the specified
		predicate. Var will be added to the predicate's argument list in
		the appropriate place.

	(ii) EDCGRef(Var1, Var2):
		EDCGRef was declared as changed for the specified predicate.
		Var1 and Var2 will be added to predicate's argument list in the
		appropriate places.  

	The elements in the enumeration can occur in any order (no duplicates
	allowed).

	This may be used at the time as implicit EDCG arguments. Hence, the list
	may be incomplete. For example: if a predicate receives two edcg
	references, zero, one or two of the edcg references may be listed, as
	long as the edcg arguments received by the predicate that are not listed
	are currently in scope.

	This may be used inside or outside of an edcg clause or goal.

(iii) Expanded EDCG argument predicate call:
	A predicate can be called with its edcg arguments listed explicitly
	(only used for backwards compatibility with DCGs, a warning message will
	be given if used).

For example:
Given that, `:- pred pred_call +edcg(changed(EDCGRef1), changed(EDCGRef2)).'
and that the references EDCGRef1 and EDCGRef2 are currently in scope, the
following predicate calls are equivalent:
	(i) IMPLICIT:
		pred_call
	(ii) EXPANDED:
		pred_call($EDCGRef1, $=EDCGRef1, $EDCGRef2, $=EDCGRef2)
	(iii) EXPLICIT:
		pred_call +edcg(EDCGRef1($EDCGRef1, $=EDCGRef1), 
				EDCGRef2($EDCGRef2, $=EDCGRef2))
	(iv) EXPLICIT & IMPLICIT:
		pred_call +edcg(EDCGRef1($EDCGRef1, $=EDCGRef1))
	(v) EXPLICIT & IMPLICIT:
		pred_call +edcg(EDCGRef2($EDCGRef2, $=EDCGRef2))


EDCG Goals
----------
An edcg goal may be written as:

(EDCGArgs -->> Goal)

This goal may be used any where within the body of a clause where any other
goal may be used.

Where EDCGArgs is a comma separated enumeration of either:

(i) EDCGRef is passed(Term):
	EDCGRef has the form passed for the goal. The variable that EDCGRef
	refers to initially is unified with Term.

(ii) EDCGRef is produced(Term):
	EDCGRef has the form produced for the goal. EDCGRef initially
	refers to a free variable. The variable that EDCGRef refers to at the
	conclusion of the goal is unified with Term.

(iii) EDCGRef is changed(Term1, Term2):
	EDCGRef has the form changed for the goal. The variable EDCGRef 
	initially refers to is unified with Term1. The variable that EDCGRef
	refers to at the conclusion of the goal is unified with Term2.

The elements in the enumeration can occur in any order. No duplicates allowed.

If the same edcg reference exists in the scope of the enclosing clause of the
goal or the enclosing edcg goal (edcg goals can be nested) then the local
definition overrides. Any edcg reference in the scope of the enclosing clause or
edcg goal is also in scope within the edcg goal.

EDCG goals may be used inside or outside of an edcg clause.

Any EDCG reference that occurs inside one of the argument terms above is not
considered part of the goal and will be expanded as if outside the goal.

For example:
Given that, `:- pred pred_call +edcg(changed(EDCGRef1), changed(EDCGRef2)).'
and that the references EDCGRef1 and EDCGRef2 are currently in scope, the
following goals are equivalent:
	(i) pred_call

	(ii)  ( EDCGRef1 is changed($EDCGRef1, $=EDCGRef1), 
		EDCGRef2 is changed($EDCGRef2, $=EDCGRef2) -->> pred_call).

	(iii) ( EDCGRef2 is changed($EDCGRef2, $=EDCGRef2) -->> pred_call).

	(iv)  ( EDCGRef1 is changed($EDCGRef1, $=EDCGRef1) -->> pred_call).

--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------