Building a Family Tree Solver in Prolog

Analogy categoryAnalogies

Family trees are a classic first project in Prolog because they demonstrate the whole workflow end to end: encode raw facts (who is whose parent, everyone's gender), derive rules that describe higher-level relationships (sibling, grandparent, ancestor) purely in terms of those facts, and then query the resulting knowledge base with variables to get every matching answer. The exercise also surfaces real subtleties — recursive relationships like ancestor/2 need a base case and a recursive case, and careless rules can double-count relationships or fail to terminate on cyclic or malformed data.

🏏

Cricket analogy: Building the family tree bottom-up from raw parent facts is like building a player's career stats from raw ball-by-ball data rather than starting from a pre-computed summary — every higher-level stat like 'strike rate' is derived, not stored directly.

Modeling Facts: Parents, Gender, and Marriage

The foundation of the solver is a small set of ground facts: parent(tom, bob)., male(tom)., female(pam)., and optionally married(tom, pam). Choosing parent/2 as the base relation (rather than separate father/2 and mother/2 facts) keeps the knowledge base minimal — gender is then a separate, orthogonal fact used only when a rule specifically needs to distinguish 'father' from 'mother', or 'son' from 'daughter'. Keeping raw facts minimal and deriving everything else through rules avoids the classic beginner mistake of hardcoding facts like grandparent(tom, jim). directly, which duplicates information already implied by two parent/2 facts and risks becoming inconsistent if the underlying data changes.

🏏

Cricket analogy: Keeping parent/2 as the single base fact and deriving father/2 via a rule is like storing raw ball-by-ball data once and computing 'boundaries hit' on demand, rather than maintaining a separately updated boundary counter that could drift from the raw data.

Deriving Rules: Siblings, Grandparents, Ancestors

With parent/2 as the base, sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y. captures shared-parent relationships, though it will count half-siblings unless you additionally check both parents match. grandparent(X, Y) :- parent(X, Z), parent(Z, Y). is a straightforward two-hop composition. The genuinely recursive case is ancestor(X, Y) :- parent(X, Y). combined with ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y)., which needs both a base case (direct parent) and a recursive case (parent of an ancestor) — omitting the base case, or writing the recursive call before establishing termination, is the most common beginner bug in this exercise.

🏏

Cricket analogy: The X \= Y check in sibling/2 is like a fielding restriction rule explicitly excluding the wicketkeeper from being counted as a slip fielder, preventing the same person from satisfying both roles in a way that would produce a nonsensical result.

prolog

% Base facts
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).
male(tom).
male(bob).
male(jim).
female(liz).
female(ann).
female(pat).

% Derived gender-specific rules
father(F, C) :- parent(F, C), male(F).
mother(M, C) :- parent(M, C), female(M).

% Sibling: share a parent, are not the same person
sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y.

% Grandparent: two parent/2 hops
grandparent(X, Y) :- parent(X, Z), parent(Z, Y).

% Ancestor: base case + recursive case
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

?- ancestor(tom, jim).
true.

?- findall(X, sibling(ann, X), Sibs).
Sibs = [pat].

Querying and Handling Edge Cases

Once the rules are in place, queries like ?- ancestor(tom, X). enumerate every descendant of tom via backtracking, and ?- findall(X, sibling(alice, X), Siblings). collects all of Alice's siblings into a list in one call rather than manually iterating solutions. Two edge cases deserve special attention: cyclic or inconsistent data (e.g., accidentally asserting parent(bob, tom). when tom is already bob's ancestor) can cause ancestor/2 to loop infinitely on some query patterns since Prolog's default resolution has no cycle detection, and half-sibling logic needs an explicit choice about whether sharing one parent or requiring both parents counts as 'sibling', which should be documented since real family trees frequently include half-siblings, step-parents, and adoptive relationships that a naive two-fact model doesn't capture well.

🏏

Cricket analogy: findall/3 collecting every sibling in one call is like a scorecard aggregator pulling every boundary hit in an innings into a single list in one pass, rather than a scorer manually noting each four and six as separate individual entries.

Prolog's default SLD-resolution does not detect cycles — if your fact base ever accidentally creates a parent cycle, recursive predicates like ancestor/2 can loop forever on certain queries. Validate input data or add cycle-guarding logic (e.g., tracking visited nodes) if the data source isn't trusted to be acyclic.

Model the minimal base relation (parent/2, male/1, female/1) and derive everything else — sibling, grandparent, ancestor — as rules.
sibling(X,Y) :- parent(P,X), parent(P,Y), X \= Y. needs the inequality check to avoid trivially matching a person with themself.
grandparent/2 is a direct two-hop composition of parent/2; ancestor/2 needs a base case plus a recursive case to handle arbitrary depth.
findall/3 collects all solutions to a goal into a list in one call, useful for gathering every sibling or descendant.
Prolog's default resolution has no cycle detection — accidental parent cycles can make recursive predicates loop forever.
Decide and document how edge cases like half-siblings, step-parents, or adoption are represented, since a naive two-fact model doesn't capture them automatically.