Pertanyaan Bagaimana menentukan (dan memberi nama) predikat perbandingan jangka aman yang sesuai dalam ISO Prolog?


Urutan istilah standar (ISO / IEC 13211-1 7.2 Urutan istilah) didefinisikan di atas semua istilah - termasuk variabel. Meskipun ada kegunaan yang bagus untuk ini - pikirkan penerapan setof/3, ini membuat banyak penggunaan yang bersih dan logis dari built-in di 8.4 Istilah perbandingan mimpi buruk deklaratif dengan imp (bentuk singkat untuk konstruk imperatif) di sekelilingnya. 8.4 Fitur perbandingan Term:

8.4 Perbandingan istilah

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

Untuk memberikan contoh, pertimbangkan:

?- X @< a.
true.

Ini berhasil, karena

7.2 Pesanan jangka

Sebuah pemesanan term_precedes (3.181) mendefinisikan apakah atau
  bukan sebuah istilah X istilah mendahului istilah Y.

Jika X dan Y adalah istilah yang identik X  term_precedes  Y
  dan Y  term_precedes  X keduanya salah.

Jika X dan Y memiliki tipe yang berbeda: X term_precedes Y jika
  jenis X mendahului jenis Y dalam urutan berikut:
variable mendahului floating point mendahului integer
  mendahului atom mendahului compound.

CATATAN - Predikat bawaan yang menguji pengaturan istilah
  didefinisikan dalam 8.4.
  ...

Dan dengan demikian semua variabel lebih kecil dari a. Tapi sekali X digunakan untuk:

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

hasilnya menjadi tidak valid.

Jadi itulah masalahnya. Untuk mengatasi hal ini, seseorang mungkin menggunakan batasan, atau tetap berpegang pada perilaku inti saja dan oleh karena itu menghasilkan suatu instantiation_error.

7.12.2 Klasifikasi kesalahan

Kesalahan diklasifikasikan menurut bentuk Error_term:

a) Akan ada Kesalahan Instansiasi ketika sebuah
    argumen atau salah satu komponennya adalah variabel, dan sebuah
    Diperlukan argumen atau komponen yang diperlukan. Memiliki
    formulir instantiation_error.

Dengan cara ini kita tahu pasti bahwa hasil didefinisikan dengan baik selama tidak ada kesalahan instantiasi terjadi.

Untuk (\==)/2, sudah ada juga dif/2 yang menggunakan batasan atau iso_dif/2 yang menghasilkan kesalahan instantiasi bersih.

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

Jadi apa pertanyaan saya tentang: Bagaimana mendefinisikan (dan nama) prediktif sesuai predikat relatif yang sesuai di ISO Prolog? Idealnya, tanpa istilah traversal eksplisit. Mungkin untuk memperjelas: Di atas iso_dif/2 tidak menggunakan istilah traversal eksplisit. Kedua (\==)/2 dan (\=)/2 melintasi istilah secara internal, tetapi biaya overhead untuk ini sangat rendah dibandingkan dengan traversal eksplisit dengan (=..)/2 atau functor/3, arg/3.


32
2017-11-03 18:33


asal


Jawaban:


iso_dif/2 jauh lebih sederhana untuk diterapkan daripada perbandingan:

  • Built-in \= operator tersedia
  • Anda sekarang persis apa argumen untuk menyediakan\=

Definisi

Berdasarkan komentar Anda, perbandingan yang aman berarti bahwa pesanan tidak akan berubah jika variabel dalam kedua subketer sudah ditentukan. Jika kita menyebutkan perbandingannya lt, kami punya misalnya:

  • lt(a(X), b(Y)) : selalu berlaku untuk semua X dan Y, karena a @< b
  • lt(a(X), a(Y)): kami tidak tahu pasti: intanciation_error
  • lt(a(X), a(X)) : selalu gagal, karena X @ <X gagal

Seperti yang dikatakan dalam komentar, Anda ingin membuang kesalahan jika, ketika melakukan penelusuran berdampingan dari kedua istilah, pasangan kata pertama (berpotensi) yang diskriminatif berisi:

  • dua variabel tidak identik (lt(X,Y))
  • sebuah variabel dan non-variabel (lt(X,a), atau lt(10,Y))

