Prolog - 2 способ реализации прародителя предиката

Question

Учитывая множество фактов, которые представляют родитель-потомок через предикат родителя/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 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