Chapter 6

Controlling Backtracking

Prof. N. G. J. Dias
Senior Professor
Department of Computer Systems Engineering,
Faculty of Computing and Technology,
University of Kelaniya,
Kelaniya
6.1 Introduction
• Prolog provides a single system predicate called ‘cut’ (denoted by !) for preventing
backtracking.
• The main function of the cut is to instruct the Prolog interpreter/complier, not to
search the unexploded branches of the current search tree.
• In other words it provides a method of pruning a search tree at run time.
• The cut also extends the expressive power of Prolog and enables the definition of a
kind of negation, called ‘negation as failure’ and associated with the ‘closed world
assumption’.

16 May 2025 NGJD@FCT-UoK 2

6.2 Effect of a Cut
6.2.1 Introduction
• Let us consider the effect of the cut in the clause 1 of the following set of clauses:
B:-P,Q,R,!,S,T,U. % Clause1
B:-V. % Clause2
X:-A,B,C,D. % Clause3
|?_X.
Here A, B, C, D, P, Q, R, S, T, U and X have the syntax of terms.
The cut will affect the execution of the goal B as illustrated below.
• When a parent goal B has been matched with the head of the Clause 1, Prolog
starts executing the conditions and if P, Q and R succeed, it will immediately
succeed in executing the cut.

16 May 2025 NGJD@FCT-UoK 3

• As a result of this successful execution of the cut, the normal Prolog search
strategy will be changed as follows:
1. Cut discards all alternative solution of the conjunction of goals (P, Q and R) to
the left of the cut.
That is, as soon as the cut is reached all alternative solution of the goal list P,Q
and R are suppressed, or in other words the goals P, Q and R cannot be
resatisfied.
2. Cut discards all clauses below it (Clause 1), matching with the original goal (B),
That is, the alternative clause about B, B:-V will also be discarded and hence
the solution from the Clause 2 will not be found.
3. Cut does not effect the goals (S, T and U) to its right in the clause.
That is, backtracking will be possible within the goal list S, T and U, or in other
words the goals S, T and U may be resatisfied.

16 May 2025 NGJD@FCT-UoK 4

 4. Cut will only affect the execution of the original goal (B).
That is, the cut will be invisible from goal X. So automatic backtracking within
the goal list A,B,C,D will remain active regardless of the cut within the clause
used for satisfying B.

• Thus ‘cut’ provides a barrier to backtracking and cuts away branches generates by
additional matches for goals P,Q,R and B.
• A more precise meaning of the cut mechanism is as follows:
Let us call the ‘parent goal’ the goal that matched the head of the clause containing
the cut.
When the cut is encountered as a goal it succeeds immediately, but it commits the
system to all choices made between the time ‘parent goal was invoked and the
time the cut was encountered. All the remaining alternatives between the parent
goal and the cut are discarded.

16 May 2025 NGJD@FCT-UoK 5

 To clarify this definition consider a clause of the form:
H :- B1,B2, ..., Bm, !, ..., Bn.
Let us assume that this clause was invoked by a goal G that matched H .
Then G is the parent goal.
At the moment that the cut is encountered, the system has already found some
solution of the goals B1, ..., Bm.
When the cut is executed, this (current) solution of B1,..., Bm becomes frozen and
all possible remaining alternatives are discarded.
Also, the goal G now becomes committed to this clause: any attempt to match G
with the head of some other clause is precluded.

16 May 2025 NGJD@FCT-UoK 6

6.2.2 Types and use of the ‘cut’
• There are two types of cuts, namely green cut and red cut.
• A green cut is one which does not alter the meaning of the program, where as a
red cut does, and hence should be avoided if possible.
• While taking their point it should be mentioned that there are occasions it is very
difficult to avoid red cuts.
• Acceptable uses of the cut include:
(i) to increase the efficiency of a section of code.
(ii) to implement an if-then-else condition.
(iii) to implement negation (not) as failure.

16 May 2025 NGJD@FCT-UoK 7

