sorting - 如何在ISO Prolog中定义(和命名)相应的安全术语比较谓词？

Question

在所有术语(包括变量)上定义了标准术语顺序(ISO / IEC 13211-1 7.2术语顺序)。尽管这样做有很好的用途-考虑setof/3的实现，但这使8.4术语比较中的内置的许多其他干净而合理的用法成为周围带有imp(声明式构造的简写形式)的声明性噩梦。 8.4术语比较功能:

8.4 Term comparison

8.4.1 (@=<)/2, (==)/2, (\==)/2, (@<)/2, (@>)/2, (@>=)/2.
8.4.2 compare/3.
8.4.3 sort/2.
8.4.4 keysort/2.

举一个例子，考虑:

?- X @< a.
true.

这成功了，因为

7.2 Term order

An ordering term_precedes (3.181) defines whether or
not a term X term-precedes a term Y.

If X and Y are identical terms then X term_precedes Y
and Y term_precedes X are both false.

If X and Y have different types: X term_precedes Y iff the
type of X precedes the type of Y in the following order:
variable precedes floating point precedes integer
precedes atom precedes compound.

NOTE — Built-in predicates which test the ordering of terms
are defined in 8.4.
...

因此，所有变量都小于 a。但是，一旦 X实例化:

?- X @< a, X = a.
X = a.

结果变为无效。

这就是问题所在。为了克服这个问题，可以要么使用约束，要么仅坚持核心行为，从而生成 instantiation_error 。

7.12.2 Error classification

Errors are classified according to the form of Error_term:

a) There shall be an Instantiation Error when an
argument or one of its components is a variable, and an
instantiated argument or component is required. It has
the form instantiation_error.

通过这种方式，我们可以确定只要没有实例化错误发生，就可以很好地定义结果。

对于 (\==)/2，已经存在使用约束的 dif/2 或产生干净实例化错误的 iso_dif/2 。

iso_dif(X, Y) :-
   X \== Y,
   ( X \= Y -> true
   ; throw(error(instantiation_error,iso_dif/2))
   ).

那么我的问题是什么:如何在 ISO Prolog中定义(和命名)相应的安全术语比较谓词？理想情况下，没有任何明确的术语遍历。也许需要澄清: iso_dif/2上面没有使用任何显式的术语遍历。 (\==)/2和 (\=)/2都在内部遍历该术语，但是与使用 (=..)/2或 functor/3, arg/3进行显式遍历相比，此操作的开销非常低。

Answer 1

iso_dif/2的实现比比较容易得多:

内置的\=运算符可用

现在，您确切要为\=提供哪些参数

定义

根据您的评论，安全比较意味着两个实例中的变量都得到实例化时顺序不会改变。如果我们将比较命名为 lt，例如:

lt(a(X), b(Y)):始终对所有X和Y都成立，因为a @< b

lt(a(X), a(Y)):我们不确定:intanciation_error

lt(a(X), a(X)):总是失败，因为X @
如评论中所述，如果在对两个术语进行并排遍历时，第一对(可能)有区别的术语包含:

两个不同的变量(lt(X,Y))

变量和非变量(lt(X,a)或lt(10,Y))

但是首先，让我们回顾一下您不想使用的可能方法:

定义一个明确的术语遍历比较函数。我知道您出于性能原因不愿意这样做，但是，这仍然是最直接的方法。我还是建议您这样做，以便您可以将引用实现与其他方法进行比较。

使用约束进行延迟的比较:我不知道如何使用ISO Prolog来进行比较，但是例如ECLiPSe，我将暂停未实例化变量集的实际比较(使用term_variables/2)，直到没有更多变量为止。以前，我还建议使用coroutine/0谓词，但我忽略了它不影响@<运算符(仅<)的事实。

这种方法不能解决您所描述的完全相同的问题，但是非常接近。一个优点是，如果赋给变量的最终值满足比较的要求，则它不会引发异常，而lt如果事先不知道，则将引发异常。

显式术语遍历(引用实现)

这是 lt( @<的安全版本)的显式术语遍历方法的实现。
请检查它是否符合您的期望。我可能错过了一些情况。我不确定这是否符合ISO Prolog，但是如果您愿意，也可以修复该问题。

lt(X,Y) :- X == Y,!,
    fail.

lt(X,Y) :- (var(X);var(Y)),!,
    throw(error(instanciation_error)).

lt(X,Y) :- atomic(X),atomic(Y),!,
    X @< Y.

lt([XH|XT],[YH|YT]) :- !,
    (XH == YH ->
         lt(XT,YT)
     ;   lt(XH,YH)).

lt(X,Y) :-
    functor(X,_,XA),
    functor(Y,_,YA),
    (XA == YA ->
       X =.. XL,
       Y =.. YL,
       lt(XL,YL)
    ;  XA < YA).

(编辑:考虑到Tudor Berariu的评论:(i)缺少var / var错误情况，(ii)首先按稀有度排序；此外，修复(i)允许我删除列表的 subsumes_term。谢谢。)

隐式术语遍历(不起作用)

这是我在不破坏条款的情况下实现相同效果的尝试。

every([],_).
every([X|L],X) :-
    every(L,X).

lt(X,Y) :-
    copy_term(X,X2),
    copy_term(Y,Y2),
    term_variables(X2,VX),
    term_variables(Y2,VY),
    every(VX,1),
    every(VY,0),
    (X @< Y ->
         (X2 @< Y2 ->
              true
          ;   throw(error(instanciation_error)))
     ;   (X2 @< Y2 ->
              throw(error(instanciation_error))
          ;   false)).

基本原理

假设 X @< Y成功。
我们要检查该关系是否不依赖于某些未初始化的变量。
因此，我分别生成了 X2和 Y2的副本 X和 Y，其中实例化了所有变量:

在X2中，变量与1统一。

在Y2中，变量统一为0。

因此，如果关系 X2 @< Y2仍然成立，我们知道我们不依赖变量之间的标准术语排序。否则，我们将引发异常，因为这意味着以前没有发生过的 1 @< 0关系使该关系失败。

缺点

(根据OP的评论)

lt(X+a,X+b)应该成功，但会产生错误。

乍一看，人们可能会认为统一使用这两个术语且值相同的变量val可以解决这种情况。但是，在比较术语中可能还会出现X，这会导致错误的判断。

lt(X,3)应该产生一个错误，但是成功。

为了解决这种情况，应将X的值大于3统一。在一般情况下，X的值应大于其他可能的术语 1 。除了实际的局限性之外，@<关系没有最大值:复合词大于非复合词，并且根据定义，复合词可以任意地变大。

因此，这种方法不是结论性的，我认为不能轻易纠正。

1 :请注意，对于任何给定的术语，我们都可以找到局部的最大和最小术语，这对于问题的目的就足够了。