Used carefully, the cut can improve the efficiency of a prolog program.
We'll explore this with a simple example of a property that relates the temperature of water to its state.
% Example 14 - The Cut For Efficiency
% water/2 relates temperature to state
water(Temp, solid) :- Temp =< 0.
water(Temp, liquid) :- Temp > 0, Temp < 100.
water(Temp, gas) :- Temp >= 100.
% h2o/2 uses the cut to be more efficient
h2o(Temp, solid) :- Temp =< 0, !.
h2o(Temp, liquid) :- Temp > 0, Temp < 100, !.
h2o(Temp, gas) :- Temp >= 100.
The property water(Temp,solid) is true if Temp is less than or equal to 0. The property water(Temp,liquid) is true if Temp is more than 0, and also less than 100. Finally, water(Temp,gas) is true if Temp is more than or equal to 100.
These three rules simply relate the temperature of water in degrees centigrade to its states. Water at or below 0°C is solid ice, between 0°C and 100°C is liquid, and at or above 100°C it is a gas, steam.
The numerical comparison operators =<, <, >, and >=, are just like most other programming languages. Notice that prolog uses =<, and not <= which looks too much like a logical implication arrow.
Inefficient Solution Search
Let's start with a simple query “is water at -10°C solid?”
?- water(-10, solid).
true
false
Prolog reports true, confirming that water at -10°C is indeed solid ice. Perhaps surprisingly, prolog asks to search for other answers. Given the go-ahead, prolog returns false, indicating no other answers.
Let's try another query, this time with a variable, and ask “what is the state of water at 50°C?”
?- water(50, X).
X = liquid
false
Prolog confirms water at 50°C is a liquid. But again, prolog asks to find additional answers. Given the go-ahead, prolog fails to find additional solutions, reporting false. To be clear, prolog isn't telling us X=liquid is false, it is telling us that X=liquid is a valid solution, and that other attempts to satisfy water(50,X) failed.
Why is prolog trying to find additional solutions after it has found one? It is because there are three rules for water and prolog must try each one just in case another one satisfies the query. Prolog doesn't know the additional rules for water won't be satisfied until it tries them.
Because we know water can only be in one state (solid, liquid or gas) we can say that prolog's search for additional solutions after finding one answer is inefficient. To be clear, prolog doesn't know water can only be in one state, so it is doing the right thing testing all of the three rules.
In our small example, there is no real harm from this inefficiency. In more complex projects, it is possible that testing the body of such rules is computationally expensive, and should be avoided where possible.
Efficient Search With The Cut
When one of the water rules is satisfied, we don't want prolog to try any others. This is a natural job for the cut. Remember, the cut commits prolog to the solution is has found at that point in the current rule, and prevents further backtracking across it. That's what we want - for prolog to commit to the water state it has found and not backtrack to check if it is in another state too.
The following are updated rules for a new h2o property, named after the chemical name for water, H2O.
% h2o/2 uses the cut to be more efficient
h2o(Temp, solid) :- Temp =< 0, !.
h2o(Temp, liquid) :- Temp > 0, Temp < 100, !.
h2o(Temp, gas) :- Temp >= 100.
A cut has been placed at the end of the rules. If prolog reaches a cut, it means the body of the rule has been satisfied (the state of the water has been confirmed) and no further backtracking is needed.
Actually, the last rule doesn't have a cut at the end. There is no harm in adding one, but it isn't needed. This is because prolog works through these rules in order, and there are no more rules for h20 to try even if backtracking were enabled.
Let's test this new h2o with the first query again.
?- h2o(-10, solid).
true
This time prolog confirms true and terminates immediately. Let's try the second query.
?- h2o(50, X).
X = liquid
Again, prolog finds one answer and terminates immediately.
Green Cut, Red Cut
The definitions of water and h2o lead to exactly the same answers to any given query. We say the two programs are logically equivalent, that they have the same logical meaning. The only difference is that h2o/2 is more efficient because it avoids unnecessary backtracking.
A cut which doesn't change the logical meaning of a program is called a green cut. In contrast, the cuts we saw earlier in happy/1 and meal/2 are red cuts because their presence or absence changes the logical meaning of the program.
If we are going to use cuts, we should try to make them green cuts wherever possible.
Mutually Exclusive Rules
Our water example is an illustration of a more general pattern where green cuts can easily be applied to improve efficiency.
The rules for water are mutually exclusive. At most, only one rule can be true for a given query. We've seen how adding a cut to the end of each mutually exclusive rule improves efficiency without changing the meaning of the definition.
The following shows how any property with mutually exclusive rules can have a green cut appended to the end of each rule.
% property with mutually exclusive rules
property(X,Y,Z) :- goal_1, goal_2, !.
property(X,Y,Z) :- goal_3, !.
property(X,Y,Z) :- goal_4, goal_5, goal_6.
As we've discussed, the final rule doesn't need a cut.
Key Points
- A cut at the end of a rule causes prolog to commit to any solution found up to that point, and prevents searching for more solutions.
- Two programs are logically equivalent, or have the same logical meaning, if they give the same answers to any given query.
- A green cut is a safe use of the cut because its presence or absence does not change logical meaning.
- A property with mutually exclusive rules can easily benefit from green cuts applied to the end of each rule. The final rule doesn't need a cut as there are no further rules to try even if backtracking were enabled.