CODEWITHSUNDEEP
prologstack-overflow
bobbaluba
bobbaluba

Reputation: 3884

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

Upvotes: 3

Views: 1884

Answers (1)

Jiri Kriz
Jiri Kriz

Reputation: 9292

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.

Upvotes: 4

Related Questions