[mercury-users] Pred defns

[Fergus Henderson]

On 27-Mar-1998, Richard A. O'Keefe <ok at atlas.otago.ac.nz> wrote:
> [Ralph Becket wrote:]
>
> 	I've got the Prolog for a syntactic expansion that I find *very*
> 	helpful indeed, and much easier to read.
> 	
> 	The idea is that X` denotes the `next state' of X and X`` expands to
> 	the extra pair of arguments X, X`.
> 
> This is EXTREMELY confusing.  If X` denotes the `next state' of X,
> then X`` should denote the `next state` of X`. 

In Prolog, the lexical syntax means that "``" is different from "` `".
The former is a single token, whereas the latter is two tokens.
Thus if you want the next state of "X`", this should be written as "X` `".

Nevertheless, I agree it might be a bit confusing (at least to SML
programmers), so perhaps it would be better to use a different operator
than "``".

...
> This has me *completely* baffled.  The one thing I can rely on in Prolog
> is that the same variable name stands for the same variable throughout
> a clause.

I agree that using Prolog variables for things which do not have the
same behaviour is probably a poor choice.  However, if you use lower-case
letters for accumulators, then this criticism would not apply.

With this approach, you would need an additional operator to get
the current state of an accumulator (rather than just using the
variable name).

> The intuition that underlies this proposal is that _real_ variables are
> boxes whose contents can be changed, and that logical variables ought to
> be syntactically bodged to behave in much the same way.

Well, I can't speak for Ralph Becket, but the intuition behind this
alternative proposal is different.  The intutition is that there
are two separate things, namely _variables_ and _accumulators_.
Accumulators are logically equivalent to sequences of variables.
So long the syntax doesn't confuse the two notions, there shouldn't
be a problem.

> No thanks.  We didn't need it in Prolog (does ISO Prolog even _have_ DCGs?)
> and we don't need it in Haskell or Clean.  The way out is to go *UP* to
> higher level constructs, not to revert to the filth of the past.

The need for accumulators is common.  The practice of simulating accumulators
using variable numbers (X0, X1, X2, etc.) can be tedious and error-prone,
and can make maintenance more difficult.  So I think accumulators *are*
a higher level construct.

Over the years there have been several proposals to extend Prolog with
EDCGs, mutable variables, etc., and the users of Mercury have been
quite persistent in asking for better support for multiple accumulators. 
At the current time there are in fact already two implementations
of such things for Mercury: a pre-processor based implementation of
EDCGs for Mercury, by Peter Szeredi and Marton Kosa, and another
implementation of a somewhat different version of EDCGs as a modification
of the Mercury compiler, by Peter Malkin (a summer student here).

The reason why neither of these have made it into the Mercury distribution
is that these proposals seemed quite complicated, and it was not clear
that the use of EDCGs would actually lead to code that was easier to read.
With EDCGs the arguments are indeed hidden, and that does seem to make
it harder to understand what the code is doing.

But I do quite like Ralph Becket's approach, modified as noted above.
It seems quite simple and I think it would lead to quite readable code.

So I'll flesh it out a little.  With this approach, we would need
several operators in addition to the ones already mentioned.
I'm not sure what would be the best choice of names for all of these
operators.  Suggestions welcome.

The operators we need are as follows:

	(1) One to get the current state of an accumulator.

	    Becket's original proposal had no operator for this,
	    but I think one is needed if we are to properly
	    distinguish variables from accumulators.

	(2) One to get the next state of an accumulator.

	    This was postfix ` in Becket's original proposal.

	(3) One to get a pair of the current state and the next state

	    This was postfix `` in Becket's original proposal.

	(4) One to get a pair of the initial state and the
	    final state.

	    Becket's original proposal didn't mention this,
	    but you want some way of doing this, for clause
	    headers.  One way would be to use the same operator
	    as for (3) but to give it a slightly different
	    meaning if it occurs in the clause head:

		foo(x'') :->				foo(X0, X) :-
			bar(x''),	means			bar(X0, X1),
			baz(x'').				baz(X1, X).

	    [N.B. `:->' is explained below.]

	(5) One to separate the clause head and clause body.

	    We don't want to use `:-', because currently the declarative
	    semantics of conjunction (`,') in ordinary clauses is
	    commutative, and we don't want to break that.

	    Using `-->' is also not a good idea because that already
	    gives us a pair of hidden arguments.

	    So we need something different.  Perhaps `:->' or `:-->'
	    would be a reasonable choice.

	(6) One to call a goal involving accumulators from
	    inside ordinary code (analagous to phrase/3 for DCGs).

	    Perhaps just acc/1 or accumulate/1.
	    Actually '{}'/1 would also be nice, but that
	    would be very confusing since it almost the exact
	    opposite of its meaning in DCGs.
	    Another alternative would be to make acc/1 a prefix
	    operator and then use `acc { Goal }'.

Perhaps the following would be a reasonable choice of operators:

	(1)	current state	#?v 		(prefix unary `#?')
	(2)	next state	#^v		(prefix unary `#^')
	(3)	state pair	#>v		(prefix unary `#>')
	(4)	head state pair	#<v		(prefix unary `#<')
	(5)	acc clause	H #:- B		(infix binary `#:-')
	(6)	acc goal	#{ G }		(prefix unary `#' and `{}').

Here's an example:

	:- pred main(io__state::di, io__state::uo) is det.
	main(#<io) #:-
		print("Hello world\n", #>io),
		#?x = 42,
		#^x = #?x + 1,
		print("42 + 1 = ", #>io), print(#?x, #>io).


Semantics
---------

The semantics of (5) must be defined by translation, in terms of (6):

	H #:- B.	means		H1 :- #{ H = H1, B }.

					where H1 is a term whose functor
					is the same as H but with fresh
					variables as arguments.

The semantics of (1-4) and (6) can be defined by specifying a
meta-interpreter for `#/1'.  (Of course, the implementation should be
by compile-time transformation; a meta-interpreter is just a nice way
of specify the semantics.)  The meta-interpreter keeps a mapping which
maps from each accumulator names to a pair consisting of its current
state variable and its final state variable.  It traverses goals
left-to-right.  It replaces references to accumulator states (i.e.
(1)-(4) above) with the appropriate variables from the map before
executing each call.  If an accumulator has no entry in the map, then a
reference to its "current state" will cause the meta-interpreter to
insert an entry in the map for that accumulator with fresh variables
for its current and final state.  At each reference to the "next state"
of an accumulator, it updates the current state variable for that
accumulator with a fresh variable.  Note that at calls, the
meta-interpreter does not pass its mapping down to the callee; the
scope of each accumulator is local to the clause in which it occurs.
At the end of each accumulator goal (i.e. (6) above), the
meta-interpreter unifies the current and final state variables for each
accumulator in its map.

Well, that's fairly vague, I guess.  I have a precise specification
(150 lines of code) if anyone's interested.

Comments?

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.