3.3 Cut

One very important, and very tricky, predicate is the ’cut’, written as the exclamation mark !. This is quite dangerous in inexperienced hands (such as yours!). It is an instruction to Prolog not to back-track looking for other solutions. Here is are some examples:

3.3.1 Examples

Negation as failure In dealing with data-base Prolog, we discovered that the correct definition of brother/2 and sister/2 require a test for inequality:

We know how to check that two terms are the same (by unification, using =/2), but how do we check that they are different? In principle by checking that they do NOT unify. In fact, Prolog has a built-in predicate \+/1 which allows this to be done:¹⁰

So different/2 could be programmed as:

The interesting thing from the present perspective is how \+/1 itself is programmed. The standard definition is the following two clauses:

These clauses MUST occur in this order, if the definition is to work. When \+ term is called, X is instantiated to term, and the first call in the body of the first clause of \+/1 tests to see if term is true. If it is known to the Prolog data-base, this call will succeed and control will pass to !/0 (’cut’). Cut always succeeds, so control passes to the built-in predicate fail/0. fail/0 always fails. (Surprise, surprise.)

Normally, when a goal fails, Prolog backtracks to see if there are any alternative solutions. Here, to see if term has any more solutions. It will then repeat the procedure until all the possibilities have been exhausted, at which point control would pass to the second clause of \+/1, which (since it has no conditions) would succeed.

However, the presence of the cut in the first clause prevents this behaviour. Instead, when the call to cut has succeeded, Prolog ‘cuts away’ all the information about alternative choices before the cut. Therefore, when fail/0 is encountered, there is nowhere else to go and the call \+ term fails straightaway.

The only situation in which the second clause will be reached is if term itself fails. This will be the case if term can’t be found in the Prolog database, or proved indirectly.

So, \+ a=b will fail if a=b; and will succeed if a=b fails.

Read carefully a Prolog textbook before using the cut yourself. (Using \+/1 is OK, provided you realise that when it fails its ’meaning’ is ’Prolog was unable to find a solution’. I.e. ’don’t know’, rather than false. This definition of negation is called ’negation by failure’.

delete_all/3 You may have noticed that the predicate delete_all/3 (which you defined in response to an exercise) does not work as anticipated if you force Prolog to give you more than one solution. Here is what happens:

Recall the definition of delete_all/3:

What happens is that, when the user requests a second solution, Prolog first of all goes back to the last procedure call made in providing the first solution (this was the second line of clause 2 of the definition, which succeeded by using clause 1 of the definition), and tries to see if there is an alternative way of satisfying the goal

There isn’t, so Prolog backtracks; having tried clause 2 unsuccessfully, it now tries clause 3. Clause 3 succeeds with Item = a and Head = a, as can be seen in the trace:

The problem arises because we have assumed that the second clause excludes the third - but it doesn’t. Now that we have access to the cut, we can impose this assumption on the program.

There are (at least) two ways to do this:

1. Indirectly by including an inequality test in clause 3:

   3. delete_all(Item, [HeadTail] , [Head|Result]):-          \+ Item = Head,          delete_all(Item, Tail, Result).     [trace]  ?- delete_all(a, [a,b,a], X).      Call: (7) delete_all(a, [a, b, a], _G294) ? creep      Call: (8) delete_all(a, [b, a], _G294) ? creep      Call: (9) a=b ? creep      Fail: (9) a=b ? creep      Call: (9) delete_all(a, [a], _G354) ? creep      Call: (10) delete_all(a, [], _G354) ? creep      Exit: (10) delete_all(a, [], []) ? creep      Exit: (9) delete_all(a, [a], []) ? creep      Exit: (8) delete_all(a, [b, a], [b]) ? creep      Exit: (7) delete_all(a, [a, b, a], [b]) ? creep     X = [b] ;      Redo: (10) delete_all(a, [], _G354) ? creep      Fail: (10) delete_all(a, [], _G354) ? creep      Redo: (9) delete_all(a, [a], _G354) ? creep      Call: (10) a=a ? creep      Exit: (10) a=a ? creep      Fail: (9) delete_all(a, [a], _G354) ? creep      Fail: (8) delete_all(a, [b, a], _G294) ? creep      Redo: (7) delete_all(a, [a, b, a], _G294) ? creep      Call: (8) a=a ? creep      Exit: (8) a=a ? creep      Fail: (7) delete_all(a, [a, b, a], _G294) ? creep     No

2. Use the cut to prevent backtracking. We insert a cut after the head of clause 2

   delete_all(_, [], []).     delete_all(Item, [Item|Tail] , Result):-        !,        delete_all(Item, Tail, Result).     delete_all(Item, [Head|Tail] , [Head|Result]):-    delete_all(Item, Tail, Result).

   Once execution of the program has passed the point at which the cut occurs, it cannot subsequently backtrack beyond this point. This means that once the head of clause 2 has unified with a goal, there is no longer any possibility of resorting to clause 3, as the following trace shows.

   [trace]  ?- delete_all(a, [a,b,a], X).      Call: (7) delete_all(a, [a, b, a], _G294) ? creep      Call: (8) delete_all(a, [b, a], _G294) ? creep      Call: (9) delete_all(a, [a], _G354) ? creep      Call: (10) delete_all(a, [], _G354) ? creep      Exit: (10) delete_all(a, [], []) ? creep      Exit: (9) delete_all(a, [a], []) ? creep      Exit: (8) delete_all(a, [b, a], [b]) ? creep      Exit: (7) delete_all(a, [a, b, a], [b]) ? creep     X = [b] ;      Redo: (10) delete_all(a, [], _G354) ? creep      Fail: (10) delete_all(a, [], _G354) ? creep      Fail: (9) delete_all(a, [a], _G354) ? creep      Fail: (8) delete_all(a, [b, a], _G294) ? creep      Fail: (7) delete_all(a, [a, b, a], _G294) ? creep     No

3.3.2 Exercises: memberchk/2