Next: Useful Tip 2 Up: Efficiency Considerations Previous: Efficiency Considerations

## Useful Tip 1

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.
This provides the definitions shown below:

```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.

Next: Useful Tip 2 Up: Efficiency Considerations Previous: Efficiency Considerations

Dave Stuart Robertson
Tue Jul 7 10:44:26 BST 1998