为什么这个 prolog 程序会导致无限递归？

Question

我正在尝试制作一个简单的知识库。然而，我正在努力让类别系统发挥作用。

这是到目前为止的程序：

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).

查询：

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

Answer 1

您遇到了名为左递归的现象。解决目标 subset(X, Z) 被简化为使用新的未绑定变量 Y 来解决目标 subset(X, Y)，并且这个导致无限地解决相同的目标subset(X, Z)等。应避免左递归。

通常的方法是区分基本事实和传递闭包的规则。你可以尝试：

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

这个公式中没有左递归。首先尝试可以终止递归的直接事实。仅当没有事实时，才执行递归调用。