[mercury-users] Pred defns

[Ralph Becket]

Richard A. O'Keefe wrote on 27 Mar:
> 	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`.  This is how ticks
> are used in SML, for example:
> ...

I'll be the first to admit that the idea is imperfect.  The double
prime, perhaps, could be changed to something else, but that isn't my
point.

Before I go on, the point behind my suggested notation is that there
are times when a *metaphor* for destructive assigment is useful.
Threading N arguments through a bit of code is no great problem, but
threading 2N arguments so I can obtain the updated `state' starts to
look very clumsy.

Of course, one can pass around state in a compound structure, but then
you have to write access & update functions and, worse, your code has
idioms like the following all the way through it:

	get(num, X, S0),
	X1 is X + 1,
	set(num, X1, S0, S1)

You might say that an higher order approach is in order

	chg(num, (lambda [X]. X+1), S0, S1)

(or whatever syntax you choose), but this also starts to fall over
when the calculation depends upon more than the `state' value being
updated.

I want my code to be as easy to read and maintain as possible.
Multiple argument pairs (with decent names) obscure the code, as do
`state containers'.  The only thing I've come up with so far that
does the job for me is this idea.  All it relies upon is the
programmer keeping in mind a *single* and very simple convention in
mind: X is the same as the latest preceding X`.

> 	For example:
> 	
> 		io__write(..., IO``),		io__write(..., IO0, IO1),
> 		io__write(..., IO``),	 |->	io__write(..., IO1, IO2),
> 		io__write(..., IO``),		io__write(..., IO2, IO3),
> 	
> 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.

Hang on a minute.  If you write

foo(X) -->
	bar(X),	% (1)
	baz(X),
	bar(X).	% (2)

then there's no guarantee that (2) will succeed just because (1) did,
but you're happy to use totally invisible variables as a
convenience...  If I wrote  in_out_pair(IO)  rather than  IO``  would
that feel any better?

> Is it intended in this example that
> 
> 	/* here IO means IO0, IO` means IO1 */
> 	io__write(..., IO``),
> 	/* here IO means IO1, IO` means IO2 */
> 	io__write(..., IO``),
> 	/* here IO means IO2, IO` means IO3 */
> 	io__write(..., IO``),
> 	/* here IO means IO3, IO` means IO4 */

This is correct.  The reading is that X unifies with the latest
preceding X` on any execution path.  That's the only rule you have to
bear in mind.

An argument X`` is just notational convenience for the pair of
arguments X, X`.

> 		X` = X + 1		 |->	X1 = X0 + 1
> 	
> Why does X mean X0 and not X?   Does it _always_ mean that even if I
> don't use tick notation?  Would
> 		Y = X + 1		 |->	Y = X0 + 1
> or would it not?  If I added a tick reference to X later, would that
> change the meaning of the program?

I was making a suggestion; I can provide the transformation if
you want.  I renamed the variables in the translated goals because
that's what the transformation does.  Renaming variables does not
change the meaning of a program.

> 		map__init(M),			map__init(M0),
> 		map__insert(M, K0, V0, M`),	map__insert(M0, K0, V0, M1),
> 		map__insert(M, K1, V1, M`), |->	map__insert(M1, K1, V1, M2),
> 		map__insert(M, K2, V2, M`),	map__insert(M2, K2, V2, M3),
> 	
> This is of course contrived.

Of course it is.  The point was to demonstrate the transformation.

> Let me point out the obvious, that the
> *syntactically* identical calls
> 
> 		map__insert(M, K0, V0, M`),
> 		map__insert(M, K0, V0, M`)
> 
> would mean different things and affect different logical variables.
> This is NOT the kind of thing I want in a declarative language.

DCGs have the same problem (see above).

