How can I fix this circular predicate in Prolog?

Question

Why doesn't this work to define "married" in Prolog?

married(X,Y):-married(Y,X).

Are these kinds of circular predicates not allowed? How would I fix it?

Thanks

Answer 1

Forgive me if I get the syntax wrong, it's been a while since I played with Prolog.

---

A typical solution is to introduce another level to the clauses, like this:

married(X, Y) :- wife(X, Y).
married(X, Y) :- wife(Y, X).

and then specifying the relations using the wife clause instead:

wife(jane, bob).
wife(alice, john).

?- married(jane, X).
X = bob

More information can be found here: CSc 8710, Deductive Databases and Logic Programming, chapter 6 - Logic and databases, under 6.5 - Special Relations.

Answer 2

As I understand it, the basic problem is that if circular definitions are allowed, although the resulting language is self-consistent, there can be subtle consequences which are often counter-intuitive. There are also efficiency considerations (circular definitions incur extra overhead).

See this detailed discussion for lots more explanation and quite a few different points of view.

Answer 3

One possible solution is to use tabling, see e.g. this answer.