when SHOULD you use the cut (!/0)?

[jjtolton]

Almost every resource on Prolog is unanimous in that the cut operator should always be avoided where possible.

I have yet to see clear guidance on where you should use the cut operator.

I'm asking because as I go through the available learning resources, I will occasionally run across rules which feature the cut operator -- my mind does not know if I should reject this example and to rewrite it a different way or if the example provided is a good example of when to use the cut operator.

So when should you use the cut operator -- or is it always avoidable?

[triska]

Every known computation can be expressed in Prolog without !/0. One can show this by implementing a Turing machine in that subset of Prolog, which I have done with:

https://www.metalevel.at/prolog/showcases/turing.pl

Thus, I find it hard to think of even a hypothetical case where one could justifiably say: "you SHOULD use !/0". With every known computation being expressible without using !/0, where would such a justification come from? It seems far more likely that it can be expressed not only in one (which is certain to exist), but even in several different additional ways without using !/0.

One note about Prolog terminology: !/0 is not an operator:

?- current_op(Pri, Fix, !).
   false.

[jjtolton]

I'm looking at the definition of tfilter and I'm thinking that a stub of the correct definition would be something like:

delete_all([], _, []).
delete_all([X|Ls], Ls2, Diff) :-
        if_(call(delete_all(Ls1, Ls2, Diff)),
            % describe logic vars
            ),
        delete_all( % recursive application with modified LVARs
                    ).

am I on the right track?

[hurufu]

I'm afraid you are thinking too procedurally. You need to think declaratively and post yourself a question: What is true about lists A, B and C? Also please observe that lists are not sets, but multisets, so my attempt looks like:

:- use_module(library(lists)).
:- use_module(library(dif)).
:- use_module(library(lambda)).

% A, B, and C are multisets. C is a difference of A and B.
multiset_difference(A/B, C) :-
    maplist(\X^maplist(dif(X), C), B),
    maplist(\Y^member(Y,A), C).

Maybe it isn't the best code, because I hardly tested it, but it is mostly to show my point.

UPTD 1: Declarative reading

Every element of B is not an element of C and every element of C is an element of A. It is as close to pure mathematical definition as it can be.

UPDT 2: I actually have run my code and it has some bugs, so it is not correct it is mostly to show how you should think about a problem, not to provide actual solution.

[UWN]

am I on the right track?

Use memberd_t/3 and adapt this here,

(Github is not very well suited for such questions which has nothing to do with the original question)

[jjtolton]

(Github is not very well suited for such questions which has nothing to do with the original question)

😅

[jjtolton]

am I on the right track?

Use memberd_t/3 and adapt this here,

(Github is not very well suited for such questions which has nothing to do with the original question)

moving discussion to new Q&A: #2507

[haijinSk]

I'm afraid, not exactly/directly what you want (the clear guidance where one should use the cut; I, too, wanted once something like that), but there is an answer, or the answer (and many his answers) by @UWN (false) on stackoverflow:

Knowing when to use cut in prolog
https://stackoverflow.com/questions/14541164/knowing-when-to-use-cut-in-prolog/14556019

Also, for me, an older paper: "Pruning in logic programming" by Lee Naish was helpful to get intuition. Unfortunately, the paper is not freely available. I read only a small part of it, but I had the "click" in my mind...

For me, the key passage from the paper was:

"[...] cut in Prolog, is best understood as the combination of two operations:

• once prevents alternative solutions to calls before the cut being considered;
• soft cut prevents alternative clauses being considered (a single “choice point” is removed)."

I'm only a Prolog beginner (and not going to be more than a beginner) and I do not use the cut operator: I write only small programs in Prolog to run "off-line" and I want to see Prolog as a declarative programming language. Personally, I don't need Prolog to be a conventional programming language with the maximal possible efficiency (in the context of the full Prolog system).

Of course, the paper has a section "The danger", the section I didn't read, I don't need it; I want declarative/relational/logical/simple to reasoning Prolog even for a beginner = without the cut. Here is the first sentence from "The danger" section:

"A danger of adding pruning operators to a logic programming language is that the result is not a logic programming language."

[hurufu]

Cuts can have a declarative semantics, but you need to restrict yourself to pure functions: https://www.researchgate.net/publication/221255396_A_Declarative_Semantics_for_the_Prolog_Cut_Operator

[triska]

There are statements in this paper that seem to be based on misconceptions and wrong assumptions about Prolog. For instance, let's try the predicate remove/3 that is shown in the paper. How do we find out its semantics, i.e., what it means? Well, let's ask Prolog about it, that's a core attraction of the language: Predicate, what do you mean?, which answers do you describe?

?- remove(Ls, R, Rs).
   Ls = [R|Rs].

Is this really the intended relation? If it were, then why not simply implement it like that? Why go through the effort of writing 10 lines for what can be described with a single line?

Or what about this:

?- remove("abcd", b, "acd").
   true.

Yet, a generalization fails:

?- remove("abcd", B, "acd").
   false.

What to make of this? It is a Prolog predicate that can no longer be reasoned about logically, and thus not a predicate as we know it from logic.

In my experience, when arguments are made for constructs that break logical properties of Prolog, then generalizations of goals and queries are often missing from the analysis. In the above example, the paper shows a mode declaration of intended usage modes but there is nothing in the code itself that ensures these modes, so the predicate is prone to being used in modes it was not intended for, and yields wrong results in these modes. Why would anyone take this risk? If all one cares about are cases where everything is ground, then one can use a functional programming language instead and likely get correct results in all cases that the language can express.

Using tfilter/3 from library(reif), it is in fact possible to implement remove/3 correctly in a single line of code:

remove(Ls, R, Rs) :-
        tfilter(dif(R), Ls, Rs).

Yielding:

?- length(Ls, _), remove(Ls, R, Rs).
   Ls = [], Rs = []
;  Ls = [R], Rs = []
;  Ls = [_A], Rs = [_A], dif:dif(R,_A)
;  Ls = [R,R], Rs = []
;  Ls = [R,_A], Rs = [_A], dif:dif(R,_A)
;  Ls = [_A,R], Rs = [_A], dif:dif(R,_A)
;  Ls = [_B,_A], Rs = [_B,_A], dif:dif(R,_A), dif:dif(R,_B)
;  Ls = [R,R,R], Rs = []
;  ... .
?- remove("abcd", b, "acd").
   true.
?- remove("abcd", B, "acd").
   B = b
;  false.

[hurufu]

Totally agree, as I said you have to use only those relations that are functions, ie have a direction from inputs to outputs. Which kinda misses the point of using Prolog in the first place, but it was an attempt to giving semantics to cuts.