[mercury-users] The Logic of Mercury

[Fergus Henderson]

On 05-Sep-1999, Randall Helzerman <rahelzer at ichips.intel.com> wrote:
> I've got a few questions for the mercurators:
> 
> 1.  Is there a good introduction to the logic behind Mercury?  It would be
>     nice to have a concise introduction which layes it bare from the
>     lambda-calculus on up--does such a description exist anywhere?

John Lloyd's book "Theory of Logic Programming" (or is it
"Foundations of Logic Programming"?) is probably a good place to start.

> 2.  What is the relationship between the logic of Mercury and
>     the logic presented in the book "A clausal theory of types"
>     by D.A. Wolfram?

I haven't read that book, so I can't comment on that one.

> 3.  Lee Naish [...] in his paper "Higher-order logic programming in Prolog"
>     criticizes Hilog and Mercury for not having the "ultimate" higher
>     order facuilty--the append/3 which was recommended by David Warren

I think you mean "apply/3" rather than "append/3".

In response to that paper, I have several remarks to make.

One point is that the expressiveness difference between call/N and
apply/3 is really not that great.  Lee gives as an example the goal
`map(plus, [2,3,4], As)', which if map/3 is implemented using apply/3
would bind `As' to `[plus(2), plus(3), plus(4)]', but which is a type
error if map/3 is implemented using call/3.  However, with the call/3
version, it is easy enough to write `map(pred(X::in, plus(X)::out) is
det, [2,3,4], As)' if that is what you want.  Alternatively, you can
use functional notation rather than predicate notation, i.e.  `As =
map(func(X) = plus(X), [2,3,4])'.  Likewise, other examples using
apply/3 can be easily expressed with call/3 using some additional
lambda expressions.  So the issue is really one of convenience rather
than being one that leads to major differences in programming style.

Now there _are_ some significant issues in Mercury with regard to
higher-order code and reusability, in particular the issue of polymorphic
modes, which is a problem for examples like the one above.
In contrast, I don't think the use of call/3 is a serious barrier to
reusability -- the distinction between call/3 and apply/3 is a far less
important issue than polymorphic modes, IMHO.

Another point is that Lee's discussion of efficiency in that paper is
rather simplistic.  Although compilers will be able to partially evaluate
higher-order code into first-order code in many situations, there will
also be many situations in which that is not possible.  A full and proper
consideration of efficiency issues needs to take into account the case
where higher-order code cannot be partially evaluated away. 
And in fact with straightforward implementation techniques applyN/N will
be significantly worse than call/N in that case, I believe, particularly
for large N.  Lee's paper does not consider that issue.

A final point is that a large amount of work would need to be done to go
from the idea in Lee's paper to a concrete proposal for a change to Mercury.
For example, Lee advocates the use of type systems for higher-order code
but in that paper he does not make any attempt to say how apply/3 could
or should be typed.  Another related issue here that Lee mentions (but does
not resolve) is that there are problems with supporting both apply/3 and
overloading of predicates based on their arity.  And of course modes and
determinism would need to be addressed too.  So it's a long way from
idea to concrete proposal to production-quality implementation.

Cheers,
	Fergus.

-- 
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.
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------