Avoid infinite looping in Prolog

Question

I have the following facts in the knowledge base:

line(a,b). -- denotes the line determined by point a and b
line(c,d). -- denotes the line determined by point c and d
lineEqual(line(a,b),line(c,d)) -- denotes the length of two lines are equal

I want to have another rule that can swap around the two arguments of lineEqual/2:

lineEqual(line(C, D), line(A, B)):-
    lineEqual(line(A,B),line(C,D)).

Unfortunately the rule will create an infinity loop in Prolog. Any other idea?

Thanks for the update. Not sure if I understood your last rule:

transitiveSymmetricRelPath(L1, L2, IntermediateNodes) :- symmetricRel(L1, L3),
                 \+member(L3, IntermediateNodes),
                 transitiveSymmetricRelPath(L1, L2, [L3 | IntermediateNodes]).

I can imagine every time it tries to strip off the head node if it happens to be linked with both L1 and L3, right? So if we end up with an empty list then we can use this rule:

transitiveSymmetricRel(L1, L2) :- transitiveSymmetricRelPath(L1, L2, []).

But the bit I am not really getting is where do you get an nonempty list of intermediate nodes of transitiveSymmetricRelPath/3 to start with. I've actually tried your code with the given fact rel(a,b). rel(a,c). and it does not return transitiveSymmetricRel(b,c), neither does it return transitiveSymmetricRel(c,b). Could you please have a look into it?

Thanks a lot!

Edited: I've got it working by modifying your rule like:

transitiveSymmetricRelPath(L2, L3, IntermediateNodes) :- symmetricRel(L1, L3),
     \+member(L3, IntermediateNodes),
     transitiveSymmetricRelPath(L1, L2, [L3 | IntermediateNodes]).

Thanks for your suggestion anyway.

liori liori · Accepted Answer · 2012-12-29T02:26:52

You should avoid introducing data-like statements (like line and lineEqual from the first example) and code (like lineEqual from second example) under a single name. Instead, keep your database facts under a different name. Then, you can e.g. define:

areLinesEqual(L1, L2) :- linesEqual(L1, L2).
areLinesEqual(L1, L2) :- linesEqual(L2, L1).

In general, if you have a relation rel and you want to build a symmetric transitive closure, you should introduce one concept at a time. For example:

symmetricRel(L1, L2) :- rel(L1, L2).
symmetricRel(L1, L2) :- rel(L2, L1).

transitiveSymmetricRel(L1, L2) :-
    transitiveSymmetricRelPath(L1, L2, []).

transitiveSymmetricRelPath(L1, L2, _) :-
    symmetricRel(L1, L2).

transitiveSymmetricRelPath(L1, L2, IntermediateNodes) :-
    symmetricRel(L1, L3),
    \+ member(L3, IntermediateNodes),
    transitiveSymmetricRelPath(L1, L2, [L3 | IntermediateNodes]).

(note that here we must basically find a path in an undirected graph, and care must be taken in order to avoid looping). In your case it will also probably be desired to consider line(A, B) and line(B, A) as the same. For that, again, you should introduce another level of indirection:

% to check two lines for identity
same(line(A, B), line(A, B)).
same(line(A, B), line(B, A)).

linesEqual2(L1, L2) :-
    same(L1, LI1),
    same(L2, LI2),
    (linesEqual(LI1, LI2); linesEqual(LI2, LI1)).

…and use linesEqual2 instead of linesEqual in the definition of symmetric relation.

The hard part now is coming with a naming scheme so that you won't confuse all those predicates…

You can also do it in another way. Given that you seek a transitive closure of a symmetric relation, it's basically a partition of the set of all nodes (here: lines) into separable subsets. This insight will help you write much more efficient code that the above… but this is a bit out of scope of this question already.

Avoid infinite looping in Prolog

1 Answers