prolog - 查找 prolog 程序给出错误结果的查询

Question

这个 Prolog 程序将第三个参数定义为前两个数字参数的最大值：

max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).

我认为这个程序工作得很好。但我被告知它可能会给出不正确的结果。你能说出时间和原因吗？

Answer 1

这是一个教科书的例子。

?- max(5,1,1).
true.

作业：为什么程序出错了？我们如何使程序正确？

编辑

max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).

我们的意图是说：

如果 X 大于 Y，则Max 为 X。否则，Max 必须为 Y。

相反，要说的是：

当第一个和第三个参数（X 和 Max）可以统一，并且 X 大于 Y 时，成功。否则，如果第二个和第三个参数（Y和Max）可以统一，则成功。

显而易见的问题出现了，第一和第三个论点不能统一，但第二个和第三个可以。

反而：

max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.

或者

max(X, Y, Max) :- X >= Y, !, Max = X.
max(_, Max, Max).

Answer 2

如果第三个参数没有实例化，它确实可以正常工作。这里的危险是如果有办法回溯到第二条规则，或者第三个参数被实例化为与第二个相同的值。它看起来不是特别安全，因为max(X, Y, Y).等于max(_, Y, Y)which 只是将结果设置为第二个值而没有任何想法。第一条规则末尾的剪切有效地确保了如果 X >= Y 则不会开始回溯，因此仅当 X < Y 且 Z 不等于 Y 时才应输入第二条规则。

虽然它主要是有效的，但这不是一个好习惯。刚接触 Prolog 的人倾向于在程序上思考并利用这样的剪辑来通过程序诡计确保特定结果最终使您退缩并导致无法以不同和有趣的方式驱动的复杂 Prolog。还有其他几种编写此谓词的方法同样有效，但不依赖于 cut 来确保它们的行为，例如：

max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.

或者

max(X, Y, Z) :- X >= Y -> Z = X ; Z = Y.

这些都不容易受到第三个被实例化的问题的影响。有趣的是，这很好地说明了红色切割和绿色切割之间的区别。您的代码有一个红色剪切，其行为取决于剪切，但如果我只是将我的第一个解决方案更改为此：

max(X, Y, X) :- X >= Y, !.
max(X, Y, Y) :- X < Y.

这是一个绿色剪切，因为行为不依赖于剪切，但 Prolog 的性能可能会略有提高，因为它不会回溯到第二个子句尝试它。在这里，我们明确告诉 Prolog，不要同时进行下一次检查，因为我们知道它会失败。使用红色切割，没有其他检查会失败。

不幸的是，两次陈述条件感觉是多余的，但依靠单一规则感觉很笨拙。在实践中，我的经验是，这样的场景最终并不是那么普遍。通常，您可以在子句的头部匹配原子或结构，这些原子或结构可以创建类似于我们在我的第一个替代项中的行为，但不需要主体。例如：

perform(scan(target, X, Y)) :- ...
perform(scan(calibration, X)) :- ...

这具有相同的效果：Prolog 会回溯，直到它统一成功，然后它会再次回溯，但匹配的排他性会阻止另一个主体被执行。如果我们发现回溯花费了太多时间，我们可以添加削减以提高性能，但实际上这不太可能成为问题。