Prolog Infinite loop on circular facts

Question

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!

score 3 · Accepted Answer · answered Mar 25 '19 at 15:54

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 failure-slice 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).

[Falsework](https://en.wikipedia.org/wiki/Falsework) I only learned very [recently](https://stackoverflow.com/search?q=falsework). — false, Mar 26 '19 at 14:01

score 1 · Answer 2 · answered Apr 16 '19 at 16:57

1

You could try tabling. Many Prolog systems have table/1 directive. You just have to place it before the predicate you want to tabulate.

:- table connected/2.
connected(A, B) :-
   connection(A, B).
connected(A, B) :- 
   connection(A, C),
   connected(C, B).

If you then run a query, recursion will automatically stop. Here is an example run with the SWI-Prolog tabling:

Welcome to SWI-Prolog (threaded, 64 bits, version 8.1.4)

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

answered Apr 16 '19 at 16:57

For SWI-Prolog: `:- use_module(library(tabling)). :- table connected/2, connection/2.` – Volodimir Kopey Jun 30 '19 at 17:05
[connection/2](https://stackoverflow.com/q/55340773/502187) is already a table, so you don't need to table it. – Jun 30 '19 at 20:41

Prolog Infinite loop on circular facts

2 Answers2