next up previous
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