Next: More on Cuts Up: Code Examples Previous: Ancestry Program

## Cut Demonstration

```% Experimenting with the use of the ``cut'' predicate
% (after Sterling and Shapiro ``The Art of Prolog'')

%       GREEN CUTS
%       ----------

%       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
*/

%       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 minimum(1,2,X) is:

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

%       Another "green cut" example:

%       delete(+List, +Item, ?Result).
%       Removes all instances of Item from List, returning the Result.

delete([H|T], H, Result):- !,
delete(T, H, Result).
delete([H|T], X, [H|Rest]):-
\+ H = X, !,
delete(T, X, Rest).
delete([], _, []).

%       RED CUTS
%       --------

%       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 minimum(1,2,X) is:

minimum(1, 2, X)
/           \
/             *<--- This branch is pruned from the tree
/               \    once the ! has been reached.
minimum(1, 2, 1)   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.
i.e. The intended meaning of minimum has been lost.

*/

%       Another "red cut" example:

%       rc_delete(+List, +Item, ?Result).
%       Like delete/3, but omits the non-unification check in the second
%       clause.  This makes the meaning of the code more obscure.

rc_delete([H|T], H, Result):- !,
rc_delete(T, H, Result).
rc_delete([H|T], X, [H|Rest]):- !,
rc_delete(T, X, Rest).
rc_delete([], _, []).

%       USING CUTS TO SPECIFY DEFAULTS
%       ------------------------------

pension(X, invalid_pension):-
invalid(X), !.
pension(X, old_age_pension):-
over_65(X),
paid_up(X), !.
pension(X, supplementary_benefit):-
over_65(X), !.
pension(_, nothing).    % This is the default if none of the above succeed.

invalid(fred).

over_65(fred).
over_65(joe).
over_65(jim).

paid_up(fred).
paid_up(joe).

/*
**BUT** This doesn't work in certain cases.  For example:
the query pension(fred,nothing) would succeed.
*/

entitlement(X, Y):-
possible_pension(X, Y).
entitlement(X, nothing):-
\+ possible_pension(X, _).

possible_pension(X, invalid_pension):-
invalid(X).
possible_pension(X, old_age_pension):-
over_65(X),
paid_up(X).
possible_pension(X, supplementary_benefit):-
over_65(X).

/*
This is a bit better, and the query entitlement(fred, nothing)
will now succeed.
*/

%       CUT AND FAIL
%       ------------

%       not(+X).
%       Succeeds if X fails.

not(X):-
X, !, fail.
not(_).
```

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