How to interpret this Prolog goal with a cut, and improve efficiency

Question

I have been reading through the answers and comments of my previous question and I have tried applying the given explanations on an example from Bratko (Prolog Programming for Artificial Intelligence, p. 130), but I am not sure I understand it completely. The example is described below:

I read the tree and the code as follows:

In the goal list C :- P, Q, R, !, S, T, U. Prolog will one by one try to instantiate the variables, as normal, to eventually get to true.. Let's say that a value is found for P and Q, and the first try on R fails, then Prolog can back track to the case where P and Q were found, and try another option for R if available. However, if R is found as well (leading to P, Q, R = true.), and ! succeeds as it always does, we throw away any choice points and there's nothing to back track to from that point on (not even C :- V.). What this means is that if no results can be found for S, the goal C :- P, Q, R, !, S, T, U. will fail immediately. But Prolog can still backtrack to A :- B, C, D. to find other values for B. If another match is found for B, C will be tried again anew. And so on.

Assuming that my interpretation is correct, if the goal C :- P, Q, R, !, S, T, U. succeeds or fails regardless of the value of B, how would you improve efficiency? My guess would be to re-write A :- B, C, D. as A :- B, !, C, D.

Is my interpretation correct? And what about my improvement in efficiency, given some a-priori information on C?

Carpet

Answer 1

Yes, your understanding is correct. To see it better, we can re-write the predicates as

a = (b & c & d)
c = (p & q & r) ~~>! (s & t & u) ; v

with & for &&:, and the rest of operators, from this answer (or if it isn't clear, see this as a pseudocode, with ~~>! passing no more than one solution through). When the cut is reached, c is committed, but a is still backtrackable.

If C in A :- B, C, D. succeeds or fails regardless of the value of B, you can also reorder the goals as

A :- C, B, D.

The cut in A :- B, !, C, D. is a red cut, it only lets B succeed once, but what if you're interested in its second result? Red cuts alter the meaning of a predicate.

Shippy

Thank you! I'm so glad I understand it now. I should try to make a better distinction in my mind when to think in trees and when not to. I didn't think about re-ordering to A :- C, B, D. because in my mind that would change the order of the tree which is not allowed and which would change the declarative meaning - but of course that is not the case and in the end we are only interested in the result of the query, and not the order. Thank you again to guide me so far! – Carpet

glad to be of help. :) – Shippy