Tetapi pertama-tama, mari kita tinjau kemungkinan pendekatan yang tidak ingin Anda gunakan:

  • Definisikan fungsi perbandingan istilah-traversal eksplisit. Saya tahu Anda lebih suka tidak, karena alasan kinerja, tapi tetap saja, ini adalah pendekatan yang paling mudah. Saya akan merekomendasikan untuk melakukannya, sehingga Anda memiliki implementasi referensi untuk dibandingkan dengan pendekatan lain.

  • Gunakan batasan untuk memiliki perbandingan yang tertunda: Saya tidak tahu cara melakukannya menggunakan ISO Prolog, tetapi dengan mis. ECLiPSe, saya akan menangguhkan perbandingan sebenarnya atas set variabel uninstanciated (menggunakan term_variables/2), hingga tidak ada lagi variabel. Sebelumnya, saya juga menyarankan menggunakan coroutine / 0 predikat, tetapi saya mengabaikan fakta bahwa itu tidak mempengaruhi @< operator (saja <).

    Pendekatan ini tidak membahas masalah yang persis sama seperti yang Anda gambarkan, tetapi sangat dekat. Salah satu keuntungannya adalah bahwa ia tidak memberikan pengecualian jika nilai akhir yang diberikan kepada variabel memenuhi perbandingan, sedangkan lt melempar satu ketika tidak tahu sebelumnya.

Traversal jangka eksplisit (implementasi referensi)

Berikut ini adalah implementasi dari pendekatan traversal jangka eksplisit untuk lt, versi aman dari @<. Harap tinjau untuk memeriksa apakah ini yang Anda harapkan. Saya mungkin melewatkan beberapa kasus. Saya tidak yakin apakah ini sesuai dengan ISO Prolog, tetapi itu bisa diperbaiki juga, jika Anda mau.

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

(Edit: dengan mempertimbangkan komentar Tudor Berariu: (i) hilang kasus kesalahan var / var, (ii) order oleh arity terlebih dahulu, terlebih lagi, memperbaiki (i) memungkinkan saya untuk menghapus subsumes_term untuk daftar. Terima kasih.)

Traversal istilah implisit (tidak berfungsi)

Inilah usaha saya untuk mencapai efek yang sama tanpa merusak istilah.

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

Alasan

Seandainya X @< Y berhasil. Kami ingin memeriksa bahwa relasi tidak bergantung pada beberapa variabel terinisialisasi. Jadi, saya menghasilkan salinan masing-masing X2 dan Y2 dari X dan Y, di mana semua variabel ditentukan:

  • Di X2, variabel disatukan dengan 1.
  • Di Y2, variabel disatukan dengan 0.

Jadi, jika hubungannya X2 @< Y2 masih berlaku, kita tahu bahwa kita tidak bergantung pada istilah pemesanan standar antar variabel. Kalau tidak, kami melempar pengecualian, karena itu berarti bahwa a 1 @< 0 Relasi, yang sebelumnya tidak terjadi, membuat relasi gagal.

Kekurangan

(berdasarkan komentar OP)

  • lt(X+a,X+b) harus berhasil tetapi menghasilkan kesalahan.

    Pada pandangan pertama, orang mungkin berpikir bahwa variabel pemersatu yang terjadi di kedua istilah dengan nilai yang sama, katakan val, dapat memperbaiki situasi. Namun, mungkin ada kejadian lain X dalam hal yang dibandingkan di mana hal ini mengarah pada penilaian yang tidak menentu.

  • lt(X,3)seharusnya menghasilkan kesalahan tetapi berhasil.

    Untuk memperbaiki kasus itu, seseorang harus bersatu X dengan sesuatu yang lebih besar dari 3. Dalam kasus umum, X harus mengambil nilai itu lebih besar dari istilah lain yang mungkin1. Keterbatasan praktis samping, yang @< Relasi tidak memiliki maksimum: istilah gabungan lebih besar daripada yang non-majemuk, dan menurut definisi, istilah majemuk dapat dibuat secara arbitrer.

Jadi, pendekatan itu tidak konklusif dan saya rasa itu tidak bisa dikoreksi dengan mudah.


1: Perlu dicatat bahwa untuk istilah apa pun, kami dapat menemukan istilah lokal maksimal dan minimal, yang akan mencukupi untuk tujuan pertanyaan.


7
2017-11-14 15:20



Berikutnya! Ini harus lebih baik daripada saya usaha sebelumnya:

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

The auxiliary maybe_unify/2 berurusan dengan variabel yang terjadi di keduanya X dan Y:

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

Memeriksa dengan 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)

5
2018-05-07 19:35



