! pronounced “cut” is a special goal in prolog which always succeeds. The purpose of cut, loosely speaking, is to freeze some of the choices made by the backtracking sytem so far. Cuts can therefore be used to increase the efficiency (time) of prolog programs. First we will see how the backtracking is affected by the use of cuts. Then we will give an example use of cuts to speed up prolog programs. We will use cuts to define a negation operator (neg) in prolog. Finally, we rewrite the 8-queens program using the neg operator.
Consider the program below,
p(a).
p(b).
p(c).
with three rules for functor p. The query ?- p(X) returns three values for X (a,b,c). See the post on non-determinism in prolog for details of this behaviour. Suppose we change the second rule to p(b) :- !. Then the effect of the cut is stop the search after the goal succeeds. Therefore X=a; X=b are the two results and the third rule is not tried.
p(a).
p(b):-!.
p(c).
?- p(X).
X = a ;
X = b .
Let us examine the query ?-p(X), p(Y). The first subgoal p(X) will succeed for two values of X. For each of those two choices Y will take one of the two values. The value of c is never returned as an answer in any of the pairs as shown below.
?- p(X), p(Y).
X = a, Y = a ;
X = a, Y = b ;
X = b, Y = a ;
X = b, Y = b .
The cut can also occur within the query as ?- q(X), !, q(Y). In this case X=a succeeds first, then the cut freezes that choice. q(Y) is the subgoal evaluated next and it succeeds for two values a, b. Therefore, the two answers are X=a, Y=a and X=a, Y=b.
?- p(X), !, p(Y).
X = a, Y = a ;
X = a, Y = b .
Effect of a cut
Parent Goal of a cut is defined to be the head of the clause containing the cut.
p(b)in the example above.The cut succeeds when it is encountered and effect of the cut if to freeze the choices that were made between the parent goal was called and the time the cut was encountered. The choices made before the parent goal and after the cut are still non-deterministic. As demonstrated by
p(Y)subgoal in the example above.
Red or Green Cuts
Consider the following predicate in ternary logic. The input is number (first argument), and the output is one of negative,zero,postive (second argument). The body for the three rules is a disjunction of logical conditions. If one of the body subgoals is true then the other subgoals have to be false. Therefore, the program is inefficient, in that the query sign(-1, Y) will succeed when the first rule is tried as the body subgoal is (-1 < 0) true. Prolog still tries to redo the first subgoal, and it tries rules the other two rules. The corresponding subgoals are -1 == 0 and -1 > 0. Both the subgoals fail.
sign(X, negative) :- X < 0.
sign(X,zero) :- X == 0.
sign(X,positive) :- X > 0.
?-sign(-1,Y).
Y = negative .
We can supress the superflous checking by introducting cuts in the program as shown below. The meaning of the cuts is,
- if the first rule succeeds then don’t try the other two rules,
- if the first rule fails and the second rule succeeds then don’t try the last rule.
Use of the cuts in the this example, did not change the output, i.e. the declarative meaning of the program is unchanged. Such cuts (which do not change) the declarative meaning of the program are called green cuts (or safe cuts).
sign1(X, negative) :- X < 0, !.
sign1(X,zero) :- X == 0, !.
sign1(X,positive) :- X > 0.
?- sign1(-1, Y).
?- sign1(0, Y).
?- sign1(1, Y).
Y = negative .
Y = zero .
Y = positive .
Given the sign1 predicate above, one might be tempted to write the following program. The program below is correct. If the first rule succeeds then clearly X is negative. If the first rule fails and the second rule succeeds then X > 0 and X =< 0 so X == 0. Otherwise, the third rule applies and X > 0.
sign2(X, negative) :- X < 0, !.
sign2(X,zero) :- X =< 0, !.
sign2(X,positive) :- X > 0.
?- sign2(-1, Y).
?- sign2(0, Y).
?- sign2(1, Y).
Y = negative .
Y = zero .
Y = positive .
The program below is obtained from sign2 by removing the cuts. The query sign3(-1, Y) succeeds for the first and the second rules. Therefore the output of this program is not the same as the output of sign2. In other words, the declarative meaning of the program sign2 changes after the cuts were removed. Therefore the cuts in sign2 are not-safe and they are called red cuts.
One has to be extremely careful with the use of cuts. It is quite easy to change the meaning of the program after (introduction/removal) of the cuts.
sign3(X, negative) :- X < 0.
sign3(X,zero) :- X =< 0.
sign3(X,positive) :- X > 0.
?- sign3(-1, Y).
Y = negative ;
Y = zero .
To cut or not to cut - Negation
Suppose prolog knows only one fact round(sphere). We can query prolog for round(earth) and as expected the answer is false. The negation predicate in prolog is \+ and therefore \+ round(earth) returns true. This limitation of prolog that is a goal cannot be proved then it is false, is called the close world assumption (CWA). Prolog is not telling us that the Earth is not round, instead it’s telling us that I cannot prove that Earth is round. Under CWA it is the same as saying Earth is not round because it cannot be proved (by Prolog) otherwise.
round(sphere).
?- round(earth).
?- \+ round(earth).
false.
true.
The negation operator (neg equivalent to \+) can be defined in prolog using the following two rules and cut. If goal G can be proved using built in predicate call(G) then freeze the search and return false (fail). If the goal G cannot be proved then call(G) fails therefore the second rule is used and neg(G) is true.
neg(G) :- call(G), !, fail.
neg(_) :- true.
?- neg(round(earth)).
true.
8-queens revisited
This time we will use the negation predicate to find the placement. Let’s revisit the check predicate but this time, we want to write it in negated form.
Say queen at position (X,Y) is in conflict with another queen at position (X1,Y1) if, they are in same column, or they are one the same diagonal (major/minor). This relationship can be expressed using the following equations. Note the use of is (it is an arithmetic operation, not unification =).
Y1 is Y - X1 + X, orY1 is Y + X1 - X, orY1 is Y
So our conflict/2 predicate which checks whether (X,Y) is in conflict with any queen in the rest of the list R is:
conflicts((X,Y), R) :-
member((X1,Y1), R),
(Y1 is Y - X1 + X;
Y1 is Y + X1 - X;
Y1 is Y).
We can now place the queens as earlier and check if they are not in conflict using the predicate above.
place1([]).
place1([(X,Y)|R]) :-
place1(R),
member(Y,[1,2,3,4,5,6,7,8]),
neg(conflicts((X,Y), R)).
?- place1([(1,Y1),(2,Y2),(3,Y3),(4,Y4),(5,Y5),(6,Y6),(7,Y7),(8,Y8)]).
Y1 = 4, Y2 = 2, Y3 = 7, Y4 = 3, Y5 = 6, Y6 = 8, Y7 = 5, Y8 = 1 ;
Y1 = 5, Y2 = 2, Y3 = 4, Y4 = 7, Y5 = 3, Y6 = 8, Y7 = 6, Y8 = 1 ;
Y1 = 3, Y2 = 5, Y3 = 2, Y4 = 8, Y5 = 6, Y6 = 4, Y7 = 7, Y8 = 1 ;
Y1 = 3, Y2 = 6, Y3 = 4, Y4 = 2, Y5 = 8, Y6 = 5, Y7 = 7, Y8 = 1 ;
Y1 = 5, Y2 = 7, Y3 = 1, Y4 = 3, Y5 = 8, Y6 = 6, Y7 = 4, Y8 = 2 ;
Y1 = 4, Y2 = 6, Y3 = 8, Y4 = 3, Y5 = 1, Y6 = 7, Y7 = 5, Y8 = 2 ;
Y1 = 3, Y2 = 6, Y3 = 8, Y4 = 1, Y5 = 4, Y6 = 7, Y7 = 5, Y8 = 2 ;
Y1 = 5, Y2 = 3, Y3 = 8, Y4 = 4, Y5 = 7, Y6 = 1, Y7 = 6, Y8 = 2 ;
Y1 = 5, Y2 = 7, Y3 = 4, Y4 = 1, Y5 = 3, Y6 = 8, Y7 = 6, Y8 = 2 ;
Y1 = 4, Y2 = 1, Y3 = 5, Y4 = 8, Y5 = 6, Y6 = 3, Y7 = 7, Y8 = 2 .
Exercises
- Express the fact that Mary likes all birds except Tweety using
!. - Consider the following program
max(X, Y, Z) :- X >= Y, !.
max(X, Y, Y).
What does this program do? Is the program correct? Is this a red or a green cut? and why?
Additional Reading
- Red and green cuts by MH van Emden - Logic Programming Newsletter, 1982.