Subject: Re: [SWIPL] keysort

From: "Richard A. O'Keefe" <[email-masked]>
Date: Tue, 20 Feb 2001 16:23:16 +1300 (NZDT)

I wrote:

    last_keys([], []) :- !.                % Green cut for inverse use
    last_keys([L|Ls], [K-L|KLs]) :-
        last(K, L),
        last_keys(Ls, KLs).

    triple_keys([], []) :- !.                % Green cut for inverse
	use
    triple_keys([L|Ls], [K-L|KLs]) :-
        L = [_,_,K],
        triple_keys(Ls, KLs).

Jonathan D Johnston asked:

	Would you explain your use of cut in the above predicates?
	Also, why do you refer to them as "Green" cuts?

This is old terminology going back to at least 1979.  I would expect that
any Prolog book worth having would explain it.

Red = danger
Green = safety

A "red" cut is one which changes the semantics of the program,
pruning away solutions that would have been found had the cut not
been there.  The cut in

    fail_if(P) :- call(P), !, fail.
    fail_if(_).

is a "red" cut because without it the predicate would always succeed.

A "green" cut is one which doesn't change the semantics of the program.
Arguably, it might prune away alternative proofs of the same solutions.
The rule for green cuts is
    - add a cut at PRECISELY the earliest point where YOU know that the
      right choices have been made so far and the compiler does NOT know.

	During my (limited) testing of these predicates, I didn't see
	any difference with or without the cut.

There WASN'T any difference in the set of solutions.  That's what makes
it a "green" cut.

The thing is that keeping choice-points around is expensive, and worse,
it's contagious.  If a predicate p calls a predicate q, and at runtime
Prolog *thinks* q might have other solutions, that will make the result
of p look non-determinate as well.

In this case, if we call

    ?- last_keys(L, []).

there is in fact only one solution, but in a Prolog system that only does
FIRST-argument indexing, the Prolog run-time system won't know that.  So
without the cut, every time you successfully call last_keys/2, there will
BE only one possible solution, but Prolog will THINK there might be more.

So the comment "Green cut for inverse use" hints that when you use this
predicate to solve for the first argument, given the second, that's when
this cut does something for efficiency without changing the set of solutions.

	I must confess that I am still sometimes confused by when
	to use cut.
	
Use a red cut when the nature of your problem demands an if-then-else effect.

Use a green cut when you know that a solution is unique and Prolog doesn't.

I don't think *anyone* much likes putting in green cuts, although after a
while you get a feel for it.  That's why Mercury makes determinism a
compile-time (declared, checked, enforced) property.