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?
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:Here is what I get in SWI:
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:
For your variations:
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:
Non-overlapping conditions. That should be obvious to you.
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 shouldX
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.