统一STO检测

在ISO Prolog中，统一只针对NSTO（不受发生检查）的情况定义。 背后的想法是涵盖主要在程序中使用并且实际上由所有Prolog系统支持的统一的情况。 更具体地说，ISO / IEC 13211-1：1995的内容如下：

7.3.3发生检查（STO）而不是主题
发生检查（NSTO）

一组方程（或两个项）是“可能发生的 –
检查“（STO）是否有办法进行
Herbrandalgorithm的步骤使得7.3.2g
发生。

一组方程（或两个方程）是“不受限制的”
发生检查“（NSTO），如果没有办法进行
通过Herbrandalgorithm的步骤
7.3.2克发生。

…

这一步7.3.2克读取：

g）如果有一个forms为X = t这样的方程
X是一个variables， t是一个非variables项
其中包含这个variables，然后退出失败（ 不是
统一的 ， 积极的发生检查 ）。

完整的algorithm被称为Herbrandalgorithm，通常被称为Martelli-Montanari统一algorithm ，它基本上是通过以非确定性方式重写一组方程来进行的。

请注意，新方程引入：

d）如果存在formsf（a ₁ ，a ₂ ，… a _N ）=的方程，
f（b ₁ ，b ₂ ，… b _N ），然后用方程组代替它
a _i = b _i 。

这意味着两个具有相同函子但不同元素的复合词将永远不会影响STO性。

这种非确定性使得STOtesting很难实现。 毕竟，testing是否需要发生检查是不够的，但是为了certificate对于执行algorithm的所有可能的方式，这种情况将不会发生。

这里是一个案例来说明情况：

?- A/B+C*D = 1/2+3*4. 

统一可能以A = 1开始，也可能以任何其他对开始，并以任何顺序继续。 为了确保NSTO的财产，必须确保没有可能产生STO情况的path。 考虑一个对于当前实现来说没有问题的情况，但这仍然是STO：

 ?- 1+A = 2+s(A). 

Prolog系统首先将这个等式重写为：

 ?- 1 = 2, A = s(A). 

现在，他们select

• 1 = 2 ，这使algorithm退出失败，或

• A = s(A)其中步骤g适用，STO性能被检测到。

我的问题是双重的。 首先它是关于unify_sto(X,Y) ISO Prolog中的一个实现（仅使用第一部分定义的内置函数 ），其中以下条件成立：

• 如果统一是STO，则unify_sto(X,Y)会产生错误，否则

• 如果unify_sto(X,Y)成功，那么X = Y成功

• 如果unify_sto(X,Y)失败，那么X = Y失败

而我的第二个问题是关于在这种情况下发布的具体错误。 参见ISO的错误类 。

---

以下是一个简单的步骤：所有的成功案例都被unify_with_occurs_check(X,Y)的成功所覆盖。 还有什么是NSTO失败和STO错误情况之间的区别。 这是事情开始变得困难…

Answer 1

第三次尝试。 这主要是以前的答案（已经有很多修改）的错误修正。 编辑：06/04/2015

当创build一个更通用的术语时，如果两个子项中的任何一个都是variables，那么我将这两个子项保留原样。 现在我在这种情况下通过调用term_general/2为“其他”子项build立一个更一般的术语。

 unify_sto(X,Y):- unify_with_occurs_check(X,Y) -> true ; ( term_general(X, Y, unify(X,Y), XG, YG), \+unify_with_occurs_check(XG,YG), throw(error(type_error(acyclic, unify(X,Y)),_)) ). term_general(X, Y, UnifyTerm, XG, YG):- (var(X) -> (XG=X, term_general(Y, YG)) ; (var(Y) -> (YG=Y, term_general(X, XG)) ; (( functor(X, Functor, Len), functor(Y, Functor, Len), X=..[_|XL], Y=..[_|YL], term_general1(XL, YL, UnifyTerm, NXL, NYL) ) -> ( XG=..[Functor|NXL], YG=..[Functor|NYL] ) ; ( XG=_, YG=_ ) ))). term_general1([X|XTail], [Y|YTail], UnifyTerm, [XG|XGTail], [YG|YGTail]):- term_general(X, Y, UnifyTerm, XG, YG), ( \+(unify_with_occurs_check(XG,YG)) -> throw(error(type_error(acyclic,UnifyTerm),_)) ; term_general1(XTail, YTail, UnifyTerm, XGTail, YGTail) ). term_general1([], [], _, [], []). term_general(X, XG):- (var(X) -> XG=X ; (atomic(X) -> XG=_ ; ( X=..[_|XL], term_general1(XL, XG) ))). term_general1([X|XTail], [XG|XGTail]):- term_general(X, XG), term_general1(XTail, XGTail). term_general1([], _). 

