2

以下看起来很不寻常：

?- 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这个意义不大。到底是怎么回事？

4

2 回答 2

3

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

?- 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.

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

内部findall发生的事情与您编写以下内容时发生的事情相同：

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

因此，虽然findall非常不纯，但它并没有完全不纯，以至于完全不像 Prolog。其实我们可以自己写：

:- 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运行都将其唯一的密钥输入数据库。

至于跟踪输出，想要在一行上表达“您的目标通过某某绑定成功”是一个不幸的结果。在成功点上，成功是真的，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.

在带有prints的环境中打印该术语是合乎逻辑的。我认为问题在于，这种逻辑行为在这里发生的所有非逻辑事物中显得很奇怪。forty_two(X)X = 42forty_two(42)

于 2020-11-06T23:12:47.297 回答
1

我做了一些代码潜水，试图弄清楚发生了什么。在 swi-prologlisting(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 源文件后，我发现它在 C-source ( )findall/4中设置了一个全局变量，并在成功时将其推送(with )。当失败未实例化时，即使和是相同的变量，最终子句也会成功。'$new_findall_bag'findall_loop/4TemplGoal'$add_findall_bag'(Templ)GoalTempl'$collect_findall_bag'(List, Tail)ListTempl

我们可以在通常未实例化的跟踪中看到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代码看起来也很相似，但我无法安装它来检查。

于 2020-11-06T14:07:27.493 回答