4

知识库

add(0,Y,Y). // clause 1
add(succ(X),Y,succ(Z)) :- add(X,Y,Z). // clause 2

询问

add(succ(succ(succ(0))), succ(succ(0)), R)

痕迹

Call: (6) add(succ(succ(succ(0))), succ(succ(0)), R)
Call: (7) add(succ(succ(0)), succ(succ(0)), _G648)
Call: (8) add(succ(0), succ(succ(0)), _G650)
Call: (9) add(0, succ(succ(0)), _G652)
Exit: (9) add(0, succ(succ(0)), succ(succ(0)))
Exit: (8) add(succ(0), succ(succ(0)), succ(succ(succ(0))))
Exit: (7) add(succ(succ(0)), succ(succ(0)), succ(succ(succ(succ(0)))))
Exit: (6) add(succ(succ(succ(0))), succ(succ(0)), succ(succ(succ(succ(succ(0))))))

我的问题

  • 我看到第 2 条中的递归调用如何在每次调用参数 1 时剥离最外层的 succ()。
  • 我看到它如何在每次调用时将外部 succ() 添加到参数 3。
  • 我看到作为这些递归调用的结果的第一个参数何时达到 0。此时，我看到第一个子句如何将第二个参数复制到第三个参数。

这就是我感到困惑的地方。

  1. 执行第一个子句后，第二个子句是否也会自动执行，然后将 succ() 添加到第一个参数？

  2. 另外，程序是如何终止的，为什么它不只是无限地向第一个和第三个参数添加 succ() 呢？

LearnPrologNow.com 的解释（我不明白）

让我们逐步了解 Prolog 处理此查询的方式。查询的跟踪和搜索树如下所示。

第一个参数不是 0 ，这意味着只能使用 add/3 的第二个子句。这导致 add/3 的递归调用。最外层的 succ 函子被剥离了原始查询的第一个参数，结果成为递归查询的第一个参数。第二个参数不变地传递给递归查询，递归查询的第三个参数是一个变量，即下面给出的跟踪中的内部变量 _G648。请注意，_G648 尚未实例化。然而，它与 R（我们在原始查询中用作第三个参数的变量）共享值，因为当查询与第二个子句的头部统一时，R 被实例化为 succ(_G648)。但这意味着 R 不再是一个完全未实例化的变量。现在是一个复杂的术语，

接下来的两个步骤基本相同。每一步，第一个参数都会变小一层 succ；下面给出的跟踪和搜索树都很好地说明了这一点。同时，每一步都将一个 succ 函子添加到 R 中，但始终不实例化最里面的变量。在第一次递归调用后 R 是 succ(_G648) 。在第二次递归调用后，_G648 被 succ(_G650) 实例化，因此 R 为 succ(succ(_G650) 。在第三次递归调用后，_G650 被 succ(_G652) 实例化，因此 R 变为 succ(succ(succ( _G652))) . 搜索树显示了这个一步一步的实例化。

在这个阶段，所有的 succ 函子都被剥离了第一个参数，我们可以应用 base 子句。第三个参数等于第二个参数，所以复数 R 中的“洞”（未实例化的变量）最终被填满，我们通过了。

4

1 回答 1

4

让我们从正确使用术语开始。

正如您正确指出的那样，这些是子句：

添加（0，Y，Y）。
添加（成功（X），Y，成功（Z））：-添加（X，Y，Z）。

让我们首先以声明的方式阅读这个程序，以确保我们正确理解它的含义：

  1. 0加号Y是Y。这是有道理的。
  2. 如果XplusY是真的，Z 那么Xplus 的继任者Y就是 的继任者 Z。

这是阅读此定义的好方法，因为它足够通用以涵盖各种使用模式。例如，让我们从最一般的查询开始，其中所有参数都是新变量：

?- 加（X，Y，Z）。
X = 0,
Y = Z;
X = 成功（0），
Z = 成功（Y）；
X = 成功（成功（0）），
Z = succ(succ(Y)) 。

在这种情况下，没有什么可以“剥离”，因为没有任何参数被实例化。然而，Prolog 仍然报告了非常明智的答案，这些答案明确了关系适用于哪些术语。

在您的情况下，您正在考虑一个不同的查询（不是“谓词定义”！），即查询：

?- 添加（succ（succ（succ（0））），succ（succ（0）），R）。
R = succ(succ(succ(succ(succ(0)))))。

这只是上面显示的更一般查询的一个特例，也是您的程序的自然结果。

我们也可以朝另一个方向去推广这个查询。例如，这是一种概括，因为我们将一个基本参数替换为一个逻辑变量：

?-添加（成功（成功（成功（0））），B，R）。
R = succ(succ(succ(B)))。

如果您按照您发布的解释进行操作，您的生活将变得非常困难，并且对逻辑程序的看法非常有限：实际上，您只能追踪可以使用谓词的一小部分模式，并且因此，程序性阅读与您实际描述的内容相去甚远。

如果你真的坚持程序性阅读，先从一个更简单的案例开始。例如，让我们考虑：

?-添加（成功（0），成功（0），R）。

要在程序上“逐步通过”，我们可以进行如下操作：

  1. 第一个子句匹配吗？（请注意，“匹配”已经是有限的阅读：Prolog 实际上应用了统一，而程序性阅读使我们远离了这种普遍性。）
  2. 答：不，因为s(_)不统一0。所以只有第二条适用。
  3. 第二个子句只有在它的主体成立时才成立，在这种情况下如果 add(0, succ(0), Z)成立。这成立（通过应用第一个子句）if Z issucc(0)和Ris succ(Z)。
  4. 因此，一个答案 是R = succ(succ(0)).。这个答案被报道。
  5. 还有其他解决方案吗？这些仅在回溯时报告。
  6. 答：不，没有其他解决方案，因为没有其他子句匹配。

我把它作为一个练习，将这种艰苦的方法应用于书中显示的更复杂的查询。这样做是直截了当的，但会越来越多地引导你远离逻辑程序最有价值的方面，在它们的通用性和优雅的声明式表达中发现。

您关于终止的问题既微妙又富有洞察力。请注意，我们必须在 Prolog 中区分存在终止和通用终止。

例如，再次考虑上面显示的最一般的查询：它产生答案，但它不终止。对于要报告的答案，找到使查询为 true的答案替换就足够了。在您的示例中就是这种情况。如果有任何可能存在的替代方案，则会尝试并在回溯时报告。

您始终可以尝试以下方法来测试查询的终止：只需 append false/0，例如：

?- 添加（X，Y，Z），假。
不终止

这使您可以专注于终止属性，而无需关心具体的答案。

还要注意，这add/3是一个可怕的关系名称：命令式总是意味着一个方向，但实际上，如果没有任何参数被实例化，这实际上更加通用和可用！一个好的谓词名称应该反映这种普遍性。

于 2017-03-17T19:30:22.477 回答