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).

Nitpick: you are new to Prolog programming, not "novel" to it. Prolog may be "novel" to you but never the other way around. :) — Daniel Lyons
choose (0,_,[]) :- !. is invalid syntax. there mustn't be a space between a predicate name and the opening parenthesis following it. — Will Ness

Willem Van Onsem Willem Van Onsem · Accepted Answer · 2017-08-04T19:06:50

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.

Using Cut and Not in Prolog Programming

2 Answers

Probably not.