Ответ 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 @Ошибка 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).

(Редактирование: с учетом замечаний Тудора Берариу: (i) отсутствие случая ошибки var/var, (ii) порядок по arity сначала, более того, fixing (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, где все переменные instanciated:

• В X2 переменные объединяются с 1.
• В Y2 переменные объединены с 0.

Итак, если соотношение X2 @< Y2 все еще выполняется, мы знаем, что мы не полагаемся на стандартный порядок состояний между переменными. В противном случае мы выставляем исключение, потому что это означает, что отношение 1 @< 0, которое ранее не происходило, заставило отношение терпеть неудачу.

Упущения

(на основе комментариев OP)

• lt(X+a,X+b) должен преуспеть, но создать ошибку.

  На первый взгляд можно подумать, что объединение переменных, которые встречаются в обоих терминах с одинаковым значением, например val, может исправить ситуацию. Однако в сравниваемых терминах могут быть другие случаи X, где это приводит к ошибочному суждению.

• lt(X,3) должен вызывать ошибку, но преуспеть.

  Чтобы исправить этот случай, нужно объединить X с чем-то большим, чем 3. В общем случае X должно принимать значение, большее любого другого возможного термина ¹. Практические ограничения в стороне, отношение @< не имеет максимума: составные термины больше, чем не-составные, и по определению составные термины могут быть сделаны произвольно большими.

Итак, этот подход не является окончательным, и я не думаю, что его можно легко исправить.

1. Заметим, что для любого заданного члена мы могли бы найти локально максимальные и минимальные члены, которых было бы достаточно для цели вопроса.

Ответ 2

Далее! Это должно сделать лучше, чем предыдущая попытка :

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)

Ответ 3

Третья попытка! Разработано и протестировано с помощью 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': "не нужно маркировать все vars"

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(Alpha,Omega) :-
    Alpha is -(10.0^1000),    % HACK!
    functor(Omega,z,255).     % HACK!

label_vars([],_,_).
label_vars([Alpha|Vs],Alpha,Omega) :- label_vars(Vs,Alpha,Omega).
label_vars([Omega|Vs],Alpha,Omega) :- label_vars(Vs,Alpha,Omega).

Ответ 4

Это не совсем оригинальный ответ, поскольку он основывается на @coredump answer.

Существует один тип запросов lt/2 (эталонная реализация, выполняющая явный обход терминов) не отвечает правильно:

| ?- lt(b(b), a(a,a)).

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

yes

Причина в том, что стандартный порядок терминов рассматривает арность перед сравнением имен функторов.

Во-вторых, 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)
     ).

Предикат lt_args(Xs, Ys) имеет значение true, если существует пара соответствующих аргументов Xi, 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)

Ответ 5

В этом ответе мы представляем предикат safe_term_less_than/2, монотонный аналог iso-prolog встроенный предикат (@<)/2 (§8.4.1, "срок меньше" ). Его основные свойства:

• Явный обход рекурсивных терминов.

• На основе prolog-coroutining объекты, в частности when/2.

  • Сравнение может прогрессировать постепенно:

    • "замораживать" всякий раз, когда создание экземпляра недостаточно [/li >
    • "просыпаться" всякий раз, когда изменяется изменение наиболее значимых терминов.

  • Текущая линия фронта сравнения представлена ​​как явный (LIFO) стек.

  • Текущее состояние напрямую передается по остаточным целям.

Следующий код был разработан и протестирован на sicstus-prolog версия 4.3.2:

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

Выше определения safe_term_less_than/2 основано на следующих вспомогательных предикатах:

Примеры запросов:

| ?- safe_term_less_than(X, 3).
prolog: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,[])) ? 
yes
| ?- safe_term_less_than(X, 3), X = 4.
no
| ?- safe_term_less_than(X, 3), X = 2.
X = 2 ? ;
no
| ?- 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,[])) ? ;
no
| ?- safe_term_less_than(X, a), X = a.
no
| ?- safe_term_less_than(X+2, Y+1), X = Y.
no

По сравнению с предыдущими ответами, мы наблюдаем:

• "Текстовый том" остаточных целей выглядит "раздутым".
• Запрос ?- safe_term_less_than(X+2, Y+1), X = Y. завершается неудачно - как и должно быть!

Ответ 6

Что такое heck! Я тоже сделаю это!

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)).
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

Редактировать 2015-05-06

Изменена реализация lt/2 для использования T_alpha и T_omega, а не две новые переменные.

• lt(X,Y) создает две копии X (X1 и X2) и две копии Y (Y1 и Y2).
• Общие переменные X и Y также разделяются X1 и Y1, а <<28 > и Y2.
• T_alpha встречается перед всеми другими терминами (в X1, X2, Y1, Y2) w.r.t. стандартный порядок.
• 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

Ответ 7

Вот эскиз того, что, по моему мнению, может быть рабочим подходом. Рассмотрим цель 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 отличаются друг от друга, то это единственные переменные, которые должны быть проверены на актуальность. Таким образом, это включает случай, когда нет общей переменной, но она даже более общая.

Ответ 8

Этот ответ следует на мой предыдущий, который представил safe_term_less_than/2.

Что дальше? Безопасный вариант compare/3 -универсально называется scompare/3:

Предикаты term_itype/2 и args_args_paired//2 такие же, как определенные ранее.