立即学习 Prolog - 递归练习中的回溯问题

Question

我无法理解这个例子中发生的事情
立即学习 Prolog - Chapter 3 - 示例 3：继任者

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

询问numeral(X)时，会先给X赋0，然后继续succ(0)，succ(0)这样逐个递增，直到用完space :

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

我很难理解为什么它会增加 succ(0)？

我知道 prolog 会先找到一个事实并匹配它，因此第一个 0。然后它会回溯看看是否还有其他解决方案，它会 "see" 规则。在规则中，它将使用实例化的 X 为 0。我失败的地方是查看为什么它不断递增 succ(0)。 X 是否变为 succ(0)，而不是 0？

我为愚蠢的大脑道歉。

Answer 1

I am struggling to understand why it increments succ(0)?

如果您再次阅读该部分，它指出：

Here’s yet another way of writing numerals, which is sometimes used in mathematical logic. It makes use of just four symbols: 0, succ , and the left and right parentheses, ( ). This style of numeral is defined by the following inductive definition:

0 is a numeral.
If X is a numeral, then so is succ(X) .

我看到很多人在第一次学习高等数学时遇到的问题之一是，当你说数学时，他们首先想到的是 Arabic numerals and a Cartesian coordinate system。

对于这个例子，你必须象征性地思考，例如Symbolic computation, or more fundamentally, Abstract rewriting system.

在这个例子中，他们没有使用阿拉伯数字，而是一种描述数字的函数式方式。换句话说，要描述一个数字，您只有起始符号 0 和一个函数 succ(x)。请注意，我说的是符号而不是数字，因为符号 0 只有放在上下文中才有意义，在本例中是 natural numbers

所以

 0 is 0
 1 is succ(0)        - The successor of 0 is 1.
 2 is succ(succ(0))  - The successor of the successor of 0 is 2 or
                       The successor of 1, e.g. succ(0), is 2.

等等。如果你读过 Lambda calculus 你会经常看到这个。

关键字 inductive 给出了另一种思考方式。使用归纳法，您需要一个起始事实和一个将您带到下一个事实的规则。所以 0 是事实，将您带到下一个事实的规则是 succ(X)。

Answer 2

我认为 Guy Coder 对正在发生的事情进行了很好、详细的解释。我将提供他的归纳解释的一个细微变体，希望能帮助带来更多的清晰度。

想想你的 Prolog 规则是怎么说的：

numeral(0).

这表示，0 是一个数字。

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

这表示，succ(X)是一个数字ifX是一个数字.

根据第一条规则，0是一个数字。也就是说，numeral(0) 为真（成功）。根据第二条规则，由于 0 是一个数字，因此 succ(0) 必须是一个数字（numeral(succ(0)) 为真）。由于 succ(0) 是一个数字，那么再次根据第二条规则， succ(succ(0)) 必须是一个数字（numeral(succ(succ(0)) 为真）。等等...

立即学习 Prolog - 递归练习中的回溯问题

Learn Prolog Now - issues with backtracking in exercise on recursion

prolog

successor-arithmetics