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.

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.

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)
    )
  ).

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.

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))
                     )
               )  
            ).