Control annotation allows the programmer to have some command on the execution flow of the program. There are three ways in which a given execution path can be forced by the programmer:
We will describe the use of pruning operators later, as they are really additions external to a logical language, while the ordering of goals and clauses stem from decisions regarding mainly performance matters, and which happen to be also useful for controlling the execution flow.
Execution of goals is always4.1 performed left-to-right. This allows the programmer to know the behavior of the program and the order in which variables will be instantiated. It also impacts the performance of the program--precisely by instantiating some variables to some values after or before some points. Consider the following piece of code:
p(a):- <something really big>. p(b). q(b).
which is called using these two different queries:
?- p(X), q(X). %% (1) ?- q(X), p(X). %% (2)
(1) will execute the big chunk of code in the first clause of p/1 to fail afterwards, and succeed with the second clause of q/1. (2) will instantiate X to b, and will not even try to execute the first clause of p/1--so the effect is more profound than just reorganizing the order of the clauses of p/1. Moreover, the optimal ordering of goals depends ultimately on the query mode, i.e., the values the variables have at runtime.
The order of clauses in a predicate determine the order in which alternative branches for a computation are taken. Therefore, in the case of several solutions, it determines the order in which these solutions are returned. Compare the code
p(a). p(b). p(c).
with the code
p(b). p(a). p(c).
In the former case, a query ?- p(X). will return the solutions X = a, X = b, X = c, and in the latter, the solutions will be returned as X = b, X = a, X = c. Therefore, putting the clauses more likely to lead to a solution in the first place is sensible, because this would shorten the computation needed to reach this solution. In fact, a wrong order of clauses can lead to non termination: the following code
n(s(X)):- n(X). n(z).
loops ad infinitum when the query ?- p(X). is issued. Switching the clauses
n(z). n(s(X)):- n(X).
returns an infinite number of solutions (of course, there is an infinite number of solutions). When all solutions are required, the whole search tree is explored, so if it is infinite, the search will never end, yielding either an infinite number of solutions, or falling into the so-called ``infinite failure'': a branch which does not lead to a solution, but with a pattern which repeats itself.
Pruning operators, to be discussed later, will help us in achieving more control on these cases.