6.3 Increasing Efficiency by Preventing Backtracking
6.3.1 Introduction
• Prolog will automatically backtrack if this is necessary for satisfying a goal.
• Automatic backtracking is a useful programming concept because it relieves the
programmer of the burden of programming backtracking explicitly.
• On the other hand, uncontrolled backtracking may cause inefficiency in a program.
• Therefore, we sometimes want to control, or to prevent, backtracking.
• We can often improve the efficiency of the program by using the ‘cut‘ facility.
• The idea is to explicitly tell Prolog: do not try other alternatives because they are
bound to fail.

16 May 2025 NGJD@FCT-UoK 8

• Let us first study the behavior of a simple example program whose execution
involves some unnecessary backtracking.
We will identify those points at which the backtracking is useless and leads to
inefficiency.

16 May 2025 NGJD@FCT-UoK 9

• Consider the double step function given below:
Y

X
0 3 6

The relation between X and Y can be specified by the 3 rules:

Rule 1 : if X < 3 then Y = 0.
Rule 2 : if 3 ≤ X and X < 6 then Y = 2.
Rule 3 : if 6 ≤ X then Y = 4.

16 May 2025 NGJD@FCT-UoK 10

 This can be written in prolog as a binary relation f(X,Y) as follows:
f(X,0):- X < 3. % Rule 1
f(X,2):- 3 =< X,X < 6. % Rule 2 1stVersion
f(X,4) :- 6 =< X % Rule 3
Note:
This program, of course, assumes that X is already instantiated to a number before
f(X,Y) is executed, as this is required by the comparison operators.
• We will make two experiments with this program.
Each experiment will reveal some source of inefficiency in the program, and we will
remove each source in turn by using the cut mechanism.

16 May 2025 NGJD@FCT-UoK 11

6.3.2 Experiment 1
• Now consider the search tree for the query,
|?_f(1,Y),2<Y.
f(1,Y), 2<Y

(1) (2) (3)

X=1,Y=0 X=1,Y=2 X=1,Y=4

1<3, 2<0 3=<1, 1<6, 2<2 6=<1, 2<4
FAIL FAIL
CUT

[ ], 2<0
FAIL
When executing the 1st goal f(1,Y), Y becomes instantiated to 0 and giving the sub
goal list 1<3, 2<0.
Now the 2nd subgoal 2<0 fails and so does the whole goal list.
16 May 2025 NGJD@FCT-UoK 12
 However, before admitting that the goal list, f(1,Y),2<Y is not satisfiable, Prolog
tries through backtracking, two useless alternatives by matching the 1st goal, f(1,Y)
with Rule 2 and Rule 3.
The 3 rules above the f relation are mutually exclusive, so that one of them at
almost will succeed. Therefore we, not Prolog, know that as soon as one rule
succeeds there is no point in trying to use others as they are bound to fail.
According to the search tree, rule 1 has become known to succeed at the point
indicated by ‘cut’.
In order to prevent futile backtracking at this point we have to tell Prolog explicitly
not to backtrack.
We can do this by using the cut mechanism.

16 May 2025 NGJD@FCT-UoK 13

 Our program, rewritten with cuts is
f(X,0):- X<3,!.
f(X,2):- 3=<X, X<6,!. 2nd Version
f(X,4):- 6=<X.
The ! symbol will now prevent backtracking at the point that it appears in the
program.
If we now ask,
|?_f(1,Y),2<Y.
Prolog will produce the same left hand branch of the above search tree.
Now prolog will try to backtrack, but not beyond the point marked ‘!’ in the
program.
The alternative branches that correspond to Rule 2 and Rule 3 will not be
generated.
16 May 2025 NGJD@FCT-UoK 14
 The new program, equipped with cuts, is in general, more efficient than the
original version without cuts.
Note:
If the cuts are now removed in this example, the program will still produce the
same result; it will perhaps only spend more time.
Clearly the cuts in this program are green cuts.

16 May 2025 NGJD@FCT-UoK 15

6.3.3 Experiment 2
• Let us now perform a second experiment with the second version of our program.
Suppose we ask
|?_f(7,Y).
Y=4
Following is the search tree for the query f(7,Y).
f(7,Y)

