Prolog - Avoid Infinite Loop -

i studying logic programming, , learn prolog case.

we can have knowledge base, can lead results, whereas prolog in infinite loop, due way expands predicates.

let assume have following logic program

p(x):- p(x). p(x):- q(x). q(x). 

the query p(john) infinite loop because prolog expands default first predicate unified. however, can conclude p(john) true if start expanding second predicate.

so why doesn't prolog expand matching predicates (implemented threads/processes model time slices), in order conclude if kb can conclude ?

in our case example, 2 processes can created, 1 expanded p(x) , other 1 q(x). when later expand q(x), our program conclude q(john).

because prolog's search algorithm matching predicates depth-first. so, in example, once matching first rule, match again first rule, , never explore others.

this not happen if algorithm breadth-first or iterative-deepening.

usually reorder kb such these situations never happen.

however, possible encode breadth-first/iterative-deepening search in prolog using meta-interpreter changes search order. extremely powerful technique not known outside of prolog world. 'the art of prolog' describes technique in detail.

you can find examples of meta-interpreters here, here , here.