prolog - 如何理解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 是另一个数字的 succ。因此，生成了另一个变量(如_G44)，_G44将匹配0，并且也会像_G42一样进一步匹配。由于_G44匹配0，那么它会向后返回到_G42，得到_G42 = succ(_G44) = succ(0).

不知道我的理解是否正确。我画了一张图来表达我对这个问题的理解。

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

Answer 1

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

可悲的是，这对最努力的员工打击最大:你总是认为你能以某种方式理解它，但最终，你无法理解它，因为有太多的方法可以调用即使是最简单的方法谓词，带有未实例化和(部分)实例化的参数，甚至带有别名变量。

你的图表很好地说明了这样的程序读取很快就会变得极其笨拙，即使对于最简单的递归定义也是如此。

理解谓词的一个更更容易理解的方法是以声明方式阅读它:

1. 0 是数字
2. 如果 X 是一个数字(无论 X 是什么!)，那么 succ(X X 的 ) 也是一个数字。

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

我的建议是重点关注对应该内容的清晰声明性描述。为了克服 Prolog 的初始障碍，您必须放弃这样的想法，即您可以非常详细地跟踪 CPU 执行的步骤(您当前正在尝试遵循该步骤)。 Prolog 的级别太高，无法以这种低级别的方式进行跟踪。这就像试图通过仅追踪说话者的神经元事件来解释法语和英语。

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