Re: CUT and FAIL in KnowledgeWorks

>>>>> On Fri, 27 Jun 2003 11:04:24 -0400, "Young, David" <dyoung@bloodhoundinc.com> said:

    David> Greetings. Would someone please offer working definitions of CUT and FAIL as
    David> implemented in KnowledgeWorks? My background is forward-chaining and DL
    David> systems; it's been over a decade since I've used Prolog.

    David> I'm coming up to speed quickly with KW's backward-chaining rule support
    David> (thanks for a great product, Xanalys!), but I'm unclear on the behavior of
    David> cut and fail. Under what conditions might I use each? Thanks much...

Hi,

Really you should read a text book on Prolog, but briefly:

"cut" means that once control passes though that point the
backtracking possibilities in that predicate are eliminated.

"fail" means that failure is forced. The predicate fails as if you had
asked to eg unify two things that didn't match.

Now when and how should you use them?

"cut" has two kinds of uses. So called, "green cuts" and "red
cuts". The former are benign cuts used to improve the efficiency of
already working code. The latter are evil spawn introduced into a
Prolog program in order to make it work.

"fail" is really only used to implement higher order logic features
like collecting all the possible answers to a query into a set.

Here are two examples (untested and in pseudo Prolog syntax):

foo( X ) :- X < 0, bar( X );
foo( X ) :- X >= 0, bar( X );

In this example we can see something that an insufficiently smart
Prolog compiler cannot. That is, that there is no point backtracking
after the test for X < 0 succeeds because the next test checks to see
if it is greater than zero. So we can introduce a cut (! in Prolog
syntax):

foo( X ) :- X < 0, !, bar( X );
foo( X ) :- X >= 0, quux( X );

You could put a cut in the other clause for symmetry but it is not
needed. ( Ultimately, this makes the early part of the clause act like
a 'guard' - a feature of other languages. )

If you then think "ah ha!" I can now remove the test for X >= 0.

foo( X ) :- X < 0, !, bar( X );
foo( X ) :- quux( X );

Then your cut has now become a "red cut" that is necessary for correct
execution.

For fail you could use it like this:

collect( X, Xs ) :-
        assert( collected( [] ),
        foo( X ),
        retract( collected( Y ) ),
        assert( collected( [ X | Y ] ) ),
        fail;
collect( X, Xs ) :-
        retract( collected( Xs ) );

Or something like that anyway, where you rely on the fact that assert
and retract cause side-effects that do not get undone by backtracking
and you use them to collect all the results of a query.

This is something how "setof" and "bagof" are built but they have to
be smarter to support nested use.

HTH 

__Jason