findall 的异常行为

Question

以下看起来很不寻常：

?- findall(X, member(X, [1, 2, 3]), X).
X = [1, 2, 3].

痕迹更是如此

?- trace, findall(X, member(X, [1, 2, 3]), X).
^  Call: (11) findall(_100058, member(_100058, [1, 2, 3]), _100058) ? creep
^  Exit: (11) findall([1, 2, 3], user:member([1, 2, 3], [1, 2, 3]), [1, 2, 3]) ? creep
X = [1, 2, 3]

根据 findall 的语义来思考这毫无意义。怎么回事？

Answer 1

我进行了一些代码研究，试图找出发生了什么。在 swi-prolog listing(findall, [source(true)]). 中给出以下代码：

findall(Templ, Goal, List) :-
    findall(Templ, Goal, List, []).

findall(Templ, Goal, List, Tail) :-
    setup_call_cleanup(
        '$new_findall_bag',
        findall_loop(Templ, Goal, List, Tail),
        '$destroy_findall_bag').

findall_loop在相应的文件中如下：

findall_loop(Templ, Goal, List, Tail) :-
    (   Goal,
        '$add_findall_bag'(Templ)   % fails
    ;   '$collect_findall_bag'(List, Tail)
    ).

查阅C源文件后，发现findall/4是在C-source('$new_findall_bag')中设置一个全局变量，findall_loop/4是在推Templ 当 Goal 成功时（使用 '$add_findall_bag'(Templ)）。当 Goal 失败时，Templ 未实例化，因此即使 List 和 Templ 是同一个变量，最终子句 '$collect_findall_bag'(List, Tail) 也会成功。

我们可以在trace中看到Templ通常是未实例化的。

?- trace, findall(X, member(X, [1, 2, 3]), Xs).
^  Call: (11) findall(_28906, member(_28906, [1, 2, 3]), _28916) ? creep
^  Exit: (11) findall(_28906, user:member(_28906, [1, 2, 3]), [1, 2, 3]) ? creep
Xs = [1, 2, 3].

所以找到 Templ 的所有实例以使 Goal 成功的过程与将所有这些实例收集到变量 List 的过程是分开的，因此我们可以使用相同的变量而不会导致和错误。但是写这样一个子句的语义对我来说意义不大。

编辑：类似的情况发生在 gprolog，其中收集解决方案的过程和检索解决方案的过程是分开的。相关的 Yap 代码看起来也很相似，但我无法安装它来检查。

Answer 2

为了扩展我的评论，这可能会有所帮助：

?- findall(X, member(X, [1, 2, 3]), Xs).
Xs = [1, 2, 3].

如果仔细观察，您会发现 Prolog（在本例中为 SWI）没有打印 X 的替换。这意味着查询成功时X没有被绑定。确实：

?- findall(X, member(X, [1, 2, 3]), Xs), var(X).
Xs = [1, 2, 3].

这并不意味着 X 永远不会 绑定而查询执行：

?- findall(X, ( member(X, [1, 2, 3]), writeln(X) ), Xs), var(X).
1
2
3
Xs = [1, 2, 3].

但是在生成所有解决方案之后，X 是未绑定的，可以绑定到其他一些值 -- 例如解决方案列表。这将适用于任何符合标准的 Prolog，因为该标准明确表示 findall 仅在创建解决方案列表后才尝试统一其第三个参数。它甚至包含一个在模板和实例化列表之间共享的示例：

findall(X, (X=1;X=2), [X, Y]).
   Succeeds, unifying X with 1, and Y with 2.

那么这个绑定和解除绑定是怎么操作的呢？使用 failure-driven 循环，如 rajashekar 在 SWI-Prolog 实现中的回答中所引用的那样。通常，后续谓词会绑定一些变量。当稍后某个时间点失败时（或者，等效地，用户在顶层提示时按 ;），回溯发生：它解除绑定变量以允许它们采用新值，然后重试一些目标。

findall里面发生的事情和你写下面的内容是一样的：

?- ( member(X, [1, 2, 3]), writeln(X), false ; true ), var(X).
1
2
3
true.

所以虽然 findall 很不纯，但所以不纯到完全 un-Prolog-like。其实我们可以自己写：

:- dynamic my_findall_bag/1.

my_findall(Template, Goal, Instances) :-
    % initialization
    retractall(my_findall_bag(_)),
    asserta(my_findall_bag([])),
    
    % collect solutions
    (   call(Goal),
        copy_term(Template, NewSolution),
        retract(my_findall_bag(PreviousSolutions)),
        asserta(my_findall_bag([NewSolution | PreviousSolutions])),
        % failure-driven loop: after saving the solution, force Goal to
        % generate a new one
        false
    ;   true ),

    % cleanup and finish; the saved solutions are in reversed order (newest
    % first), so reverse them
    retract(my_findall_bag(AllSavedSolutions)),
    reverse(AllSavedSolutions, Instances).

这符合预期：

?- my_findall(X, member(X, [1, 2, 3]), Xs).
Xs = [1, 2, 3].

甚至：

?- my_findall(X, member(X, [1, 2, 3]), X).
X = [1, 2, 3].

一个小问题是应该检查 Goal 的实例化。主要问题是所有 my_findall 调用共享同一个包，因此从 my_findall（或并行）内部调用 my_findall 将让你不开心。这可以使用某种 gensym 机制来解决，为每个 my_findall 运行提供进入数据库的唯一密钥。

至于跟踪输出，这是想要在一行中表达“您的目标已通过 such-and-such 绑定成功”的不幸结果。在成功的时候，是真，findall(X, ..., X)成功，是真，X = [1, 2, 3]，因此是真，目标的成功实例是findall([1, 2, 3], ..., [1, 2, 3])。

考虑：

forty_two(FortyTwo) :-
    var(FortyTwo),
    FortyTwo = 42.

my_call(Goal) :-
    format('about to call ~w~n', [Goal]),
    call(Goal),
    format('success: ~w~n', [Goal]).

例如：

?- my_call(forty_two(X)).
about to call forty_two(_2320)
success: forty_two(42)
X = 42.

所以 forty_two(42) 是 forty_two(X) 的后继实例。尽管 forty_two(42) 没有成功：

?- forty_two(42).
false.

在 X = 42 的环境中打印术语 forty_two(X) 打印 forty_two(42) 是 合乎逻辑的 。我认为问题是这种 合乎逻辑的 行为在所有 non-logical 发生的事情中显得很奇怪。

findall 的异常行为

Unusual behaviour of findall

prolog

prolog-findall