14.8 Imparting More Control in Prolog: Cut

The ! operator is the cut predicate in Prolog. The cut predicate gives the programmer a measure of control over the search process—an impurity—so it should be used with caution. (The use of the cut predicate in Prolog is, in spirit, not unlike the use of goto in C or call/cc in Scheme in its manipulation of normal program control.) Cut is a predicate that always evaluates to true:

However, the cut predicate has a side effect: It both freezes parts of solutions already found and prevents multiple/alternative solutions from being produced/considered. In this way, it prunes branches in the resolution search tree and reduces the number of branches in the search tree considered.

The cut predicate can appear in a Prolog program in the body of a rule or in a goal (as a subgoal). In either case, when the cut is encountered, it freezes (i.e., fixes) any prior instantiations of free variables bound during unification for the remainder of the search and prevents backtracking. As a consequence, alternative instantiations, which might lead to success, are not tried. Reconsider the path predicate from Section 14.7.1, but with a cut included (line 6):

Output statements have been added to the body of the rules to assist in tracing the search. Consider the goal path (X, c):

The search tree for this goal is shown in Figure 14.5. The edge labels in the figure denote the line number from the Prolog program involved in the match from subgoal source to antecedent target. The left subtree corresponds to the rule on line 6, whose antecedent contains a cut. Here, the cut freezes the binding of X to b, so that the right subtree is not considered. Once a cut has been encountered (i.e., evaluated to true), during backtracking the search of the subtrees of the parent node of the node containing the cut stops, and the search resumes with the parent node of the parent, if present. As a result, the cut prunes from the search tree all siblings to the right of the node with the cut. Consider the following modification to the path predicate:

The two rules constituting the prior path predicate are transposed and the cut is shifted from the last predicate of the body of one of the rules to the last predicate of the body of the other rule. Reconsider the goal path (X, c):

The search tree for this goal is presented in Figure 14.6. Notice that the output statements trace the depth-first search of the resolution tree. In this example, the failure in the left subtree occurs before the cut is evaluated, so the solution X=a is found. Once the cut is evaluated (after X is bound to a), the solution X=a is frozen and the right subtree is never considered. Now consider one last modification to the path predicate:

The cut predicate is shifted one term to the left on line 6. Reconsider the goal path (X, c):

The search tree for the goal path (X, c) is presented in Figure 14.7. Unlike in the prior example, here the failure in the left subtree occurs after the cut is evaluated, so even the solution X=a is not found. Now no solutions are returned.

In the three preceding examples, the cut predicate is used in the body of a rule. However, the cut predicate can also be used (as a subgoal) in a goal. Consider the following database:

We use the cut predicate in the goal on line 23 in the following transcript to prevent consideration of alternative instantiations of X by freezing the first instantiation (i.e., X=dostoyevsky):

Notice how the cut in the goal on line 23 froze the instantiation of X to dostoyevsky, so that backtracking pursued only alternative instantiations of Y (lines 26 and 28) to prove the goal. Consider replacing the second fact (line 2) with the rule author(orwell) :- !:

The cut in the rule on line 2 affects the results of the goals on lines 1, 5, and 13. In particular, once a variable is bound to orwell, no additional instantiations are considered. The cut freezes the instantiations and prevents backtracking to the left of the cut predicate in a line of code, while alternative instantiations are considered to the right of the cut predicate:

Lastly, reconsider the member1/2 predicate in Section 14.7.3:

This definition of member1/2 returns true as many times as there are occurrences of the element in the input list:

Using a cut we can prevent multiple solutions from being produced such that member1/2 returns true only once, even if the element occurs more than once in the input list:

However, this modification prevents multiple solutions universally. As a consequence, we can no longer successfully query for all elements of the input list (as we did at the end of Section 14.7.3):

Conceptual Exercises for Section 14.8

Exercise 14.8.1 Consider the following two Prolog programs, each of which is a variation of the path program from Section 14.8, where the cut predicate is in a different position. Predict the output and draw the search tree for the goal path(X,c) using each of the following two programs:

(a)

(b)

Exercise 14.8.2 Consider the following Prolog database:

For each of the following goals, draw the search tree and indicate which parts of it the cut prunes, as done in Figures 14.5–14.7:

