3.2 Rule Ordering, Goal Ordering, and Termination
Prolog was the first reasonably successful attempt to create a logic programming language. Underlying logic programming is a simple (and seductive) vision: the task of the programmer is simply to describe problems. The programmer should write down (in the language of logic) a declarative specification (that is: a knowledge base), which describes the situation of interest. The programmer shouldn’t have to tell the computer what to do. To get information, he or she simply asks the questions. It’s up to the logic programming system to figure out how to get the answer.
Well, that’s the idea, and it should be clear that Prolog has taken some important steps in this direction. But Prolog is not , repeat not , a full logic programming language. If you only think about the declarative meaning of a Prolog program, you are in for a very tough time. As we learned in the previous chapter, Prolog has a very specific way of working out the answers to queries: it searches the knowledge base from top to bottom, clauses from left to right, and uses backtracking to recover from bad choices. These procedural aspects have an important influence on what actually happens when you make a query. We have already seen a dramatic example of a mismatch between the procedural and declarative meaning of a knowledge base (remember the p:- p program?), and as we shall now see, it is easy to define knowledge bases which (read logically) describe the same situations, but which behave very differently. Let’s consider the matter.
Recall our earlier descendant program (let’s call it descend1.pl ):
child(anne,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).
descend(X,Y) :- child(X,Y).
descend(X,Y) :- child(X,Z),
descend(Z,Y).
We’ll make one change to it, and call the result descend2.pl :
child(anne,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).
descend(X,Y) :- child(X,Z),
descend(Z,Y).
descend(X,Y) :- child(X,Y).
All we have done is change the rule order. So if we read the program as a purely logical definition, nothing has changed. But does the change give rise to procedural differences? Yes, but nothing significant. For example, if you work through the examples you will see that the first solution that descend1.pl finds is
X = anne Y = bridget
whereas the first solution that descend2.pl finds is
X = anne Y = emily
But (as you should check) both programs generate exactly the same answers, they merely find them in a different order. And this is a general point. Roughly speaking (we’ll add a caveat later on) changing the order of rules in a Prolog program does not change (up to the order in which solutions are found) the program’s behaviour.
So let’s move on. We’ll make one small change to descend2.pl , and call the result descend3.pl :
child(anne,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).
descend(X,Y) :- descend(Z,Y),
child(X,Z).
descend(X,Y) :- child(X,Y).
Note the difference. Here we’ve changed the goal order within a rule, not the rule order. Now, once again, if we read the program as a purely logical definition, nothing has changed; it means the same thing as the previous two versions. But this time the program’s behaviour has changed dramatically. For example, if you pose the query
?- descend(anne,emily).
you will get an error message (“out of local stack”, or something similar). Prolog is looping. Why? Well, in order to satisfy the query descend(anne,emily) Prolog uses the first rule. This means that its next goal will be to satisfy the query
?- descend(W1,emily).
for some new variable W1 . But to satisfy this new goal, Prolog again has to use the first rule, and this means that its next goal is going to be
?- descend(W2,emily).
for some new variable W2 . And of course, this in turn means that its next goal is going to be descend(W3,emily) and then descend(W4,emily) , and so on. That is, the (at first glance innocuous) change in the goal order has resulted in procedural disaster. To use the standard terminology, we have here a classic example of a left recursive rule, that is, a rule where the leftmost item of the body is identical (modulo the choice of variables) with the rule’s head. As our example shows, such rules easily give rise to non-terminating computations. Goal order, and in particular left recursion, is the root of all evil when it comes to non-termination.
Still, as we said earlier, we need to make one small caveat about rule ordering. We said earlier that rule ordering only changes the order in which solutions are found. However this may not be true if we are working with non-terminating programs. To see this, consider the fourth (and last) variant of our descendant program, namely descend4.pl :
child(anne,bridget).
child(bridget,caroline).
child(caroline,donna).
child(donna,emily).
descend(X,Y) :- child(X,Y).
descend(X,Y) :- descend(Z,Y),
child(X,Z).
This program is descend3.pl with the rule ordering reversed. Now (once again) this program has the same declarative meaning as the other variants, but it is also procedurally different from its relatives. First, and most obviously, it is very different procedurally from both descend1.pl and descend2.pl . In particular, because it contains a left recursive rule, this new program does not terminate on some input. For example (just like descend3.pl ) this new program does not terminate when we pose the query
?- descend(anne,emily).
But descend4.pl is not procedurally identical to descend3.pl . The rule ordering reversal does make a difference. For example, descend3.pl will not terminate if we pose the query
?- descend(anne,bridget).
However descend4.pl will terminate in this case, for the rule reversal enables it to apply the non-recursive rule and halt. So when it comes to non-terminating programs, rule ordering changes can lead to some extra solutions being found. Nonetheless, goal ordering, not rule ordering, is what is truly procedurally significant. To ensure termination, we need to pay attention to the order of goals within the bodies of rules. Tinkering with rule orderings does not get to grips with the roots of termination problems — at best it can yield some extra solutions.
Summing up, our four variant descendant programs are Prolog knowledge bases which describe exactly the same situations, but behave differently. The difference in behaviour between descend1.pl and descend2.pl (which differ only in the way rules are ordered) is relatively minor: they generate the same solutions, but in a different order. But descend3.pl and descend4.pl are procedurally very different from their two cousins, and this is because they differ from them in the way their goals are ordered. In particular, both these variants contain left recursive rules, and in both cases this leads to non-terminating behaviour. The change in rule ordering between descend3.pl and descend4.pl merely means that descend4.pl will terminate in some cases where descend3.pl will not.
What are the ramifications of our discussion for the practicalities of producing working Prolog programs? It’s probably best to say the following. Often you can get the overall idea (the big picture) of how to write the program by thinking declaratively, that is, by thinking in terms of describing the problem accurately. This is an excellent way to approach problems, and certainly the one most in keeping with the spirit of logic programming. But once you’ve done that, you need to think about how Prolog will work with knowledge bases you have written. In particular, to ensure termination, you need to check that the goal orderings you have given are sensible. The basic rule of thumb is never to write as the leftmost goal of the body something that is identical (modulo variable names) with the goal given in the head. Rather, place such goals (which trigger recursive calls) as far as possible towards the right of the tail. That is, place them after the goals which test for the various (non-recursive) termination conditions. Doing this gives Prolog a sporting chance of fighting it’s way through your recursive definitions to find solutions.
