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

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

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

For pred1/2, the second argument has no influence on termination at all, whereas in pred2/2, the first argument has no influence. To see this, try the original definitions with the fact:

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

See closure/3 for a general approach to avoid such loops.

For completeness, here is another variation of transitive closure which has some conceptual advantages:

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.