Refactoring tangled, circular rules in Prolog

I'm a little ashamed of trying to say anything after @sharky's excellent post. But if I were approaching the problem I would make a few smaller changes and accept that Prolog is not completely logical. This is to say I would select @sharky's suggestion of avoiding mutual recursion altogether.

For one thing, gender in reality is an intrinsic rather than a derived fact. By this I merely mean that I don't derive my maleness from belonging to a father/uncle/brother relation with someone else.

If you put male(X) before sibling(X,Y) rather than after, it has no effect on the logical meaning of the program, but it will change the way the program is executed by Prolog in ways that matter practically. For instance if X is unbound, male(X) may generate (assuming you make the change I suggest) without having to re-enter brother/2 by a distant mutual recursion from sibling/2.

I would encourage you to separate facts from predicates, unless the facts are really base cases.

Unfortunately, Prolog isn't going to save you from having to design a coherent data model. You still need to worry about whether you're storing the right data in the right shape. You can provide the rich API you've come up with either way, it's just that right now you have the data kind of smeared all over. You can box yourself in with anything, it's just that in Prolog you tend to get partial results even when that has happened.

I feel like tabling might be of some help to you but since it only exists in fairly obscure implementations the benefit may be too limited. I've never used it myself so I don't know if it does indeed solve these problems or just mitigates the symptoms of mild problems. I suspect the latter simply because if it were both really helpful and solving an important intrinsic problem I'd expect it to have been ported to GNU and SWI (but perhaps I'm overly optimistic).

Generally, this is a tricky problem. Checks for this kind of recursion are possible (similarly for the occurs-check in unification), however most implementations omit them because (a) it is generally unclear which recursive paths to exclude; (b) it is too computationally expensive; or (c) there is usually a way for the programmer to circumvent the problem in the code.

There are a number of ways of dealing with this, some nastier than others. I will present a way which:

• Permits you to reasonably define your predicates naïvely;
• Deals with an incomplete set of facts;
• Is horribly inefficient;
• Does not recurse infinitely.

The way I will describe employs the use of a meta-interpreter. The standard interpreter in Prolog will not check if your code is executing the same clause over and over again. For example, there is a nasty case of mutual recursion between your definitions of brother/2 and sibling/2. While the definition you've provided for them appears to be fine, consider what happens to them when they are called with all parameters unbound:

brother(X, Y) ↝ sibling(X, Y) ↝ brother(X, Y) ↝ ... (ad infinitum/nauseum)

Instead, what we can do is define how these predicates should be executed knowing full well they may be infinitely recursive by directing their execution through a separate predicate, which I'll call meta/1. This predicate is the meta-interpreter, and will guide Prolog as to how it should execute the rules and facts you have provided in a way which prevents infinite recursion. Here is one possible definition (with comments inline):

meta(Goal) :-
    % defer to meta/2 with a clause reference accumulator 
    meta(Goal, []).

meta(true, _ClauseRefs) :- 
    % the body to execute is true (i.e., a fact); just succeed.
    !,
    true.

meta(meta(X), ClauseRefs) :-
    % the body to execute is a call to the meta interpreter. 
    % interpret the interior goal X, and NOT the interpreter itself.
    !,
    meta(X, ClauseRefs).

meta((G0, G1), ClauseRefs) :- 
    % interpret a conjunct: ,/2. G0 then G1:
    !,
    % interpret the first sub-goal G0
    meta(G0, ClauseRefs),
    % then interpret the second sub-goal G1
    meta(G1, ClauseRefs).

meta((G0 ; G1), ClauseRefs) :- 
    % interpret a disjunct: ;/2. One or the other:
    ( meta(G0, ClauseRefs) 
    ; meta(G1, ClauseRefs) 
    ),
    !.

meta(G0, ClauseRefs) :-
    % G0 is an executable goal: look up a clause to execute 
    clause(G0, Body, Ref),
    % check to see if this clause reference has already been tried 
    \+ memberchk(Ref, ClauseRefs),
    % continue executing the body of this previously unexecuted clause 
    meta(Body, [Ref|ClauseRefs]).

meta/1 and meta/2 are designed so that they execute goals provided to them in a way which ensures that every clause used in the branch of execution of the goal is explicitly not repeated. In order to use it in your case, consider the following:

