Previous Table of Contents Next


6.4.5. The Transitive Closure Problem

Consider the following code:

   sibling(constance, cathleen).
   sibling(cathleen, john).
   sibling(X, Y) :- sibling(X, Z), sibling(Z, Y).

This code defines a relation sibling by two “base” clauses and a recursive clause. It does not seem like dangerous code because the two base clauses appearing first seem to block any potential infinite recursion; indeed, the code gives correctly the two first answers to the query sibling(constance, X). Unfortunately, however, when we type the semicolon for more solutions, the query does loop infinitely. This is a common problem encountered in knowledge-base applications; it is referred to as the transitive closure problem because we are trying to take the transitive closure of the base clauses.

What has happened here? Let’s pick up the debugger trace after the second solution:

   1  1  Redo: sibling(constance,john) ?
   3  2  Redo: sibling(cathleen,john) ?
   4  3  Call: sibling(cathleen,_732) ?
   4  3  Exit: sibling(cathleen,john) ?
   5  3  Call: sibling(john,_77) ?
   6  4  Call: sibling(john,_1180) ?
   7  5  Call: sibling(john,_1347) ?
   8  6  Call: sibling(john,_1514) ?
   …

This highlights the problem. As soon as we call sibling with a first argument (say, john) that does not appear as a first argument in the base clauses, we immediately skip to the recursive clause and call a goal of exactly the same form.

The solution is to separate the two levels of the predicate from each other and treat sibling as the transitive closure of some other relation, say sibling_base. The revised code looks very much like the parent and ancestor relations:

   sibling_base(constance, cathleen).
   sibling_base(cathleen, john).

   sibling(X, Y) :- sibling_base(X, Y).
   sibling(X, Y) :- sibling_base(X, Z), sibling(Z, Y).

This problem is made more complex when reflexive or symmetric relations are desired. A full treatment of the associated issues is found in O’Keefe’s book (1990).

6.4.6. Tail Recursion Optimization

As in Lisp compilers, most modern Prolog compilers have tail recursion optimization. This means that if a clause defining p ends in a call to p, the recursive call is not compiled in such a way as to push an execution frame on a stack, but rather as a jump to the beginning of the code for the predicate. This means that a recursive predicate can execute without eating up stack space. Clauses that end with a call to the predicate being defined, without calling the predicate being defined anywhere else, are called tail-recursive; the method of compilation is called tail recursion optimization.

To make full use of this feature, it is sometimes necessary to re-express a predicate to pass a partial solution parameter to the recursive call. This parameter is often referred to as an accumulator. The classic example is the reverse predicate, which is coded most naturally as follows:

   reverse([], []).
   reverse([X|Xs], Zs) :-
    reverse(Xs, Xsrev),
    append(Xsrev, [X], Zs).

Besides being inefficient in having calls to append that involve N recursive calls, where N is the length of the list being reversed, this code is not able to be tail-recursion optimized.

The usual tail-recursive version involves a call to an auxiliary tail- recursive predicate with an extra accumulator argument:

   reverse(X, Y) :-
    revappend(X, [], Y).

   % revappend(X, A, Y):  the reverse of X,
   % appended onto A, results in Y.
   revappend([], A, A).
   revappend([X|Xs], A, Y) :-
    revappend(Xs, [X|A], Y).

Note that the second argument of revappend is in some sense a trick, but that the predicate nevertheless has a perfectly logical meaning. Whenever we write an auxiliary predicate, even if it arises from some coding technique such as this, it is useful to try to find the real meaning of the predicate and express it in a comment.

6.4.7. First Argument Indexing

Another optimization found in most compilers and many interpreters is first argument indexing. Prolog implementers discovered early on that the clauses defining a given predicate often differed from each other in the outermost function symbol of the first argument. They then developed strategies for exploiting this.

When executing a query of the form append(X, Y, Z), for instance, Prolog should theoretically try to match each recursive call to append with both clauses of the definition. However, if it remembers that the first clause of append has the empty list as its first argument, and the second clause has a non-empty list as its first argument, it can throw away any unnecessary backtrack points simply by looking at the format of the first argument, X. If X is an uninstantiated variable, it needs to look at both clauses; but if it is the empty list or a non-empty list, it needs to look at only one clause.

This is taken a bit further in most Prolog systems. When a predicate definition is processed, the clauses are classified according to the outermost function symbol of the first argument and then placed in an efficient data structure such as a hash table for easy lookup. Calls with partially instantiated first arguments can then be executed in much less time than before and with much less overhead because useless backtrack points are discarded before they are even reached. In compiled Prolog code, this can turn a backtracking call to a multi-clause predicate into a straightforward transfer to a single clause.

We can exploit first argument indexing by ordering the arguments of the predicates so that the outermost function symbol of the first argument is the one that is most likely to be different from clause to clause. For predicates that traverse a list, for example, this means putting the list being traversed as the first argument. Thus the revappend predicate as given in the last section can be executed efficiently, but not if we had made the accumulator the first argument, as follows:

   reverse(X, Y) :-
    revappend([], X, Y).

   revappend(A, [], A).
   revappend(A, [X|Xs], Y) :-
    revappend([X|A], Xs, Y).

Even though the predicate definitions have the same logical meaning as before, many Prologs execute the second definition more slowly.


Previous Table of Contents Next