(1) (2) (3)

X=7,Y=0 X=7,Y=2 X=7,Y=4

7<3, ! 3=<7, 7<6, ! 6=<7
FAIL

[ ], 7<6,! []
FAIL Solution Y=4
16 May 2025 NGJD@FCT-UoK 16
• Let us analyze what has happened.
All three rules were tried before the answer was obtained.
This produced the following sequence of goals:
Try rule 1: 7 < 3 Fails backtrack and try rule 2 (cut was not reached)
Try rule 2: 3 =< 7 succeeds, but then 7<6 fails, backtrack and try rule 3 (cut was
not reached).
Try rule 3: 6 =< 7 succeed.
This trace reveals another source of inefficiency.
First it is established that X<3 is not true (7<3 fails). The next goal is 3 =<X (3=<7
succeeds).
But we know that once the first test has failed, the second test is bound to succeed
as it is the negation of the first.
Therefore, the second test is redundant and the corresponding goal can be
omitted. The same is true about the goal 6=<X in rule 3.
16 May 2025 NGJD@FCT-UoK 17
This leads to the following, more economical formulation of 3 mutually exclusive rules:
if X<3 then Y= 0
else if X<6 then Y= 2
else Y= 4
We can now omit the conditions in the program that are guaranteed to be true
whenever they are executed. This leads to the third version of the program:
f(X,0):-X<3,!.
f(X,2):-X<6,!. 3rd Version
f(X,4).
This program produces the same results as our original version, but is more efficient
than both previous versions.

16 May 2025 NGJD@FCT-UoK 18

 Note:
If we remove the cuts in the above program, then it becomes
f(X,0):-X<3.
f(X,2):-X<6.
f(X,4).
This may produce multiple solutions, some of which are not correct.
Example:
|?_f(1,Y).
Y=0;
Y=2;
Y=4;
no.

16 May 2025 NGJD@FCT-UoK 19

 It is important to notice that, in contrast to the second version of the program, this
time the cuts do not only affect the procedural behaviour, but also change the
declarative meaning of the program.
Cleary the cuts introduced in the 3rd version are red cuts.

16 May 2025 NGJD@FCT-UoK 20

6.4 Examples of using Cut
6.4.1 Computing Maximum
• The procedure for finding the larger of two numbers can be programmed as a
relation
max(X,Y,Max)
where Max = X if X ≥ Y and Max = Y if X < Y.
• This corresponds to the following two clauses.
max(X,Y,X):-X >= Y.
max(X,Y,Y):-X < Y.
• These two rules are mutually exclusive. If the first one succeeds, then the second
one will fail. If the first one fails, then the second must succeed.
Therefore a more economical formulation with if–then-else is possible:
If X ≥Y then Max = X
else Max =Y
16 May 2025 NGJD@FCT-UoK 21
 This is written in prolog using a cut as:
max(X,Y,X):-X>=Y,!.
max(X,Y,Y).

16 May 2025 NGJD@FCT-UoK 22

6.4.2 Single Solution Membership
• We have been using the relation
member(X,L)
for establishing whether X is in the list L.
The program was:
member(X,[X|L]).
member(X,[Y|L]):-member(X,L).
• This is non-deterministic, since if X occurs several times then any occurrence can
be found.
• Let us now change member into a deterministic procedure which will find only the
first occurrence.
The change is simple: we only have to prevent backtracking as soon as X is found,
which happens when the first clause succeeds.

16 May 2025 NGJD@FCT-UoK 23

 The modified program is:
member(X,[X|L]):-!.
member(X,[Y|L]):-member(X,L).
This program will generate just one solution.
For example,
|?_member(X, [a,b,c]).
X=a;
no

16 May 2025 NGJD@FCT-UoK 24

