CODEWITHSUNDEEP
prologprolog-cut
Charles Khunt
Charles Khunt

Reputation: 2505

Using the Cut to Increase Efficiency

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?

Upvotes: 3

Views: 317

Answers (2)

false
false

Reputation: 10102

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...

Upvotes: 1

twinterer
twinterer

Reputation: 2436

For this purpose, some Prolog systems offer a "soft cut" *->/2:

parent_of(X,Y) :- father_of(X,Y) *-> true ; mother_of(X,Y).

In general for If *-> Then ; Else, if the condition If succeeds, Then is executed, an on backtracking only alternative solutions for If and Then are returned. Only in the case that If has no solutions at all, Else is executed.

This requires you to know the mode, i.e., the calling pattern, of your predicate. In your case, if the mode of your predicate parent_of is parent_of(++,?), then adding a soft cut is fine (assuming that names are unique or appear only for one gender). In the case of parent_of(++,++), even a regular cut would be fine, though unnecessary unless you have duplicate facts in your database (symmetry breaking is one use case for cuts). However, if you also have to cater for parent_of(-,?), then a cut really cuts away solutions.

In general: only use cuts when you are sure that the branch(es) of the search tree that you cut away contain no solutions, or only symmetric solutions that you are not interested in.

Upvotes: 0

Related Questions