> 	The only mildly tricky bit is that you sometimes have to add
> 	unifications to balance things up:
> 	
> 		( foo(X) ->			( foo(X0) ->	
> 			bar(X``)			bar(X0, X1), Y1 = Y0
> 		;			 |->	;		
> 			baz(Y``)			baz(Y0, Y1), X1 = X0
> 		),				),		
> 		quux(X, Y)			quux(X1, Y1)	
> 	
> 	But that really isn't hard to arrange at all.
> 
> Oh?  Nothing in your message preceding this example would lead anyone to
> expect these extra unifications.

Okay, I'm at fault for not giving all the details in my first message.
My intention was to first gauge interest.  What I'm suggesting amounts
to very little more than a generalisation of naming DCG argument
pairs.

> What happens if you have
> 	(   foo(Z) ->
> 	    bar(X``)
> 	;/* not foo(X) */
> 	    baz(Y``)
> 	),
> 	(   yoo(Z) ->
> 	    tick(X``)
> 	;/* not yoo(Z) */
> 	    tock(Y``)
> 	),
> 	hoo(X, Y, Z).
> Just where do you undisclosed rules for cases like this put the extra
> unifications?

Be fair - I did not give any rules, I only gave examples.  If there is
interest then I'll post the rules.  The above would become (keeping
the original starting variable names)

	( foo(Z) ->
		bar(X, X1), Y1 = Y
	;
		baz(Y, Y1), X1 = X
	),
	( yoo(Z) ->
		tick(X1, X2), Y2 = Y1
	;
		tock(Y1, Y2), X2 = X1
	),
	hoo(X2, Y2, Z)

I claim the version with primes is easier to read.

> Do they have the _same_ effect when they are applied to
> the if-expansion
> 
> 	(   foo(Z) ->
> 	    bar(X``)
> 	    (   yoo(Z) ->
> 		tick(X``),
> 		hoo(X, Y, Z)
> 	    ;/* not yoo(Z) */
> 		tock(Y``),
> 		hoo(X, Y, Z)
> 	    )
> 	;/* not foo(X) */
> 	    baz(Y``)
> 	    (   yoo(Z) ->
> 		tick(X``),
> 		hoo(X, Y, Z)
> 	    ;/* not yoo(Z) */
> 		tock(Y``),
> 		hoo(X, Y, Z)
> 	    )
> 	).

This becomes

	( foo(Z),
	  bar(X, X1) ->
	  	( yoo(Z) ->
			tick(X1, X2),
			hoo(X2, Y, Z),
		;
			tock(Y, Y1),
			hoo(X1, Y, Z),
		)
	;
		baz(Y, Y1),
		( yoo(Z) ->
			tick(X, X1),
			hoo(X1, Y1, Z),
		;
			tock(Y, Y1),
			hoo(X1, Y1, Z)
		)
	).

No extra unifications are needed because there are no consumers after
the top-level if-then-else.

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

No.  The intuition is that doing everything using ordinary Prolog
syntax can lead to code that is hard to understand and maintain.  I do
find it somewhat distasteful that syntactically identical goals do not
have the same behaviour, but that's just what happens with DCGs and
they *are* a useful tool.  The same goes for Peter van Roy's named
threads package and variants.

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

God, I've really stepped on your toes over this one.  YES, if someone
can show me how to make an updated state vector via a calculation that
uses multiple elements of that vector IN A CONCISE AND OBVIOUS MANNER
then I will be a very happy man.  But so far I ain't seen it.

Ralph

p.s. As an example of where this is an issue, a friend has challenged
me to rewrite the SPEC benchmark 129compress.c in Mercury and get it
to run within a factor of 6 as fast.  The algorithm is LZW using
double hashing.  129compress.c is an opaque bit of code that has been
finely tuned by many hands to the point where it is all but a step
away from assembler.  There are something like 26 global variables in
it and I'd say a good 18 of them are updated in the main
loop.

I've decided to do as clean a rewrite as I can in Mercury.  I've opted
to store the state in a container with access and update functions.
I'll leave it to the compiler to optimise all the low-level detail.
It still looks clunky on the page and I'd very much like a way of
handling that amount of state in an elegant way.