Percobaan ketiga! Dikembangkan dan diuji dengan GNU Prolog 1.4.4.


Pameran 'A': "sesederhana itu"

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

Pameran 'B': "tidak perlu label semua 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)
   ).

Beberapa kode bersama:

alpha_omega (Alpha, Omega): -
    Alpha adalah - (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).

5
2018-05-09 18:26



Ini bukan jawaban yang sepenuhnya asli, karena dibangun di atas @ coredump's menjawab.

Ada satu jenis pertanyaan lt/2 (implementasi referensi melakukan traversal istilah eksplisit) gagal menjawab dengan benar:

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

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

yes

Alasannya adalah bahwa urutan standar istilah menganggap arity sebelum membandingkan nama functor.

Kedua, lt/2 tidak selalu melempar instatiation_error ketika datang ke membandingkan variabel:

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

no

Saya menulis di sini kandidat lain untuk implementasi eksplisit referensi:

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

Predikatnya lt_args(Xs, Ys) benar ketika ada sepasang argumen yang sesuai Xi, Yi seperti yang lt(Xi, Yi) dan Xj == Yj untuk semua pasangan sebelumnya Xj, Yj (sebagai contoh lt_args([a,X,a(X),b|_], [a,X,a(X),c|_]) adalah benar).

Beberapa contoh kueri:

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

4
2018-01-11 13:37



Dalam jawaban ini kami menyajikan predikat safe_term_less_than/2, analog monotonik ke  predikat bawaan  (@<)/2  (§8.4.1, "istilah kurang dari"). Sifat utamanya adalah:

  • Eksplisit traversal dari istilah rekursif.
  • Berdasarkan  fasilitas, khususnya when/2.

    • Perbandingannya bisa berlanjut bertahap:

      • "membekukan" setiap kali Instansiasi tidak cukup
      • "Bangun" setiap kali Instansiasi dari istilah yang paling signifikan berubah
    • Sekarang garis depan perbandingan digambarkan sebagai tumpukan eksplisit (LIFO).

    • Keadaan saat ini secara langsung melewati tujuan sisa.

Kode berikut telah dikembangkan dan diuji  versi 4.3.2:

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

Definisi di atas safe_term_less_than/2didasarkan pada predikat tambahan berikut:

i_less_than _ ([L-R | LRs]): -
   Cond = (? = (L, R); nonvar (L), nonvar (R)),
    kapan(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),
       membandingkan(Ord, L_type, R_type),
      ord_lt_step_ (Ord, L, R, LRs)
   ).

term_itype (V, T): -
   ( var(V) -> melemparkan(kesalahan(instantiation_error, _))
   ; mengapung(V) -> T = t1_float (V)
   ; bilangan bulat(V) -> T = t2_integer (V)
   ; callable(V) -> T = t3_callable (A, F), functor(V, F, A)
   ; throw (error (system_error, _))
   ).

ord_lt_step _ (<, _, _, _).
ord_lt_step _ (=, L, R, LRs): -
   ( senyawa(L)
   -> L = .. [_ | Ls],
      R = .. [_ | Rs],
       frasa(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).

Contoh kueri:

| ? - 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)), pengguna: i_lt_step_ (X, 3, []))?
iya nih
| ? - safe_term_less_than (X, 3), X = 4.
tidak
| ? - safe_term_less_than (X, 3), X = 2.
X = 2? ;
tidak
| ? - 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)), pengguna: i_lt_step_ (X, a, []))? ;
tidak
| ? - safe_term_less_than (X, a), X = a.
tidak
| ? - safe_term_less_than (X + 2, Y + 1), X = Y.
tidak

Dibandingkan dengan jawaban sebelumnya, kami mengamati:

  • "Volume teks" dari gol sisa tampak seperti "kembung".
  • Kueri ?- safe_term_less_than(X+2, Y+1), X = Y. gagal — seperti seharusnya!

4
2017-12-01 18:11



Apa itu? heck! Saya akan mencobanya juga!

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

Beberapa hal tambahan lainnya:

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

Mari kita melakukan beberapa tes (dengan GNU Prolog 1.4.4):

