Prolog 程序 returns 错误

Question

我在 Prolog 中实现了以下电源程序：

puissance(_,0,1).
puissance(X,N,P) :- N>0,A is N-1, puissance(X,A,Z), P is Z*X.

代码执行预期的操作，但在正确答案后打印 "false."。我不明白为什么。我正在使用 swi-序言。

Answer 1

可以这样做：

puissance(X,N,P) :-
  ( N > 0 ->
    A is N-1,
    puissance(X,A,Z),
    P is Z*X
  ; P = 1 ).

然后它只会打印一个答案。

(您的代码在每次递归调用时都会留下一个“选择点”，因为您有两个析取点并且没有剪切。使用 if-then-else 或在某处剪切会删除这些。然后取决于解释器会发生什么。 Sicstus 仍然会询问您是否想要（（试图找到））更多答案。）

Answer 2

您可以将 cut 运算符（即 !）添加到您的解决方案中，这意味着序言不应在第一次成功统一后尝试回溯并找到更多解决方案已经到了那个地步。（即你正在修剪解决方案树）。

puissance(_,0,1) :- !.
puissance(X,N,P) :- N>0,A is N-1, puissance(X,A,Z), P is Z*X.

通俗解释：

序言试图查看是否还有更多解决方案的原因是：

在你的递归中最后一次调用 puissance 时，first puissance 子句成功，因为 P=1，你一路返回到顶部调用以使用该选择产生的最终值与 P 执行统一。

但是，对于最后一次调用 puissance，Prolog 没有机会检查 second puissance 子句是否会 also 是可满足的并可能导致不同的解决方案，因此除非你告诉它不要检查进一步的解决方案（通过在成功后对第一个子句使用 cut），它有义务去回到那一点，也检查第二个子句。

一旦执行，它就会发现第二个子句无法满足，因为 N = 0，因此该特定尝试失败。

所以 "false" 实际上意味着 prolog 也检查了其他选择点并且无法以任何其他方式统一 P 来满足它们，即 P 没有更多有效的统一。

事实上，您首先可以选择寻找其他解决方案，这恰恰意味着还有其他路线具有潜在可满足的子句尚未探索。

Answer 3

语义差异

目前，puissance/3 有 3 个不同的版本，我想展示其中一些版本之间的显着语义差异。

作为测试用例，我考虑查询：

?- puissance(X, Y, Z), false.

这个查询是什么意思？在声明中，它显然等同于 false。尽管如此，这个查询非常有趣，因为它终止 iff puissance/3 普遍终止.

现在，让我们尝试对程序的不同变体进行查询：

原始定义（来自问题）：

?- puissance(X, Y, Z), false.
ERROR: puissance/3: Arguments are not sufficiently instantiated

已接受的答案：
```
?- puissance(X, Y, Z), false.
false.
```

其他答案：

?- puissance(X, Y, Z), false.
ERROR: puissance/3: Arguments are not sufficiently instantiated

显然，接受的答案中显示的解决方案产生了不同的结果，值得进一步考虑。

程序又来了：

puissance(_,0,1) :- !.
puissance(X,N,P) :- N>0,A is N-1, puissance(X,A,Z), P is Z*X.

先问个简单的问题：到底有哪些解决方案？这被称为最通用的查询，因为它的参数都是新变量：

?- puissance(X, Y, Z).
Y = 0,
Z = 1.

程序回答：只有单一解：Y=0, Z=1.

那是 不正确的 （要查看这一点，请尝试 ?- puissance(0, 1, _) 成功的查询，与 same program claiming that Y can only be 0), and a significant difference from the program in the question.为了比较，原始程序产生：

?- puissance(X, Y, Z).
Y = 0,
Z = 1 ;
ERROR: puissance/3: Arguments are not sufficiently instantiated

没关系：在回溯时，程序会抛出一个 实例化错误 以指示此时无法进一步推理。但重要的是，它 而不是 只是失败了！

改进确定性

所以，让我们坚持原来的程序，并考虑查询：

?- puissance(1, 1, Z).
Z = 1 ;
false.

我们想去掉 false，这是因为程序 不确定性。

解决此问题的一种方法是使用 library(clpfd) 中的 zcompare/3。这使您可以 重新定义 比较，并使结果可用于索引，同时保留谓词的通用性。

这是一种可能的解决方案：

puissance(X, N, P) :-
        zcompare(C, 0, N),
        puissance_(C, X, N, P).

puissance_(=, _, 0, 1).
puissance_(<, X, N, P) :-
        A #= N-1,
        puissance(X, A, Z),
        P #= Z*X.

有了这个版本，我们得到：

?- puissance(1, 1, Z).
Z = 1.

这现在是确定性的，如预期的那样。

现在，让我们考虑一下上面这个版本的测试用例：

?- puissance(X, Y, Z), false.
nontermination

啊哈！因此，此查询既不会抛出 实例化错误 也不会终止，因此不同于迄今为止发布的所有版本。

让我们考虑使用此程序的最一般查询：

?- puissance(X, Y, Z).
Y = 0,
Z = 1 ;
X = Z,
Y = 1,
Z in inf..sup ;
Y = 2,
X^2#=Z,
Z in 0..sup ;
Y = 3,
_G3136*X#=Z,
X^2#=_G3136,
_G3136 in 0..sup ;
etc.

啊哈！所以我们得到了满足这个关系的所有整数的符号表示。

这很酷，因此我建议您在 Prolog 中对整数进行推理时使用 CLP(FD) 约束。这将使你的程序更通用，也让你更容易提高它们的效率。

Prolog 程序 returns 错误

Prolog program returns false

prolog

prolog-toplevel

语义差异

改进确定性