Prolog Use of Cuts

Question

I am re-writing the following function in Prolog:

V1:

f(X,Y):- X < 2, Y is X+1.
f(X,3):- 2 =< X, X < 5.
f(X,Y):- 5 =< X, Y is 8-X.

As V2:

f(X,Y) :-
    X < 2,
    Y is X + 1. 
f(X,Y) :-
    X >= 2,
    X < 5,
    Y is 3.
f(X,Y) :-
    X >= 5,
    Y is 8-X.

I then wanted to experiment with cuts. For green cuts (V3):

f(X,Y) :-
    X < 2, !,
    Y is X + 1.
f(X,Y) :-
    X >= 2,
    X < 5, !,
    Y is 3.
f(X,Y) :-
    X >= 5,
    Y is 8-X.

For red cuts (V4):

f(X,Y) :-
    X < 2, !,
    Y is X + 1.
f(X,Y) :-
    X < 5, !,
    Y is 3.
f(X,Y) :-
    Y is 8-X.

However, I don't understand their advantage, as deleting the cuts would allow the same behaviour of the code... Any help?

Answer 1

As you noted the first version shows green cuts and the second red cuts. It is not necessary that you will feel the difference between these two versions.

a) one reason can be efficiency, but for toy codes with fast machines you hardly notice it.

b) shuffling the rules should not change code's behavior in case of green cuts, and that's true for the first code. But in the second code, if you put the second clause before the first one than the behavior changes: f(0,3) is true, but initially it was false. Therefore you would feel difference if you shuffle the rules.

Advantage of shuffling is that you don't care about order but content - that's one of the points declarative programing.

Answer 2

All your versions V1..V4 are observationally equivalent, so you got some reasoning right. Still, there are differences.

Avoiding superfluous choice points

In many implementations, V1 and V2 might be particularly less efficient, for, internally, they "leave open a choice point". This is so because such Prologs do not look any further to the other rules. So each goal f(1,X) consumes a bit of memory that can be freed only on backtracking (or using !). Here is a simple way to try this out yourself:

loop(Goal) :-
   Goal,
   loop(Goal).

Here is what I get in SWI:

?- time(loop(f1(1,2))).
% 5,991,554 inferences, 81.282 CPU in 81.443 seconds (100% CPU, 73713 Lips)
ERROR: Out of local stack
?- time(loop(f2(1,2))).
% 5,991,553 inferences, 85.032 CPU in 85.212 seconds (100% CPU, 70462 Lips)
ERROR: Out of local stack

Whereas V3 and V4 seem to run indefinitely - at least much longer than 85s. Experiments such as this one are funny for very tiny programs but are not very practical for bigger ones. Fortunately, there is a simple way to tell in many Prologs whether or not a query is executed determinately. To see if your system does this, enter:

?- X = 1.
   X = 1.

For your variations:

?- f1(1,2).
   true
;               % <== Prolog asked for another answer
   false.       % <== only to conclude that there is none.
?- f2(1,2).
   true
;  false.       % same again
?- f3(1,2).
   true.         % <== Prolog knows there will be no further answer
?- f4(1,2).
   true.

Avoiding recalculations - making cuts red

While V3 avoids superfluous choice points, V4 now even avoids superfluous calculations. So it should be the most efficient. But it comes at the price of fixing the order of the clauses.

---

However, V3 was only possible, because two necessary conditions for green cuts coincided:

1. Non-overlapping conditions. That should be obvious to you.

2. Safe testing of instantiations. This is far from obvious. Please note that the goal X < 2 has an implicit test for a correct instantiation attached! It produces an instantiation error should X be an uninstantiated variable. It is because of this very test that the cut in V3 happens to be a green cut. Without that testing, it would be a red cut.

Note also that V1 and V2 would not be equivalent, if the second rule would be alone! For the goal f(X,5). would fail in V1 but it would produce an error in V2.