Commit

Assume we want to make Social Security payments. That is, pay(X,Y) means ``pay the sum X to Y''. Assume that we also have this code fragment.

 
pay(X,Y):-

		       british(X),

		       entitled(X,Details,Y).

pay(X,Y):-

		       european(X),

		       entitled(X,Details,Y).

Consequently, if we have successfully checked that a person is British and, for some reason, the subgoal entitled(X,Details,Y) fails (or some later computation forces backtracking back to redo the call to pay/2 that we are considering) then there may be no point in

• checking if they are ``european'' (assuming that there are no regulations under which British people can qualify for payment as being European when they fail to qualify as British citizens).
• checking to see if there is more than one entry for the person in some database accessed by british/1.

The truth is, of course, that we may want these two consequences whether or not entitled/3 fails.

If this is so, then we insert a cut as shown below and highlighted by a .

 
pay(X,Y):-

		       british(X),

			 ,

		       entitled(X,Details,Y).

pay(X,Y):-

		       european(X),

			 ,

		       entitled(X,Details,Y).
 [-5pt]

• On backtracking through the list of subgoals: a cut can be thought of as indicating that all attempts to redo a subgoal to the left of the cut results in the subgoal immediately failing. We sometimes say that any unifications taking place prior to the cut have been frozen and cannot be remade.
• On backtracking into the predicate once the call had exited: if one of the clauses defining the predicate had previously contained a cut that had been executed then no other clauses for that predicate may be used to resatisfy the goal being redone. We sometimes say that, once a cut is executed, later clauses have been chopped out of the search space.

Note that, with the cut in the position it is above, it is still possible that entitled/3 could be resatisfied. We have to guarantee that we have made entitled/3 determinate before we can guarantee that pay/2 is determinate. We have to do some more on this issue.

Also note that the effect of cut ( !/0) prunes the search space only until the parent goal of the cut fails. If we leave the Fail port of pay/2 and some previous goal leads to another call to pay/2 then the cut ( !/0) has no effect until it is executed.

We also have to remember that cut ( !/0) has two distinct effects: backtracking cannot redo any subgoals to the left of the cut and clauses in the program database for the same predicate that are textually after the current clause are unreachable. See figure 9.1 for a graphic representation of these effects on a rather artificial program.

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

b(1).

b(4).

c(X):- 		 d(X),!,e(X).

c(X):- 		f(X).

d(X):- 		 g(X).

d(X):- 		 h(X).

e(3).

f(4).

g(2).

h(1).

  
Figure 9.1: The Effect of cut on the AND/OR Tree