[mercury-users] Pred defns

[Fergus Henderson]

On 06-Apr-1998, Ralph Becket <rwab1 at cam.sri.com> wrote:
> Fergus Henderson wrote on 5 Apr:
> > My answer is to say that ensuring "Clean Denotational Semantics of
> > Source Code" is one of the foremost goals of Mercury.
[...]
> > One of the key features of Mercury is
> > that it takes the ideal of PROgramming in LOGic and makes it a
> > reality -- your program is indeed a set of statements in logic
[...]
> Yes, I can't argue with the intention, but I'm not totally sure it's
> realizable - and you do use DCGs in quite a bit of Mercury code!

True. 

However, DCGs *can* be interpreted as just statements in logic,
so long as you use `phrase/3' (currently we *don't*, which is
probably something that we should fix) to invoke them from non-DCG code.
If you do that, then the semantics of DCGs can be defined as follows:

	phrase(H, S0, S) :-
		H --> B,
		phrase(B, S0, S).
	phrase({G}, S, S) :-
		G.
	phrase((A, B), S0, S) :-
		phrase(A, S0, S1),
		phrase(B, S1, S).
	phrase((if A then B else C), S0, S) :-
		(if phrase(A, S0, S1) then
			phrase(B, S1, S)
		else
			phrase(C, S0, S)
		).
	% plus a few other clauses for `not', `;', etc.

According to this viewpoint, when we write DCGs, we're just
writing clauses for '-->'/2.  Everything we write is therefore
just statements in logic.

Saying that we're still programming in logic is perhaps misleading,
because actually we're programming in DCGs, and phrase/3 is
an interpreter for DCGs.  But that's just a different way of viewing
what is happening, and both viewpoints are correct.

Now, you can of course argue about the utility of the 
programming-directly-in-logic viewpoint, because in practice
the alternative viewpoint (programming-in-DCGs, which can be
easily *translated* into logic) tends to be much more useful.
However, the former viewpoint does have a nice conceptual elegance.
And past experience suggests that preserving nice theoretical
properties often leads to later practical advantages.
So I'm reluctant to ditch it.

> This whole debate is about how to help programmers by abbreviating a
> common idiom (accumulator threading) in as clean a way as possible and
> nobody's yet suggested anything that satisfies the Program as (just)
> Logic criterion.

My first modified version of your original proposal (with lower-case
names for accumulators, with `#:-' instead of `:-', and with `#{...}'
having an analgous role to that of phrase/3) satisfied this definition
in the same way that DCGs do.  However, the interpreter in this case is
considerably more complex -- ~120 lines of code as compared to ~20 for
DCGs.

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