Prolog - Avoid Infinite Loop

Question

I am currently studying logic programming, and learn Prolog for that case.

We can have a Knowledge Base, which can lead us to some results, whereas Prolog will get in infinite loop, due to the way it expands the predicates.

Let assume we have the following logic program

p(X):- p(X).
p(X):- q(X).
q(X).

The query p(john) will get to an infinite loop because Prolog expands by default the first predicate that is unified. However, we can conclude that p(john) is true if we start expanding the second predicate.

So why doesn't Prolog expand all the matching predicates (implemented like threads/processes model with time slices), in order to conclude something if the KB can conclude something ?

In our case for example, two processes can be created, one expanded with p(X) and the other one with q(X). So when we later expand q(X), our program will conclude q(john).

Answer 1

Because Prolog's search algorithm for matching predicates is depth-first. So, in your example, once matching the first rule, it will match again the first rule, and will never explore the others.

This would not happen if the algorithm is breadth-first or iterative-deepening.

Usually is up to you to reorder the KB such that these situations never happen.

However, it is possible to encode breadth-first/iterative-deepening search in Prolog using a meta-interpreter that changes the search order. This is an extremely powerful technique that is not well known outside of the Prolog world. 'The Art of Prolog' describes this technique in detail.

You can find some examples of meta-interpreters here, here and here.