6.4.3 Adding an Element to a List without Duplication
• Often we want to add an item X to a list L so that X is added only if X is not yet in L.
• If X is already in L, then L remains the same because we do not want to have
redundant duplicates in L.
• As we know, the ‘add’ relation has three arguments,
add(X,L,L1)
where X is the item to be added, L is the list to which X is to be added and L1 is the
resulting new list.
• Now our rule for adding can be formulated as,
if X is member of list L then L1=L,
else L1 is equal to L with X inserted.
• It is easiest to insert X in front of L so that X becomes the head of L1.
This is then program as follows:
add(X,L,L):-member(X,L),!.
add(X,L,[X|L]).
16 May 2025 NGJD@FCT-UoK 25
• The behavior of this procedure is illustrated by the following example.
|?_add(a,[b,c],L).
L=[a,b,c].
|?_add(X,[b,c],L).
L=[b,c]
X=b.
• If we now omit the cut in the foregoing program then ‘add’ relation will also add
duplicate items.
For example,
|?_add(a,[a,b,c],L).
L=[a,b,c];
L=[a,a,b,c];
no
• So the cut is necessary here to specify the right relation and not only to improve
efficiency.
16 May 2025 NGJD@FCT-UoK 26
6.4.4 Classification into Categories
• Assume we have a database of results of tennis games played by members of a
club.
The results are in the program represented as facts like
beat(tom, jim).
beat(ann, tom).
beat(pat, jim).
• We want to define a relation,
class(Player, Category)
that ranks the players into categories.
We have just 3 categories:
Winners - Every player who won all his or her games is a winner.
Fighter - Any player that won some games and lost some.
Sportsman - Any player who lost all his or her games.
16 May 2025 NGJD@FCT-UoK 27
• For example, if all the results available are just those above then Ann and Pat are
winners, Tom is a fighter and Jim is a sportsman.
• These 3 rules can be expressed using if-then-else condition. Such a formulation is,
If X beats somebody and X was beaten by somebody
then X is a fighter.
else if X beat somebody
then X is a winner.
else if X got beaten by somebody
then X is a sportsman.
• This formulation can be readily translated into Prolog. The mutual exclusion of the
3 alternative categories is indicated by the cuts.

16 May 2025 NGJD@FCT-UoK 28

 class(X,fighter):-beat(X,_), beat(_,X),!.
class(X,winner):-beat(X,_),!.
class(X,sportsman):-beat(_,X).
• Notice that the cut in the clause for winner is not necessary.

16 May 2025 NGJD@FCT-UoK 29

Exercises
1. Let a program be:
p( 1).
p( 2) :- !.
p( 3).
Write all Prolog's answers to the following questions:
(a) ?- p( x).
(b) ?- p( X), p( Y).
(c) ?- p( X), !, p( Y).

16 May 2025 NGJD@FCT-UoK 30

2. The following relation classifies numbers into three classes: positive,zero and
negative:
class( Number, positive) :- Number > 0.
class( 0, zero).
class( Number, negative) :- Number < 0.
Define this procedure in a more efficient way using cuts.
3. Define the procedure
split( Numbers, Positives, Negatives)
which splits a list of numbers into two lists: positive ones( including zero) and
negative ones.
For example, split([ 3,-1,0,5,-2], [ 3 ,0,5], [ -1,-2])
Propose two versions: one with a cut and one without.

16 May 2025 NGJD@FCT-UoK 31

6.5 Negation as Failure
6.5.1 The special goals fail and true in Prolog
• Let us try to understand the action of the goals fail and true through the following
examples.
Example 1 Consider the statement:
Mary likes all animals but snakes.
First part of the statement can be expressed as follows:
Mary likes any X if X is an animal.
This is in Prolog:
likes(mary,X):-animal(X).
But we have to exclude snakes. This can be done by using a different formulation.
If X is a snake then ‘Mary likes X’ is not true.
else if X is an animal then ‘Mary likes X’.
16 May 2025 NGJD@FCT-UoK 32
 That something is not true can be said in Prolog by using a special goal, fails, which
