3.8  Using Cut

• Commit to current clause
• Prune alternative solutions

Cut (written as !) prunes away part of the Prolog search-space. This can be a very powerful mechanism for improving the performance of programs, and even the suppression of unwanted solutions. However, it can also be easily misused and over-used.

Cut does two things:

commit

Disregard any later clauses for the predicate.

prune

Throw away all alternative solutions to the goals to the left of the cut.

3.8.1  Commit to current clause

Consider the following encoding of the “minimum” predicate:

Whilst logically correct, the behaviour of this encoding is non-optimal for two reasons. Consider the goal :- min(2,3,M). Although the first clause succeeds, correctly instantiating M to 2, Prolog leaves an open choice point. If these clauses and goal occur as part of a larger program and goal, a failure might occur later, causing backtracking to this open choice point. Prolog would then, in vain, try to find another minimum using the second clause for min. So there is a double drawback: firstly, an open choice point consumes memory, and secondly the unsuccessful evaluation of the second clause costs execution time.

To achieve the same logic, but more efficient behaviour, the programmer can introduce a cut. For example min is typically encoded as follows:

The cut removes the unnecessary choice point, which means that the second clause will never be executed if the first clause passed the cut. This effectively makes the test in the second clause redundant, and it can therefore be removed.

3.8.2  Prune alternative solutions

A cut may occur anywhere where a goal may occur, consider the following:

where first_prime returns the first prime number smaller than X. In this case, it calls a predicate prime/2, which generates prime numbers smaller than X, starting from the largest one. The effect of the cut here is to prune away all the remaining solutions to prime(X,P) once the first one is generated, so that on backtracking, prime(X,P) is not tried for alternative solutions. The cut will also commit the execution to this clause for first_prime/2, but as there is only one clause, this has no visible effect.