标准术语顺序(ISO/IEC 13211-1 7.2 术语顺序(是针对所有术语(包括变量(定义的。虽然这有很好的用途——想想setof/3的实现，这使得 8.4 术语比较中内置的许多干净和合乎逻辑的使用成为到处都是 imps(命令式结构的缩写(的声明性噩梦。8.4 术语比较功能：

8.4 术语比较

8.4.1 (@=<(/2， (==(/2， (==(/2， (@<(/2， (@>(/2，(@>=(/2.
8.4.2 比较/3.
8.4.3 排序/2.
8.4.4 键排序/2.

举个例子，请考虑：

?- X @< a.
true.

这成功了，因为

7.2 术语顺序
排序term_precedes (3.181( 定义是否或
不是术语X术语先于术语Y。
如果X和Y是相同的术语，则X term_precedes Y
Y term_precedes X都是假的。
如果X和Y具有不同的类型：X term_precedes Y
X类型按以下顺序
在Y类型之前： variable先于floating point先于integer
先于atom先于compound .
NOTE — 测试术语
顺序的内置谓词在 8.4 中定义。
...

因此所有变量都小于 a .但是一旦X被实例化：

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

结果无效。

这就是问题所在。为了克服这个问题，人们可以使用约束，或者只坚持核心行为，因此产生instantiation_error。

7.12.2 错误分类
错误根据Error_term的形式分类：
a( 当
参数或其组件之一是变量，并且
实例化参数或组件是必需的。它有
形式instantiation_error .

通过这种方式，我们确信只要没有实例化错误发生，结果就得到了很好的定义。

对于(==)/2，已经有使用约束的dif/2或产生干净实例化错误的dif_si/2(以前称为iso_dif/2(。

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

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

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(首先按arity排序;此外，修复(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成功了。我们要检查关系是否不依赖于一些未初始化的变量。因此，我生成了X和Y的X2和Y2的相应副本，其中所有变量都是实例化的：

在X2中，变量与1统一。
在Y2中，变量与0统一。

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

缺点

(根据OP的评论(

lt(X+a,X+b)应该成功，但会产生错误。
乍一看，人们可能会认为将两个术语中出现的变量统一为相同的值，例如val，可能会解决这种情况。但是，在比较的术语中，可能会发生其他X，这会导致错误的判断。
lt(X,3)应该会产生错误，但会成功。
为了解决这种情况，应该将X与大于 3 的东西统一起来。在一般情况下，X应取大于其他任何可能项¹ 的值。撇开实际限制不谈，@<关系没有最大值：复合项大于非复合项，根据定义，复合项可以任意大。

因此，这种方法不是决定性的，我认为它不容易纠正。

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

第三次尝试！使用 GNU Prolog 1.4.4 开发和测试。

图表"A"："尽可能简单">

lt(X,Y) :-
   X == Y,
   (  X = Y
   -> alpha_omega(Alpha,Omega),
      term_variables(X+Y,Vars),                           % A
      + + (label_vars(Vars,Alpha,Omega), X @< Y),
      (  + (label_vars(Vars,Alpha,Omega), X @> Y)
      -> true
      ;  throw(error(instantiation_error,lt/2))
      )
   ;  throw(error(instantiation_error,lt/2))
   ).

图表"B"："无需标记所有变量">

lt(X,Y) :-
   X == Y,
   (  X = Y
   -> alpha_omega(Alpha,Omega),
      term_variables(X,Xvars),                            % B
      term_variables(Y,Yvars),                            % B 
      vars_vars_needed(Xvars,Yvars,Vars),                 % B
      + + (label_vars(Vars,Alpha,Omega), X @< Y),
      (  + (label_vars(Vars,Alpha,Omega), X @> Y)
      -> true
      ;  throw(error(instantiation_error,lt/2))
      )
   ;  throw(error(instantiation_error,lt/2))
   ).
vars_vars_needed([],    [],    []).
vars_vars_needed([A|_], [],    [A]).
vars_vars_needed([],    [B|_], [B]).
vars_vars_needed([A|As],[B|Bs],[A|ABs]) :-
   (  A == B
   -> ABs = [B]
   ;  vars_vars_needed(As,Bs,ABs)
   ).

一些共享代码：

alpha_omega(阿尔法，欧米茄( ：-    阿尔法是 -(10.0^1000(， % 黑客！    函子(欧米茄，z，255(.    %黑客！label_vars([]，_，_(。label_vars([阿尔法|Vs]，Alpha，Omega( ：- label_vars(Vs，Alpha，Omega(.label_vars([欧米茄|Vs]，Alpha，Omega( ：- label_vars(Vs，Alpha，Omega(.

这不是

一个完全原创的答案，因为它建立在@coredump的答案之上。

有一种类型的查询lt/2(执行显式术语遍历的参考实现(无法正确回答：

| ?- lt(b(b), a(a,a)).
no
| ?- @<(b(b), a(a,a)).
yes

原因是术语的标准顺序在比较函子名称之前考虑了arity。

其次，在比较变量时，lt/2并不总是会引发instatiation_error：

| ?- lt(a(X), a(Y)).
no

我在这里写了另一个参考显式实现的候选者：

lt(X,Y):- var(X), nonvar(Y), !, throw(error(instantiation_error)).
lt(X,Y):- nonvar(X), var(Y), !, throw(error(instantiation_error)).
lt(X,Y):-
    var(X),
    var(Y),
    ( X == Y -> throw(error(instatiation_error)) ; !, false).
lt(X,Y):-
    functor(X, XFunc, XArity),
    functor(Y, YFunc, YArity),
    (
        XArity < YArity, !
      ;
        (
            XArity == YArity, !,
            (
                XFunc @< YFunc, !
              ;
                XFunc == YFunc,
                X =.. [_|XArgs],
                Y =.. [_|YArgs],
                lt_args(XArgs, YArgs)
            )
        )
    ).
lt_args([X1|OtherX], [Y1|OtherY]):-
    (
        lt(X1, Y1), !
      ;
        X1 == Y1,
        lt_args(OtherX, OtherY)
     ).

当有一对对应的参数Xi时，谓词lt_args(Xs, Ys)为真，Yi使得所有前一对的lt(Xi, Yi)和Xj == Yj Xj，Yj(例如lt_args([a,X,a(X),b|_], [a,X,a(X),c|_])为真(。

一些示例查询：

| ?- lt(a(X,Y,c(c),_Z1), a(X,Y,b(b,b),_Z2)).
yes
| ?- lt(a(X,_Y1,c(c),_Z1), a(X,_Y2,b(b,b),_Z2)).
uncaught exception: error(instatiation_error)

到底是什么！我也试一试！

lt(X,Y) :-
   X == Y,
   (  X = Y
   -> term_variables(X,Xvars),
      term_variables(Y,Yvars),
      list_vars_excluded(Xvars,Yvars,XonlyVars),
      list_vars_excluded(Yvars,Xvars,YonlyVars),
      _   = s(T_alpha),
      functor(T_omega,zzzzzzzz,255), % HACK!
      copy_term(t(X,Y,XonlyVars,YonlyVars),t(X1,Y1,X1onlyVars,Y1onlyVars)),
      copy_term(t(X,Y,XonlyVars,YonlyVars),t(X2,Y2,X2onlyVars,Y2onlyVars)),
      maplist(=(T_alpha),X1onlyVars), maplist(=(T_omega),Y1onlyVars),
      maplist(=(T_omega),X2onlyVars), maplist(=(T_alpha),Y2onlyVars),
      % do T_alpha and T_omega have an impact on the order?
      (  compare(Cmp,X1,Y1),      
         compare(Cmp,X2,Y2)
      -> Cmp = (<)                % no: demand that X @< Y holds
      ;  throw(error(instantiation_error,lt/2))
      )
   ;  throw(error(instantiation_error,lt/2))
   ).

一些更辅助的东西：

listHasMember_identicalTo([X|Xs],Y) :-
   (  X == Y
   -> true
   ;  listHasMember_identicalTo(Xs,Y)
   ).
list_vars_excluded([],_,[]).
list_vars_excluded([X|Xs],Vs,Zs) :-
   (  listHasMember_identicalTo(Vs,X)
   -> Zs = Zs0
   ;  Zs = [X|Zs0]
   ),
   list_vars_excluded(Xs,Vs,Zs0).

让我们做一些测试(使用GNU Prolog 1.4.4(：

？- lt(a(X，Y，c(c(，Z1(， a(X，Y，b(b，b(，Z2((.是的？- lt(a(X，Y，b(b，b(，Z1(， a(X，Y，c(c(，Z2((.不？- lt(a(X，Y1，c(c(，Z1(， a(X，Y2，b(b，b(，Z2((.未捕获的异常：错误(instantiation_error，LT/2(？- lt(a(X，Y1，b(b，b(，Z1(， a(X，Y2，c(c(，Z2((.未捕获的异常：错误(instantiation_error，LT/2(？- lt(b(b(， a(a，a((.是的？- lt(a(X(， a(Y((.未捕获的异常：错误(instantiation_error，LT/2(？- lt(X， 3(.未捕获的异常：错误(instantiation_error，LT/2(？- lt(X+a， X+b(.是的？- lt(X+a， Y+b(.未捕获的异常：错误(instantiation_error，LT/2(？- lt(a(X(， b(Y((.是的？- lt(a(X(， a(Y((.未捕获的异常：错误(instantiation_error，LT/2(？- lt(a(X(， a(X((.不

编辑 2015-05-06

更改了lt/2的实现，以使用T_alpha和T_omega，而不是两个新变量。

lt(X,Y)制作了两份X(X1和X2(和两份Y(Y1和Y2(。
X和Y的共享变量也由X1和Y1共享，以及由X2和Y2共享。
T_alpha排在所有其他术语(X1、X2、Y1、Y2(之前，即标准顺序。
T_omega排在标准顺序中的所有其他术语之后。
在复制的术语中，X但不Y(反之亦然(的变量与 T_alpha/T_omega 统一。
- 如果这对术语排序有影响，我们还无法决定排序。
- 如果没有，我们就完成了。

现在，@false给出的反例有效：

?- lt(X+1,1+2).
uncaught exception: error(instantiation_error,lt/2)
?- X=2, lt(X+1,1+2).
no

以下是我认为可能是一种工作方法的草图。考虑目标lt(X, Y)和term_variables(X, XVars), term_variables(Y, YVars)。

该定义的目的是确定进一步的实例化是否会更改术语顺序 (7.2(。因此，我们可能希望直接找出责任变量。由于term_variables/2以与术语顺序相关的相同方式遍历术语，因此以下情况成立：

如果存在更改术语顺序的实例化，则必须实例化以见证更改的变量位于列表前缀 XCs 、YCs分别为 XVars 和 YVars，并且

XCs、YCs、XVars和YVars相同，或者
XCs 和 YCs 在最后一个元素之前是相同的，或者
XCs 和 YCs 直到末尾是相同的，其中一个列表具有另一个元素，而另一个列表与其相应的变量列表 XVars 或 YVars 相同。

作为一个有趣的特例，如果XVars和YVars中的第一个元素不同，那么这些是唯一要测试相关性的变量。因此，这包括没有公共变量的情况，但它比这更通用。

下一个！这应该比我之前的尝试做得更好：

lt(X,Y) :-
   X == Y,
   (  X = Y
   -> term_variables(X,Xvars),
      term_variables(Y,Yvars),
      T_alpha is -(10.0^1000),  % HACK!
      functor(T_omega,z,255),   % HACK!
      copy_term(t(X,Y,Xvars,Yvars),t(X1,Y1,X1vars,Y1vars)),
      copy_term(t(X,Y,Xvars,Yvars),t(X2,Y2,X2vars,Y2vars)),
      copy_term(t(X,Y,Xvars,Yvars),t(X3,Y3,X3vars,Y3vars)),
      copy_term(t(X,Y,Xvars,Yvars),t(X4,Y4,X4vars,Y4vars)),
      maplist(=(T_alpha),X1vars), maplist(maybe_unify(T_omega),Y1vars),
      maplist(=(T_omega),X2vars), maplist(maybe_unify(T_alpha),Y2vars),
      maplist(=(T_omega),Y3vars), maplist(maybe_unify(T_alpha),X3vars), 
      maplist(=(T_alpha),Y4vars), maplist(maybe_unify(T_omega),X4vars),
      % do T_alpha and T_omega have an impact on the order?
      (  compare(Cmp,X1,Y1),     
         compare(Cmp,X2,Y2),
         compare(Cmp,X3,Y3),
         compare(Cmp,X4,Y4),
      -> Cmp = (<)                % no: demand that X @< Y holds
      ;  throw(error(instantiation_error,lt/2))
      )
   ;  throw(error(instantiation_error,lt/2))
   ).

辅助maybe_unify/2处理X和Y中出现的变量：

maybe_unify(K,X) :-
   (  var(X)
   -> X = K
   ;  true
   ).

使用 GNU-Prolog 1.4.4 进行检查：

?- lt(a(X,Y,c(c),Z1), a(X,Y,b(b,b),Z2)).
yes
?- lt(a(X,Y,b(b,b),Z1), a(X,Y,c(c),Z2)).
no
?- lt(a(X,Y1,c(c),Z1), a(X,Y2,b(b,b),Z2)).
uncaught exception: error(instantiation_error,lt/2)
?- lt(a(X,Y1,b(b,b),Z1), a(X,Y2,c(c),Z2)).
uncaught exception: error(instantiation_error,lt/2)
?- lt(b(b), a(a,a)).
yes
?- lt(a(X), a(Y)).
uncaught exception: error(instantiation_error,lt/2)
?- lt(X, 3).
uncaught exception: error(instantiation_error,lt/2)
?- lt(X+a, X+b).
yes
?- lt(X+a, Y+b).
uncaught exception: error(instantiation_error,lt/2)
?- lt(a(X), b(Y)).
yes
?- lt(a(X), a(Y)).
uncaught exception: error(instantiation_error,lt/2)
?- lt(a(X), a(X)).
no
?- lt(X+1,1+2).
uncaught exception: error(instantiation_error,lt/2)
?- lt(X+X+2,X+1+3).                                       % NEW
uncaught exception: error(instantiation_error,lt/2)

在这个答案中，我们提出了谓词safe_term_less_than/2，这是iso-prolog内置谓词(@<)/2的单调类似物(§8.4.1，"项小于"(。其主要特性是：

递归项的显式遍历。
基于prolog-coroutining设施，特别是when/2。
- 比较可能会逐渐进行：
  - 实例化不足时"冻结">
  - 每当最重要术语的实例化发生变化时"唤醒">
- 比较的当前前线表示为显式 (LIFO( 堆栈。
- 当前状态直接围绕剩余目标传递。

以下代码已在 sicstus-prolog 版本 4.3.2 上开发和测试：

safe_term_less_than(L, R) :-                    % exported predicate
   i_less_than_([L-R]).

上述safe_term_less_than/2定义基于以下辅助谓词：

i_less_than_([L-R|LRs]( ：-   Cond = (？=(L，R( ; nonvar(L(，nonvar(R((，   when(Cond， i_lt_step_(L，R，LRs((.i_lt_step_(L， R， LRs( ：-   ( L == R   -> i_less_than_(LRs(   ; term_itype(L， L_type(，      term_itype(R， R_type(，      比较(Ord， L_type， R_type(，      ord_lt_step_(Ord， L， R， LRs(   ).term_itype(V， T( ：-   ( var(V( -> 抛出(错误(instantiation_error，_((   ; 浮点数(V( -> T = t1_float(V(   ; 整数(V( -> T = t2_integer(V(   ; 可调用(V( -> T = t3_callable(A，F(， 函子(V， F， A(   ;                抛出(错误(system_error，_((   ).ord_lt_step_(<， _， _， _(.ord_lt_step_(=， L， R， LRs( ：-   ( 化合物(L(   -> L =..[_|Ls]，      R =..[_|Rs]，      短语(args_args_paired(Ls，Rs(， LRs0， LRs(，      i_less_than_(LRs0(   ; i_less_than_(LRs(   ).args_args_paired([]， []( --> []。args_args_paired([L|Ls]， [R|Rs]( --> [L-R]， args_args_paired(Ls， Rs(.

示例查询：

| ？- safe_term_less_than(X， 3(.序：trig_nondif(X，3，_A，_B(，prolog：trig_or([_B，X]，_A，_A(，prolog：when(_A，(？=(X，3(;nonvar(X(，nonvar(3((，user：i_lt_step_(X，3，[](( ？是的| ？- safe_term_less_than(X， 3(， X = 4.不| ？- safe_term_less_than(X， 3(， X = 2.X = 2 ？ ;不| ？- safe_term_less_than(X， a(.prolog：trig_nondif(X，a，_A，_B(，prolog：trig_or([_B，X]，_A，_A(，prolog：when(_A，(？=(X，a(;nonvar(X(，nonvar(a((，user：i_lt_step_(X，a，[](( ？ ;不| ？- safe_term_less_than(X， a(， X = a.不| ？- safe_term_less_than(X+2， Y+1(， X = Y.不

与之前的答案相比，我们观察到：

剩余目标的"文本量"似乎有点"臃肿"。
查询?- safe_term_less_than(X+2, Y+1), X = Y.失败 - 就像它应该的那样！

这个答案是我之前提出的safe_term_less_than/2答案的后续。

下一步是什么？compare/3的一个安全变体 - 难以想象地称为scompare/3：

比较(Ord， L， R( ：-   i_scompare_ord([L-R]， Ord(.i_scompare_ord([]， =(.i_scompare_ord([L-R|Ps]， X( ：-   when((？=(L，R(;nonvar(L(，nonvar(R((， i_one_step_scompare_ord(L，R，Ps，X((.i_one_step_scompare_ord(L， R， LRs， Ord( ：-   ( L == R   -> scompare_ord(LRs， Ord(   ; term_itype(L， L_type(，      term_itype(R， R_type(，      比较(Rel， L_type， R_type(，      ( Rel \== (=(      -> Ord = rel      ; 化合物(L(      -> L =..[_|Ls]，         R =..[_|Rs]，         短语(args_args_paired(Ls，Rs(， LRs0， LRs(，         i_scompare_ord(LRs0， Ord(      ; i_scompare_ord(LRs ， Ord(      )   ).

谓词term_itype/2和args_args_paired//2与前面定义的谓词相同。

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

8.4 术语比较

7.2 术语顺序

7.12.2 错误分类

定义

显式术语遍历(参考实现(

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

理由

缺点

编辑 2015-05-06

相关内容

最新更新

热门标签：