always fails, thus forcing the parent goal to fail.
The above formulation is translated into Prolog, using ‘fail’, as follows:
likes(mary,X):-snake(X),!,fail.
likes(mary,X):-animal(X).
The first rule here will take care of snakes: If X is a snake then the cut will prevent
backtracking (thus excluding the second rule) and ‘fail’ will cause the failure.
These 2 clauses can be written more compactly as one clause as follows:
likes(mary,X):-snakes(X),!,fail; animal(X).
Note:
The semicolon (;) in the body of the above clause represents the disjunction (or) of
the conditions.

16 May 2025 NGJD@FCT-UoK 33

Example 2
We can use the same idea as in Example 1 to define the relation
different(X,Y)
which is true if X and Y are different.
We have to more precise, however, because ‘different’ can be understood in
several ways:
o X and Y do not match.
o X and Y are not literally same.
o The values of arithmetic expressions X and Y are not equal.
Let us choose, here X and Y are different if they do not match.
The key to saying this in Prolog is:
if X and Y match then different(X,Y) fails
else different(X,Y) succeeds.

16 May 2025 NGJD@FCT-UoK 34

 We again use the cut and fail combination:
different(X,Y):-X=Y, !, fail.
different(X,Y).
This can also be written as one clause:
different(X,Y):-X=Y, !, fail; true.
The goal ‘true’ is a goal that always succeeds.

16 May 2025 NGJD@FCT-UoK 35

6.5.2 Defining Negation as Failure
• The examples in section 6.5.1 indicate that it would be useful to have a unary
relation (1-place predicate) ‘not’ such that
not(Goal)
is true if Goal is not true.
• We will now define the ‘not’ relation as follows:
If Goal succeeds then not(Goal) fails,
else not(Goal) succeeds.
• This definition can be written in Prolog as,
not(P):-P,!,fail.
not(P).

16 May 2025 NGJD@FCT-UoK 36

• The same definition can also be written as one clause:
not(P):-P,!,fail; true.
• Notes
1. Now, we will assume that ‘not’ is a built-in Prolog procedure that behaves as
defined here.
2. We will also assume that ‘not’ is defined as a prefix operator so that we can
also write the goal,
not(snake(X))
as
not snake(X).
3. Some Prolog implementations, in fact support this notation. If not, then we
always define not ourselves as above.
In many Prolog implementations (e.g. Wisdom Prolog), ‘not Goal’ is written as
‘ \+ Goal’.
16 May 2025 NGJD@FCT-UoK 37
 4. It should be noted that ‘not’ defined as failure, as here, does not exactly to
correspond the negation in mathematical logic.
This difference can cause unexpected behavior if ‘not’ is used without care.
5. ‘not’ is a useful facility and often be used advantageously in place of cut.

16 May 2025 NGJD@FCT-UoK 38

• The two examples in section 6.5.1 can be rewritten with not as:

different(X,Y):-not (X=Y).
likes(mary,X):-animal(X),not snake(X).

• Our tennis classification program in section 6.4.4 can also be rewritten, using not,
in a way that is closer to the initial definition of the three categories:

class(X,fighter):-beat(X,_),beat(_,X).
class(X,winner):-beat(X,_),not beat(_,X).
class(X,sportsman):-beat(_,X),not beat(X,_).

16 May 2025 NGJD@FCT-UoK 39

Exercises
1. Given two lists, Candidates and RuledOut, write a sequence of goals (using
member and not) that will through backtracking find all the items in RuledOut.
2. Define the set subtraction relation
difference(Set1, Set2, SetDifference)
where all the three sets are represented as lists.
For example:
difference( [a,b,c,d], [b,d,e,f], [a,c] )

16 May 2025 NGJD@FCT-UoK 40

6.6 Problems with Cut and Negation
6.6.1 Advantages
• With cut we can often improve the efficiency of the program. The idea is to
explicitly tell Prolog: do not try other alternatives because they are bound to fail.
• Using cut we can specify mutually exclusive rules; so we can express rules of the
form:
if condition P then conclusion Q,
otherwise conclusion R.
In this way, cut enhances the expressive power of the language.

16 May 2025 NGJD@FCT-UoK 41

