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!

Nippur

Do you really mean H =:= 1? Note that this goal produces an error if H is not instantiated. – Sabella

To be honest, I didn't really think about the specific test in the code examples as I was rather referring to the situation of having the two different base cases. I added the equal to one test just to have something happen during recursion which could help me clarify my question. – Nippur

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.

Mainly

I do not agree. ! can be used in safe places, and if you want to obtain efficiency sometimes you should use it. Workarounds often produce much less readable code, which would be a gain in efficiency at the cost of readability, which is the wrong trade direction. – Zoroastrian

Your disagreement seems to be confined against statements that are not made in the post you are attaching this comment to. It does not say that !/0 cannot be used in safe places, nor does it say that you must not use !/0 to improve efficiency, nor does it say that all or only a minority of workarounds produce more readable code, and it certainly does not say that trading readability for efficiency goes in the right direction. Is there anything contained in the actual post you disagree with? – Mainly

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]) :- !.

Tether

You favorite version incorrectly fails for base(Xs), Xs = [2] – Sabella

Well, then state it. It is by no means evident. – Sabella

It is true that cuts are not always bad. But it's also bad to encourage beginners to use them so profusely and they should truly be avoided if they're only being used "just to get the predicate to work". It's like saying, in C, that gotos are bad. They aren't all bad, but if you give a beginner free reign on goto's and don't have proper guidelines for when you really need to use them, it can result in very bad programming habits and poorly structured code. So in a solution like the above, it would be good to explain why the cuts are essential rather than just "throw them out there". :) – Teasley