如何理解Prolog中的递归搜索？

Question

这是一段以递归方式定义数字的 Prolog 代码：

numeral(0). 
numeral(succ(X))  :-  numeral(X).

当给定查询numeral(X).Prolog 将返回：

X  =  0  ; 

X  =  succ(0)  ; 

X  =  succ(succ(0))  ; 

X  =  succ(succ(succ(0)))  ; 

X  =  succ(succ(succ(succ(0))))  ; 

X  =  succ(succ(succ(succ(succ(0)))))  ; 

X  =  succ(succ(succ(succ(succ(succ(0))))))  ; 

X  =  succ(succ(succ(succ(succ(succ(succ(0)))))))  ; 

X  =  succ(succ(succ(succ(succ(succ(succ(succ(0)))))))) 
yes

根据我所了解的，在进行查询时，prolog 会首先X生成一个类似 的变量(_G42)，然后它会搜索事实和规则以找到匹配项。

在这种情况下，它将找到0（事实）作为正确匹配。然后它也会尝试匹配规则。那是考虑_G42不是0，_G42而是另一个数字的成功。因此，生成了另一个变量（如_G44），_G44将匹配0并且也将像 一样走得更远_G42。既然_G44匹配0，那么它就会倒退_G42，得到_G42 = succ(_G44) = succ(0)。

我不确定我的理解是否正确。我做了一个图表来显示我对这个问题的理解。

如果分析是正确的，我仍然觉得很难设计这样的递归函数。由于我是Prolog的新手，我想知道这种定义是否总是在应用程序中使用（例如构建专家系统，验证协议）还是只是为了初学者更好地理解基本搜索过程？如果经常使用，那么设计这种递归定义的重点是什么？

Answer 1

我的个人观点：尤其是作为初学者，你“理解 Prolog 中的递归搜索”的机会为零。无数初学者试图以这种方式理解 Prolog，但他们总是失败。

可悲的是，这对最勤奋的工人的打击最大：你总是认为你可以以某种方式理解它，但最终，你不能，因为有太多的方法来调用即使是最简单的谓词，带有未实例化和（部分）实例化的参数, 甚至带有别名的变量。

您的图表很好地说明了即使是最简单的递归定义，这样的程序阅读也会很快变得非常笨拙。

一个多理解谓词更容易处理的方法是阅读声明：

1. 0 是一个数字
2. 如果 X是数字（不管X是！），然后 succ(X)的X是同样的数字。

请注意，:-even 表示←，即从右到左的含义。

我的建议是专注于对应该持有的内容进行清晰的声明性描述。要克服 Prolog 的初始障碍，您必须放弃这样一种想法，即您可以在当前尝试遵循的极端细节中跟踪 CPU 执行的步骤。Prolog 太高级了，无法以这种低级方式进行跟踪。这就像通过仅追踪说话者的神经元活动来尝试在法语和英语之间进行解释。

写一个明确的定义，然后将搜索留给 Prolog。还有许多其他有效的方法可以理解和分解声明性定义，而不会被低级细节所淹没。参见例如program-slicing和failure-slicing。只要您停留在 Prolog 的所谓纯单调子集中，它们就可以工作。专注于这个领域，你将能够取得非常快的进步。