到目前为止，在这个问题中提到的unit testing：

 unit_tests:- member([TermA,TermB], [[_A+_B,_C+_D], [_E+_F, 1+2], [a(_G+1),a(1+_H)], [a(1), b(_I)], [A+A,a(B)+b(B)], [A+A,a(B,1)+b(B)]]), (unify_sto(TermA, TermB)->Unifies=unifies ; Unifies=does_not_unify), writeln(test(TermA, TermB, Unifies)), fail. unit_tests:- member([TermA,TermB], [[A+A,B+a(B)], [A+A,A+b(A)], [A+A,a(_)+b(A)], [1+A,2+s(A)], [a(1)+X,b(1)+s(X)]]), catch( ( (unify_sto(TermA, TermB)->true;true), writeln(test_failed(TermA, TermB)) ), E, writeln(test_ok(E))), fail. unit_tests. 

Answer 2

这里又一次尝试：

 unify_sto(X,Y):- unify_with_occurs_check(X,Y) -> true ; ( term_general(X, Y, XG, YG), \+(unify_sto1(XG,YG)), throw(error(type_error(acyclic,unify(X,Y)),_)) ). unify_sto1(X, Y):- unify_with_occurs_check(X,Y). unify_sto1(X, Y):- X\=Y. term_general(X, Y, XG, YG):- ((var(X) ; var(Y)) -> (XG=X, YG=Y) ; (( functor(X, Functor, Len), functor(Y, Functor, Len), X=..[_|XL], Y=..[_|YL], term_general1(XL, YL, NXL, NYL) ) -> ( XG=..[Functor|NXL], YG=..[Functor|NYL] ) ; ( XG=_, YG=_ ) )). term_general1([X|XTail], [Y|YTail], [XG|XGTail], [YG|YGTail]):- term_general(X, Y, XG, YG), term_general1(XTail, YTail, XGTail, YGTail). term_general1([], [], [], []). 

它首先尝试unify_with_occurs_check，如果不成功，则继续构build两个更一般的术语，遍历每个术语的结构。

• 如果两个术语都是一个variables，那么它们都保持原样。
• 如果两个词都是同一个primefaces，或者它们都是同一个函子和同义词的复合词，那么它就会穿越它的论点，为它们提供一个更一般的术语。
• 否则，它会为每个术语分配一个新的新variables。

然后再次尝试unify_with_occurs_check更一般的术语来testing非循环统一并相应地抛出错误。

[*]对于term_general1/4术语中的aritytesting是贪婪的，因为term_general1/4将会失败recursion，因为OP声称只使用这个链接的第一部分定义的内置谓词，不包含length/2 。 。 （ 编辑：在调用term_general1之前添加了两个functor/3来testing函数和函数，以便在它们的函数不匹配时不尝试内部检查）

例如：

 ?- unify_sto(s(1)+A,A+s(B)). A = s(1), B = 1 ?- unify_sto(1+A,2+s(A)). ERROR: Type error: `acyclic' expected, found `unify(1+_G5322,2+s(_G5322))' ?- unify_sto(a(1)+X,b(1)+s(X)). ERROR: Type error: `acyclic' expected, found `unify(a(1)+_G7068,b(1)+s(_G7068))' 

编辑06/02/2015：

上面的解决scheme查询失败：

 unify_sto(A+A,a(A)+b(A)). 

这是不会产生统一的错误。

这里有一个对每个子项都进行处理的algorithm的改进，一旦发现它就会产生错误：

 unify_sto(X,Y):- unify_with_occurs_check(X,Y) -> true ; ( term_general(X, Y, unify(X,Y), XG, YG), \+unify_with_occurs_check(XG,YG), throw(error(type_error(acyclic,unify(X,Y)),_)) ). unify_sto1(X, Y):- unify_with_occurs_check(X,Y). unify_sto1(X, Y):- X\=Y. term_general(X, Y, UnifyTerm, XG, YG):- ((var(X) ; var(Y)) -> (XG=X, YG=Y) ; (( functor(X, Functor, Len), functor(Y, Functor, Len), X=..[Functor|XL], Y=..[Functor|YL], term_general1(XL, YL, UnifyTerm, NXL, NYL) ) -> ( XG=..[Functor|NXL], YG=..[Functor|NYL] ) ; ( XG=_, YG=_ ) )). term_general1([X|XTail], [Y|YTail], UnifyTerm, [XG|XGTail], [YG|YGTail]):- term_general(X, Y, UnifyTerm, XG, YG), \+(unify_with_occurs_check(XG,YG))-> throw(error(type_error(acyclic,UnifyTerm),_)) ; term_general1(XTail, YTail, UnifyTerm, XGTail, YGTail). term_general1([], [], _, [], []). 

在原始答案中产生错误结果的查询的testing用例：

  ?- unify_sto(A+A,a(A)+b(A)). ERROR: Type error: `acyclic' expected, found `unify(_G6902+_G6902,a(_G6902)+b(_G6902))' ?- unify_sto(A+A, a(_)+b(A)). ERROR: Type error: `acyclic' expected, found `unify(_G5167+_G5167,a(_G5173)+b(_G5167))' 

