It is of course completely true that the order matters a great deal in this case. In fact, in this case, the order of goals matters
much more than students typically realize! In my experience, students who write down and then run the first version frequently walk away with the impression that "Prolog is slow". But in fact this is a performance problem only in the widest sense of the word: This is rather a
termination problem.
Luckily, there is a powerful way to detect such problems in Prolog, based on program slicing. The trick is to narrow down the program to those fragments that exhibit the same problem.
For example, let us start with the first program and one fact for parent_of/2:
parent_of(a, b).
ancestor_of(P, P).
ancestor_of(A, P) :-
ancestor_of(A, Parent),
parent_of(Parent, P).
Rather insidiously, from a quick first test, the program even
seems to work as intended:
?- ancestor_of(X, Y).
X = Y ;
X = a,
Y = b .
With the following query, we get to the core of the problem:
?- ancestor_of(X, Y), false.
Nontermination!
Now the point: I can systematically remove some aspects of the program by simply removing goals and even entire clauses. For example, what about this fragment, where I have commented out a few parts:
% ancestor_of(P, P).
ancestor_of(A, P) :-
ancestor_of(A, Parent).
% parent_of(Parent, P).
In other words, we are now talking about:
ancestor_of(A, P) :-
ancestor_of(A, Parent).
This fragment
by itself already does not terminate:
?- ancestor_of(X, Y), false.
Nontermination!
The point is: No pure goal you add
after the single goal, and no pure clause you add to this program can
prevent this nontermination! It will always stay there unless you insert new constraints (goals)
before the goal, or change the clause altogether.
The possible application of such reasoning is a rather unique property of Prolog. In fact, I know of no other programming language that even comes close to admitting such a general and easily applicable mechanism for reasoning about termination properties and other aspects!
More holds: Such reasoning can be automated! It is comparatively easy to write a Prolog program that systematically eliminates goals and clauses for you, and reasons about the resulting fragments. Some kinds of nontermination can even be automatically detected (the general problem is of course undecidable).
A few practical guidelines for writing efficient and especially terminating Prolog programs can also be derived from such considerations.