Prolog compiler return error

Question

I have this hypothetical program to check if a path exists from point A to B.

/*city rules*/

edge(phx, tuc).
edge(tuc, ccg).
edge(ccg, sf).

connected(C1, C2) :-
   edge(C1, C2).
connected(C1, C2) :- 
   edge(C1, X),
   connected(X, C2).

the problem is it returns true, then false. Where is the false coming from?

Answer 1

Let's look at the exact reply you got from Prolog! First you got a single true and on pressing SPACE or ; you eventually got:

?- connected(phx,sf).
   true
;  false.

So you got true ; false. as the complete answer. The ; means "or". So Prolog essentially says: Your query connected(phx,sf). is the same as true ; false. So you need to look at the entire answer to understand what it means. Of course that is a bit odd, when true. would be good enough.

But first let's have another example:

?- connected(phx,X).
   X = tuc
;  X = ccg
;  X = sf
;  false.

Here Prolog's complete answer is: connected(phx,X). describes the same set of solutions as X = tuc ; X = ccg ; X = fg ; false. which again would be shorter if false would be omitted.

So why does Prolog write out this false? Prolog computes the answers incrementally. It first shows you X = tuc and waits what you would do. In a sense, it is a bit lazy not to show you everything at once. Sometimes, Prolog does know that there will be no further answer, in that case, it writes a dot directly:

?- member(X,[1,2]).
   X = 1
;  X = 2.

Here Prolog says: dixi! I have spoken.

But sometimes, it is not that sure:

?- member(1,[1,2]).
   true
;  false.

After proving that 1 is a member, it stops, otherwise it would have to explore the list further.

So this ; false. means: After the last answer/solution, Prolog was not yet sure that everything has been explored. This might be an inefficiency, it might be an indication that something can be improved. However, never, ever take this as pretext to insert a cut into your program. The cut in another answer is completely malaprop. It is the source for many, many errors. Before starting to use cuts you really should learn the other, pure part of Prolog, first.

BTW: Here is a better definition for connected/2 which avoids infinite loops by using closure/3 (click on it to get the definition).

connected(C0,C) :-
   edge(C0,C1)
   closure0(edge,C1,C).