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

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

你的“问题”(即目标顺序)的根源深深 Root 于语言的基础。

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

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