Next: Using Cuts to Up: No Title Previous: Negation

# Cuts

Prolog is good at backtracking but uncontrolled backtracking can be a nuisance. The cut symbol (written as `!`) is a special subgoal used to provide a limited form of control over backtracking, by committing the Prolog interpreter to a particular portion of the potential search space. An example will help start to explain how this works. The code for this example can be found in Section 13.2 and further discussion appears in Sterling & Shapiro ``The Arto fo Prolog''.

We start with the following definition of `minimum/3`:

```% minimum(+Number1, +Number2, ?Minimum).
% Succeeds if Minimum is the minimum value of Number1 and Number2.

minimum(X, Y, X):-
X =< Y.
minimum(X, Y, Y):-
X > Y.
```

The potential search tree for the goal `minimum(1,2,X)` is:

```                 minimum(1, 2, X)
/             \
/               \
minimum(1, 2, 1)    minimum(1, 2, 2)
/                    \
/                      \
/                        \
1 =< 2                     1 > 2
```

In other words, the Prolog interpreter, in trying to satisfy `minimum(1,2,X)` would first test whether `1 =< 2`, which succeeds giving the result `minimum(1,2,1)`. However, if forced to backtrack it would also try the second clause and try to establish `1 > 2`, which will fail. It would be useful to have some way of telling the Prolog interpreter, once it had established `1 =< 2` that there is no point in looking for any other ways of finding a solution. This information can be given by putting a cut after the first subgoal of the first clause, as shown in `gc_minimum/3`.

```%  gc_minimum(+Number1, +Number2, ?Minimum).
%Identical to minimum/3 but with a cut in the first clause.

gc_minimum(X, Y, X):-
X =< Y, !.
gc_minimum(X, Y, Y):-
X > Y.
```

The potential search tree for the goal `gc_minimum(1,2,X)` is:

```                 gc_minimum(1, 2, X)
/           \
/             *<--- This branch is pruned from the tree
/               \    once the ! has been reached.
gc_minimum(1, 2, 1)   gc_minimum(1, 2, 2)
/                   \
/                     \
/                       \
1 =< 2, !                 1 > 2
/
/
!
```

Notice that this doesn't alter the set of results which can be obtained from running the program. All it does is pre--empt search which would be fruitless. Having put the cut into `gc_minimum/3` we might go one step further and remove the `X > Y` test in the second subgoal. The argument for doing this might be that if we know that the cut in the first clause will prevent the second clause ever being tried if `X =< Y` then the only condition under which the second clause is reached is when `X > Y`, so we don't need to make this test explicit. By making this change we get `rc_minimum/3` as shown below:

```% rc_minimum(+Number1, +Number2, ?Minimum).
% Like to gc_minimum/3 but with the check in the second clause
% left out, because the programmer thinks it isn't needed (given
% that Y should be the chosen minimum if X isn't).

rc_minimum(X, Y, X):-
X =< Y, !.
rc_minimum(_, Y, Y).
```

The potential search tree for the goal `rc_minimum(1,2,X)` is:

```                 rc_minimum(1, 2, X)
/           \
/             *<--- This branch is pruned from the tree
/               \    once the ! has been reached.
rc_ minimum(1, 2, 1)   rc_minimum(1, 2, 2)
/
/
/
1 =< 2, !
/
/
!
```

But there is a major flaw in this reasoning, as shown by calling the goal `minimum(1, 2, 2)`, which will (erroneously) succeed, since the first clause doesn't match and the cut is therefore never reached. Thus the intended meaning of `rc_minimum/3` is different from that of `minimum/3`. Some people refer to cuts which don't alter the meaning of the program as ``green cuts'' and cuts which do alter the meaning of the program as ``red cuts''.

Next: Using Cuts to Up: No Title Previous: Negation

Dave Stuart Robertson
Tue Jul 7 10:44:26 BST 1998