Logic Programming
Backtracking and the Cut predicate
I Backtracking
I The Cut predicate
I Common uses of the cut (!)
1. Confirm the choice of a rule
2. Cut-fail combination
3. Terminate a “generate-and-test”
Undesired backtracking behavior
I There are situations where Prolog does not behave as
expected.
Undesired backtracking behavior
I There are situations where Prolog does not behave as
expected.
I Example:
f a t h e r ( mary , g e o r g e ) .
f a t h e r ( joh n , g e o r g e ) .
f a t h e r ( sue , h a r r y ) .
f a t h e r ( g e o r g e , edward ) .
Undesired backtracking behavior
I There are situations where Prolog does not behave as
expected.
I Example:
f a t h e r ( mary , g e o r g e ) .
f a t h e r ( joh n , g e o r g e ) .
f a t h e r ( sue , h a r r y ) .
f a t h e r ( g e o r g e , edward ) .
I This works as expected for:
?− f a t h e r (X , Y ) .
X = mary ,
Y = george ;
X = joh n ,
Y = george ;
X = sue ,
Y = harry ;
X = george ,
Y = edward .
I However, for this:
?− f a t h e r ( , X ) .
X = george ;
X = george ;
X = harry ;
X = edward .
I However, for this:
?− f a t h e r ( , X ) .
X = george ;
X = george ;
X = harry ;
X = edward .
I Once we find that george is a father, we don’t expect to get
the answer again.
I Consider the following recursive definition:
is nat (0).
i s n a t (X): −
i s n a t (Y) ,
X i s Y+1.
In the following, by issuing the backtracking request, all
natural numbers can be generated:
?− i s n a t (X ) .
X = 0 ;
X = 1 ;
X = 2 ;
X = 3 ;
X = 4 ;
X = 5 ;
X = 6 ;
...
I There is nothing wrong with this behavior!
I Consider:
member (X , [ X | ] ) .
member (X , [ | Y] ) : −
member (X , Y ) .
I Consider:
member (X , [ X | ] ) .
member (X , [ | Y] ) : −
member (X , Y ) .
I the query:
?− member ( a , [ a , b , a , a , a , v , d , e , e , g , a ] ) .
true ;
true ;
true ;
true ;
true ;
false .
I Consider:
member (X , [ X | ] ) .
member (X , [ | Y] ) : −
member (X , Y ) .
I the query:
?− member ( a , [ a , b , a , a , a , v , d , e , e , g , a ] ) .
true ;
true ;
true ;
true ;
true ;
false .
I Backtracking confirms the answer several times. But we only
need it once!
The cut predicate (!)
I The cut predicate !/0 tells Prolog to discard certain choices of
backtracking.
I It has the effect of pruning branches of the search space.
I As an effect,
I the programs will run faster,
I the programs will occupy less memory (less backtracking
points to be remembered).
Example: library
I Reference library:
Example: library
I Reference library:
I determine which facilities are available: basic, general.
Example: library
I Reference library:
I determine which facilities are available: basic, general.
I if one has an overdue book, only basic facilities are available.
Example: library
I Reference library:
I determine which facilities are available: basic, general.
I if one has an overdue book, only basic facilities are available.
f a c i l i t y ( Pers , Fac ): −
b o o k o v e r d u e ( Pers , Book ) ,
b a s i c f a c i l i t y ( Fac ) .
basic facility ( references ).
basic facility ( enquiries ).
a d d i t i o n a l f a c i l i t y ( borrowing ) .
additional facility ( inter library exchange ).
g e n e r a l f a c i l i t y (X): −
b a s i c f a c i l i t y (X ) .
g e n e r a l f a c i l i t y (X): −
a d d i t i o n a l f a c i l i t y (X ) .
c l i e n t ( ’ C . Wetzer ’ ) .
c l i e n t ( ’A . Jones ’ ) .
b o o k o v e r d u e ( ’ C . Wetzer ’ , book00101 ) .
b o o k o v e r d u e ( ’ C . Wetzer ’ , book00111 ) .
b o o k o v e r d u e ( ’ A . Jones ’ , book010011 ) .
c l i e n t ( ’ C . Wetzer ’ ) .
c l i e n t ( ’A . Jones ’ ) .
b o o k o v e r d u e ( ’ C . Wetzer ’ , book00101 ) .
b o o k o v e r d u e ( ’ C . Wetzer ’ , book00111 ) .
b o o k o v e r d u e ( ’ A . Jones ’ , book010011 ) .
?− c l i e n t (X ) , f a c i l i t y (X , Y ) .
X = ’C . Wetzer ’ ,
Y = references ;
X = ’C . Wetzer ’ ,
Y = enquiries ;
X = ’A . Jones ’ ,
Y = references ;
X = ’A . Jones ’ ,
Y = enquiries .
Example: library revisited (and with cut)
f a c i l i t y ( Pers , Fac ): −
b o o k o v e r d u e ( Pers , Book ) ,
!,
b a s i c f a c i l i t y ( Fac ) .
basic facility ( references ).
basic facility ( enquiries ).
a d d i t i o n a l f a c i l i t y ( borrowing ) .
additional facility ( inter library exchange ).
g e n e r a l f a c i l i t y (X): −
b a s i c f a c i l i t y (X ) .
g e n e r a l f a c i l i t y (X): −
a d d i t i o n a l f a c i l i t y (X ) .
I The goal ?−client(X), facility (X, Y) is answered by Prolog
in the following way:
? - client(X) , facility(X, Y).
X =’C.Wetzer’
? - bfacility(’C.Wetzer’, Y)c. ...
?-bbook overdue(’C.Wetzer’, Book)c, !, basic facility(’C.Wetzer’, Y).
Book=book00101 Book=book00111
?- b!c, basic facility(’C.Wetzer’, Y). ¸
?- bbasic facility(’C.Wetzer’, Y)c.
Y =references Y =enquiries
X X
I Guarded gate metaphor!
I Guarded gate metaphor!
I Effect of the cut:
I Guarded gate metaphor!
I Effect of the cut:
I if a client has an overdue book, only allow basic facilities,
I Guarded gate metaphor!
I Effect of the cut:
I if a client has an overdue book, only allow basic facilities,
I no need to look for all overdue books,
I Guarded gate metaphor!
I Effect of the cut:
I if a client has an overdue book, only allow basic facilities,
I no need to look for all overdue books,
I no need to consider any other rules about facilities.
I Guarded gate metaphor!
I Effect of the cut:
I if a client has an overdue book, only allow basic facilities,
I no need to look for all overdue books,
I no need to consider any other rules about facilities.
I ! always succeeds (with empty substitutions).
I Guarded gate metaphor!
I Effect of the cut:
I if a client has an overdue book, only allow basic facilities,
I no need to look for all overdue books,
I no need to consider any other rules about facilities.
I ! always succeeds (with empty substitutions).
I When the cut is encountered as a goal:
I Guarded gate metaphor!
I Effect of the cut:
I if a client has an overdue book, only allow basic facilities,
I no need to look for all overdue books,
I no need to consider any other rules about facilities.
I ! always succeeds (with empty substitutions).
I When the cut is encountered as a goal:
I the system becomes commited to all the choices made since
the parent (here this is facility ) was invoked,
I Guarded gate metaphor!
I Effect of the cut:
I if a client has an overdue book, only allow basic facilities,
I no need to look for all overdue books,
I no need to consider any other rules about facilities.
I ! always succeeds (with empty substitutions).
I When the cut is encountered as a goal:
I the system becomes commited to all the choices made since
the parent (here this is facility ) was invoked,
I all other alternatives are discarded (e.g. the branch indicated
by ¸above),
I Guarded gate metaphor!
I Effect of the cut:
I if a client has an overdue book, only allow basic facilities,
I no need to look for all overdue books,
I no need to consider any other rules about facilities.
I ! always succeeds (with empty substitutions).
I When the cut is encountered as a goal:
I the system becomes commited to all the choices made since
the parent (here this is facility ) was invoked,
I all other alternatives are discarded (e.g. the branch indicated
by ¸above),
I an attempt to satisfy any goal between the parent and the cut
goal will fail,
I Guarded gate metaphor!
I Effect of the cut:
I if a client has an overdue book, only allow basic facilities,
I no need to look for all overdue books,
I no need to consider any other rules about facilities.
I ! always succeeds (with empty substitutions).
I When the cut is encountered as a goal:
I the system becomes commited to all the choices made since
the parent (here this is facility ) was invoked,
I all other alternatives are discarded (e.g. the branch indicated
by ¸above),
I an attempt to satisfy any goal between the parent and the cut
goal will fail,
I if the user asks for a different solution, Prolog goes to the
backtrack point above the parent goal (if any). In the example
above the first goal is ( client (X)) is the backtrack point
above the goal.
1. Confirm the choice of a rule (tell the system the right rule
was found).
2. Cut-fail combination (tell the system to fail a particular goal
without trying to find alternative solutions).
3. Terminate a “generate-and-test” (tell the system to
terminate the generation of alternative solutions by
backtracking).
Confirm the choice of a rule
I Situation:
Confirm the choice of a rule
I Situation:
I There are some clauses associated with the same predicate.
Confirm the choice of a rule
I Situation:
I There are some clauses associated with the same predicate.
I Some clauses are appropriate for arguments of certain forms.
Confirm the choice of a rule
I Situation:
I There are some clauses associated with the same predicate.
I Some clauses are appropriate for arguments of certain forms.
I Often argument patterns can be provided (e.g. empty and
nonempty lists), but not always.
Confirm the choice of a rule
I Situation:
I There are some clauses associated with the same predicate.
I Some clauses are appropriate for arguments of certain forms.
I Often argument patterns can be provided (e.g. empty and
nonempty lists), but not always.
I If no exhaustive set of patterns can be provided, give rules for
specific arguments and a “catch all” rule at the end.
sum to ( 1 , 1 ) .
sum to (N, Res ): −
N1 i s N−1,
sum to ( N1 , Res1 ) ,
Res i s Res1 + N .
sum to ( 1 , 1 ) .
sum to (N, Res ): −
N1 i s N−1,
sum to ( N1 , Res1 ) ,
Res i s Res1 + N .
When backtracking, there is an error (it loops - why?):
?− sum to ( 5 , X ) .
X = 15 ;
ERROR : Out o f l o c a l s t a c k
I Now using the cut (!):
c s u m t o ( 1 , 1): − ! .
c s u m t o (N, Res ): −
N1 i s N−1,
c s u m t o ( N1 , Res1 ) ,
Res i s Res1 + N .
I Now using the cut (!):
c s u m t o ( 1 , 1): − ! .
c s u m t o (N, Res ): −
N1 i s N−1,
c s u m t o ( N1 , Res1 ) ,
Res i s Res1 + N .
The system is committed to the boundary condition, it will
not backtrack for others anymore:
?− c s u m t o ( 5 , X ) .
X = 15.
I Now using the cut (!):
c s u m t o ( 1 , 1): − ! .
c s u m t o (N, Res ): −
N1 i s N−1,
c s u m t o ( N1 , Res1 ) ,
Res i s Res1 + N .
The system is committed to the boundary condition, it will
not backtrack for others anymore:
?− c s u m t o ( 5 , X ) .
X = 15.
However:
?− c s u m t o ( −3 , Res ) .
ERROR : Out o f l o c a l s t a c k
Placing the condition N =< 1 in the boundary condition fixes
the problem:
s s u m t o (N, 1): −
N =< 1 , ! .
s s u m t o (N, Res ): −
N1 i s N−1,
s s u m t o ( N1 , Res1 ) ,
Res i s Res1 + N .
Cut ! and not
I Where ! is used to confirm the choice of a rule, it can be
replaced by not/1.
Cut ! and not
I Where ! is used to confirm the choice of a rule, it can be
replaced by not/1.
I not(X) succeeds when the goal X fails.
Cut ! and not
I Where ! is used to confirm the choice of a rule, it can be
replaced by not/1.
I not(X) succeeds when the goal X fails.
I using not is considered to be good programming style:
Cut ! and not
I Where ! is used to confirm the choice of a rule, it can be
replaced by not/1.
I not(X) succeeds when the goal X fails.
I using not is considered to be good programming style:
I but programs may become less efficient (why?)
Cut ! and not
I Where ! is used to confirm the choice of a rule, it can be
replaced by not/1.
I not(X) succeeds when the goal X fails.
I using not is considered to be good programming style:
I but programs may become less efficient (why?)
I there is a trade-off between readability and efficiency!
I A variant with not:
nsum to ( 1 , 1 ) .
nsum to (N, Res ): −
n o t (N =< 1 ) ,
N1 i s N−1,
nsum to ( N1 , Res1 ) ,
Res i s Res1 + N .
I A variant with not:
nsum to ( 1 , 1 ) .
nsum to (N, Res ): −
n o t (N =< 1 ) ,
N1 i s N−1,
nsum to ( N1 , Res1 ) ,
Res i s Res1 + N .
I When not is used, there may be double work:
A:− B , C .
A:− n o t (B ) , D .
I A variant with not:
nsum to ( 1 , 1 ) .
nsum to (N, Res ): −
n o t (N =< 1 ) ,
N1 i s N−1,
nsum to ( N1 , Res1 ) ,
Res i s Res1 + N .
I When not is used, there may be double work:
A:− B , C .
A:− n o t (B ) , D .
in the above, B is tried twice after backtracking.
The cut-fail combination
I fail /0 is a built-in predicate.
The cut-fail combination
I fail /0 is a built-in predicate.
I When it is a goal, it fails and causes backtracking.
The cut-fail combination
I fail /0 is a built-in predicate.
I When it is a goal, it fails and causes backtracking.
I Using fail after the cut changes the backtracking behavior.
I Example:
I Example:
I we are interested in average taxpayers,
I Example:
I we are interested in average taxpayers,
I foreigners are not average,
I Example:
I we are interested in average taxpayers,
I foreigners are not average,
I if the taxpayer is not foreigner, apply some general criteria.
I Example:
I we are interested in average taxpayers,
I foreigners are not average,
I if the taxpayer is not foreigner, apply some general criteria.
a v e r a g e t a x p a y e r (X): −
f o r e i g n e r (X ) , ! , f a i l .
a v e r a g e t a x p a y e r (X): −
s a t i s f i e s g e n e r a l c r i t e r i o n (X ) .
I Example:
I we are interested in average taxpayers,
I foreigners are not average,
I if the taxpayer is not foreigner, apply some general criteria.
a v e r a g e t a x p a y e r (X): −
f o r e i g n e r (X ) , ! , f a i l .
a v e r a g e t a x p a y e r (X): −
s a t i s f i e s g e n e r a l c r i t e r i o n (X ) .
What if the cut ! isnt used?
I Example:
I we are interested in average taxpayers,
I foreigners are not average,
I if the taxpayer is not foreigner, apply some general criteria.
a v e r a g e t a x p a y e r (X): −
f o r e i g n e r (X ) , ! , f a i l .
a v e r a g e t a x p a y e r (X): −
s a t i s f i e s g e n e r a l c r i t e r i o n (X ) .
What if the cut ! isnt used?
I then a foreigner that satisfied the general criterion will be
considered an average taxpayer.
I The general criterion:
I The general criterion:
I a person whose spouse earns more than 3000 is not average,
I The general criterion:
I a person whose spouse earns more than 3000 is not average,
I otherwise, a person is average if they earn between 1000 and
3000.
I The general criterion:
I a person whose spouse earns more than 3000 is not average,
I otherwise, a person is average if they earn between 1000 and
3000.
s a t i s f i e s g e n e r a l c r i t e r i o n (X): −
s p o u s e (X , Y ) ,
g r o s s i n c o m e (Y , I n c ) ,
I n c > 3000 ,
! , fail .
s a t i s f i e s g e n e r a l c r i t e r i o n (X): −
g r o s s i n c o m e (X , I n c ) ,
I n c < 3000 ,
Inc > 2000.
I Gross income:
I Gross income:
I pensioners with less than 500 have no gross income,
I Gross income:
I pensioners with less than 500 have no gross income,
I otherwise, gross income is the sum of the gross salary and the
investment income.
I Gross income:
I pensioners with less than 500 have no gross income,
I otherwise, gross income is the sum of the gross salary and the
investment income.
g r o s s i n c o m e (X , Y): −
r e c e i v e s p e n s i o n (X , P ) ,
P < 500 ,
! , fail .
g r o s s i n c o m e (X , Y): −
g r o s s s a l a r y (X , Z ) ,
i n v e s t m e n t i n c o m e (X , W) ,
Y i s Z + W.
I not can be implemented with the cut-fail combination.
I not can be implemented with the cut-fail combination.
n o t (P): − c a l l (P ) , ! , f a i l .
n o t (P ) .
I not can be implemented with the cut-fail combination.
n o t (P): − c a l l (P ) , ! , f a i l .
n o t (P ) .
I Note though that Prolog will take issue with you trying to
redefine essential predicates.
Replacing the cut in cut-fail situations
I The cut can be replaced with not.
Replacing the cut in cut-fail situations
I The cut can be replaced with not.
I This replacement does not affect the efficiency in the cut-fail
situations.
Replacing the cut in cut-fail situations
I The cut can be replaced with not.
I This replacement does not affect the efficiency in the cut-fail
situations.
I However, programs have to be rearranged:
a v e r a g e t a x p a y e r (X): −
n o t ( f o r e i g n e r (X ) ) ,
n o t ( ( s p o u s e (X , Y ) ,
g r o s s i n c o m e (Y , I n c ) ,
I n c > 3000)
), ...
Terminating a “generate and test”
I Tic-tac-toe.
Terminating a “generate and test”
I Tic-tac-toe.
I Natural number division:
d i v i d e ( N1 , N2 , R e s u l t ): −
is nat ( Result ) ,
P r o d u c t 1 i s R e s u l t * N2 ,
P r o d u c t 2 i s ( R e s u l t +1) * N2 ,
P r o d u c t 1 =< N1 , P r o d u c t 2 > N1 ,
!.
Problems with the cut
I Consider the example:
cappend ( [ ] , X , X ) : − ! .
cappend ( [ A | B ] , C , [ A |D] ) : −
cappend (B , C , D ) .
?− cappend ( [ 1 , 2 , 3 ] , [ a , b , c ] , X ) .
X = [1 , 2 , 3 , a , b , c ] .
?− cappend ( [ 1 , 2 , 3 ] , X , [ 1 , 2 , 3 , a , b , c ] ) .
X = [a, b, c ].
?− cappend (X , Y , [ 1 , 2 , 3 , a , b , c ] ) .
X = [] ,
Y = [1 , 2 , 3 , a , b , c ] .
Problems with the cut
I Consider the example:
cappend ( [ ] , X , X ) : − ! .
cappend ( [ A | B ] , C , [ A |D] ) : −
cappend (B , C , D ) .
?− cappend ( [ 1 , 2 , 3 ] , [ a , b , c ] , X ) .
X = [1 , 2 , 3 , a , b , c ] .
?− cappend ( [ 1 , 2 , 3 ] , X , [ 1 , 2 , 3 , a , b , c ] ) .
X = [a, b, c ].
?− cappend (X , Y , [ 1 , 2 , 3 , a , b , c ] ) .
X = [] ,
Y = [1 , 2 , 3 , a , b , c ] .
I The variant of append with a cut works as expected for the
first two queries above. However, for the third, it only offers
one solution (all the others are cut!)
I Consider:
n u m b e r o f p a r e n t s ( adam , 0 ) : − ! .
n u m b e r o f p a r e n t s ( eve , 0 ) : − ! .
n u m b e r o f p a r e n t s (X , 2 ) .
?− n u m b e r o f p a r e n t s ( eve , X ) .
X = 0.
?− n u m b e r o f p a r e n t s ( j o h n , X ) .
X = 2.
?− n u m b e r o f p a r e n t s ( eve , 2 ) .
true .
I Consider:
n u m b e r o f p a r e n t s ( adam , 0 ) : − ! .
n u m b e r o f p a r e n t s ( eve , 0 ) : − ! .
n u m b e r o f p a r e n t s (X , 2 ) .
?− n u m b e r o f p a r e n t s ( eve , X ) .
X = 0.
?− n u m b e r o f p a r e n t s ( j o h n , X ) .
X = 2.
?− n u m b e r o f p a r e n t s ( eve , 2 ) .
true .
I The first two queries work as expected.
I Consider:
n u m b e r o f p a r e n t s ( adam , 0 ) : − ! .
n u m b e r o f p a r e n t s ( eve , 0 ) : − ! .
n u m b e r o f p a r e n t s (X , 2 ) .
?− n u m b e r o f p a r e n t s ( eve , X ) .
X = 0.
?− n u m b e r o f p a r e n t s ( j o h n , X ) .
X = 2.
?− n u m b e r o f p a r e n t s ( eve , 2 ) .
true .
I The first two queries work as expected.
I The third query gives an unexpected answer. This is due to
the fact that the particular instantiation of the arguments
does not match the special condition where the cut was used.
I Consider:
n u m b e r o f p a r e n t s ( adam , 0 ) : − ! .
n u m b e r o f p a r e n t s ( eve , 0 ) : − ! .
n u m b e r o f p a r e n t s (X , 2 ) .
?− n u m b e r o f p a r e n t s ( eve , X ) .
X = 0.
?− n u m b e r o f p a r e n t s ( j o h n , X ) .
X = 2.
?− n u m b e r o f p a r e n t s ( eve , 2 ) .
true .
I The first two queries work as expected.
I The third query gives an unexpected answer. This is due to
the fact that the particular instantiation of the arguments
does not match the special condition where the cut was used.
I In fact, here, the pattern that distinguishes between the
special condition and the general case is formed by both
arguments together.
I The predicate above can be fixed in two ways:
n u m b e r o f p a r e n t s 1 ( adam , N) : − ! , N = 0 .
n u m b e r o f p a r e n t s 1 ( eve , N) : − ! , N = 0 .
n u m b e r o f p a r e n t s 1 (X , 2 ) .
n u m b e r o f p a r e n t s 2 ( adam , 0 ) : − ! .
n u m b e r o f p a r e n t s 2 ( eve , 0 ) : − ! .
n u m b e r o f p a r e n t s 2 (X , 2): −
X \ = adam , X , \= e v e .
I The cut is a powerful construct and should be used with great
care.
I The advantages of using the cut can be major, but so are the
dangers.
I There are two types of cut:
I green cuts: when no solutions are discarded by cutting,
I red cuts: the part of the search space is cut, and this part
contains solutions.
I Green cuts are harmless, whereas red cuts should be used with
great care.
I Read Chapter 3, Chapter 7, Sections 7.5, 7.6, 7.7
of [Clocksin and Mellish, 2003].
I Read Chapter 7 of [Nilsson and Maluszynski, 2000].
I Read Section 12.2 of [Brna, 1988].
I Try out in Prolog the examples.
I Solve the corresponding exercises.
I Read: Chapter 4 of [Clocksin and Mellish, 2003].
I Also read: Chapter 5, Section 5.1 of
[Nilsson and Maluszynski, 2000].
I Carry out the examples in Prolog.
I Items of interest:
I what is the effect of the cut predicate (!), “guarded gate”
metaphor,
I common uses of the cut: 1. confirming the use of a rule, 2.
cut-fail combination, 3. terminate a “generate and test”,
I cut elimination (can it be done, does it cost in terms of
computational complexity?)
I problems with cut (green cuts/red cuts).
Brna, P. (1988).
Prolog Programming A First Course.
copyright Paul Brna.
Clocksin, W. F. and Mellish, C. S. (2003).
Programming in Prolog.
Springer, Berlin, 5th edition.
Nilsson, U. and Maluszynski, J. (2000).
Logic, Programming and Prolog.
copyright Ulf Nilsson and Jan Maluszynski, 2nd edition.
