[m-dev.] EDCGs

[Peter Nicholas MALKIN]

Hi,

Below is a proposed syntax for EDCGs (Extended Definite Clause Grammars).
Following the syntax description is an example, an EDCG version of the
calculator.m program in the samples directory.

Peter

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

EDCGs are as their name implies are similar to DCGs, except more variation is
allowed in the usage of implicit arguments (referred to here as hidden
arguments). 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 hidden variables) 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. A hidden variable represents a single variable at a time, but not
necessarily always the same variable. Each hidden variable has associated with
it a name (hidden variables are module qualified) that must be distinct from all
other hidden variable names. A hidden variable can be only be used in specific
places where it is in scope. 


EDCG Declarations
=================

Type Declarations
-----------------
Each hidden variable must be declared using an `htype' declaration. Each hidden
variable has a type associated with it, the type of the variable it represents.

The htype declaration is of the following form:

:- htype(HiddenName, Type).

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


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

:- pred PredName(VisableArgs)[+hidden(HiddenVars)].

Where `+' and `hidden' are required syntactic elements and HiddenVars is a
comma-separated enumeration of HiddenVar's. A HiddenVar can be one of
two forms: 

	changed(HiddenName)
	passed(HiddenName)

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

For each HiddenVar the predicate declaration is extended with two (changed) or
one (passed) additional argument, in the order the hidden variables are listed.
The additional argument(s) have the Mercury type, as specified in the
corresponding htype declaration for HiddenName. A predicate can be called
with its hidden variables listed explicitly (only used for backwards
compatability with DCGs, a warning message will be given if used).

Two different predicates are not allowed to be defined with the same functor 
and the same "visual" arity (the number of arguments not including hidden 
arguments). Two different predicates are not allowed to be defined with the same
functor and the same "total" arity (hidden plus visual arity). There is no
overloading allowed for predicates with hidden variables.

Every clause that uses hidden variables must have the functor '-->>' instead 
of ':-', to symbolise that the order of the goals in the body of the clause 
is significant.


Mode Declarations
-----------------
Each hidden variable must have an `hmode' declaration specifying the mode(s)
of the hidden variable. Only here can the mode of a hidden variable be 
specified.

The hmode declaration is of the following form:

:- hmode(HiddenName, [changed(Mode, Mode),] [passed(Mode)]) 

Where HiddenName is the name of a hidden variable declared in an `htype'
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 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 variable (this is not
necessary and can be extended). Only one hmode declaration is allowed for any
particular hidden variable.

Hidden argument modes cannot be declared in normal predicate mode 
declarations. When a predicate has a hidden variable then its mode
declaration will be expanded 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).

NB: The form of the hidden variable is in no way related to its mode. There is
no restriction upon which mode(s) can be assigned to which form.


EDCG Manipulations
==================

EDCG Operators
--------------
There are two primitive operators to manipulate hidden variables:

(i) changing: `HiddenName <+ NewValue' -> `NewVar = NewValue'
A new variable (NewVar) is created and HiddenName now represents that variable.
NewVar is unified with the value NewValue. This can only be used with hidden
variables that are in the changed form.

(ii) accessing:	`HiddenName >: IntermediateValue' -> `Var = IntermediateValue'
The variable that the hidden variable currently represents (Var) is unified 
with the value IntermediateValue. The hidden variable continues to represent 
the same variable. This can be used with hidden variables that are in either
form.


EDCG Lambda Expressions
-----------------------
An EDCG lamda expression is of the form:

pred(Arg1::Mode1, Arg2::Mode2, ...)+hidden(HiddenVars) is Det -->> Goal

