3.2. Pruning the search by means of cut

As shown in the previous section, Prolog constantly searches the clauses in a program in order to reach a success branch in the SLD-tree for a query. If a failure branch is reached (i.e., a non-empty resolvent which cannot be reduced any further), Prolog has to ‘unchoose’ the last-chosen program clause, and try another one. This amounts to going up one level in the SLD-tree, and trying the next branch to the right. This process of reconsidering previous choices is called backtracking. Note that backtracking requires that all previous resolvents are remembered for which not all alternatives have been tried yet, together with a pointer to the most recent program clause that has been tried at that point. Because of Prolog’s depth-first search strategy, we can easily record all previous resolvents in a goal stack: backtracking is then implemented by popping the upper resolvent from the stack, and searching for the next program clause to resolve with.

As an illustration, consider again the SLD-tree in Figure 3.1. The resolvent in the middle branch

:-teaches(peter,expert_systems).

cannot be reduced any further, and thus represents a failure branch. At that point, the stack contains (top-down) the previous resolvents

:-follows(S,C),teaches(peter,C).
?-student_of(S,peter).

The top one is popped from the stack; it has been most recently resolved with follows(paul,expert_systems), so we continue searching the program from that clause, finding follows(maria,ai_techniques) as the next alternative.

A node in the SLD-tree which is not a leaf is called a choice point, because the subtree rooted at that node may contain several success branches, each of which may be reached by a different choice for a program clause to resolve with. Now, suppose a subtree contains only one success branch, yielding an answer to our query. If we want to know whether there are any alternative answers, we can force Prolog to backtrack. However, since the rest of the subtree does not contain any success branches, we might as well skip it altogether, thus speeding up backtracking. But how do we tell Prolog that a subtree contains only one success branch? For this, Prolog provides a control device which is called cut (written !), because it cuts away (or prunes) part of the SLD-tree.

To illustrate the effect of cut, consider the following program.

parent(X,Y):-father(X,Y).
parent(X,Y):-mother(X,Y).
father(john,paul).
mother(mary,paul).

The SLD-tree for the query ?-parent(john,C) is given in Figure 3.4. The answer given by Prolog is { C → paul }. By asking whether there are any other answers, we force Prolog to backtrack to the most recent choice point for which there are any alternatives left, which is the root of the SLD-tree (i.e. the original query). Prolog tries the second clause for parent, but discovers that this leads to a failure branch.

Figure 3.4 SLD-tree for the query ?-parent(john,C).

Of course, we know that this backtracking step did not make sense: if John is a father of anyone, he can’t be a mother. We can express this by adding a cut to the first parent clause:

parent(X,Y):-father(X,Y),!.
parent(X,Y):-mother(X,Y).
father(john,paul).
mother(mary,paul).

The cut says: once you’ve reached me, stick to all the variable substitutions you’ve found after you entered my clause. That is: don’t try to find any alternative solutions to the literals left of the cut, and also: don’t try any alternative clauses for the one in which the cut is found. Given this modified program, the SLD-tree for the same query is shown in Figure 3.5. Since ! is true by definition, the resolvent :-! reduces to the empty clause. The shaded part represents the part of the SLD-tree which is pruned as a result of the cut. That is: every alternative at choice points below and including ?-parent(john,C), which are on the stack when the cut is reached, are pruned.

Figure 3.5 The effect of cut.

Note carefully that a cut does not prune every choice point. First of all, pruning does not occur above the choice point containing the head of the clause in which the cut is found. Secondly, choice points created by literals to the right of the cut, which are below the cut in the SLD-tree but are not yet on the stack when the cut is reached, are not pruned either (Figure 3.6).

Figure 3.6 Cut prunes away alternative solutions for s, but not for t. Also, choice points above :-q(X,Y) are not pruned.

Tip

The example in Figure 3.6 assumes there are two solutions for :-s(X) and for :-t(Y), and one solution for :-r(X,Y).

A cut is harmless if it does not cut away subtrees containing success branches. If a cut prunes success branches, then some logical consequences of the program are not returned as answers, resulting in a procedural meaning different from the declarative meaning. Cuts of the first kind are called green cuts, while cuts of the second kind are called red cuts. A green cut merely stresses that the conjunction of literals to its left is deterministic: it does not give alternative solutions. In addition, it signifies that if those literals give a solution, the clauses below it will not result in any alternatives.

This seems to be true for the above program: John is the father of only one child, and no-one is both a father and a mother. However, note that we only analysed the situation with regard to a particular query. We can show that the cut is in fact red by asking the query ?-parent(P,paul). The answer { P → mary } is pruned by the cut (Figure 3.7). That is, the literal father(X,Y) left to the cut is only deterministic if X is instantiated (is substituted by a non-variable value).

Figure 3.7 A success branch is pruned.

Note that success branches are also pruned for the first query if John has several children:

parent(X,Y):-father(X,Y),!.
parent(X,Y):-mother(X,Y).
father(john,paul).
father(john,peter).
mother(mary,paul).
mother(mary,peter).

The SLD-tree for the query ?-parent(john,C) is given in Figure 3.8. Indeed, the second answer { C → peter } is pruned by the cut. This clearly shows that the effect of a cut is not only determined by the clause in which it occurs but also by other clauses. Therefore, the effect of a cut is often hard to understand.

Figure 3.8 Another success branch is pruned.

Programs with cuts are not only difficult to understand; this last example also shows that their procedural interpretation (the set of answers they produce to a query) may be different from their declarative interpretation (the set of its logical consequences). Logically, cut has no meaning: it always evaluates to true, and therefore it can always be added or removed from the body of a clause without affecting its declarative interpretation. Procedurally, cut may have many effects, as the preceding examples show. This incompatibility between declarative and procedural interpretation makes it a very problematic concept. Much research in Logic Programming aims at replacing it by higher-level constructs which have cleaner declarative meanings and which are easier to understand. The most important of these will be considered in the next two sections.

Exercise 3.3 

Draw the SLD-tree for the query ?-likes(A,B), given the following program:

likes(peter,Y):-friendly(Y).
likes(T,S):-student_of(S,T).
student_of(maria,peter).
student_of(paul,peter).
friendly(maria).

Add a cut in order to prune away one of the answers { A → peter, B → maria }, and indicate the result in the SLD-tree. Can this be done without pruning away the third answer?