The cut is sometimes mistakenly thought of as stopping all backtracking in the rule it appears.
The following example is designed to illustrate which backtracking can happen around a cut.
% Example 13 - The Cut With More Backtracking
% main meal
homemade(pizza).
homemade(soup).
homemade(fish).
% dessert
ripe(apple).
ripe(orange).
ripe(banana).
% meal has tasty dish and ripe fruit
meal(Main, Fruit) :- homemade(Main), !, ripe(Fruit).
The program establishes some facts and relations about what makes a nice meal. A meal consists of a homemade main dish, and fruit that is ripe. Pizza, soup and fish are homemade dishes. The apple, orange and banana are ripe.
We've placed a cut in the body of the rule defining a meal to explore its effect on backtracking.
Most General Query
A query where every parameter is a fresh unbound variable is called a most general query. Such queries ask for all possible solutions, and are a good way to test the generality of our prolog definitions.
Let's issue the most general query for meal/2.
?- meal(Main, Fruit).
Fruit = apple,
Main = pizza
Fruit = orange,
Main = pizza
Fruit = banana,
Main = pizza
Prolog has found three combinations that make a nice meal, pizza and apple, pizza and orange, pizza and banana. None of these has soup or fish as a main meal.
Clearly the cut had an effect on limiting the combinations to these three out of a possible nine. Let's find out how.
Backtracking and Not Backtracking
To find solutions for the query meal(Main,Fruit) prolog uses its definition homemade(Main),!,ripe(Fruit).
Working left to right, the first goal is homemade(Main). This is easy enough to resolve as the database has several facts for homemade dishes. The first is homemade(pizza), so Main=pizza is a candidate solution.
Having found one potential solution for homemade(Main), prolog then moves right along the definition homemade(Main),!,ripe(Fruit). The next part is the cut. As we know, this always succeeds but has the side-effect of telling prolog to commit to any solutions found up to this point in the rule, and stop any backtracking back across it. That means prolog commits to Main=pizza.
Moving right again, prolog has to find solutions to ripe(Fruit). This is also straightforward because the database lists facts about ripe fruit. Prolog's answer above returns all three options for fruit. This shows that backtracking is enabled for ripe(Fruit). This is permitted because it takes place entirely to the right of the cut. That is, to find different solutions for ripe(Fruit), prolog does not need to backtrack across the cut.
The following search tree illustrates which backtracking is allowed, and which is prevented by the cut.
Key Points
- The most general query has all parameters as unbound variables.
- Most general queries test the generality of a prolog definition.
- The cut does not prevent backtracking in a rule if it is entirely to the right of it.