Search code examples
prologstack-overflow

Why is this prolog program causing infinite recursion?

I am trying to make a simple knowledge base. However, I'm struggling getting the category system to work.

Here is the program so far:

subset(tomatoes, fruits).
subset(fruits, food).
subset(X, Z) :- subset(X, Y), subset(Y, Z), not(X==Y), not(Y==Z), not(X==Z).
member(X, Z) :- member(X, Y), subset(Y, Z).
member(t1, tomatoes).

Query:

member(t1,tomatoes).
ERROR: Out of local stack
   Exception: (1,765,494) member(t1, _G28504) ? abort
% Execution Aborted
Solution

  • You encountered the phenomenon called left recursion. Solving the goal subset(X, Z) is reduced to solving the goal subset(X, Y) with a new unbound variable Y and this leads to solving the same goal subset(X, Z) etc, ad infinitum. Left recursions should be avoided.

    The usual approach is to dinstinguish between basic facts and rules for transitive closures. You could try:

    subset1(tomatoes, fruits).
subset1(fruits, food).

subset(X, Y) :- subset1(X, Y).
subset(X, Z) :- subset1(X, Y), subset(Y, Z).

member1(t1, tomatoes).
member1(t2, tomatoes).

member(X, Y) :- member1(X, Y).
member(X, Z) :- member1(X, Y), subset(Y, Z).

?- member(t1, food).       ===> TRUE

    There is no left recursion in this formulation. First a direct fact is tried that can terminate the recursion. Only if there is no fact, a recursive call is performed.