6.6.2 Problems with Cut
• If there is no cut in the program we can change the order of clauses and goals, and
this will only affect the efficiency of the program, not the declarative meaning.
• On the other hand, in programs with cuts, a change in the order of clauses may
affect the declarative meaning. This means that we can get different results.
The following example illustrates:
𝑝 ∶ − 𝑎, 𝑏.
𝑝 ∶ − 𝑐.
The declarative meaning of this program is: 𝑝 is true if and only if 𝑎 and 𝑏 are both
true or 𝑐 is true.
This can be written as a logic formula:
𝑝 ⟺ (𝑎 ∧ 𝑏) ∨ 𝑐

16 May 2025 NGJD@FCT-UoK 42

 We can change the order of the two clauses and the declarative meaning remains
the same.
Let us now insert a cut:
𝑝 ∶ −𝑎, !, 𝑏.
𝑝 ∶ −𝑐.
The declarative meaning is now:
𝑝 ⟺ (𝑎 ∧ 𝑏) ∨ (∼ 𝑎 ∧ 𝑐).
If we swap the clauses,
𝑝 ∶ −𝑐.
𝑝 ∶ −𝑎, !, 𝑏.
Then the meaning becomes:
𝑝 ⟺ 𝑐 ∨ (𝑎 ∧ 𝑏).
The important point is that when we use the cut facility we have to pay more
attention to the procedural aspects.
16 May 2025 NGJD@FCT-UoK 43
6.6.3 Problems with Negation
• It should be noted that ‘not’ may also cause problems, and so should also be used
with care.
• The problem is that ‘not’, as defined here, does not correspond exactly to negation
in mathematics.
Example 1
If we ask Prolog
|?_not human(mary).
Prolog will probably answer ‘yes’.
But this should not be understood as Prolog saying ‘Mary is not human’.
What Prolog really means to say is: ‘There is not enough information in the
program to prove that Mary is human’.
This arises because when processing a ‘not’ goal, Prolog does not try to prove this
goal directly. Instead, it tries to prove the opposite, and if the opposite cannot be
proved then Prolog assumes that the ‘not’ goal succeeds.
16 May 2025 NGJD@FCT-UoK 44
 Such reasoning is based on the so–called closed world assumption.
According to this assumption the world is closed in the sense that everything that
exists is in the program or can be derived from the program. Accordingly then, if
something is not in the program (or cannot be derived from it) then it is not true
and consequently its negation is true.
This deserves special care because we do not normally assume that ‘the world is
closed’: with not explicitly entering the clause
human(mary).
into our program, we do not normally mean to imply that Mary is not human.
Example 2
We will, by example, further study the special care that ‘not’ requires:
r(a).
q(b).
p(X):-not r(X).

16 May 2025 NGJD@FCT-UoK 45

 If we now ask,
|?_q(X), p(X).
then Prolog will answer,
X=b.
If we ask apparently the same question
|?_p(X), q(X).
then Prolog will answer:
no
The key difference between both questions is that the variable X is, in the first
case, already instantiated when p(X) is executed, where at that point X is not yet
instantiated in the second case.

16 May 2025 NGJD@FCT-UoK 46

Summary
• The cut facility prevents backtracking. It is used both to improve the efficiency of
programs and to enhance the expressive power of the language.
• Efficiency is improved by explicitly telling Prolog (with cut) not to explore
alternatives that we know are bound to fail.
• Cut makes it possible to formulate mutually exclusive conclusions through rules of
the form:
if Condition then Conclusion1 otherwise Conclusion2
• Cut makes it possible to introduce negation as failure: not Goal is defined through
the failure of Goal.
• Two special goals are sometimes useful: true always succeeds, fail always fails.

16 May 2025 NGJD@FCT-UoK 47

• There are also some reservations against cut: inserting a cut may destroy the
correspondence between the declarative and procedural meaning of a program.
Therefore, it is part of good programming style to use cut with care and not to use
it without reason.
• not defined through failure does not exactly correspond to negation in
mathematical logic. Negation as failure makes the closed world assumption.
Therefore, the use of not also require special care.
• In many Prolog implementations, not is written as ‘\+’.

16 May 2025 NGJD@FCT-UoK 48