Prolog Backtracking On Finding A Solution And Returning False

Question

I'm taking a crack at Prolog (using SWI-Prolog) and everything works like I want it to, i.e., the logic is calculated correctly and it finds the right solutions but the whole backtracking thing is screwing with me.

Here's the code:

tall(X) :- skinny(X) ; eatless(X).
eatless(X) :- playsmore(X).
playsmore(X) :- hasxbox(X) ; hasplaystation(X).

skinny(a).
vegetarian(a).
hasxbox(b).
eatsburger(c).
hasplaystation(d).

list_all_tall :- forall(tall(Tall), writeln(Tall)).

Very basic stuff. Here's what I get as a result of my queries:

?- tall(a).
true ; % Note 1
false.

?- tall(b).
true ; % Note 2
false.

?- tall(c).
false.

?- tall(d).
true.

As you can see from Notes 1 and 2, it waits for me to hit ; to move on and then considers the first solution as null and eventually outputs false.

I can use cuts to control this behavior better but I also want the following commands to work properly:

?- tall(X).
X = a ;
X = b ;
X = d.

And:

?- list_all_tall.
a
b
d
true.

These two commands give the solution exactly the way I want. Its just the ones for Notes 1 and 2 that are driving me up the wall. Is there a way that I can keep the functionality as it is right now for tall(X). and list_all_tall., while fixing the functionality of tall(a). and tall(b). to my liking, i.e., the program should exit with a true. after I ask tall(a). or tall(b).

I'd appreciated it if instead of giving straight answers someone could actually explain how I could go about fixing it myself because maybe my way of thinking in Prolog is all bassackwards.

PS: No offense intended to tall, skinny, fat, burger eating, video game playing, vegetarian folks.

Answer 1

Just to supplement Daniel's well-explained answer (+1) for your specific case, consider:

tall(a).

Prolog will look at the first match, which is through:

tall(X) :- skinny(X) ; eatless(X).

This will succeed because skinny(a) will succeed. However, there's a disjunction ; leaving a choice point for Prolog that it hasn't explored yet. Because skinny(a) succeeds and the choice point is pending, you get true but prompted to seek more. Prolog then backtracks to the choice point and tries to satisfy eatless(a) but fails. Thus, you get:

?- tall(a).
true ; % because `skinny(a)` succeeded
false. % because `eatless(a)` failed

Taking another example:

tall(d).

Again, this matches the tall/1 predicate, but this time, skinny(d) fails and prolog moves right on (due to the disjunction) to eatless(d) which succeeds. However, there are no more choice points after that success, so you get:

?- tall(d).
true.  % There were no choice points available after success

Answer 2

The best thing to do is not worry about it, because you're not always going to be able to prevent it.

Prolog doesn't ever know that there will be another answer. It just knows that there may be another answer. This is called a choice point. Whenever Prolog reaches an alternative, it creates a choice point and then follows the first option. If that option doesn't work out, it backs up to the most recent choice point and tries the next alternative. If it runs out of alternatives without finding an answer, you get no or false.

You can try to write your code so that you don't get a choice point if you know there are no more items. member/2, for instance, in some Prologs you get false after the last item and in others you do not. But it isn't a composition problem to have a dud choice point after all your solutions. Your user interface probably won't show users Prolog's prompts directly. You can use setof/3 and the other extralogical predicates to get all the solutions. The false won't "leak" out into the world. It's a little unnerving at first, but just trust it and don't worry too much about it.

Answer 3

It is possible to run the same predicate, tall/1 in this case, in different modes based on different instantiation patterns. When you run ?- tall(a). you instantiate the argument (i.e., X=a) and you want to receive either true or false (and no choicepoints, indicated by ;). In Prolog this mode is called semi-deterministic.

You can force your predicate to be semi-deterministic for this specific instantiation pattern in the following way:

tall(X):- (ground(X) -> once(tall0(X)) ; tall0(X)).

Here ground(X) succeeds just in case X is fully instantiated. Fully instantiated means that it is not a variable nor is it a compound term containing a variable. tall0(X) is your original predicate.

The second mode you want to use is ?- tall(X). Here you expect all results to be given subsequently, using ;. This mode is called non-deterministic in Prolog.

The complete code for your example is:

tall(X):- (ground(X) -> once(tall0(X)) ; tall0(X)).
tall0(X):- skinny(X) ; eatless(X).
eatless(X):- playsmore(X).
playsmore(X):- hasxbox(X) ; hasplaystation(X).
skinny(a).
hasxbox(b).
hasplaystation(d).

Now the single predicate tall/1 can be called in the two modes, producing the behavior you want. Semi-deterministic usage:

?- tall(a).
true.

Non-deterministic usage:

?- tall(X).
X = a ;
X = b ;
X = d.

Hope this helps!