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 Schelog
subgoaling engine. However, when a further subgoal down the
line fails, and time comes to retry the cut goal, Schelog
will refuse to try alternate clauses for the predicate in
whose definition the cut occurs. In other words, the cut
causes Schelog 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
predicate, as defined in sec 3.2:
(define %factorial (%rel (x y x1 y1) [(0 1)] [(x y) (%is x1 (- x 1)) (%factorial x1 y1) (%is y (* y1 x))]))
(%which () (%factorial 0 1)) => ()true (%which (n) (%factorial 0 n)) => ([n 1])
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
We now get three subgoals. Solving the first, we get
‑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
If we placed a cut at the first clause:
... [(0 1) !] ...
the attempt to find more solutions for
1) is nipped in the bud.
%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
G0 = (%if-then-else Gbool Gthen Gelse)
We first unify
G0 with the first clause-head,
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
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 should now fail — or even if we simply retry for
more solutions — we are guaranteed that the second
clause-head will not be tried. If it were not for the cut,
G0 would attempt to unify with the second clause-head, which will
of course succeed, and
Gelse will be tried.
Another common abstraction using the cut is negation.
The negation of goal
G is defined as
(%not G), where
%not is defined as follows:
(define %not (%rel () [(g) g ! %fail] [(g) %true]))
g’s negation is deemed a failure if
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.