Why is this prolog program causing infinite recursion?

Question

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

I'm a bit rusty on Prolog, but have you tried putting your facts first? As in, moving member(t1, tomatoes) up above the recursive rules? — acjay

Jiri Kriz Jiri Kriz · Accepted Answer · 2011-10-21T15:22:17

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.

Why is this prolog program causing infinite recursion?

1 Answers