Problem with `\+` in Prolog queries with variables

Question

I'm reading "Seven languages in seven weeks" atm, and I'm stumped over some Prolog query that I don't understand the 'no' response to.

The friends.pl file looks like this:

likes(wallace, cheese).
likes(grommit, cheese).
likes(wendolene, sheep).

friend(X, Y) :- \+(X = Y), likes(X, Z), likes(Y, Z).

I can do some trivial queries on it, such as:

| ?- ['friends'].
compiling /home/marc/btlang-code/code/prolog/friends.pl for byte code...
/home/marc/btlang-code/code/prolog/friends.pl compiled, 12 lines read - 994 bytes written, 8 ms

yes
| ?- friend(wallace,grommit).

yes
| ?- friend(wallace,wendolene).

no

This is all as expected. Now, I want to introduce a variable in the query. My intent being that Prolog will give me a list of all of Wallace's friends. I'm expecting X = grommit, but I'm getting no:

| ?- trace.
The debugger will first creep -- showing everything (trace)

yes
{trace}
| ?- friend(wallace,X).
      1    1  Call: friend(wallace,_16) ?
      2    2  Call: \+wallace=_16 ?
      3    3  Call: wallace=_16 ?
      3    3  Exit: wallace=wallace ?
      2    2  Fail: \+wallace=_16 ?
      1    1  Fail: friend(wallace,_16) ?

no
{trace}

It doesn't even try to unify X (_16) with grommit. Why?

Hospitalet

Answer 1

It is the definition of friend:

friend(X, Y) :- \+(X = Y), likes(X, Z), likes(Y, Z).

The important thing here is that you start with \+(X = Y) which is normally defined as:

\+ Goal :- Goal,!,fail

Note that this means that if goal succeeds, you are sure to fail. Free variables (ones that havent been assigned) will always unify, and thus be equal, so you will always fail with a free variable. It will thus never assign a value to X or Y if it doesn't already have one.

Instead

friend(X, Y) :-  likes(X, Z), likes(Y, Z), \+(X = Y)

will behave more as you expect.

The problem here is that prolog gives you powerful ways to control the flow of programs, but those dont really fit nicely with its more logic oriented design. It should be possible to express "negation as failure" type constraints in a way that does not produce these problems. I'm not a huge prolog fan for this reason.

Thorathoracic

Answer 2

Regarding Philip JF's comment above:

It should be possible to express "negation as failure" type constraints in a way that does not produce these problems.

This is possible: The modern solution for such problems are constraints. In this case, use for example dif/2, available in all serious Prolog systems.

Nonfeasance

gprolog (v1.3): uncaught exception: error(existence_error(procedure,dif/2),friend/2) – Hospitalet

Try for example SWI, Yap, SICStus, B-Prolog, and several others. – Nonfeasance

Answer 3

The first subgoal of friend/2 is \+(X = Y). This is executed by first trying to find a solution for X = Y, then negating that result. The predicate =/2 is roughly the equivalent of unify/2, that is it tries to unify the left operand with the right operand. Now, when you are asking queries using e.g. friend(wallace, gromit), the two atoms wallace and gromit do not unify; but when a free variable is thrown into the mix, it always unifies with whatever term is given, so X = Y is always successful, therefore \+(X = Y) always fails, and the execution never gets past that first subgoal.

Zinnia

OK, understood. How would you reformulate friend/2 so it works with a query containing variables? – Hospitalet

At first glance, I would have used the equality operator ==/2 and rewritten it as friend(X, Y) :- \+(X == Y), likes(X, Z), likes(Y, Z). but this version has the defect of including yourself within your friends, e.g. friend(wallace, X) will list wallace as a solution. So it's better, as Philip JF suggests, even if he's still using the unification operator, to put the check at the end: friend(X, Y) :- likes(X, Z), likes(Y, Z), X \== Y. (Note that \==/2 is equivalent to negating ==/2, but clearer, just more direct.) – Zinnia

Answer 4

Another issue with having the inequality constraint first is: It is uncapable to find a binding for the unbound X (excluding the trivial case of unifying it with grommit for the moment). Prolog finds bindings by running through its database, trying to unify the unbound variable. That is why likes(grommit, Z) will find some binding for Z which can then be further processed, because there are likes clauses in the database. But there are no such clauses for the inequality of grommit with something, so Prolog cannot produce any bindings. As things stand, the friend predicate has to make sure that all variables are bound before the inequality can be tested.

Sedda