Prolog/Cuts and Negation

Programming | Prolog | Cuts and Negation

This section explains the use of cuts to control backtracking, the way negation is used in Prolog and a useful combination of both.

The cut

Consider the following program.

a :- b.
b :- c.
c :- d.
b.

If you load this into Prolog and ask Prolog ?- a., Prolog will evaluate it by first searching for any rule that can make a true; it adds a to its list of goals to prove. The first rule states that a is true if b is true, so Prolog adds the goal b to its list. It finds a rule for c and now needs to prove d, which fails. Prolog now removes the goal d from its list, because it couldn't prove it, and tries to prove c in a different way. This is known as backtracking. Prolog can't prove c either, backtracks again and tries b. It can prove this, using the last line of the program and Prolog terminates.

Understanding how Prolog evaluates your query is essential in Prolog programming. To control the way Prolog evaluates your program, you can use the cut operator: !. the cut operator is an atom, and can be used in the following way:

a(X) :- b(X), c(X), !, d(X).

If Prolog finds a cut in a rule, it will not backtrack on the choices it has made. For instance, if it has chosen frank for the variable X and encounters a cut, Prolog will consider frank the only option for X, even if there are other possibilities in the database. This is illustrated by the following program

a(X, Y) :- b(X), !, c(Y).
b(1).
b(2).
b(3).

c(1).
c(2).
c(3).

If we ask Prolog ?- a(Q, R). it will first answer

?- a(Q, R).
Q = 1
R = 1 ;

And when we ask Prolog for more answers, using the ;-key:
Q = 1
R = 2 ;
Q = 1
R = 3 ;
No
.

As you can see Prolog considers 1 as the only option for Q, whereas it returns all alternatives for R. When Prolog starts out on the query it tries to prove a(Q, R), using the first line of the program. To prove this rule, it needs to first prove b(Q), it succeeds with Q = 1. Then Prolog encounters a cut and sets Q = 1 as the only option for Q. It continues with the last goal of the rule, c(R). It first finds R = 1. and completes its goal. When user presses ;, Prolog first checks for alternatives to the goal c(R). Remember, when Prolog encountered the cut it hadn't chosen an instantiation for R yet, so it can still look for alternatives for R. When it runs out of alternatives for R, Prolog can't look for alternatives for Q, and terminates.

To understand how the cut changes the meaning of a program, consider the following:

a(X) :- b(X), !, c(X).
b(1).
b(2).
b(3).

c(2).

Without the cut in the first line, Prolog would return Q = 2 to the query ?- a(Q). With the cut Prolog fails to find an answer. To prove the goal, it first proves b(Q) with Q = 1. It then encounters a cut, is committed to Q=1 and can't find a proof for c(1). If it could have searched for alternatives, it would have found that Q=2 makes both b(Q) and c(Q) true, but the cut doesn't allow that. However, if we ask Prolog a(2), it will return yes. Now, Prolog instantiates the X in the first line of the program with 2, because the user has specified it, and when Prolog reaches the cut X becomes committed to 2, allowing Prolog to prove c(2).

The cut also works across multiple rules. If a program has two rules for the goal a(X), and Prolog encounters a cut in the first rule, it is not only committed to the instantiations of the variables, but also to the first rule for a(X). Prolog will not consider the second rule. For instance, the following program:

a(X) :- b(X), !, c(X).
a(X) :- d(X).

b(1).
b(4).

c(3).

d(4).

will fail for the query ?- a(X).. Prolog could solve the query with the second rule, using X =4 and the last line of the program, but Prolog tries the first rule first and when it encounters the cut, it is forced to ignore all alternatives to a(Q). This time, the query ?- a(4) will fail too, because Prolog still reaches the cut. When it tries a(4) with the first rule, it succeeds in proving b(4) and reaches the cut. It then tries c(4), which fails, and Prolog has to terminate. If the lines b(4). and b(1). are removed from the program, Prolog fails on the first rule, before it encounters the cut, and is allowed to solve the query with the second rule.

Using Cuts

examples where cuts are necessary
if-then-else structures
advice on using cuts (red cuts & green cuts)

Negation

not(X) is the way to implement negation in Prolog; however not(X) does not mean that X is false, it means that X can't be proven true.

For example, with the database:

man('Adam').
woman('Eve').

asking not(man('Adam')). will return no.

Cut-Fail negation

Examples

not(Goal) :- call(Goal),!,fail.
not(Goal).

Exercises

previous: Putting it Together next: Reading and Writing code