Многие предикаты по существу используют некоторую форму транзитивного замыкания, но только для того, чтобы обнаружить, что окончание должно быть исправлено. Почему бы не решить эту проблему раз и навсегда с помощью closure0/3
:
:- meta_predicate closure0(2,?,?).
:- meta_predicate closure(2,?,?).
:- meta_predicate closure0(2,?,?,+). % internal
closure0(R_2, X0,X) :-
closure0(R_2, X0,X, [X0]).
closure(R_2, X0,X) :-
call(R_2, X0,X1),
closure0(R_2, X1,X, [X1,X0]).
closure0(_R_2, X,X, _).
closure0(R_2, X0,X, Xs) :-
call(R_2, X0,X1),
non_member(X1, Xs),
closure0(R_2, X1,X, [X1|Xs]).
non_member(_E, []).
non_member(E, [X|Xs]) :-
dif(E,X),
non_member(E, Xs).
Существуют ли случаи, когда это определение не может быть использовано для реализации транзитивного закрытия?
Почему dif/2?
Чтобы ответить на комментарий @WouterBeek в деталях: dif/2
или iso_dif/2
идеальны, потому что они могут показывать или сигнализировать о потенциальных проблемах. Однако в текущих реализациях цикл верхнего уровня часто скрывает фактические проблемы. Рассмотрим цель closure0(\_^_^true,a,b)
, которая, безусловно, сама по себе проблематична. При использовании следующих систем фактическая проблема непосредственно не видна.
| ?- closure0(\_^_^true,a,b). % SICStus
yes
?- closure0(\_^_^true,a,b). % SWI
true ;
true ;
true ...
Оба цикла верхнего уровня не показывают того, что мы действительно хотим видеть: оборванных ограничений. В SICStus нам нужна псевдо-переменная для создания некоторой подстановки, в SWI запрос должен быть обернут call_residue_vars/2
. Таким образом, теперь отображаются все переменные с ограничениями.
| ?- closure0(\_^_^true,a,b), Alt=t. % SICStus
Alt = t ? ;
Alt = t,
prolog:dif(_A,a),
prolog:dif(b,_A) ? ;
Alt = t,
prolog:dif(_A,a),
prolog:dif(_B,_A),
prolog:dif(_B,a),
prolog:dif(b,_B),
prolog:dif(b,_A) ...
?- call_residue_vars(closure0(\_^_^true,a,b),Vs). % SWI
Vs = [] ;
Vs = [_G1744, _G1747, _G1750],
dif(_G1744, a),
dif(b, _G1744) ;
Vs = [_G1915, _G1918, _G1921, _G1924, _G1927, _G1930, _G1933],
dif(_G1915, a),
dif(b, _G1915),
dif(_G1921, _G1915),
dif(_G1921, a),
dif(b, _G1921) ...