Answer 3

这是我的尝试：

 unify_sto(X,Y):- unify_with_occurs_check(X,Y) -> true ; ( term_general(X, XG), term_general(Y, YG), \+(unify_sto1(XG,YG)), throw(error(type_error(acyclic,unify(X,Y)),_)) ). unify_sto1(X, Y):- unify_with_occurs_check(X,Y). unify_sto1(X, Y):- X\=Y. term_general(X, Y):- (var(X) -> Y=X ; (atomic(X) -> Y=_ ; ( X=..[Functor|L], term_general1(L, NL), Y=..[Functor|NL] ))). term_general1([X|XTail], [Y|YTail]):- term_general(X, Y), term_general1(XTail, YTail). term_general1([], []). 

它首先尝试unify_with_occurs_check ，如果不成功，则继续为每个参数build立一个更一般的术语，然后试图统一这个术语并testing它是否是循环的。 如果是循环types的非循环types的抛出。

例如：

 ?- unify_sto(1+A,2+s(A)). ERROR: Unhandled exception: error(type_error(acyclic,unify(1+_G3620,2+s(_G3620)))) 

Answer 4

这是我用来testing@ gusbro版本的版本。 这个想法是马尔泰利 – 蒙塔纳利的字面意思。 通过重写等式列表[X1=Y1,X2=Y2|Etc] ，某些重写规则立即应用 – 使用！ 承诺。 而对于某些规则，我不是那么肯定，所以我把它们作为原始algorithm不确定。

注意rewrite_sto/1会失败或产生一个错误。 我们对成功的案例不感兴趣，这个案件没有任何search。 另外，可以消除导致（即时）失败的等式！ 这有点不直观，但我们只在这里findSTO案例。

 unify_with_sto_check(X,Y) :- ( \+ unify_with_occurs_check(X, Y) -> rewrite_sto([X=Y]) % fails or error ; X = Y ). rewrite_sto(Xs0) :- select(X=Y, Xs0,Xs), ( X == Y ; nonvar(X), nonvar(Y), functor(X,F,A), \+ functor(Y,F,A) ; var(X), var(Y), X = Y ), !, rewrite_sto(Xs). rewrite_sto(Xs0) :- select(X=Y, Xs0, Xs1), nonvar(X), nonvar(Y), functor(X,F,A), functor(Y,F,A), !, X =.. [_|XArgs], Y =.. [_|YArgs], maplist(\Xi^Yi^(Xi=Yi)^true, XArgs, YArgs, XYs), append(XYs,Xs1,Xs), rewrite_sto(Xs). rewrite_sto(Xs0) :- select(X=Y, Xs0,Xs), ( var(X), nonvar(Y) -> unify_var_term(X, Y) ; nonvar(X), var(Y) -> unify_var_term(Y, X) ; throw(impossible) ), rewrite_sto(Xs). unify_var_term(V, Term) :- ( unify_with_occurs_check(V, Term) -> true ; throw(error(type_error(acyclic_term, Term), _)) ). 

Answer 5

在SWI-prolog中：

 unify_sto(X,Y) :- \+ unify_with_occurs_check(X,Y), X = Y, !, writeln('Error: NSTO failure'), fail. unify_sto(X,Y) :- X = Y. 

给出以下结果：

 [debug] ?- unify_sto(X,s(X)). Error: NSTO failure false. [debug] ?- unify_sto(X,a). X = a. [debug] ?- unify_sto(b,a). false.