recursion - is_integer(X) 过程如何工作？

Question

我在 Mellish、Clocksin 中读到了关于 Prolog 的书，并得到了这个:

is_integer(0).

is_integer(X) :- is_integer(Y), X is Y + 1.

使用查询?- is_integer(X). 零输出很容易，但它如何得到 1, 2, 3, 4...

我知道仅解释写作并不容易，但我会感激任何尝试。

在第一个结果 X=0 之后，我点击 ; 然后查询变为 is_integer(0) 或者仍然是 is_integer(X) ？

我花了很长时间寻找这个问题的良好解释。提前致谢。

Answer 1

这触及了 Prolog 如此有趣和困难的核心。你绝对不傻，只是非常不同。

这里有两条规则。替代方案的存在会导致选择点的产生。您可以将选择点视为 Prolog 看到进行计算的替代方法的时刻。 Prolog 总是按照规则在数据库中出现的顺序尝试规则，这将与它们在源文件中出现的顺序相对应。因此，当您发出查询 is_integer(X) 时，第一条规则将 X 与 0 匹配并将其统一。这是您的第一个结果。

当您按“;”时你告诉 Prolog 失败，这个答案是 Not Acceptable ，这会触发回溯。 Prolog 唯一要做的就是尝试输入另一个规则，该规则以 is_integer(Y) 开头。 Y是一个新变量；它最终可能会或可能不会被实例化为与 X 相同的值，到目前为止，您还没有看到任何原因为什么不会出现这种情况。

此调用 is_integer(Y) 本质上重复了迄今为止已尝试的计算。它将输入第一条规则 is_integer(0) 并尝试。此规则将成功，Y 将与 0 统一，然后 X 将与 Y+1 统一，并且规则将在 X 与 1 统一后退出。

当您按“;”时再次，Prolog 将备份到最近的选择点。这次，最近的选择点是 is_integer/1 的第二条规则中的 is_integer(Y) 调用。所以调用栈的深度更大，但是我们还没有离开第二条规则。事实上，每个后续结果将通过在第二规则的先前位置的激活中在该位置处从第一规则回溯到第二规则来获得。我非常怀疑像前面这样的口头解释会有帮助，所以请看看这个垃圾的 ASCII 艺术，说明调用树是如何演变的:

1     2       2
     /         \
    1           2
               /
              1

^     ^        ^
|     |        |
0     |        |
     1+0       |
             1+(1+0)

其中数字表示激活哪个规则，级别表示调用堆栈的深度。接下来的几个步骤将像这样演变:

2            2
 \            \
  2            2
   \            \
    2            2
   /              \
  1                2
                  /
                 1

   ^             ^
   |             |
1+(1+(1+0))      |
 = 3          1+(1+(1+(1+0)))
                = 4

请注意，我们总是通过将堆栈深度增加 1 并达到第一个规则来生成一个值。