Commutativity of Cut Operator in Prolog

Question

I'm currently studying Prolog, and in one of the notes I'm reading an example is given of how to use the cut operator correctly. Consider the following function to remove all elements of a particular value from a list.

rm(_,[],[]).
rm(A,[A|L],R) :- rm(A,L,R).
rm(A,[B|L],[B|R]) :- rm(A,L,R).

Due to backtracking, this is not a correct definition of the function, and the function will return all sublists of the list obtained from removing some elements of a particular value, but not necessarily all of them. The notes I'm reading say that a correct way to fix this is to replace the second line by the line

rm(A,[A|L],R) :- !, rm(A,L,R)

But that replacing the line by

rm(A,[A|L],R) :- rm(A,L,R), !

is not correct. I'm not sure why the second example is an incorrect way to fix the function. In swipl, replacing the second term by these fixes seems to always return the same answer on the test cases I consider. What am I missing here?

In the case of !, rm(A, L, R), if rm(A, L, R) fails, there will be no backtracking since it is pruned by the cut. In the case of rm(A, L, R), !, if rm(A, L, R) fails, there will be backtracking since the cut has not yet been encountered. — lurker

false false · Accepted Answer · 2017-04-22T22:14:14

Your example is a perfect example to illustrate why using the cut here is never a good idea.

Using rm(A,[A|L],R) :- !, rm(A,L,R). makes only sense if both the first and second argument are sufficiently instantiated. But if they are insufficiently instantiated, you get an incomplete answer like:

?- rm(X, [a], R).
   X = a, R = [].       % incomplete

This clearly misses an answer, as it constrains X to be a only. But if X is anything else, we get a different result, namely:

?- X = b, rm(X,[a],R).
R = [a].

Using the cut at the end as in rm(A,[A|L],R) :- rm(A,L,R), !. is even worse: First, all our assumptions so far must hold, and then additionally the third argument must not be instantiated. Otherwise we get additional incorrect solutions.

?- rm(a,[a],R).
R = [].

?- rm(a,[a],[a]).
true                 % incorrect

Just recall what we are asking here:

User: When removing a from the list [a] what do we get?

Prolog: Nothing, nil, nada.

User: But can't I have instead of nothing just [a]? Please!

Prolog: OK, I give in.

That's not the way you want to implement an accounting system.

So both uses of cuts are bad. But the second one is clearly worse for it has many more preconditions to remember and is also inefficient. On the other hand there are some cases where you can use these predicates. But typically it is quite difficult to remember when this is safe. Thus such cuts are a permanent source of errors.

Is there any hope to get rid of all this fine print? Fortunately, there is a way out using if_/3 from library(reif) for SICStus|SWI. Download it and say:

:- use_module(reif).

rm(_,[],[]).
rm(A,[X|Xs], Ys0) :-
   if_(A = X, Ys0 = Ys, Ys0 = [X|Ys]),
   rm(A, Xs, Ys).

This program is comparably efficient but does not have any of the aforementioned defects:

?- rm(X, [a], R).
   X = a,
   R = []
;  R = [a],
   dif(X, a).

Note the second new answer! It says that for all X that are different to a, the list remains unchanged.

Commutativity of Cut Operator in Prolog

1 Answers