Using Cut and Not in Prolog Programming

Question

I am new to Prolog Programming. So I want to know following. I know the use of Cut (!) in Prolog. Can somebody explain me, the use of Not in Prolog ,when and how to use Not & how to rewrite the following with out using Cut and avoiding the backtracking. ( using only predicates)

choose (0,_,[]) :- !.
choose (N,[H|T], [H|R]) :- M is N-1, Choose (M,T,R).
choose(N, [_|T],R) :- Choose(N,T,R)

And explain me how to rewrite the following (using only predicates)

chooseAll(N,L,Res) :-
    chooseAll(N,L,[],Res).

chooseAll(N,L,Seen,Res):-
    choose(N,L,R),
    not(member(R,Seen)),
    !,
    chooseAll(N,L,[R|Seen],Res).
chooseAll(_,_,Res,Res).

Answer 1

Please let us take a brief step back and consider a few issues that are more general than how to use one or two specific predicates such as !/0 or not/1.

First, let us fix a few syntax issues, and let your original code read:

choose(0,_,[]) :- !.
choose(N,[H|T], [H|R]) :- M is N-1, choose(M,T,R).
choose(N, [_|T],R) :- choose(N,T,R).

chooseAll(N,L,Res) :-
    chooseAll(N,L,[],Res).

chooseAll(N,L,Seen,Res):-
    choose(N,L,R),
    not(member(R,Seen)),
    !,
    chooseAll(N,L,[R|Seen],Res).
chooseAll(_,_,Res,Res).

Starting from this, I apply the following two minor changes:

• Instead of not/1, I use (\+)/1, because (\+)/1 is ISO but not/1 is, well, not.
• Instead of (is)/2, I use the CLP(FD) constraint (#=)/2 to advertise more recent language constructs and make explicit that we are reasoning only over integers in this case, not for example floats or other kinds of numbers. Think of this as guaranteeing additional type safety.

We these two small changes we obtain:

choose(0,_,[]) :- !.
choose(N,[H|T], [H|R]) :- M #= N-1, choose(M,T,R).
choose(N, [_|T],R) :- choose(N,T,R).

chooseAll(N,L,Res) :-
    chooseAll(N,L,[],Res).

chooseAll(N,L,Seen,Res):-
    choose(N,L,R),
    \+ member(R,Seen),
    !,
    chooseAll(N,L,[R|Seen],Res).
chooseAll(_,_,Res,Res).

Now let's start! I am eager to try out the main predicate by asking: Which solutions are there at all?

To find out, I post the so-called most general query, where all arguments are fresh variables:

?- chooseAll(X, Y, Z).
X = 0,
Z = [[]].

What? There is only a single solution of this predicate, right? Right?

Probably not.

So, I would like to get more answers for such basic questions. To get them, I make the following additional changes:

• I remove the !/0.
• I use dif/2 to state that two terms are different.
• I slightly reorder the clauses.
• I add the constraints N #> 0 for those clauses that only apply if N is greater than 0.

So, we have:

choose(0,_,[]).
choose(N,[H|T], [H|R]) :- N #> 0, M #= N-1, choose(M,T,R).
choose(N, [_|T],R) :- N #> 0, choose(N,T,R).

chooseAll(N,L,Res) :-
    chooseAll(N,L,[],Res).

chooseAll(_,_,Res,Res).
chooseAll(N,L,Seen,Res):-
    choose(N,L,R),
    maplist(dif(R), Seen),
    chooseAll(N,L,[R|Seen],Res).

And now we have for example:

?- chooseAll(X, Y, Z).
Z = [] ;
X = 0,
Z = [[]] ;
X = 1,
Y = [_1966|_1968],
Z = [[_1966]] ;
X = 1,
Y = [_3214, _3220|_3222],
Z = [[_3220], [_3214]],
dif(_3220, _3214) ;
X = 1,
Y = [_3560, _3566, _3572|_3574],
Z = [[_3572], [_3566], [_3560]],
dif(_3572, _3560),
dif(_3572, _3566),
dif(_3566, _3560) .
X = 0,
Z = [[]].

I leave it as an exercise to figure out if this program is now too general, too specific or both, and to either add or remove the necessary constraints to obtain only the desired answers.

The main point I wanted to show is that sticking to pure predicates helps you to obtain much more general programs. Using !/0 and (\+)/1 doesn't help with that. To avoid backtracking in specific cases while retaining the predicate's generality, use for example the new predicate if_/3.

Answer 2

not/1 is a predicate with one parameter: the goal (in your example member(R,Seen)).

It works according to negation as finite failure principle. It means that not(P) succeeds, given Prolog finds no way to satisfy P. In other words, if you would query Prolog for P directly, it would return false. If Prolog however gets into a infinite loop with P, it will also loop forever in not(P).

If on the other hand P succeeds (with unification or not), not(P) will fail.

Since it only succeeds if P is false, no unification will be done in not. In case P succeeds, not(P) fails and any unifications done are thus undone.

So not(member(R,Seen)) checks whether R is not a member of Seen. In case Seen is a variable, not(member(R,Seen)) will fail. Given R is a variable, not(member(R,Seen)) will succeed given Seen is not an empty list.

The cut ! on the other hand has nothing to do with not/1. In your example it simply means that if not(member(R,Seen) succeds, the cut will be executed, and thus the redo on the last chooseAll/1 will not be done in that case.

So how does the chooseAll/4 predicate works? It is called with Seen as an empty list. In the first clause, we first call choose(N,L,R) which generates a combination of numbers into a list R. We want to prevent that the same list is generated again and again, and thus next use a not(member(R,Seen)) call to check whether R is already in Seen. For the first result, this is not the case, so we cut ! to prevent the system from backtracking and selecting the last clause and next we call chooseAll recursively but with R added to the Seen list.

In the recursive call, we ask again choose/3 to generate a combination R and add it to the seen list. But now it will generate the same result as the first time: choose/3 will for each call create answers in the same order. So that means Prolog will backtrack over not(member(R,Seen)) and ask choose/3 to generate the next combination. That combination will not be part of Seen, so not(member(R,Seen)) will succeed and as a result we will again cut and make a recursive call with R added to Seen.

This will keep going on until choose/3 is complete exhausted and fails to come up with a combination R that is not yet part of Seen. In that case, Prolog will backtrack over the chooseAll/4 predicate and thus execute the last one, which unifies the result Res with the Seen list.

This is however an inefficient approach: for each answer we generate, we will call the predicate again until it generates a new answer. Therefore an ISO predicate the findall/3 predicate. It will put all the results of a predicate in a list (and not in a reverse order). We can use it like:

chooseAll(N,L,Res) :-
    findall(R,choose(N,L,R),Res).

Note: as the documentation on not/1 specifies:

True if Goal cannot be proven. Retained for compatibility only. New code should use \+/1.

So you better use \+ member(R,Seen) since it is more mnemonic.