Negation in Prolog

The first Prolog example in Bruce Tate’s Seven Languages in Seven Weeks has a bug.  Tate defines the predicate \+ to be “logical negation”, but this is incorrect.  It’s like logical negation, but differs in ways that cause straightforward queries to fail.

Problem with the First Example

The first example involves facts about Wallace and Grommit.  Here is the program that I load into GNU Prolog 1.3.0.

Listing 1

likes(wallace, cheese).
likes(grommit, cheese).
likes(wendolene, sheep).
friend(X, Y) :- \+(X = Y), likes(X, Z), likes(Y, Z).

This is a straightforward attempt at encoding the knowledge we’d express in English as: “Wallace and Grommit like cheese; Wendolene likes sheep” and “Two different things are friends if they both like at least one of the same thing”.  Evaluation 1 shows the results of querying this knowledge base.

Evaluation 1

| ?- likes(wallace, cheese).
 yes

| ?- friend(wallace, grommit).
 yes

| ?- friend(wallace, wallace).
 no

| ?- likes(wallace, Q).
Q = cheese
 yes

| ?- likes(Q, cheese).
Q = wallace ? a
Q = grommit
 no

| ?- friend(wallace, Q).
 no

The first three queries look reasonable.  The fourth and fifth queries make Prolog search and report correct assignments of atoms to the variable Q. The sixth query attempts this same type of query; however, it fails to find an assignment. This is unexpected, as we know from our second query that Q=grommit is a consistent assignment!

Improved First Example

Listing 2 gives a version of the first example that behaves as expected.  The fix is to move the constraint \+(X = Y) to the end of the rule.

Listing 2

likes(wallace, cheese).
likes(grommit, cheese).
likes(wendolene, sheep).
friend(X, Y) :- likes(X, Z), likes(Y, Z), \+(X = Y).

Evaluation 2

| ?- friend(wallace, Q).
Q = grommit ? ;
 no

\+ is Not Logical Negation

The fact that Listing 2 produces the correct output by reordering the predicates might be unsettling if one’s mental model of a Prolog program is that of a set of logical statements comprehended by a black box theorem prover. However, \+ is not logical negation and, more broadly, it is dangerous to ignore the details of how Prolog goes about searching for solutions.

The predicate \+(M) is implemented as “negation as failure” (NAF). The first thing this predicate does is attempt to prove the goal M. If this can be satisfied, then the next thing the predicate does is to make a cut. Cuts freeze all variable assignments made in a rule, from the beginning up to the point at which the cut appears. Finally, the predicate fails explicitly. All of this machinery effectively causes \+(M) to be false if M is true.

The incorrect behavior in the first program is due to the cut. The M goal in \+(M) contains free variables, and it is easy to find an assignment for those variables such that M is true. The cut prevents any other assignments of these variables to atoms, and therefore \+(M) is always false and the rule can never succeed.

For listing 1, Prolog does something like the following:

  1. Goal 1: friend(wallace, Y)
  2. Goal 2: \+(wallace = Y)
  3. Goal 3: wallace = Y
  4. Succeed 3: Y <-- wallace
  5. Cut and prevent reassignment of Y
  6. Fail 2 with no possibility of success because \+(wallace = (Y = wallace)) is always false
  7. Fail 1

By moving the negation predicate to the end of the rule, Prolog will search for variable assignments for the variables in the goal M before the negation predicate appears.  Prolog does something like the following for listing 2:

  1. Goal 1: friend(wallace, Y)
  2. Goal 2: likes(wallace, Z)
  3. Succeed 2: Z <-- cheese
  4. Goal 3: likes(Y, cheese)
  5. Succeed 3: Y <-- wallace
  6. Goal 4: \+(wallace = wallace)
  7. Fail 4, with a similar reasoning as above
  8. Backtrack to 3 (cuts don’t freeze variables set in other goals)
  9. Goal 3: likes(Y, cheese)
  10. Succeed 3: Y <-- grommit
  11. Goal 4: \+(wallace = grommit)
  12. Succeed 4, because wallace = grommit is false
  13. Succeed 1, since we’ve succeeded in all sub-goals

Tags:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: