Prolog

Question

给定一组通过谓词 parent/2 表示父子关系的事实，在定义关系 "progenitor"(ancestor ) 与谓词 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

主要区别在于两者的终止属性，前提是关系中存在一些循环。为了理解这一点，我将使用 failure-slice 将程序缩减到其本质 w.r.t。终止。

pred1(X,Z) :- false, parent(X,Z).
pred1(X,Z) :- parent(X,Y), pred1(Y,Z). % Z has no influence

pred2(X,Z) :- false, parent(X,Z).
pred2(X,Z) :- parent(Y,Z), pred2(X,Y). % X has no influence

对于pred1/2，第二个参数对终止完全没有影响，而在pred2/2中，第一个参数没有影响。要看到这一点，请尝试使用以下事实的原始定义：

parent(a,a).

?- pred1(b, _), false.  % terminates
?- pred2(b, _), false.  % loops

?- pred1(_, b), false.  % loops
?- pred2(_, b), false.  % terminates

有关避免此类循环的一般方法，请参阅 closure/3。

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

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

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

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

在此片段中，第一个参数仅被传递。所以，不管参数是什么，程序都会循环！

?- pred3(b,b), false.  % loops

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

Prolog - 2 ways for progenitor predicate implementation

parent-child

failure-slice

transitive-closure