Commutativity of disjunction in Prolog

Question

I've just started learning Prolog and I encountered a problem that I don't understand. When I ask:

?- fail; true.

Prolog answers:

true

Which is something I expected. But, if I ask:

?- true; fail.

Prolog answers:

true ;
false.

..and I don't understand why. The disjunction operator should be commutative. Why are these two Prolog answers different?

Answer 1

it's just a detail of top level interaction, then you could observe a different behaviour depending on Prolog interpreter you're using.

SWI-Prolog, in introductory documentation, gives some information:

2.1.2 Executing a query

After loading a program, one can ask Prolog queries about the program. The query below asks Prolog what food `sam' likes. The system responds with X = if it can prove the goal for a certain X. The user can type the semi-colon (;) or spacebar6 if (s)he wants another solution. Use the return key if you do not want to see the more answers. Prolog completes the output with a full stop (.) if the user uses the return key or Prolog knows there are no more answers. If Prolog cannot find (more) answers, it writes false.

Answer 2

Also note that the Prolog disjunction operator, (;)/2, is not commutative in general. For example:

?- !; write(else).
true.

?- write(then); !.
then
true ;
true.

The right branch of the disjunction is only tried on backtracking if the implicit choice point is not cut when executing the left branch. Note that a clause such as:

foo :- (!; write(else)).

is equivalent to:

foo :- !.
foo :- write(else).

Thus, cuts and (other) side-effects result in (;)/2 not behaving as logical disjunction.

Answer 3

The confusion regards how prolog displays results. When you make a query in prolog, it will attempt to find all possible answers. That means it will start at the first fact or clause, go through them sequentially and, when it can finally make the query true, displays the answer. If there was a choice point in the process of finding the last solution, prolog prompts the user to seek more possible successful solutions.

In the case of:

?- false ; true.

This query starts by looking at the clause false, which fails and then, since there's a disjunction ;, checks the clause after the ; which is true. This succeeds, and prolog displays:

true

Note that when it found this solution, there were no more choices, so there's no prompt for further solutions.

Now let's look at the second example:

?- true ; false.

Prolog looks at the first clause, true, and succeeds and tells the user:

true

But in this case, it hasn't exhausted all of the possible solutions since there's a disjunction ; that created another choice. So when you enter the ; at the prompt:

true ;

You tell prolog to find more solutions. Prolog goes back and checks the clause after the disjunction and encounters false. This fails and there are no other solutions. Therefore, your request for further solutions fails and prolog outputs false:

true ;
false

The first true means it succeeded. The false means it found no more solutions and failed on the second attempt.

Prolog's behavior is to seek solutions sequentially through the appropriate clauses and present them as long as you ask for them until it fails. When it finally fails, you get false. Some prologs output no. The behavior above is not a commutativity issue.