17

如果我想确保两个变量不会实例化为同一个术语，那么首选的方法是什么？

假设我需要在图中找到有向边，并且节点不能对自身有边：

node(a, x, y). node(b, z, x). node(c, y, y).

（这里的边是 a -> c，b -> a，但不是c -> c）

以下作品：

edge(A, B) :- node(A, _, X), node(B, X, _), A \== B.

这也有效[swi-prolog]：

edge(A, B) :- dif(A, B), node(A, _, X), node(B, X, _).

这显然不起作用（因为 A 和 B 都没有被实例化？）：

edge(A, B) :- A \== B, node(A, _, X), node(B, X, _).

我想我对第一个解决方案的问题是，对于更复杂的谓词，在失败node之前可能会发生许多不必要的统一。另一方面，在一个库中，这表明它不适合在如此简单的情况下使用（尽管它具有我似乎正在寻找的确切功能）edge。dif

4

3 回答 3

15

仅出于优雅和教学的原因，dif/2在这里以及在绝大多数其他情况下显然更可取，因为您已经注意到“可能会发生很多不必要的统一”，而且还因为dif/2它是一个纯粹且很好的声明性谓词，可以与(\==)/2. dif/2也是 SWI-Prolog 中的自动加载谓词，这意味着您无需显式导入任何库即可使用它，并且dif/2像任何内置谓词一样可用。

如果您使用dif/2，您可以更轻松地推断您的代码。例如，在您的情况下，您从以下开始：

边缘（A，B）：-节点（A，_，X），节点（B，X，_），差异（A，B）。

然后，您知道这dif/2是一个完全纯谓词，您知道您也可以将其写为：

边缘（A，B）：-差异（A，B），节点（A，_，X），节点（B，X，_）。

此外，由于您知道dif/2始终终止，因此您知道此更改最多可以改善程序的终止属性。

像所有约束一样，dif/2旨在使用。我强烈推荐它而不是不可交换的不纯谓词。

如果您担心性能，这里有一个小比较，只是在两个谓词可以互换使用的用例中dif/2与非声明性进行比较：(\==)/2

?- N = 1_000_000，时间（（介于（1，N，_），dif（a，b），假））。
% 11,000,005 次推理，0.352 CPU 在0.353 秒内（100% CPU，31281029 唇）

?- N = 1_000_000，时间（（介于（1，N，_），a\==b，假））。
%@ % 3,000,001 次推理，0.107 秒内的 0.107 CPU （99% CPU，28167437 唇）

因此，使用(\==)/2. 然而，在使用这种低级谓词时也有更严重的缺点：它更难理解、更容易出错、并且不是声明性的。

因此，我建议简单地使用dif/2来表示两个术语是不同的。

于 2012-12-07T08:20:45.550 回答
7

首先，当两个论点都成立时dif/2，(\==)/2意思相同，即自由变量。因此，如果您可以确保论点是有根据的——或者更确切地说是充分实例化，使得进一步的实例化不会影响结果(\==)/2——那么它就不会产生影响。

在您的示例中，我们需要确定答案node/3总是包含一个基本的第一个论点。在这种情况下，(\==)/2程序很好。在极少数情况下，它的效率可能低于该dif/2版本。想想目标edge(X, X)。

在许多情况下，(\==)/2或什至(\=)/2明显更有效。另一方面，与正确性相比，效率有多重要？

看待这一点的另一种方式是从两个方面考虑(\==)/2和(\=)/2作为近似值：只有当双方都同意时，我们才会有一个安全的最终结果。

从历史上看，dif/2它是最古老的内置谓词之一。它出现在第一个 Prolog 系统中，有时称为 Prolog 0，以将其与下一个版本区分开来，后者通常被认为是第一个 Prolog——Marseille Prolog——Prolog 1。Prolog 1 不再有dif/2，它在这个Prolog 来到爱丁堡的形状。此外，dif/2它不是 ISO 标准的一部分（当前），因为它需要一些类似协程的机制。许多（相当旧的）Prolog 系统没有这样的机制。然而，即使在 ISO Prolog 中，也可以做得更好：

iso_dif(X, Y) :-
   X == Y,
   !,
   fail.
iso_dif(X, Y) :-
   X \= Y,
   !.
iso_dif(X, Y) :-
   throw(error(instantiation_error,iso_dif/2)).

（这是另一个可能更有效的实现）

请注意有问题的情况如何被停止整个计算的错误所覆盖。

当前支持dif/2开箱即用的 Prolog 系统有 B、SICStus、SWI、YAP。它位于 IF、Ciao、XSB、Scryer 的库中。

另请参阅此答案。

为了支持我关于开销的说法，这里是在同一台机器上的各种 Prolog 中的测试。在 SWI 中，有 10 倍的开销，在 B 中，没有开销。正如@nfz 所指出的，编译时数字略有不同。所以你的里程可能会有所不同。

SWI 6.3.4-55

?- 1000=I,time(( dif(X,Y), between(1,I,X), between(1,I,Y), false ))。
% 22,999,020 次推理，5.162 CPU在 5.192 秒内（99% CPU，4455477 唇）
错误的。

?- 1000=I,time(( 介于(1,I,X),介于(1,I,Y), X \== Y, false ))。
% 2,000,001 推理，0.511 CPU在 0.521 秒内（98% CPU，3912566 唇）
错误的。

乙 7.8

| ?- 1000=I,time(( dif(X,Y), between(1,I,X), between(1,I,Y), false ))。
CPU时间0.364秒。
不
| ?- 1000=I,time(( 介于(1,I,X),介于(1,I,Y), X \== Y, false ))。   
CPU时间0.356秒。
不

雅普

?- 1000=I,time(( dif(X,Y), between(1,I,X), between(1,I,Y), false ))。
% 2.528 CPU在 2.566 秒 ( 98% CPU)
不
?- 1000=I,time(( 介于(1,I,X),介于(1,I,Y), X \== Y, false ))。
% 0.929 CPU在 0.963 秒内 (96% CPU)
不
于 2012-12-07T19:47:57.353 回答
7

查询是元解释的，开销可能超过 和 的dif(X,Y)差异X\==Y。您应该比较这两个谓词：

t1:-
    1000=I,
    time(t1(I)).


t1(I):-
    dif(X,Y), 
    between(1,I,X), 
    between(1,I,Y), 
    false.

t2:-
    1000=I,
    time(t2(I)).


t2(I):-
    between(1,I,X), 
    between(1,I,Y), 
    X\==Y,
    false.

在 B-Prolog 上，我得到以下结果：

| ?- cl(t)
Compiling::t.pl
compiled in 0 milliseconds
loading::t.out

yes
| ?- t1
CPU time 0.14 seconds.
no
| ?- t2
CPU time 0.078 seconds.
no
| ?- 1000=I,time(( dif(X,Y), between(1,I,X), between(1,I,Y), false )).
CPU time 0.234 seconds.
no
| ?- 1000=I,time(( between(1,I,X), between(1,I,Y), X \== Y, false )).
CPU time 0.218 seconds.
于 2012-12-09T22:08:18.657 回答