Custom subset not backtracking

Question

I'm new to prolog and I've been having trouble with some homework. On some part of my code I have to generate subsets of a given set on backtracking. Meaning, the code should try for a subset, and when it fails the next condition, try the next subset. I have done some research and the default function subset won't backtrack because as explained in this question both arguments are input arguments. So I built a custom one, which still isn't backtracking. Can you give me a hint on what I'm failing on? Here's my code:

    numNutrients(8).
    product(milk,[2,4,6]).
    product(porkChops,[1,8]).
    product(yoghurt,[3,1]).
    product(honey,[5,7]).
    product(plastic,[3,5,2]).
    product(magic,[5,7,8]).

nutrientlist(N,L):-findall(I,between(1,N,I),L).

subset2([],[]):-!.
subset2([X|T],[X|T2]):-
    subset2(T,T2).
subset2([_|T],[T2]):-
    subset2(T,T2).

shopping(K,L):-
    numNutrients(J),
    nutrientlist(J,N),
    findall(P,product(P,_),Z),
    subset2(X,Z),
    length(X,T),
    T =< K,
    covers(X,N),
    L = X.

covers(_,[]):-!.
covers([X|L],N):-
    product(X,M),
    subset2(M,N),
    subtract(N,M,T),
    covers(L,T).

main:-
    shopping(5,L),
    write(L).

The problem is on predicate shopping(K,L). When it gets to predicate subset2, it gives the whole set, which has length 6 (not 5), then fails and doesn't backtrack. Since all previous predicates can't backtrack it just fails.

So, why doesn't subset2 backtrack?

Thank you for your time.

Answer 1

Primary focus: subset2/2

First, let us focus only on the predicate that shows different properties from those you expect.

In your case, this is only subset2/2, defined by you as:

subset2([], []) :- !.
subset2([X|T], [X|T2]) :-
        subset2(T, T2).
subset2([_|T], [T2]) :-
        subset2(T, T2).

I will now use declarative debugging to locate the cause of the problem.

For this method to apply, I remove the !/0, because declarative debugging works best on pure and monotonic logic programs. See logical-purity for more information. Thus, we shall work on:

subset2([], []).
subset2([X|T], [X|T2]) :-
        subset2(T, T2).
subset2([_|T], [T2]) :-
        subset2(T, T2).

Test cases

Let us first construct a test case that yields unintended answers. For example:

?- subset2([a], [a,b]).
false.

That obviously not intended. Can we generalize the test case? Yes:

?- subset2([a], [a,b|_]).
false.

So, we have now an infinite family of examples that yield wrong results.

Exercise: Are there also cases where the program is too general, i.e., test cases that succeed although they should fail?

Locating mistakes

Why have we seen unintended failure in the cases above? To locate these mistakes, let us generalize the program.

For example:

subset2(_, []).
subset2([_|T], [_|T2]) :-
        subset2(T, T2).
subset2(_, [T2]) :-
        subset2(T, T2).

Even with this massive generalization, we still have:

?- subset2([a], [a,b|_]).
false.

That is, we have many cases where we expect the query to succeed, but it fails. This means that the remaining program, even though it is a massive generalization of the original program, is still too specific.

Correcting the program

To make the shown cases succeed, we have to either:

• add clauses that describe the cases we need
• or change the existing clauses to cover these cases too.

For example, a way out would be to add the following clause to the database:

subset2([a], [a,b|_]).

We could even generalize it to:

subset2([a], [a|_]).

Adding either or both of these clauses to the program would make the query succeed:

?- subset2([a], [a,b|_]).
true.

However, that is of course not the general definition of subset2/2 we are looking for, since it would for example still fail in cases like:

?- subset2([x], [x,y|_]).
false.

Therefore, let us go with the other option, and correct the existing definition. In particular, let us consider the last clause of the generalized program:

subset2(_, [T2]) :-
        subset2(T, T2).

Note that this only holds if the second argument is a list with exactly one element which is subject to further constraints. This seems way too specific!

Therefore, I recommend you start by changing this clause so that it at least makes the test cases collected so far all succeed. Then, add the necessary specializations to make it succeed precisely for the intended cases.