无法理解为什么序言会无限循环

Question

来自 Bratko 的书，Prolog Programming for Artificial Intelligence (4th Edition) 我们有以下不起作用的代码 -

anc4(X,Z):-
    anc4(X,Y),
    parent(Y,Z).
anc4(X,Z):-
    parent(X,Z).

书中第 55 页的图 2.15 显示 parent(Y,Z) 一直调用，直到堆栈内存不足。

我不明白的是 prolog 对 anc4(X,Y) 进行递归调用，而不是首先对父级 (Y,Z) 进行递归调用。为什么 prolog 不一遍又一遍地转到 第一行 、anc4(X,Y)，而是转到第二行？

能否请您详细说明为什么一直调用 parent(Y,Z) 行？

谢谢。

Answer 1

如果没有 tabling 机制，Prolog 默认无法处理左递归。只有一些 Prolog 系统支持制表，通常您需要显式声明哪些谓词被制表。

如果您使用的是XSB、YAP 或 SWI-Prolog，尝试在包含 anc4/2 谓词定义的源文件顶部添加以下指令：

:- table(anc4/2).

然后重试您的查询。制表机制检测查询何时调用自身的 variant (*) 并暂停执行该分支，直到找到查询答案并尝试另一个分支（在您的案例中由第二条）。如果发生这种情况，将使用该答案恢复执行。

(*)这里的变体是指两个项在变量重命名时相等。

Answer 2

您的 'problem'（即目标顺序）的起源深深植根于语言的基础。

Prolog基于简单高效的时间顺序回溯策略，实现了SLD resolution，左递归子句，如anc4/2，导致无限递归。实际上，逗号运算符 (,)/2 代表

evaluate the right expression only if the left expression holds

因此，子句中目标的顺序实际上是程序的重要组成部分。

对于您的具体案例，

... , parent(Y,Z).

如果

则无法调用

anc4(X,Y),

不成立。

目标顺序的对应项是子句顺序。

即从句交换后整个程序的语义不同：

anc4(X,Z):-
    parent(X,Z).
anc4(X,Z):-
    anc4(X,Y),
    parent(Y,Z).

为了更好地理解问题，我认为也值得尝试这个定义。

Can't understand why is prolog looping infinitly