prolog - Prolog 中 Cut 算子的交换性

Question

我目前正在学习 Prolog，在我正在阅读的一篇笔记中，给出了如何正确使用 cut 运算符的示例。考虑以下函数从列表中删除特定值的所有元素。

rm(_,[],[]).
rm(A,[A|L],R) :- rm(A,L,R).
rm(A,[B|L],[B|R]) :- rm(A,L,R).

由于回溯，这不是函数的正确定义，并且该函数将返回通过删除特定值的一些元素获得的列表的所有子列表，但不一定是全部。我正在阅读的注释说解决此问题的正确方法是将第二行替换为行

rm(A,[A|L],R) :- !, rm(A,L,R)

但是将行替换为

rm(A,[A|L],R) :- rm(A,L,R), !

不正确。我不确定为什么第二个示例是修复该功能的错误方法。在 swipl 中，用这些修复替换第二项似乎总是在我考虑的测试用例上返回相同的答案。我在这里缺少什么？

Answer 1

您的示例是一个完美的示例，可以说明为什么在这里使用剪切永远不是一个好主意。

使用rm(A,[A|L],R) :- !, rm(A,L,R).仅当第一个参数和第二个参数都被充分实例化时才有意义。但如果它们没有充分实例化，您会得到一个不完整的答案，例如:

?- rm(X, [a], R).
   X = a, R = [].       % incomplete

这显然错过了答案，因为它限制了 X成为a仅有的。但如果X是别的什么，我们得到不同的结果，即:

?- X = b, rm(X,[a],R).
   R = [a].

在末尾使用剪切，如 rm(A,[A|L],R) :- rm(A,L,R), !. 所示更糟糕的是:首先，到目前为止我们所有的假设都必须成立，然后此外第三个参数不能被实例化。否则我们会得到额外的错误解决方案。

?- rm(a,[a],R).
   R = [].
?- rm(a,[a],[a]).
   true, unexpected.              % incorrect

回想一下我们在这里问的是什么:

User: When removing a from the list [a] what do we get?

Prolog: Nothing, nil, nada.

User: But can't I have instead of nothing just [a]? Please!

Prolog: OK, I give in.

这不是您想要实现会计系统的方式。

所以这两种削减的用法都是不好的。但第二种显然更糟糕，因为它需要记住更多的先决条件，而且效率也很低。另一方面，在某些情况下您可以使用这些谓词。但通常很难记住什么时候这是安全的。因此，这种削减是错误的永久来源。

是否有希望摆脱所有这些细则？幸运的是，有一种方法可以使用 if_/3来自library(reif)对于 SICStus | SWI 。下载它并说:

:- use_module(reif).

rm(_,[],[]).
rm(A,[X|Xs], Ys0) :-
   if_(A = X, Ys0 = Ys, Ys0 = [X|Ys]),
   rm(A, Xs, Ys).

该程序相当有效，但没有任何上述缺陷:

?- rm(X, [a], R).
   X = a, R = []
;  R = [a], dif(X, a).

注意第二个新答案!它说对于所有人X与 a 不同，列表保持不变。