Right up front: This is not a homework exercise. I’m trying to learn Prolog and this is just a problem that happens to need solving and for which Prolog is a perfect fit.
I have a bunch of family relations which comprise my facts:
male/1
female/1
husband/2
wife/2
father/2
mother/2
grandfather/2
grandmother/2
son/2
daughter/2
brother/2
sister/2
uncle/2
aunt/2
nephew/2
niece/2
cousin/2
The data that I have are incomplete, many links of the family mesh are missing. My facts come from an external source, I can only supply the rules. For a given person, I might have male, brother and cousin, for another mother and wife. In the worst case, I barely know cousin, but have enough other facts to be able to infer who is, say, the uncle, therefore that the person might be that brother mentioned elsewhere, hence is male. And so forth.
There’s no way in which I can influence which facts there will be. That’s the whole point of the problem: If the facts were complete, I wouldn’t need to do this. I could do the guesswork by hand, but that’s what a computer is for, if I can find a way of expressing it. The goal is therefore to fill the missing links as good as possible, especially with regard to the ‘indirect’ relations around uncle, aunt, nephew, niece and especially cousin, which are notoriously incomplete.
I could write my rules naïvely like this:
male(Who) :-
brother(Who, _); father(Who, _); uncle(Who, _); …
brother(Who, Whose) :-
sibling(Who, Ofwhom), male(Who).
sibling(Who, Whose) :-
brother(Who, Whose) ; brother(Whose, Who).
motherly_cousin(Cousin, Whose) :-
cousin(Cousin, Whose),
sibling(Mother, Uncle_or_Aunt),
parent(Uncle_or_Aunt, Cousin).
I am rather sure that I am trying to solve the problem in a fundamentally wrong way, as I see no way of breaking the circular reasoning. And without breaking the circles, any Prolog program that I’ll devise for this will degenerate into endless recursions.
So what could I do to break this tangle down into something that can be solved?
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:
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:
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!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.