Prolog : avoid redundant choice points (non-determinism) with and without cut operator

Question

Firstly, I have read all other posts on SO regarding the usage of cuts in Prolog and definitely see the issues related to using them. However, there's still some unclarity for me and I'd like to settle this once and for all.

In the trivial example below, we recursively iterate through a list and check whether every 2nd element is equal to one. When doing so, the recursive process may end up in either one of following base cases: either an empty list or a list with a single element remains.

base([]).
base([_]).
base([_,H|T]) :- H =:= 1, base(T).

When executed:

?- time(base([1])).
   % 0 inferences, 0.000 CPU in 0.000 seconds (74% CPU, 0 Lips)
   true ;
   % 2 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 99502 Lips)
   false.

?- time(base([3,1,3])).
   % 2 inferences, 0.000 CPU in 0.000 seconds (79% CPU, 304044 Lips)
   true ;
   % 2 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 122632 Lips)
   false.

In such situations, I always used an explicit cut operator in the 2nd base case (i.e. the one representing one element left in the list) like below to do away with the redundant choice point.

base([]).
base([_]) :- !.
base([_,H|T]) :- H =:= 1, base(T).

Now we get:

?- time(base([1])).
   % 1 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 49419 Lips)
   true.

?- time(base([3,1,3])).
   % 3 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 388500 Lips)
   true.

I understand that the behaviour of this cut is specific to the position of the rule and can be considered as bad practice.

Moving on however, one could reposition the cases as following:

base([_,H|T]) :- H =:= 1, base(T).
base([_]).
base([]).

which would also do away with the redundant choice point without using a cut, but of course, we would just shift the choice point to queries with lists with an even amount of digits like below:

?- time(base([3,1])).
% 2 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 99157 Lips)
true ;
% 2 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 96632 Lips)
false.

So this is obviously no solution either. We could however adapt this order of rules with a cut as below:

base([_,H|T]) :- H =:= 1, base(T), !.
base([_]).
base([]).

as this would in fact leave no choice points. Looking at some queries:

?- time(base([3])).
% 1 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 157679 Lips)
true.

?- time(base([3,1])).
% 3 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 138447 Lips)
true.

?- time(base([3,1,3])).
% 3 inferences, 0.000 CPU in 0.000 seconds (82% CPU, 393649 Lips)
true.

However, once again, this cut's behaviour only works correctly because of the ordering of the rules. If someone would reposition the base cases back to the original form as shown below:

base([]).
base([_]).
base([_,H|T]) :- H =:= 1, base(T), !.

we would still get the unwanted behaviour:

?- time(base([1])).
   % 0 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 0 Lips)
   true ;
   % 2 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 119546 Lips)
   false.

In these sort of scenarios, I always used the single cut in the second base case as I'm the only one ever going through my code and I got kind of used to it. However, I've been told in one of my answers on another SO post that this is not recommended usage of the cut operator and that I should try to avoid it as much as possible.

This brings me to my bipartite question:

• If a cut, regardless of the position of the rule in which it is present, does change behaviour, but not the solution (as in the examples above), is it still considered to be bad practice?

• If I would like to do away with a typical redundant choice point as the one in the examples above in order to make a predicate fully deterministic, is there any other, recommended, way to accomplish this rather than using cuts?

Thanks in advance!

Answer 1

Always try hard to avoid !/0. Almost invariably, !/0 completely destroys the declarative semantics of your program.

Everything that can be expressed by pattern matching should be expressed by pattern matching. In your example:

every_second([]).
every_second([_|Ls]) :-
        every_second_(Ls).

every_second_([]).
every_second_([1|Rest]) :- every_second(Rest).

Like in your impure version, no choice points whatsoever remain for the examples you posted:

?- every_second([1]).
true.

?- every_second([3,1]).
true.

?- every_second([3,1,3]).
true.

Notice also that in this version, all predicates are completely pure and usable in all directions. The relation also works for the most general query and generates answers, just as we expect from a logical relation:

?- every_second(Ls).
Ls = [] ;
Ls = [_G774] ;
Ls = [_G774, 1] ;
Ls = [_G774, 1, _G780] ;
Ls = [_G774, 1, _G780, 1] .

None of the versions you posted can do this, due to the impure or non-declarative predicates (!/0, (=:=)/2) you use!

When reasoning about lists, you can almost always use pattern matching alone to distinguish the cases. If that is not possible, use for example if_/3 for logical purity while still retaining acceptable performance.

Answer 2

The trick is "currying" over number of unbounds in the rule:

base([]). 
base([_|Q]) :- base2(Q).

base2([]). 
base2([H|Q]) :- H =:= 1, base(Q).

However, it is a bad rule to say cuts are bad. In fact, my favorite will be:

base([]) :- !. 
base([_]) :- !. 
base([_,H|Q]) :- !, H =:= 1, base(Q).

Thing about this example of primes(++):

primes([5]).
primes([7]).
primes([11]).

vs

primes([5]) :- !.
primes([7]) :- !.
primes([11]) :- !.