Does it make sense to use a cut when a predicate backtracks into the same solution?

Question

I am writing a simple matrix library and I have stumbled into a solution that brings up an opportunity to learn about the purpose of cuts.

boolean_mult(1,1,1).
boolean_mult(1,0,0).
boolean_mult(0,1,0).
boolean_mult(0,0,0).

binary_dot_product([B1],[B2],Solution) :-
    boolean_mult(B1,B2,Solution).
binary_dot_product([1|_],[1|_],1). % computation can end here.
binary_dot_product([_|B1s],[_|B2s],Solution) :-
    binary_dot_product(B1s,B2s,Solution).

This solution makes sense from a declarative perspective. Given two lists of 1's and 0's, B1 and B2, if the boolean product of their heads is 1 then the dot product of the lists is 1. Otherwise take the dot product of their tails. The dot product of singleton lists is the boolean product of the two elements.

The problem that I am having though is shown in this query:

?- binary_dot_product([1,0,1],[1,1,1],X).
X = 1 ;
X = 1 ;
X = 1.

I am able to backtrack three times, which from a declarative perspective does not make sense. There can only be one dot product! Not 3!

I can easily fix this problem with the use of a cut:

binary_dot_product([B1],[B2],Solution) :-
    boolean_mult(B1,B2,Solution).
binary_dot_product([1|_],[1|_],1) :- !. 
binary_dot_product([_|B1s],[_|B2s],Solution) :-
    binary_dot_product(B1s,B2s,Solution).

And now:

?- binary_dot_product([1,0,1],[1,1,1],X).
X = 1.

Up to this point in my Prolog career I have avoided cuts like the plague as I have been warned about their dangers. In this situation though I feel like a cut makes a lot of sense.

What am I gaining and losing from a use of a cut in the above code?

Answer 1

EDIT (since OP insisted ;-)

I am answering this question:

What am I gaining and losing from a use of a cut in the above code?

I am not sure what you are gaining. You are losing the ability to ask more general questions that you get for free if you do not use cuts in your code.

In the general case, getting the same correct solution more than once is a strong indication that your code, with or without cuts, is either redundant or plain wrong. This is not universally true of course but from experience, it is true often enough.

---

You shouldn't "avoid cuts like the plague". You should use cuts when you need them, and not use them when you don't need them.

This is too big of a topic to answer on SO. Every decent Prolog textbook explains cuts and discusses when you need them and why; and use your judgement, which will improve as you program.

However: if your program is incorrect without cuts, cuts will not fix it.

---

Consider those problems.

1. Given two boolean vectors, what is their dot product?

2. Implement a predicate with three arguments. The first two arguments are boolean vectors, and the third argument is the dot product.

In Prolog-land, the second problem assumes that you can ask questions like "given one vector and a dot product, what is the other vector?" Can either one of your current implementations do that? And are you going to ask such questions? And even if you didn't think you are going to ask such question, given that you could do it, could you come up with uses for it? Do you see where this is going?

---

Now, your code. There are issues with it (see for example the comment that Isabelle Newbie just made).

This does not give wrong results:

:- module(boolean, [add/3, mult/3, dot_product/3]).

add(1,1,1).
add(1,0,1).
add(0,1,1).
add(0,0,0).

mult(1,1,1).
mult(1,0,0).
mult(0,1,0).
mult(0,0,0).

dot_product(V1, V2, P) :-
    same_length(V1, V2),
    maplist(mult, V1, V2, [H|T]),
    foldl(add, T, H, P).

Using it:

?- use_module(boolean).
true.

?- dot_product([1,0,1],[1,1,1],P).
P = 1 ;
false.

?- dot_product([1, 1], [1, 0], Product).
Product = 1 ;
false.

?- dot_product([1, 1], V2, 1).
V2 = [1, 1] ;
V2 = [1, 0] ;
V2 = [0, 1] ;
false.

?- dot_product(V1, V2, 1).
V1 = V2, V2 = [1] ;
V1 = V2, V2 = [1, 1] ;
V1 = [1, 1],
V2 = [1, 0] ;
V1 = [1, 0],
V2 = [1, 1] ;
V1 = V2, V2 = [1, 0] ;
V1 = [1, 1],
V2 = [0, 1] ;
V1 = [0, 1],
V2 = [1, 1] ;
V1 = V2, V2 = [0, 1] ;
V1 = V2, V2 = [1, 1, 1] ;
V1 = [1, 1, 1],
V2 = [1, 1, 0] .

?- dot_product(V1, V2, P).
V1 = V2, V2 = [1],
P = 1 ;
V1 = [1],
V2 = [0],
P = 0 ;
V1 = [0],
V2 = [1],
P = 0 ;
V1 = V2, V2 = [0],
P = 0 ;
V1 = V2, V2 = [1, 1],
P = 1 ;
V1 = [1, 1],
V2 = [1, 0],
P = 1 ;
V1 = [1, 0],
V2 = [1, 1],
P = 1 .

EDIT2: There is still a choice point left after the last correct answer. To get rid of it, you can use tabling (as available in SWI-Prolog, for example). Make both add/3 and mult/3 tables, like this (before defining them):

:- table add/3, mult/3.

No more "false"s:

?- dot_product([1,0,1],[1,1,1],P).
P = 1.

?- dot_product(V1, [1, 0], 0).
V1 = [0, 1] ;
V1 = [0, 0].

---

The "same length" seems important enough; since there are no cuts, you can use the predicate to "generate-and-test". Anyway, dot product is only defined for vectors of the same length, isn't that so?

I made no attempt at optimizing the code. As you observe in your question, you can short-cut if the arguments are ground. This would be a good use of a cut (or an if-then-else): if arguments are ground, look for any "1" in any of the vectors; otherwise, use generic algorithm.

To check for "1" in a ground list, you could use memberchk(1, List).