Search code examples
prologtransitive-closurefailure-slice

Prolog Infinite loop on circular facts

Here is circular part of my facts (define relation between people):

connection(harry, ron).
connection(ron, harry).
connection(hermione, harry).

I want to find out if there is a connection, either directly or through other people using recursion.

This code runs into an infinite loop in the above situation:

connected(A, B) :-
   connection(A, B).
connected(A, B) :- 
   connection(A, C),
   connected(C, B).

I want the recursion to stop when it encounters previous searches. For example:

?- connected(hermione, X).
X = harry ;
X = ron.

Thank you!

Solution

  • Prolog's execution mechanism is quite un-intuitive. It combines recursion (as you know it from other languages) with backtracking. But there is a nice way out. You can consider smaller programs instead of your original program.

    To better understand the actual loop, here is the minimal program fragment called a that is the cause for non-termination. There is some extra falsework in it: Some goals false. With these goals the number of inferences is reduced (or stays the same). Thus, when the resulting program is looping, this is also a reason why your original program loops.

    connection(harry, ron).
connection(ron, harry).
connection(herminone, harry) :- false.

connected(A, B) :- false, connection(A, B).
connected(A, B) :-
    connection(A, C),
    connected(C, B), false.

?- connected(A, B).

    The query still loops. Note that it fails (and thus terminates) when asked the right persons (you know who, I suppose):

    ?- connected(tom, B).
   false.

    To solve this problem, the simplest way is to use closure/3 like so:

    connected(A, B) :-
   closure(connection, A, B).