What is the difference in execution if the cut '!' is present?

Question

counter([],[]).
counter([H|T],[[H,C1]|R]) :- counter(T,[[H,C]|R]),!, C1 is C+1.
counter([H|T],[[H,1]|R]) :- counter(T,R).

What is the effect of the "!" as I'm getting the same output for an input in both the above and below code?

 counter([],[]).
 counter([H|T],[[H,C1]|R]) :- counter(T,[[H,C]|R]),C1 is C+1.
 counter([H|T],[[H,1]|R]) :- counter(T,R).

I'm new to Prolog.

Electrometallurgy

what output? what input? what is your test call? – Discretion

If i invoke count([a,a,b], X). I get the result X=[ [a, 2], [b, 1] ]. for both codes the only difference is that the fullstop in the end is delayed without the " ! " – Electrometallurgy

so there is a difference after all. cut says to Prolog to cut any further possible searches out. without it, Prolog wants to try to find more solutions, will try to match the third clause. – Discretion

Answer 1

What is the effect of the "!"

The cut prunes the search space. That is, in an otherwise pure and monotonic program, the cut will remove some solutions or answers. As long as those are redundant that's fine. It sounds so innocent and useful, doesn't it? Let's have a look!

^{_{And lest I forget, using [E,Nr] to denote pairs is rather unusual, better use a pair E-Nr.}}

We will now compare counter_cut/2 and counter_sans/2.

| ?- counter_cut([a,a],Xs).
     Xs = [[a,2]].

| ?- counter_sans([a,a],Xs).
     Xs = [[a, 2]]
  ;  Xs = [[a, 1], [a, 1]].     % <<< surprise !!!

So the cut-version has fewer solutions. Seems the solution counter_cut/2 retained is the right one. In this very particular case. Will it always take the right one? I will try a minimally more general query:

| ?- counter_cut([a,B],Xs).
     B = a,
     Xs = [[a, 2]].

| ?- counter_sans([a,B],Xs).
     B = a,
     Xs = [[a, 2]]
  ;  Xs = [[a, 1], [B, 1]].

Again, _sans is chattier, and this time, it is even a bit right-er; for the last answer includes B = b. In other words,

| ?- counter_cut([a,B], Xs), B = b.
     fails.              % incomplete !

| ?- counter_sans([a,B], Xs), B = b.
     B = b,
     Xs = [[a,1],[b,1]].

So sometimes the _cut version is better, and sometimes _sans. Or to put more directly: Both are wrong somehow, but the _sans-version at least includes all solutions.

Here is a "purified" version, that simply rewrites the last rule into two different cases: One for the end of the list and the other for a further, different element.

counter_pure([],[]).
counter_pure([H|T],[[H,C1]|R]) :- counter_pure(T,[[H,C]|R]), C1 is C+1.
counter_pure([H],[[H,1]]).
counter_pure([H,D|T],[[H,1]|R]) :- dif(H,D), counter_pure([D|T],R).

From an efficiency viewpoint that is not too famous.

Here is a test case for efficiency for a system with rational tree unification:

?- Es = [e|Es], counter(Es, Dict).
resource_error(stack).

Instead, the implementation should loop smoothly, at least till the end of this universe. Strictly speaking, that query has to produce a resource error, but only after it has counted up to a number much larger than 10^100000000.

Comport

Thanks for doing the actual efficiency analysis which I shied away from! – Liar

Answer 2

Here's my pure and hopefully efficient solution:

counter([X|L], C):- counter(L, X, 1, C).

counter([],X, Cnt, [[X,Cnt]]).
counter([Y|L], X, Cnt, [[X,Cnt]|C]):-
  dif(X, Y),
  counter(L, Y, 1, C).
counter([X|L],X, Cnt, [[X,XCnt]|C]):-
  Cnt1 #= Cnt+1,
  Cnt1 #=< XCnt,
  counter(L, X, Cnt1, [[X,XCnt]|C]).