where HiddenVars is as is in `pred' declarations.


EDCG Higher Order Predicate Calls
---------------------------------
call(Closure [, Arg1 [, Arg2 ...]])+hidden(HiddenVars)

Where HiddenVars is a comma separated enumeration of either:

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

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

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

(edcg(HiddenVars) -->> Goal)

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

Where HiddenVars is a comma separated enumeration of either:

(i) HiddenName(Var):
	HiddenName has the form passed for the goal. HiddenName represents Var
	during the goal.
or

(ii) HiddenName(Var1, Var2):
	HiddenName has the form changed for the goal. HiddenName initially
	represents Var1 for the goal. The variable HiddenName represents at the
	conclusion of the goal is unified with Var2.


EDCG Scope
==========
The scope of an edcg variable is either:

(i) The entire clause of any predicate which the hidden variable was listed in
the hidden argument part of the predicate's pred declaration.

(ii) The entire goal of an EDCG-goal within any clause. If the same hidden
variable exists in the scope of the enclosing clause of the goal then the local
definition overrides.


EXAMPLE
=======

% A simpler calculator - parses and evaluates integer expressions.

% This example uses EDCGs and is based upon the calculator example in the
% samples directory.

:- module calculator.
:- interface.
:- import_module io.

% All io predicates are assumed to use EDCGs. Thus in the module io will be two
% declartions - 
% :- htype(io, io__state).  
% :- hmode(io, changed(di, uo)).
%
:- pred main+hidden(changed(io)) is det.

:- implementation.
:- import_module list, char, int, string.

:- htype(char_list, list(char)).
:- hmode(char_list, changed(in, out)).

:- type expr
	--->	number(int)
	;		plus(expr, expr)
	;       minus(expr, expr)
	;       times(expr, expr)
	;       div(expr, expr).

main -->> 
	io__read_line(Res),
	( Res = error(_),
		io__write_string("Error reading from stdin\n")
	; Res = eof,
		io__write_string("EOF\n")
	; Res = ok(Line),
		
		( call(fullexpr, X)+hidden(char_list(Line, [])) ->
			evalexpr(X, Num),
			io__write_int(Num),
			io__write_string("\n")
		;
			io__write_string("Syntax error\n")
		),
		main	% recursively call ourself for the next line(s)
	).

:- pred evalexpr(expr::in, int::out) is det.
evalexpr(number(Num), Num).
evalexpr(plus(X,Y),  Z) :- evalexpr(X,A), evalexpr(Y,B), Z is A + B.
evalexpr(minus(X,Y), Z) :- evalexpr(X,A), evalexpr(Y,B), Z is A - B.
evalexpr(times(X,Y), Z) :- evalexpr(X,A), evalexpr(Y,B), Z is A * B.
evalexpr(div(X,Y),   Z) :- evalexpr(X,A), evalexpr(Y,B), Z is A // B.

:- pred fullexpr(expr::out)+hidden(changed(char_list)) is semidet.
fullexpr(X)-->>
	expr(X),
	char_list_des('\n').

:- pred expr(expr::out) +hidden(changed(char_list)) is semidet.
expr(Expr) -->>
	factor(Factor),
	expr2(Factor, Expr).

:- pred expr2(expr::in, expr::out) +hidden(changed(char_list)) is semidet.
expr2(Factor, Expr) -->>
	( char_list_des('+') -> 
		factor(Factor2), 
		expr2(plus( Factor, Factor2), Expr)
	; char_list_des('-') -> 
		factor(Factor2), 
		expr2(minus(Factor, Factor2), Expr)
	; Expr = Factor
	).

:- pred factor(expr::out) +hidden(changed(char_list)) is semidet.
factor(Factor) -->>
	term(Term),
	factor2(Term, Factor).

:- pred factor2(expr::in, expr::out) +hidden(changed(char_list)) 
	is semidet.
factor2(Term, Factor) -->>
	( char_list_des('*') -> term(Term2), factor2(times(Term,Term2), Factor)
	; char_list_des('/') -> term(Term2), factor2(div(Term,Term2), Factor)
	; Factor = Term
	).

:- pred term(expr::out) +hidden(changed(char_list)) is semidet.
term(Term)	-->>
	( const(Const) ->
		string__from_char_list(Const, ConstString),
		string__to_int(ConstString, Num),
		Term = number(Num)
	;
		char_list_des('('), expr(Term), char_list_des(')')
	).

:- pred const(list(char)::out) +hidden(changed(char_list)) is semidet.
const([Digit|Rest]) -->>
	digit(Digit),
	( const(Const) ->
		Rest = Const
	;
		Rest = []
	).

:- pred digit(char::out) +hidden(changed(char_list)) is semidet.
digit(Char) -->>
	char_list_des(Char),
	char__is_digit(Char).

:- pred char_list_des(char) +hidden(changed(char_list)).
:- mode char_list_des(in) is semidet.
:- mode char_list_des(out) is semidet.

char_list_des(Char) -->>
	char_list >: [Char|CharList],
	char_list <+ CharList.

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