[net.lang.prolog] Problem With "Not"

Narain@Rand-Unix@sri-unix.UUCP (08/16/83)

In browsing through the Prolog utilities today I came across one
that advised using \+ instead of not ( or something ) and noticed
the following example:

bachelor(X):-not(married(X)),male(X).

If we add:

married(a).
married(b).
male(c).

then :-bachelor(Y). fails. This is what the example said or implied.
But if we rewrite the rule as:

 bachelor(X):-male(X),not(married(X)).

 then :-bachelor(Y). succeeds with Y=c.

I think this is serious since the order of literals should not affect
what the program computes, only its efficiency if at all.
The problem arises since at runtime the argument to "not" contains a
variable.  This changes the meaning of not(X) to:

 there exists a Y such that not(married(Y)). In which case Y may be
 bound to any element in the set:

Herbrand-Universe for the program - {Y such that married(Y) is
derivable} a potentially infinite set.

But the call to not(married(Y)) must not fail.

No doubt this has been observed before and I would greatly appreciate
any comments on how to avoid the problem.

-- Sanjai

ok@edai.UUCP (Richard O'Keefe) (08/27/83)

A full reply to the "Problem with not" message has been sent to the ARPAnet
Prolog digest.  The points I make in it are
1) Please say which utility (it was Not.Hlp, which is not in fact a
   utility) and QUOTE ACCURATELY.
2) The reason Not.Hlp tells you to use '\+'/1 rather than 'not'/1 is that
   the latter doesn't exist in Dec-10 Prolog.  If you are running the bare
   Dec-10 Prolog system, not(X) fails for ANY X, including not(fail).  The
   \+ symbol is as close as you can get to |-/- without hacking the tokeniser.
3) Anybody who says that the order shouldn't make any difference isn't
   talking about Dec-10 Prolog, where the fact that the order makes a lot of
   difference to virtually EVERYTHING is both clearly stated in the manual and
   in the Clocksin & Mellish book, and is vital to getting the efficiency
   which separates Dec-10 Prolog from all other Prologs.  (E.g. Dec-10
   Prolog on a KL-10 : LM-Prolog on an LM2 = 10:1, both compiled.)
4) Dec-10 Prolog is step 3 on the way to getting an efficient logic
   programming language.  It manages the efficient bit ok, but the logic
   didn't fare quite so well.  MU Prolog, available from the University of
   Melbourne, IS order-independent, and the not problem simply doesn't
   exist in it.  Negated goals in MU Prolog are suspended until they are
   ground.  MU Prolog is step 4 on the way to getting an efficient logic
   programming language.  Now if only they could figure out how to make
   it run fast...  (Though it's better than a lot of the junk being sold
   commercially.)
5) When there are unbound variables in a negated goal, there are two
   possible interpretations, and NO theory which justifies either.  I
   claim that what Dec-10 Prolog does is correct (because negation flips
   quantifier type), and have never understood why some people expect a
   negation to bind variables.  If you want a logic programming language
   which has explicit quantifiers so that both interpretations can be
   expressed, have a look at Seif Haridi's LPL.