Prolog - 祖谓词实现的 2 种方法

Question

给定一组通过谓词Parent/2表示父子关系的事实，使用谓词pred1/2和pred2/2定义关系“祖先”（祖先）时有什么区别，如下所示？

pred1(X,Z) :- parent(X,Z).
pred1(X,Z) :- parent(X,Y), pred1(Y,Z).

pred2(X,Z) :- parent(X,Z).
pred2(X,Z) :- parent(Y,Z), pred2(X,Y).

Answer 1

主要区别在于两者的终止属性，前提是关系中存在一些循环。为了理解这一点，我将使用一个失败切片，它将程序在终止时缩减到其本质。

pred1(X,Z) :- false，父级(X,Z)。
pred1(X, Z ) :- 父级(X,Y), pred1(Y, Z )。% Z没有影响

pred2(X,Z) :- false，父级(X,Z)。
pred2( X ,Z) :- 父级(Y,Z), pred2( X ,Y)。% X没有影响

对于pred1/2，第二个参数对终止完全没有影响，而在 中pred2/2，第一个参数没有影响。要了解这一点，请尝试原始定义和事实：

父级（a，a）。

?- pred1(b, _), false。
   错误的。% 终止
?- pred2(b, _), false。
   循环。
?- pred1(_, b), false。
   循环。
?- pred2(_, b), false。
   错误的。% 终止

请closure/3参阅 参考资料 来避免此类循环的一般方法。

为了完整起见，这是传递闭包的另一种变体，它具有一些概念上的优点：

pred3(X,Z) :- parent(X,Z).
pred3(X,Z) :- pred3(X,Y), pred3(Y,Z).

唉，它的终止特性最差。事实上，它永远不会终止，正如以下片段所证明的那样：

pred3(X,Z) :- false，父级(X,Z)。
pred3(X,Z) :- pred3(X,Y), false , pred3(Y,Z)。

在此片段中，仅传递第一个参数。因此，无论参数是什么，程序总是会循环！

?- pred3(b,b), false。
   循环。