The following Prolog program determines the insurance premium. The insurance premium depends on the vehicle's horsepower and the driver's age.
calculateCarInsurance(PS, Insurance) :- PS < 60, Insurance = 100.
calculateCarInsurance(PS, Insurance) :- PS >= 60, PS < 100, Insurance = 200.
calculateCarInsurance(PS, Insurance) :- PS >= 100, Insurance = 300.
isInRiskyGroup(Age) :- Age < 25.
calculateCarInsurance(PS, Age, _) :- Age < 18 , fail.
calculateCarInsurance(PS, Age, Insurance) :-
Age >= 18,
isInRiskyGroup(Age),
calculateCarInsurance(PS, I2),
Insurance is I2 * 2.
calculateCarInsurance(PS, Age, Insurance) :-
not(isInRiskyGroup(Age)),
calculateCarInsurance(PS, Insurance).
Now, I need to: a) Optimize the program with Green Cuts, and b) Change Green to Red Cuts, by deleting unneeded predicates. The behavior of the program should be the same.
As I have no knowledge about cuts in Prolog, how would I approach this?
Let's start with the basics. The cut operator is ! and always succeeds. The cut cannot be backtracked past—it's like a one-way gate. Another way of looking at it is that it commits you to the decisions you've made so far.
Usages of the cut are grouped into several categories. A green cut is, by definition, a cut that does not change the runtime semantics of the program at all. A green cut is just a way for the programmer to tell Prolog that you already know you're out of solutions. If Prolog doesn't know there are no more solutions, it will ask you if you want another solution and then fail, every time. For instance, look at this implementation of min/3:
min1(X, Y, X) :- X < Y.
min1(X, Y, Y) :- Y <= X.
?- min1(3, 4, X).
X = 3 ;
false.
See how Prolog asked me if I wanted another solution, and then failed? That's evidence that there was an extra choice point on the stack. We can eliminate it with a cut:
min2(X, Y, X) :- X < Y, !.
min2(X, Y, Y) :- Y =< X.
Now when we ask Prolog about min2/3 we'll get just one answer:
?- min2(3, 4, X).
X = 3.
See, no prompt, just the one solution.
Now, what makes this a green cut as opposed to a red cut is that there is no real change of behavior or reasoning. It's just that Prolog has no way of knowing that X < Y and Y =< X are mutually exclusive—the green cut is our way of telling Prolog, once you've determined X is less than Y, there's no point in checking to see if Y is less than X. This removes the choice point from the stack, to get technical. This is sometimes an important optimization, since Prolog spends a lot of time backtracking and the time it spends trying impossible cases is wasted.
A red cut is a somewhat different animal. A red cut is any cut that does change the behavior in an extralogical fashion. To show you an example of a red cut, you might try to eliminate the second test from min/3 altogether:
min3(X, Y, X) :- X < Y, !.
min3(_, Y, Y).
You may do this thinking to yourself, "by the time we get to the second clause we know that X is not less than Y, so there's no need to check and see if Y is less than or equal to X." It seems reasonable at first blush and you see it appears to have the same behavior as min2/3, knowing there is one solution like before:
?- min3(3, 4, X).
X = 3.
?- min3(4, 3, X).
X = 3.
However, because we have eliminated some of the logic, we have opened ourselves up to subtle bugs involving backtracking. Looking at min/3 as a relationship between three entities, we can use min3/3 to produce falsehoods that min1/3 and min2/3 do not:
?- min1(3, 100, 100).
false.
?- min2(3, 100, 100).
false.
?- min3(3, 100, 100).
true.
100 is not the minimum of 3 and 100, but min3/3 will affirm anything with the same second two values, provided the third one is not a variable. In other words, we assumed in our use of the red cut in min3/3 that we would never show up with a value in the third position. We assumed we would use the third parameter as an "out" parameter.
Let's take this knowledge and have a look at your homework assignment. The first thing that jumps out at me is that there is this same kind of overlapping conditional logic in the first two rules:
calculateCarInsurance(PS,Insurance) :-
PS < 60, ...
calculateCarInsurance(PS,Insurance) :-
PS >= 60, ...
At the very least, we can add a green cut after PS < 60 to commit us there: if PS is less than 60, it really can't also be over 60, so a green cut there is absolutely harmless.
I would caution that one never wants to add red cuts. They are occasionally necessary when you need to screw around with Prolog's reasoning to make it work like you want. In this case, you could note that calculateCarInsurance may return more than one solution. You may not want this behavior, you may instead want to commit to the first one you get. In that case you could add a cut to the end of all the bodies of the calculateCarInsurance rules. Then you'd get a single solution no matter how many solutions Prolog can find. This changes the logical behavior of the program, but may be desirable depending on your requirements. This could also have the same negative side-effect of min3/3 though, if we wanted to verify an insurance result, calculateCarInsurance would probably affirm calculations it would never produce.
I hope that's enough to get you on the right track.