for review: EDCGs and insts

[Peter Schachte]

On Mon, 2 Mar 1998, Peter Nicholas MALKIN wrote:
> > > 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.
> > 
> > Shouldn't they be insts?  If not, why does changed need two modes?
> 
> No. I assume you mean that, say if a hidden argument of form `passed'
> was given an instantiation of INST then the mode MODE would be inferred to
> be;
> 
> :- mode MODE :: INST -> INST.
> 
> BUT, the hidden argument forms are not reflections of variable
> instantiations but instead of the flow of the hidden argument. Do not
> think of hidden arguments in terms of variable instantiation.
> 
> It is possible to have a hidden argument of form passed with the mode out.

I can see that `consumed' with mode out would make sense, but I would
expect `passed' with mode out would be a problem when the next goal that
used that hidden argument was reached.

The modes for these uses (we need a word for the set of possibilities
{changed, passed, consumed, produced}; for now I'll call them `uses')
have to be compatible.  The final inst of `produced' and `changed' has
to be compatible with the initial inst of `changed', `passed', and
`consumed', doesn't it?  As far as I can see, you really only need to
specify three insts: the initial inst for `produced', the final inst
for `consumed', and the common inst for everything else.  Call them
`first', `middle', and `last'.  Then the modes for the introduced
arguments in the generated code would be

	produced:  first->middle
	passed:	   middle->middle
	changed:   middle->middle, free->middle
	consumed:  middle->last

I also think first will usually be free, middle will usually be
ground, and last will usually be dead(whatever middle is), so I think
it makes sense to have these as defaults.  Why make users write, and
maintainers read, lots of text that has little information other than
"yup, it's the usual"?

> The forms make the most sense when thought of in terms of predicate calls
> within the body of a clause:
> 
> Passed indicates that the predicate call recieves a hidden argument and
> passes on the same hidden argument, to the next goal.

Do you mean by this that the call winds up with two extra arguments?
I would expect that one would be enough for `passed'.

> I probably was not very clear in my explanation of EDCGs, if this makes it
> clearer then please let me know so that I can change the documentation.

I think that was a clearer explaination; it would be a good idea to
put it in the doc.

> I suggest you have a look at the example;
> 
> ~pnmalk/MERCURYDEVELOPERS/calculator.m
> 
> Which replaces DCG notation with EDCG notation using a changed hidden
> argument.

FWIW, I've appended a version of the same program using my global
variable implementation.  Note that this is for Prolog, so there are
no declarations; the arguments that need to be added are inferred.
I've tested this code a bit and it seems to work.

-Peter Schachte			| "Under capitalism, man exploits man. Under
pets at cs.mu.OZ.AU		| communism, it's just the opposite." - John
http://www.cs.mu.oz.au/~pets/	| Kenneth Galbraith 
PGP key available on request	| 

================================================================

%  File     : calculator.pl
%  RCS      : $Id: calculator.pl,v 1.1 1998/03/03 01:35:03 pets Exp pets $
%  Author   : Peter Schachte, based on work by Fergus Henderson
%  Origin   : Tue Mar  3 11:08:56 1998
%  Purpose  : Example use of global variables
%  Copyright: (c) 1998 University of Melbourne. \%\
%
% A simpler calculator --- parses and evaluates integer expressions using 
% global variables instead of the more obvious DCG implementation.

:- module(calculator, [
	main/0
   ]).

:- load_files(library(globals), [when(compile_time),if(changed)]).
:- use_module(library(lineio)).
:- use_module(library(ctypes)).

user:runtime_entry(start) :- main.		% define main for Quintus

main ::-
	get_line(Line, Term),
	$line := Line,
	(   is_endfile(Term) ->
		true
	;   expr(Expr),
	    $line = [] ->
		evalexpr(Expr, Num),
		write(Num),
		nl,
		main
	;   write('invalid expression'),
	    nl,
	    main
	).

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.

% Simple recursive-descent parser.

expr(Expr) ::-
	factor(Factor),
	expr_tail(Factor, Expr).


expr_tail(Factor, Expr) ::-
	(   nextchar(C),
	    expr_op(C, Factor, Factor2, Factor3) ->
		factor(Factor2),
		expr_tail(Factor3, Expr)
	;   Expr = Factor
	).

expr_op(0'+, Factor1, Factor2, plus(Factor1, Factor2)).
expr_op(0'-, Factor1, Factor2, minus(Factor1, Factor2)).


factor(Factor) ::-
	term(Term),
	factor_tail(Term, Factor).


factor_tail(Term, Factor) ::-
	(   nextchar(C),
	    factor_op(C, Term, Term2, Term3) ->
		term(Term2),
		factor_tail(Term3, Factor)
	;   Factor = Term
	).

factor_op(0'*, Term1, Term2, times(Term1, Term2)).
factor_op(0'/, Term1, Term2, div(Term1, Term2)).


term(Term) ::-
	(   num(Num) ->
	      Term = number(Num)
	;   nextchar(0'(),
	    expr(Term),
	    nextchar(0'))
	).

num(Num) ::-
	nextchar(Digit),
	is_digit(Digit, 10, Value0),
	num_tail(Value0, Num).

num_tail(Value0, Value) ::-
	(   nextchar(Digit),
	    is_digit(Digit, 10, Value1),
	    Value2 is Value0*10+Value1,
	    num_tail(Value2, Value)
	;   Value = Value0
	).

nextchar(C) ::-
	$line = [C|Tail],		% this could instead be written
	$line := Tail.			% $line = [C | $:=line]