反身传递闭包的定义

Question

许多谓词本质上使用某种形式的传递闭包，但发现必须解决终止问题。为什么不使用 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或dif_si/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) ...

- false

---

为什么要使用 nonmember/2 而不是 \+ memberchk/2？这可能有一个很好的用例，但我自己想不出来。 - Wouter Beek

@WouterBeek：如果涉及变量，则\+ memberchk/2或\+member/2会产生错误的结果。使用dif/2或iso_dif/2的nonmember/2不会有这个问题。 - false

Answer 1

这很有用，但我认为还不够理想，因为我无法在创建路径的点处剪切重复路径。

考虑完全图K_n：

n_complete(N, Es) :-
    numlist(1, N, Ns),
    phrase(pairs(Ns), Es).

adjacent(Edges, X, Y) :- member(edge(X, Y), Edges).

pairs([]) --> [].
pairs([N|Ns]) --> edges(Ns, N), pairs(Ns).

edges([], _) --> [].
edges([N|Ns], X) --> [edge(X,N),edge(N,X)], edges(Ns, X).

以下查询现在具有超指数级运行时间，尽管可以在多项式时间内找到闭包：

?- length(_, N), n_complete(N, Es), portray_clause(N),
   time(findall(Y, closure0(adjacent(Es), 1, Y), Ys)),
   false.
1.
16 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 1982161 Lips)
2.
54 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 4548901 Lips)
3.
259 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 14499244 Lips)
4.
1,479 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 16219595 Lips)
5.
9,599 inferences, 0.000 CPU in 0.000 seconds (100% CPU, 27691393 Lips)
6.
70,465 inferences, 0.002 CPU in 0.002 seconds (100% CPU, 28911161 Lips)
7.
581,283 inferences, 0.020 CPU in 0.020 seconds (100% CPU, 29397339 Lips)
8.
5,343,059 inferences, 0.181 CPU in 0.181 seconds (100% CPU, 29488001 Lips)
9.
54,252,559 inferences, 1.809 CPU in 1.808 seconds (100% CPU, 29994536 Lips)
10.
603,682,989 inferences, 19.870 CPU in 19.865 seconds (100% CPU, 30381451 Lips)

如果能够用这个元谓词表达更高效地确定闭包的方法，那将是很好的。

例如，人们通常会使用 Warshall 算法在立方时间内计算闭包，并编写类似于以下代码的代码：

node_edges_closure(Node, Edges, Closure) :-
        warshall_fixpoint(Edges, [Node], Closure).

warshall_fixpoint(Edges, Nodes0, Closure) :-
        findall(Y, (member(X, Nodes0), adjacent(Edges, X, Y)), Nodes1, Nodes0),
        sort(Nodes1, Nodes),
        (   Nodes == Nodes0 -> Closure = Nodes0
        ;   warshall_fixpoint(Edges, Nodes, Closure)
        ).

相对于声明式的 closure0/3，这种方法存在一些缺点，但是它是可行的：

?- length(_, N), n_complete(N, Es), portray_clause(N),
   time(node_edges_closure(1, Es, Ys)),
   false.
1.
% 16 inferences, 0.000 CPU in 0.000 seconds (75% CPU, 533333 Lips)
2.
% 43 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 1228571 Lips)
3.
% 69 inferences, 0.000 CPU in 0.000 seconds (85% CPU, 1769231 Lips)
4.
% 115 inferences, 0.000 CPU in 0.000 seconds (89% CPU, 2346939 Lips)
5.
% 187 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 2968254 Lips)
6.
% 291 inferences, 0.000 CPU in 0.000 seconds (92% CPU, 3548780 Lips)
7.
% 433 inferences, 0.000 CPU in 0.000 seconds (95% CPU, 3866071 Lips)
8.
% 619 inferences, 0.000 CPU in 0.000 seconds (96% CPU, 4268966 Lips)
9.
% 855 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 4500000 Lips)
10.
% 1,147 inferences, 0.000 CPU in 0.000 seconds (98% CPU, 4720165 Lips)
etc.

- mat

---

不确定在一般情况下如何完成这个任务：只要有基础值，就可以想象得到，但是谁应该一直检查基础性呢？ - false