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.
