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:
Consider the following encoding of the “minimum” predicate:
min(X,Y, Min) :- X <Y, Min = X. min(X,Y, Min) :- Y=<X, Min = Y. |
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:
min(X,Y, Min) :- X<Y, !, Min = X. min(X,Y, Y). |
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.
A cut may occur anywhere where a goal may occur, consider the following:
first_prime(X, P) :- prime(X,P), !. |
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.