Many predicates essentially use some form of transitive closure, only to discover that termination has to be addressed too. Why not solve this once and forever with 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).
Are there cases where this definition cannot be used for implementing transitive closure?
Why dif/2?
To answer @WouterBeek's comment in detail: dif/2
or dif_si/2
are ideal, because they are able to show or signal potential problems. However, in current implementations the top-level loop often hides the actual issues. Consider the goal closure0(\_^_^true,a,b)
which certainly is quite problematic in itself. When using the following systems the actual problem is directly not visible.
| ?- closure0(\_^_^true,a,b). % SICStus
yes
?- closure0(\_^_^true,a,b). % SWI
true ;
true ;
true ...
Both top-level loops do not show what we actually want to see: the dangling constraints. In SICStus we need a pseudo variable to produce some substitution, in SWI, the query has to be wrapped with call_residue_vars/2
. In this manner all variables that have constraints attached are now shown.
| ?- 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) ...
It's useful, but in my opinion not yet ideal because I cannot cut duplicate paths at the point of their creation.
Consider, with the complete graph K_n:
The following query now has super-exponential runtime, although the closure can actually be found in polynomial time:
It would be great if a more efficient way to determine the closure could also be expressed with this meta-predicate.
For example, one would normally simply use Warshall's algorithm to compute the closure in cubic time, with code similar to:
Yielding (with all drawbacks in comparison to the nicely declarative
closure0/3
):