10.2 Using Cut

Well, we now know what cut is. But how do we use it in practice, and why is it so useful? As a first example, let’s define a (cut-free) predicate max/3 which takes integers as arguments and succeeds if the third argument is the maximum of the first two. For example, the queries

?- max(2,3,3).

and

?- max(3,2,3).

and

?- max(3,3,3).

should succeed, and the queries

?- max(2,3,2).

and

?- max(2,3,5).

should fail. And of course, we also want the program to work when the third argument is a variable. That is, we want the program to be able to find the maximum of the first two arguments for us:

?- max(2,3,Max).

Max = 3
yes

?- max(2,1,Max).

Max = 2
yes

Now, it is easy to write a program that does this. Here’s a first attempt:

max(X,Y,Y):- X =< Y.
max(X,Y,X):- X>Y.

This is a perfectly correct program, and we might be tempted simply to stop here. But we shouldn’t: it’s not good enough.

What’s the problem? There is a potential inefficiency. Suppose this definition is used as part of a larger program, and somewhere along the way max(3,4,Y) is called. The program will correctly set Y=4 . But now consider what happens if at some stage backtracking is forced. The program will try to re-satisfy max(3,4,Y) using the second clause. This is completely pointless: the maximum of 3 and 4 is 4 and that’s that. There is no second solution to find. To put it another way: the two clauses in the above program are mutually exclusive: if the first succeeds, the second must fail and vice versa. So attempting to re-satisfy this clause is a complete waste of time.

With the help of cut, this is easy to fix. We need to insist that Prolog should never try both clauses, and the following code does this:

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

Note how this works. Prolog will reach the cut if max(X,Y,Y) is called and X  =<  Y succeeds. In this case, the second argument is the maximum, and that’s that, and the cut commits us to this choice. On the other hand, if X  =<  Y fails, then Prolog goes onto the second clause instead.

Note that this cut does not change the meaning of the program. Our new code gives exactly the same answers as the old one, but it’s more efficient. In fact, the program is exactly the same as the previous version, except for the cut, and this is a pretty good sign that the cut is a sensible one. Cuts like this, which don’t change the meaning of a program, have a special name: they’re called green cuts.

But some readers will dislike this code. After all, isn’t the second line redundant? If we have to use this line, we already know that the first argument is bigger that the second. Couldn’t we squeeze out a little more efficiency with the help of our new cut construct? Let’s try. Here’s a first (faulty) attempt:

max(X,Y,Y) :- X =< Y,!.
max(X,Y,X).

Note that is the same as our earlier green cut max/3 , except that we have got rid of the > test in the second clause. How good is it? Well, for some queries it’s fine. In particular, it answers correctly when we pose queries in which the third argument is a variable. For example:

?- max(100,101,X).

X = 101
yes

and

?- max(3,2,X).

X = 3
yes

Nonetheless, it’s not the same as the green cut program: the new max/3 does not work correctly. Consider what happens when all three arguments are instantiated. For example, consider the query

?- max(2,3,2).

Obviously this query should fail. But in our new version, it will succeed! Why? Well, this query simply won’t unify with the head of the first clause, so Prolog goes straight to the second clause. And the query will unify with the second clause, and (trivially) the query succeeds! So maybe getting rid of that > test wasn’t quite so smart after all.

But there is another way. The problem with the new code is simply that we carried out variable unification before we traversed the cut. Suppose we handle our variables a little more intelligently (using three variables instead of two) and explicitly unify after we have crossed the cut:

max(X,Y,Z) :- X =< Y,!, Y = Z.
max(X,Y,X).

As the reader should check, this program does work, and (as we hoped for) it avoids the explicit comparison made in the second clause of our green cut version of max/3 .

But there is an important difference between the new version of the program and the green cut version. The cut in the new program is a classic example of what is known as a red cut. As this terminology is supposed to suggest, such cuts are potentially dangerous. Why? Because if we take out such a cut, we don’t get an equivalent program. That is, if we remove the cut, the resulting code does not compute the maximum of two numbers any more. To put it another way, the presence of the cut is indispensable to the correct functioning of the program. (This was not the case in the green cut version — the cut there merely improved efficiency.) Because red cuts are indispensable cuts, their presence means that programs containing them are not fully declarative. Now, red cuts can be useful on occasions, but beware! Their use can lead to subtle programming mistakes and make code hard to debug.

So, what to do? It’s probably best to work as follows. Try and get a good, clear, cut-free program working, and only then try to improve its efficiency by using cuts. Use green cuts whenever possible. Red cuts should be used only when absolutely necessary, and it’s a good idea to explicitly comment on any red cuts in your code. Working this way will maximise your chances of striking a good balance between declarative clarity and procedural efficiency.