Be careful how you order your clauses. The order of clauses and/or subgoals in a Prolog program with a declarative interpretation doesn't affect its declarative meaning buy often affects the way the program is executed. For example, the ancestor relation from the program Section 13.1 was defined as follows:
ancestor(A, B):- parent(A, B). ancestor(A, B):- parent(P, B), ancestor(A, P).
By switching the ordering of the clauses and/or subgoals in this definition we can obtain 3 different ways of defining the ancestor relation:
ancestor1
has the two clauses switched around.
ancestor2
has the order of subgoals switched around.
ancestor3
has the order of both clauses and subgoals switched around.
ancestor1(A, B):- parent(P, B), ancestor1(A, P). ancestor1(A, B):- parent(A, B). ancestor2(A, B):- parent(A, B). ancestor2(A, B):- ancestor2(A, P), parent(P, B). ancestor3(A, B):- ancestor3(A, P), parent(P, B). ancestor3(A, B):- parent(A, B).
All of these variants of ancestor/2
have the same declarative meaning;
the order of clauses or subgoals doesn't affect this. However, the
way they are executed by the Prolog interpreter is very different,
giving a different external behaviour of the program. Consider the
following transcript of a Prolog session, in which we have first loaded the
definitions in Section 13.1 and then the variants of
ancestor
given above. We
then give the goal to find some ancestor of dave
using each of
the definitions in turn :
yes | ?- ancestor(X, dave). X=clive ; X=clarissa ; X=alan ; X=andrea ; X=bruce ; X=betty yes | ?- ancestor1(X, dave). X=alan ; X=andrea ; X=bruce ; X=betty ; X=clive ; X=clarissa yes | ?- ancestor2(X, dave). X=clive ; X=clarissa ; X=alan ; X=andrea ; X=bruce ; X=betty yes | ?- ancestor3(X, dave). %%% Local stack overflow - forced to abort %%%
Although ancestor1
and ancestor2
return the same values
for X
, these values
are returned in a different order. This is because in ancestor1
the
recursive clause appears before the base case, so the interpreter always
tries to find a solution ``the long way'' before considering the shorter
alternative. In ancestor3
, the combination of putting the
recursive case first and putting the recursive call to
ancestor3
before the step to parent
causes the interpreter to descend through an endless chain of subgoals until
it eventually runs out of memory and drops dead.
The moral of the story is : Your Prolog program may have a nice declarative interpretation but if you want it to execute you must often consider its procedural aspects.