5 Backtracking
5.1 Fail
The fail/1 predicate is provided by Prolog. When it is called, it causes the failure of the rule. And this will be for ever, nothing can change the statement of this predicate. You can ask you what is its utility. We can associate it to the Cut/1 predicate, described in the next subsection in this report.it allow us to include the negation in a rule.A typical use of fail is a negation of a predicate.We can resume the fail with this sheme :
goal(X) :- failure(X),!,fail.
goal(X).
failure(X) are the conditions that make goal(X) fail.5.2 Cut
Up to this point, we have worked with Prolog's backtracking. We have seen how to use the backtracking to write compact predicates. Sometimes it is desirable to selectively turn off backtracking. Prolog provides a predicate that performs this function. It is called the cut/1, represented by an exclamation point (!).The cut/1 effectively tells Prolog to freeze all the decisions made so far in this predicate. That is, if required to backtrack, it will automatically fail without trying other alternatives. We will first examine the effects of the cut/1 and then look at some practical reasons to use it . When the cut/1 is encountered, it re-routes backtracking. It short-circuits backtracking in the goals to its left on its level, and in the level above, which contained the cut/1. That is, both the parent goal and the goals of the particular rule being execut/1ed are affected by the cut/1. The effect is undone if a new route is taken into the parent goal.
We will write some simple predicates that illustrate the behavior of the cut/1, first adding some data to backtrack over.
data(pentiumIII).
data(athlon).
Here is the first test case. It has no cut/1 and will be used for comparison purposes.
compare_cut_1(X) :-
data(X).
compare_cut_1('last chip').
This is the control case, which exhibits the normal behavior.
?- compare_cut_1(X), write(X), nl, fail.
pentiumIII
athlon
last chip
no
Next, we put a cut/1 at the end of the first clause.
compare_cut_2(X) :-
data(X),
!.
compare_cut_2('last chip').
Note that it stops backtracking through both the data subgoal (left), and the compare_cut_2/1 parent (above).
?- compare_cut_2(X), write(X), nl, fail.
pentiumIII
no
Next we put a cut/1 in the middle of two subgoals.
compare_cut_3(X,Y) :-
data(X),
!,
data(Y).
compare_cut_3('last chip').
Note that the cut inhibits backtracking in the parent compare_cut_3/2 and in the goals to the left of (before) the cut (first data). The second data/1 to the right of (after) the cut is still free to backtrack.
?- compare_cut_3(X,Y), write(X-Y), nl, fail.
pentiumIII - pentiumIII
pentiumIII - athlon
no
Performance is the main reason to use the cut/1. This separates the logical purists from the pragmatists. Various arguments can also be made as to its effect on code readability and maintainability. It is often called the 'goto' of logic programming. You will most often use the cut/1 when you know that at a certain point in a given predicate, Prolog has either found the only answer, or if it hasn't, there is no answer. In this case you insert a cut/1 in the predicate at that point. Similarly, you will use it when you want to force a predicate to fail in a certain situation, and you don't want it to look any further. 5.3 Not
For logical puritey, it is always possible to rewrite the predicates without the cut/1. This is done with the built-in predicate not/1. Some claim this provides for clearer code, but often the explicit and liberal use of 'not' clutters up the code, rather than clarifying it. When using the cut/1, the order of the rules become important. Let's try to rewrite compare_cut_2/1 with the not/1 predicate.
not_2(X) :- X = pentiumIII.
not_2(X) :- not(X = pentiumIII).
You can now see the difference between not/1 and cut/1, but the code is here to simple to see really the difference of clarity.Try with compare_cut_3 :
not_3(X,Y) :- X = pentiumIII,data(Y).
not_3(X,Y) :- not(X = pentiumIII),not(Y).
Now, you can imaginate what will be the difference between the algorithms based on the cut/1 and those on the not/1. The result is the same, it's just a way of thinking.
it is interesting to note that not/1 is defined using the cut/1. It also uses call/1, another built-in predicate that calls a predicate.
not(X) :- call(X), !, fail.
not(X).