8 The Cut (!)
The cut (called !) is a special goal that is used to prune backtracking options. Like the %true goal, the cut goal too succeeds, when accosted by the Racklog subgoaling engine. However, when a further subgoal down the line fails, and time comes to retry the cut goal, Racklog will refuse to try alternate clauses for the predicate in whose definition the cut occurs. In other words, the cut causes Racklog to commit to all the decisions made from the time that the predicate was selected to match a subgoal till the time the cut was satisfied.
For example, consider again the %factorial predicate, as defined in %is:
(define %factorial (%rel (x y x1 y1) [(0 1)] [(x y) (%is x1 (- x 1)) (%factorial x1 y1) (%is y (* y1 x))]))
But what if we asked for (%more) for either query? Backtracking will try the second clause of %factorial, and sure enough the clause-head unifies, producing binding [x . 0]. We now get three subgoals. Solving the first, we get [x1 . -1], and then we have to solve (%factorial -1 y1). It is easy to see there is no end to this, as we fruitlessly try to get the factorials of numbers that get more and more negative.
If we placed a cut at the first clause:
the attempt to find more solutions for (%factorial 0 1) is nipped in the bud.
Calling %factorial with a negative number would still cause an infinite loop. To take care of that problem as well, we use another cut:
(define %factorial (%rel (x y x1 y1) [(0 1) !] [(x y) (%< x 0) ! %fail] [(x y) (%is x1 (- x 1)) (%factorial x1 y1) (%is y (* y1 x))]))
Using raw cuts as above can get very confusing. For this reason, it is advisable to use it hidden away in well-understood abstractions. Two such common abstractions are the conditional and negation.
An “if ... then ... else ...” predicate can be defined as follows
(define %if-then-else (%rel (p q r) [(p q r) p ! q] [(p q r) r]))
(Note that for the first time we have predicate arguments that are themselves goals.)
Consider the goal
We first unify G0 with the first clause-head, giving [p . Gbool], [q . Gthen], [r . Gelse]. Gbool can now either succeed or fail.
Case 1: If Gbool fails, backtracking will cause the G0 to unify with the second clause-head. r is bound to Gelse, and so Gelse is tried, as expected.
Case 2: If Gbool succeeds, the cut commits to this
clause of the %if-then-else. We now try Gthen. If
Gthen should now fail —
Thus, g’s negation is deemed a failure if g succeeds, and a success if g fails. This is of course confusing goal failure with falsity. In some cases, this view of negation is actually helpful.