2

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.

false
  • 10,264
  • 13
  • 101
  • 209
Bill Qualls
  • 397
  • 1
  • 7
  • 20
  • 1
    The `false` means that Prolog had a choice point to go back to in an attempt to find further answers and it found no more, so it comes back `false`. The order in which your predicates and facts are set up can impact whether it thinks it has more choices to explore. Swap the order of your `married` clauses and see what happens. :) In your case, the `false` occurs when your first clause succeeds and then Prolog goes back to attempt the second clause. – lurker Jan 27 '14 at 20:24
  • You're right. There is no recursion. Recursion was in an earlier attempt at this problem when I said spouse(X,Y):-spouse(Y,X). But that just caused loop, so I changed to this (easier?) example. I tried swapping the married clauses, but that just gave the same results. – Bill Qualls Jan 27 '14 at 20:33
  • I fixed it...sorta. I added a cut. The queries shown above work correctly now (no "false"). But...add another spouse predicate, and the query stops after the first pair only. spouse(bill,cheryl). spouse(emma,nate). married(X,Y) :- spouse(Y,X), !. married(X,Y) :- spouse(X,Y). Query...missing emma,nate: 6 ?- married(X,Y). X = cheryl, Y = bill. 7 ?- – Bill Qualls Jan 27 '14 at 20:38
  • 2
    possible duplicate of [Why is this prolog query both true and false?](http://stackoverflow.com/questions/3323201/why-is-this-prolog-query-both-true-and-false) – false Jan 27 '14 at 21:33
  • I wouldn't necessarily add a cut just to get rid of the `false` for the very reason you are observing, which is that "just adding cuts" can eliminate solutions you may want later on. Is the `false` causing a problem? BTW, I swapped the clauses and I didn't get the same result. The cases where false occurs moves per my prior explanation. I think you experienced that as well. It just seemed the same. The `false` will follow the cases where the first of the two clauses succeeds. – lurker Jan 27 '14 at 21:36
  • 1
    In my experience, you almost always wind up with an extra `false` arising in the middle layers of the code. The performance problems are usually elsewhere in the code, and since normal users are protected from the "aesthetics" of the REPL it tends not to be worth it to try and find it and remove it. For beginners like us, excising it with a cut is usually more trouble than it's worth. – Daniel Lyons Jan 27 '14 at 23:39
  • @mbratch Your comments are of answer quality. I can't speak for Bill Qualls, but I'd vote it up if it were an answer. – SQB Jan 29 '14 at 07:08
  • @ATS thanks. I consolidated my comments and added some detail to formulate an answer. – lurker Jan 29 '14 at 16:06

1 Answers1

4

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.

lurker
  • 56,987
  • 9
  • 69
  • 103
  • You said "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." So true! Thank you for your explanation. – Bill Qualls Jan 29 '14 at 16:44
  • +1 Excellent answer! And exactly what @BillQualls says. – SQB Jan 30 '14 at 07:00