CODEWITHSUNDEEP
recursionprologpredicate
Anders
Anders

Reputation: 499

Checking implicit rule predicate in Prolog

I hope I've used an understandable title. What I want to achieve is prolog to determine a relation even though it isn't explicitly stated.

brother(anders, jason).
sister(anders, madonna).
siblings(X,Y) :- sister(X,Y).
siblings(X,Y) :- brother(X,Y).
siblings(X,Y) :- siblings(X,Z), siblings(Z,Y).

It's the sibling rule I'm struggling with. Clearly Jason is Anders brother, and Madonna is Anders sister. Jason and Madonna is therefor Anders' siblings. They are also siblings with each other even though this isn't explicitly stated. How do I make prolog determine this by checking the siblings of a sibling? It's my last rule that will cause a stack overflow \o/ which really isn't that much of a surprise. Is this achievable in a recursive fashion or do I need to write more rules like:

siblings(X,Y) :- sister(X,Z), brother(Z,Y).
siblings(X,Y) :- sister(X,Z), sister(Z,Y).
siblings(X,Y) :- brother(X,Z), sister(Z,Y).
siblings(X,Y) :- brother(X,Z), brother(Z,Y).

The above would not work if we had a very large family and even bigger gaps in our brother/sister facts, that could mean that I have to check if a person is sibling to my siblings sibling and so on.

It might not be a good real world example but I'm looking for the concept of handling these situation rather than a solution to a specific problem.

Upvotes: 1

Views: 437

Answers (2)

Will Ness
Will Ness

Reputation: 71070

that's transitive closure you want:

sibl(A,B):- brother(A,B) ; brother(B,A) ; sister(A,B) ; sister(B,A).

sibl_trans(A,B):- sibl(A,B).
sibl_trans(A,B):- sibl(A,C), sibl_trans(C,B).

Your definition is like

sibl_trans(A,B):- sibl(A,B).
sibl_trans(A,B):- sibl_trans(A,C), sibl_trans(C,B).

This is left recursion. Not good, with depth-first search of Prolog. Could work with iterative deepening.

This question comes up very frequently.

Upvotes: 1

Daniel Lyons
Daniel Lyons

Reputation: 22803

It might work automatically in a Prolog with tabling (YAP or XB) given the appropriate annotation, but most of us live within the limitations of standard-ish Prolog. Your additional rules are really just pushing food around on your plate. You can see you would need ever more of them to handle a situation like this:

brother(anders, brian).
brother(celeste, donal).
sister(brian, celeste).

If you want sibling(anders, X) to ever unify X with donal you're going to need a bigger boat.

Let's call this your recursive rule:

siblings(X,Y) :- siblings(X,Z), siblings(Z,Y).

This can't ever succeed, because in order to succeed, it must first succeed. The stack overflow isn't happening because you're calling siblings/2 recursively, it's happening because it calls it twice to fulfill it once. It spends two dollars to earn one. But you can break even by spending what you make, by replacing that rule with this:

siblings(X, Z) :- brother(X, Y), siblings(Y, Z).
siblings(X, Z) :- sister(X, Y),  siblings(Y, Z).

This is a capital improvement, but it isn't enough. This basically gets us directed siblinghood. Brian is Anders's brother, but Anders isn't Brian's brother. The problem is severe enough that we'll never acknowledge Anders and Donal's siblinghood. We can fix that by adding a few more rules:

siblings(X, Y) :- brother(X, Y) ; brother(Y, Z).
siblings(X, Y) :- sister(X, Y)  ; sister(Y, X).

These rules make brotherhood and sisterhood undirected. Now you get all the results you'd ever want:

?- siblings(anders,Y).
Y = brian ;
Y = anders ;
Y = celeste ;
Y = donal ;
Y = brian ;
Y = celeste ;
false.

Bet you can figure out how to eliminate the self-siblinghood problem. The other duplicates may turn out to be more troublesome. Give it a shot and let us know if you get stuck.

Upvotes: 2

Related Questions