Exercise 14.8.3 John Robinson’s development of the concept of unification is a seminal contribution to automatic theorem proving and logic programming. During resolution, Prolog binds values to variables through unification. However, most implementations of Prolog, including SWI-Prolog, do not check if a candidate clause contains any instances of the variable being matched—a test called the occurs-check. For instance, the terms X and philosopher(X) can never be unified; there is no substitution for X that could ever make the two terms match. Therefore, an implementation of unification that does not perform the occurs-check is optimistic and, ultimately, incomplete. For what reasons might implementers decide not to perform the occurs-check?

Programming Exercises for Section 14.8

Exercise 14.8.4 When the complete predicate in Section 14.7.8 succeeds, it repeatedly returns true:

Modify the complete predicate using a cut to rectify this problem.

Exercise 14.8.5 Consider the following Prolog implementation of the bubblesort algorithm:

Now consider the following goal:

As can be seen, after producing the sorted list (line 2), the predicate produced multiple spurious solutions. Modify the bubblesort predicate to ensure that it does not return any additional results after it produces the first result—which is always the correct one:

Exercise 14.8.6 Define a Prolog predicate squarelistofints/2 that returns true if the list of integers represented by its second parameter are the squares of the list of integers represented by its first parameter, and false otherwise. If an element of the first list parameter is not an integer, insert it into the second list parameter in the same position. The built-in Prolog predicate integer/1 succeeds if its parameter is an integer and fails otherwise.

Examples:

Exercise 14.8.7 Implement the Towers of Hanoi algorithm in Prolog. Towers of Hanoi is a mathematical puzzle using three pegs, where the objective is to shift a stack of discs of different sizes from one peg to another peg using the third peg as an intermediary. At the start, the discs are stacked along one peg such that the largest disc is at the bottom and the remaining discs are progressively smaller, with the smallest at the top. Only one disc may be moved at a time—the uppermost disc on any peg, and a disc may not be placed on a disc that is smaller than it. The following is a sketch of an implementation of the solution to the Towers of Hanoi puzzle in Prolog:

Complete this program. Specifically, define the bodies of the two rules constituting the towers predicate. Hint: The body of the second rule requires four terms (lines 3–6).

Example (with three discs):

The solution to the Towers of Hanoi puzzle is an exponential-time algorithm that requires 2ⁿ–1 moves, where n is the number of discs. Thus, if we ran the program with an input size of 100 discs on a computer that performs 1 billion operations per second, the program would run for approximately 4 × 10¹¹ centuries!

Exercise 14.8.8 Define the = predicate in Prolog using only the !, fail, and = predicates. Name the predicate donotunify.

Exercise 14.8.9 Define the == predicate in Prolog using only the !, fail,and == predicates. Name the predicate notequal.

Exercise 14.8.10 Consider the following Prolog database:

Prolog responds to the goal sibling (X, Y) with

Thus, Prolog thinks that lucia is a sibling of herself (line 1) and that olga is a sibling of herself (line 7). Modify the sibling rule so that Prolog does not produce pairs of siblings with the same elements.

Exercise 14.8.11 The following is the definition of the member1/2 Prolog predicate presented in Section 14.7.3:

The member1 (E, L) predicate returns true if the element represented by E is a member of list L and fails otherwise.

(a) Give the response Prolog produces for the goal
.

(b) Give the response Prolog produces for the goal
.

(c) Define a Prolog predicate notamember (E, L) that returns true if E is not a member of list L and fails otherwise.

Exercise 14.8.12 Define a Prolog predicate emptyintersection/2 that succeeds if the set intersection of two given list arguments, representing sets, is empty and fails otherwise. Do not use any built-in set predicates.

Exercise 14.8.13 The following is the triple predicate, which triples a list (i.e., given [3], it produces [3, 3, 3]):

For instance, if L=[1, 2, 3], triple produces [1, 2, 3, 1, 2, 3, 1, 2, 3] in LLL. Rewrite the triple predicate so that for X= [1, 2, 3], LLL is set equal to [1, 1, 1, 2, 2, 2, 3, 3, 3]. The revised triple predicate must not produce duplicate results.

Exercise 14.8.14 Implement a “negation as failure” not1/1 predicate in Prolog. Hint: The solution requires a cut.