? - lt (a (X, Y, c (c), Z1), a (X, Y, b (b, b), Z2)).
iya nih
? - lt (a (X, Y, b (b, b), Z1), a (X, Y, c (c), Z2)).
tidak
? - lt (a (X, Y1, c (c), Z1), a (X, Y2, b (b, b), Z2)).
eksepsi yang tidak tertangkap: kesalahan (instantiation_error, lt / 2)
? - lt (a (X, Y1, b (b, b), Z1), a (X, Y2, c (c), Z2)).
eksepsi yang tidak tertangkap: kesalahan (instantiation_error, lt / 2)
? - lt (b (b), a (a, a)).
iya nih
? - lt (a (X), a (Y)).
eksepsi yang tidak tertangkap: kesalahan (instantiation_error, lt / 2)
? - lt (x, 3).
eksepsi yang tidak tertangkap: kesalahan (instantiation_error, lt / 2)
? - lt (X + a, X + b).
iya nih
? - lt (X + a, Y + b).
eksepsi yang tidak tertangkap: kesalahan (instantiation_error, lt / 2)
? - lt (a (X), b (Y)).
iya nih
? - lt (a (X), a (Y)).
eksepsi yang tidak tertangkap: kesalahan (instantiation_error, lt / 2)
? - lt (a (X), a (X)).
tidak

Edit 2015-05-06

Mengubah implementasi lt/2 menggunakan T_alpha dan T_omega, bukan dua variabel baru.

  • lt(X,Y) membuat dua salinan X (X1 dan X2) dan dua salinan Y (Y1 dan Y2).
  • Variabel bersama X dan Yjuga dibagikan oleh X1 dan Y1, dan oleh X2 dan Y2.
  • T_alpha datang sebelum semua persyaratan lainnya (dalam X1, X2, Y1, Y2) w.r.t. urutan standar.
  • T_omega datang setelah  semua istilah lain dalam tatanan standar.
  • Dalam istilah yang disalin, variabel yang ada di dalamnya X tapi tidak masuk Y (dan sebaliknya) disatukan dengan T_alpha / T_omega.
    • Jika ini punya dampak pada pemesanan jangka, kita belum bisa memutuskan pemesanan.
    • Jika tidakkami selesai.

Sekarang, counterexample yang diberikan oleh @false berfungsi:

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

3
2018-05-05 10:39



Berikut ini adalah sketsa dari apa yang saya yakini sebagai pendekatan kerja. Pertimbangkan tujuannya lt(X, Y) dan term_variables(X, XVars), term_variables(Y, YVars).

Tujuan dari definisi ini adalah untuk menentukan apakah atau tidak instantiation lebih lanjut mungkin mengubah urutan istilah (7.2). Jadi kita mungkin ingin mencari tahu variabel yang bertanggung jawab secara langsung. Sejak term_variables/2 melintasi sebuah istilah dengan cara yang sama yang relevan dengan urutan waktu, yang berikut ini berlaku:

Jika ada instantiation yang mengubah urutan istilah, maka variabel yang harus dipakai untuk menyaksikan perubahan yang berada di daftar awalan XCs, YCs dari XVars dan YVars masing-masing, dan juga

  1. XCs, YCs, XVars, dan YVars identik, atau

  2. XCs dan YCs identik hingga elemen terakhir, atau

  3. XCs dan YCs identik hingga akhir di mana satu daftar memiliki elemen lebih lanjut, dan daftar lainnya identik dengan daftar variabel terkait XVars atau YVars.

Sebagai kasus khusus yang menarik, jika elemen pertama di XVars dan YVars berbeda, maka itu adalah satu-satunya variabel yang akan diuji untuk relevansi. Jadi ini termasuk kasus di mana tidak ada variabel umum, tetapi bahkan lebih umum dari itu.


3
2018-05-07 08:40



Jawaban ini mengikuti saya yang sebelumnya yang disajikan safe_term_less_than/2.

Apa berikutnya? Varian yang aman dari compare/3—Disebut secara tak terduga scompare/3:

scompare (Ord, L, R): -
   i_scompare_ord ([L-R], Ord).

i_scompare_ord ([], =).
i_scompare_ord ([L-R | Ps], X): -
    kapan((? = (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),
       membandingkan(Rel, L_type, R_type),
      (Rel \ == (=)
      -> Ord = Rel
      ; senyawa(L)
      -> L = .. [_ | Ls],
         R = .. [_ | Rs],
          frasa(args_args_paired (Ls, Rs), LRs0, LRs),
         i_scompare_ord (LRs0, Ord)
      ; i_scompare_ord (LRs, Ord)
      )
   ).

Predikatnya term_itype/2 dan args_args_paired//2 sama seperti didefinisikan sebelumnya.


3
2017-12-02 19:50