Using the Cut to Increase Efficiency

Question

If I have the following knowledge base, how do I add a cut to the parent_of term so that if an X is already determined to be a father, prolog won't attempt to "check" if X is also a mother?

father_of(max,john).
father_of(max,james).
father_of(max,gabe).
mother_of(june,john).
mother_of(june,james).

parent_of(X,Y) :- father_of(X,Y).
parent_of(X,Y) :- mother_of(X,Y).

For example, I want:

parent_of(max,Y) to be: Y=john, Y=james, Y=gabe

parent_of(june,Y) to be: Y=john, Y=james

For the first one, I don't want prolog to even attempt to check if max is a mother_of since it was already determined that he is a father_of.

I've already tried so many combinations including:

parent_of(X,Y) :- father_of(X,Y),!.  <-- fixes an X and Y and thus will list only Y=john
parent_of(X,Y) :- !,father_of(X,Y). <-- works for parent_of(max,Y) but not parent_of(jane)

Is this even possible?

Answer 1

Doing such optimizations is extremely tricky. And Prolog is quite performing in such matters without any optimizations.

But as a general rule: You cannot simply set the cut into the program, you need to perform all kinds of tests in advance. I suspect that those tests are easily more expensive than the overhead you intend to remove. Here is an attempt. Honestly, I have not a very good feeling, because you should rather learn pure Prolog first.

So we assume that there is no solution to: ?- father_of(P,_), mother_of(P,_).

parent_of(F, C) :-
   (  atom(F), \+ \+ father_of(F, _) -> !
   ;  true
   ),
   father_of(F, C).
parent_of(M, C) :-
   mother_of(M, C).

Is this really better? Maybe, and maybe not.

But in any case, you have already understood one important point: clever optimizations require extensive testing. I believe above is correct, but I am not even sure that this will be faster. After all, there are now two lookups for father_of/2 in place of one for father_of/2 and one for mother_of/2. The naive version might be readily faster...