Prolog: stop condition?

Question

Here's a very trivial Prolog knowledge base:

spouse(bill,cheryl).
married(X,Y) :- spouse(X,Y).
married(X,Y) :- spouse(Y,X).

I ran the following queries. Note that sometimes the answer is the correct name (only), but other times the answer is the correct name and "false".

1 ?- married(bill,X).
X = cheryl ;
false.

2 ?- married(cheryl,X).
X = bill.

3 ?- married(X,bill).
X = cheryl.

4 ?- married(X,cheryl).
X = bill ;
false.

Can someone explain this seemingly inconsistent behavior? Thanks in advance.

Answer 1

The false response from Prolog means that Prolog had a choice point to go back to in an attempt to find further answers and it found no more. The order in which your predicates and facts are set up can impact whether it thinks it has more choices to explore.

In the given case:

spouse(bill,cheryl).

married(X,Y) :- spouse(X,Y).
married(X,Y) :- spouse(Y,X).

1 ?- married(bill,X).
X = cheryl ;
false.

2 ?- married(cheryl,X).
X = bill.

3 ?- married(X,bill).
X = cheryl.

4 ?- married(X,cheryl).
X = bill ;
false.

In the two false cases, the query married/2 is satisfied by the first of two married/2 clauses. Once satisified, Prolog realizes it has another choice to make (the second married/2 clause), and prompts for you to look for more. You press ;, then Prolog explores the second (and final) clause, finds no more solutions, and comes back false.

Swap the order of your married/2 clauses and see what happens:

spouse(bill,cheryl).

married(X,Y) :- spouse(Y,X).
married(X,Y) :- spouse(X,Y).

?- married(bill,X).
X = cheryl.

?- married(cheryl,X).
X = bill ;
false.

?- married(X,bill).
X = cheryl ;
false.

?- married(X,cheryl).
X = bill.

As expected, the results are reversed since we've changed which queries are satisfied by the first clause.

The false response can appear inconsistent to beginning Prolog programmers and "feel" like an error or warning, but it's actually a perfectly normal Prolog response. Prolog is quite consistent in its behavior of attempting to find solutions and, when no more choices exist, will return false. If Prolog has exhausted all the other choices before it finds the final solution, it displays the solution and doesn't return false (as in the case above in which the second clause is the only solution).

There is a temptation to try and "clean up" the false responses by using cuts. Although this can have the desired short-term result, it is risky since you are removing choice points from the predicate and as you add data and logic may eliminate solutions which you really want.

Thus, in the modified case:

spouse(bill,cheryl).
spouse(emma,nate).

married(X,Y) :- spouse(X,Y), !.  % If we found the spouse, we're done, no more!
married(X,Y) :- spouse(Y,X).

?- married(bill,X).
X = cheryl.

?- married(cheryl,X).
X = bill.

?- married(X,bill).
X = cheryl.

?- married(X, cheryl).
X = bill.

Yay, life is good! But wait, what if we do this:

?- married(X,Y).
X = bill,
Y = cheryl.

?-

Are bill and cheryl the only married couple? No... it left out nate and emma. The cut eliminated the rest of the solutions.