是否应该在定义加法的规则中交换第一个和第二个参数？

Question

在 Prolog 中有两种可能的加法规则，根据 cTI 具有不同的终止属性：

cTI reports sum(A,B,C)terminates_if b(A);b(C). 对于以下规则：

sum(0, Y, Y).
sum(s(X), Y, s(Z)) :-
  sum(X, Y, Z).

cTI reports sum(A,B,C)terminates_if b(A),b(B);b(C). 用于以下规则（X 和 Y 交换）：

sum(0, Y, Y).
sum(s(X), Y, s(Z)) :-
  sum(Y, X, Z).

可以通过执行查询 sum(X, 0, Z). 和 SWISH 来观察差异，Prolog 的在线 SWI-Prolog 实现。

它returns第一条规则的解决方案如下：

?- sum(X, 0, Z).
   X = Z, Z = 0
;  X = Z, Z = s(0)
;  X = Z, Z = s(s(0))
;  X = Z, Z = s(s(s(0)))
;  X = Z, Z = s(s(s(s(0))))
;  …

并且returns第二条规则的解决方案如下：

?- sum(X, 0, Z).
   X = Z, Z = 0
;  X = Z, Z = s(_1302)
;  false.

这两个规则中哪一个是正确的？

Answer 1

在讨论同一个程序的不同版本时，重命名这些版本很有帮助，这样它们就可以在同一个程序中共存：

sumA(0, Y, Y).
sumA(s(X), Y, s(Z)) :- sumA(X, Y, Z).

sumB(0, Y, Y).
sumB(s(X), Y, s(Z)) :- sumB(Y, X, Z).


?- sumA(X, 0, Z).
   X = 0, Z = 0
;  X = s(0), Z = s(0)
;  X = s(s(0)), Z = s(s(0))
;  X = s(s(s(0))), Z = s(s(s(0)))
;  ...
?- sumB(X, 0, Z).
   X = 0, Z = 0
;  X = s(_A), Z = s(_A).

（以上输出来自Scryer，可读性更好）

在查看具体定义之前，请考虑一下我们对 X 和 Z 期望的一组解决方案。两者应该是相同的，并且它们应该描述所有自然的 s(X)-numbers 0, s(0), s(s(0)) ... 所以我们有无限多的解决方案。我们，有限的人和我们有限的 Prolog 系统，该如何描述无限多的解呢？好吧，我们可以试一试，就开始¹。这就是我们在 sumA 中看到的。这里的好处是，每个答案实际上都是一个解决方案（也就是说，没有变量剩余 ²）。遗憾的是程序没有终止（普遍）。至少它以公平的方式生成所有解决方案。等待足够长的时间，您最喜欢的解决方案³也会出现。

在sumB中，无限的自然数集以完全不同的方式被枚举。首先，我们得到 0 的解决方案，然后我们得到一个 answer，其中包括所有其他 ≥ 1 的数字。因此我们将这个无限集压缩为一个变量！这就是逻辑变量的力量。当然，我们在这里付出了很小的代价，因为现在我们实际上还包括了 s(_A) 的参数中的所有内容。一切，包括 s(nothing).

?- Z = s(nothing), sumA(Z, 0, Z).
false.
?- Z = s(nothing), sumB(Z, 0, Z).
   Z = s(nothing).

Which of these two rules is correct?

sumA和sumB都正确。并且 sumB 只要我们能够将我们的数字与其他术语区分开来（这大致对应于一个类型良好的程序）。

但是哪个更好呢？这一切都取决于。通常谓词会在某些上下文中使用。也许后续目标只有在其论点之一得到证实时才会终止。在这种情况下，sumA 可能更可取。如果没有进一步的目标，那么 sumB 总是更可取的。这一切都取决于一点。

最重要的是，一些解的无穷大可以优雅地包含在逻辑变量中，从而改进终止属性。对于更复杂的情况，这还不够，但这些变量将附加约束。

^{1) 如果我们得到 resource_error(memory)，请不要沮丧，它只是一个有限系统。

2) 确切地说没有剩余约束。

3) 我最喜欢的数字是 7^7^7 和 9^9^9。对于当前的实现，这将需要一些时间和 space。}

是否应该在定义加法的规则中交换第一个和第二个参数？

Should the first and second arguments be swapped in a rule defining addition?

termination

prolog

addition

successor-arithmetics