---

Using if_3 as suggested by @false:

counter([X|L], C):- counter(L, X, 1, C).

counter([],X, Cnt, [[X,Cnt]]).
counter([Y|L], X, Cnt, [[X,XCnt]|C]):-
  if_(X=Y,
    (
      Cnt1 #= Cnt+1,
      Cnt1 #=< XCnt,
      counter(L, X, Cnt1, [[X,XCnt]|C])
    ),
    (
      XCnt=Cnt,
      counter(L, Y, 1, C)
    )
  ).

Blackleg

In current implementations, counter([a,b], C) leaves a CP open. – Comport

Maybe, if_/3? – Comport

I think dif(X,Y) is redundant and leads to useless information, as an example: ?- counter([X,Y],C). X = Y, C = [[Y, 2]] ; C = [[X, 1], [Y, 1]], dif(X, Y), dif(X, Y). as you see dif(X,Y) is twice !! I think that's because dif(X,Y) is in the definition of =/3, So you could just remove it (If I'm not missing something....). – Opportunist

@coder: right, looking into =/3 I see that dif/2 is called if needed. – Blackleg

Answer 3

The cut operator ! commits to the current derivation path by pruning all choice points. Given some facts

fact(a).
fact(b).

you can compare the answers with and without cut:

?- fact(X).
X = a ;
X = b.

?- fact(X), !.
X = a.

As you can see, the general query now only reports its first success. Still, the query

?- fact(b), !.
true.

succeeds. This means, that cut violates the interpretation of , as logical conjunction:

?- X = b, fact(X), !.
X = b.

?- fact(X), !, X=b.
false.

but from our understanding of conjunction, A ∧ B should hold exactly when B ∧ A holds. So why do this at all?

• Efficiency: cuts can be used such that they only change execution properties but not the answers of a predicate. These so called green cuts are for instance described in Richard O'Keefe's Craft of Prolog. As demonstrated above, maintaining correctness of a predicate with cut is much harder than one without, but obviously, correctness should come before efficiency.

  It looks as if your problem was green, but I am not 100% sure if there is not a change in the answers.

• Negation: logical negation according to the closed world assumption is expressed with cut. You can define neg(X) as:

  neg(X) :-
    call(X),
    !,
    false.
  neg(_) :-
    true.
  

  So if call(X) succeeds, we cut the choice point for the second rule away and derive false. Otherwise, nothing is cut and we derive true. Please be aware that this is not negation in classical logic and that it suffers from the non-logical effects of cut. Suppose you define the predicate land/1 to be one of the continents:

  land(africa).
  land(america).
  land(antarctica).
  land(asia).
  land(australia).
  land(europe).
  

  and then define water as everything not on land:

  water(X) :-
    neg(land(X)).
  

  then you can correctly obtain:

  ?- water(pacific).
  true.
  
  ?- water(africa).
  false.
  

  But you can also derive:

  ?- water(space).
  true.
  

  which should not hold. In particular, in classical logic:

  land(africa) ∧
  land(america) ∧
  land(antarctica) ∧
  land(asia) ∧
  land(australia) ∧
  land(europe) → ¬ land(space).
  

  is not valid. Again, you should know well what you are doing if you use negation in Prolog.

Liar

Answer 4

Here is my attempt using if_/3:

counter([], []).
counter([H|T], [[H,C]|OutT] ):-
         if_( 
               T=[], 
               (C = 1,OutT=[]), 
               (
                 [H|T] = [H,H1|T2],
                 if_(
                       H=H1, 
                       (counter([H1|T2], [[H1,C1]|OutT]), C is C1+1),
                       (C = 1, counter([H1|T2], OutT))
                     )
               )  
            ).  

Opportunist

Why =(T,[]) in place of T = []? – Comport

Just a notation...I think that way is more obvious that we use =/3 and not =/2... – Opportunist