brother_of(a, b).
brother_of(b, c).
brother_of(d, e).
brother_of(X, Y) :- meta((sibling_of(X, Y), male(X))).

male(a).
male(d).
male(b).
male(X) :- meta(brother_of(X, _)).

female(c).
female(e).
female(X) :- meta(sister_of(X, _)).

sister_of(X, Y) :- meta((sibling_of(X, Y), female(X))).

sibling_of(X, Y) :- meta(brother_of(X, Y)).
sibling_of(X, Y) :- meta(brother_of(Y, X)).
sibling_of(X, Y) :- meta(sister_of(X, Y)).
sibling_of(X, Y) :- meta(sister_of(Y, X)).

Notice how the body of any of the recursive clauses is wrapped in a call to meta/1, guiding Prolog to execute their definition using the meta-interpreter which will ensure that their execution (by interpretation) will not be recursive. For example, the goal:

?- sister_of(X,Y).
X = c,
Y = b ;
X = c,
Y = b ;
X = c,
Y = b ;
... 
X = e,
Y = d ;
false.

Note that it terminates after finding all bindings via all possible non-recursive execution paths, meaning there may be a lot of repetition (hence, the source of inefficiency). To find unique bindings, you could use setof/3 as follows:

?- setof(sister_of(X,Y), sister_of(X,Y), Set).
Set = [sister_of(c, b), sister_of(e, d)].

This is just one method which you might find useful, and is often a nice (albeit advanced) tool for Prolog programmers to be aware of. You don't need to stick to the inherent execution strategy.

For anyone thinking about simply using meta/1 and meta/2 in practice, there are some other things you should consider:

• Perhaps you might want or need to permit the same clause to be executed more than once when executing a (sub-)goal (e.g., if you need to execute the same clause but with different head bindings). As an example, think about how you'd implement ancestor/2 recursively using the meta-interpreter, which may need to execute the same clause (itself) several times over with different head bindings (i.e., path expansion). In this case, instead of simply tracking clause references, you could track clause references and their particular head bindings as Ref-Head items, and check to see if these have been executed before. This might be a whole lot extra information to cart around, and could be expensive!
• The definition of meta/1 and meta/2 above only deal with predicates such as facts (with the implicit true as their body); or predicates with bodies defined using any combination of conjunction (,/2) and disjunction (;/2). You can simply add more clauses to meta/2 to deal with other language constructs, such as implication (->/2), negation (\+/1), cut (!/0), etc. if you need to.
• Not all problems like this necessitate a meta-interpreter. For example, you might be able to get away with simply structuring your clauses carefully and check for modes (i.e., predicate bindings being ground/non-ground) before they are executed, however this can get tricky the more complex the program is.
• If you think about the problem hard enough, perhaps there's a way you could simply avoid using recursion altogether: i.e., don't use recursive definitions, but instead, use predicates with different names which aren't mutually recursive.

+1 for a nice twist on the usual "family example".

In addition to what others already said, consider using Constraint Handling Rules (CHR). They seem like a good fit for this problem, where a fixpoint needs to be computed from a set of facts and rules.

EDIT: As requested, a small example. I focus on an illustration surrounding brother_of/2. First, notice that brother_of/2 is clearly more specific than male/1, since we know that a brother is always male, but not vice versa. Informally, the first CHR rule thus says: When brother_of(X,_) holds, and male(X) holds, then drop the male(X) constraint, because it can always be deduced later. The second rule shows an example of deducing that brother(X, Y) holds. The third rule removes redundant brother_of/2 constraints.

The complete code, tested with SWI-Prolog:

:- use_module(library(chr)).

:- chr_constraint male/1, brother_of/2, child_parent/2.

brother_of(X, Y) \ male(X) <=> brother_of(X, Y).

male(X), child_parent(X, P), child_parent(Y, P) ==> X \== Y | brother_of(X, Y).

brother_of(X, Y) \ brother_of(X, Y) <=> true.

Example query and its result:

?- male(john), child_parent(john, mary), child_parent(susan, mary).
brother_of(john,susan)
child_parent(susan,mary)
child_parent(john,mary)
true ;
false.