使用\ ==/2或dif/2

Question

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

假设我需要在图中找到有向边,并且节点不能有自己的边:

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

(这里的边是 - > 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另一方面,是在图书馆,这表明它并不意味着在这种简单的情况下使用(虽然它,我似乎在寻找精确的功能).

Answer 1

仅仅为了优雅和教学原因,dif/2在这里以及在绝大多数其他情况下显然是可取的,因为你已经注意到"可能会发生许多不必要的统一",而且因为它dif/2是一个纯粹且很好的声明性谓词,它可以在不改变程序含义的情况下,可以在所有方向和子句中的任何地方使用,与之相反(\==)/2.dif/2也是SWI-Prolog的自动装载断言,这意味着你需要没有导入任何图书馆明确地使用它,并dif/2可以像任何内置谓词.

如果您使用,dif/2您可以更轻松地推理您的代码.例如,在您的情况下,您从以下开始:

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

然后,如你所知,这dif/2是一个完全纯粹的谓词,你知道你也可以这样写:

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

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

像所有约束一样,dif/2意味着要使用.我强烈推荐它而不是不可交换的不纯的谓词.

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

?- N = 1_000_000, time((between(1,N,_),dif(a,b),false)).
% 11,000,005 inferences, 0.352 CPU in 0.353 seconds (100% CPU, 31281029 Lips)

?- N = 1_000_000, time((between(1,N,_),a\==b,false)).
%@ % 3,000,001 inferences, 0.107 CPU in 0.107 seconds (99% CPU, 28167437 Lips)

因此,使用时有时会带来性能优势(\==)/2.但是,使用这种低级谓词时也存在更严重的缺点:它更难理解,更容易出错,而且没有声明性.

因此,我建议简单地dif/2用来表达两个术语不同.

Answer 2

该查询是元解释和开销可能超过的差异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.

Answer 3

首先,当两个参数都是基础时dif/2,(\==)/2意思相同,即可变自由.因此,如果你能确保论证是基础的 - 或者说足够实例化,以便进一步的实例化不会影响结果(\==)/2- 那么它就不会有所作为.

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

在许多情况下,(\==)/2甚至(\=)/2更高效.另一方面,与正确性相比,效率有多重要？

另一种看待这种情况的方法是考虑(\==)/2并(\=)/2从两个方面作为近似:只有两者都同意,我们才能获得安全的最终结果.

从历史上看,它dif/2是最古老的内置谓词之一.它存在于第一个Prolog系统中,它有时被称为Prolog 0,以区别于下一个版本,它通常被认为是第一个Prolog - 马赛Prolog - Prolog 1. Prolog 1不再具有dif/2,它就在这个Prolog来到爱丁堡的形状.此外,dif/2它不是ISO标准(当前)的一部分,因为它需要一些类似coroutining的机制.许多(相当较老的)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的库中.

另见这个答案.

为了支持我对开销的主张,这里是在同一台机器上的各种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 inferences, 5.162 CPU in 5.192 seconds (99% CPU, 4455477 Lips)
false.

?- 1000=I,time(( between(1,I,X), between(1,I,Y), X \== Y, false )).
% 2,000,001 inferences, 0.511 CPU in 0.521 seconds (98% CPU, 3912566 Lips)
false.

B 7.8

| ?- 1000=I,time(( dif(X,Y), between(1,I,X), between(1,I,Y), false )).
CPU time 0.364 seconds.
no
| ?- 1000=I,time(( between(1,I,X), between(1,I,Y), X \== Y, false )).   
CPU time 0.356 seconds.
no

YAP

?- 1000=I,time(( dif(X,Y), between(1,I,X), between(1,I,Y), false )).
% 2.528 CPU in 2.566 seconds ( 98% CPU)
no
?- 1000=I,time(( between(1,I,X), between(1,I,Y), X \== Y, false )).
% 0.929 CPU in 0.963 seconds ( 96% CPU)
no