创建和使用显式列表 vs 遍历失败的枚举

Question

我经常遇到这个问题，但我从来不确定应该采用哪种方法。下面是处理一些季节事实的两种方法。

我想要弄清楚的是是否使用方法1或2以及每种方法的利弊，特别是对于大量的事实。

方法1似乎很浪费，因为事实是可用的，为什么要建立它们的列表（特别是一个大列表）。如果列表足够大，这肯定会有内存影响？而且它没有利用Prolog的自然回溯特性。

方法2利用回溯来为我递归，我猜它会更省内存，但通常这样做好的编程实践吗？它可能更难理解，并且可能会有其他副作用？

我能看到的一个问题是，每次调用“fail”时，我们失去了将任何东西传递回调用谓词的能力，例如，如果它是“methodtwo（SeasonResults）”，因为我们故意连续失败谓词。因此，“methodtwo”需要断言事实以存储状态。

推测方法2会更快，因为它没有（大量）列表处理要做？

我可以想象，如果我有一个列表，那么“methodone”就是正确的选择..或者总是这样吗？在任何情况下，使用“methodone”将列表断言为事实，然后使用方法2处理它们是否有意义？完全疯了吗？

但是，我也读到过，断言事实是一个非常“昂贵”的业务，所以即使对于大型列表，处理列表可能也是正确的选择？

有什么想法吗？或者有时使用一种而不是另一种，这取决于（什么）情况吗？例如，为了内存优化，使用方法2，包括断言事实，并为了速度使用方法1？

season(spring).
season(summer).
season(autumn).
season(winter).

 % Season handling
showseason(Season) :-
    atom_length(Season, LenSeason),
    write('Season Length is '), write(LenSeason), nl.

% -------------------------------------------------------------
% Method 1 - Findall facts/iterate through the list and process each
%--------------------------------------------------------------
% Iterate manually through a season list
lenseason([]).
lenseason([Season|MoreSeasons]) :-
    showseason(Season),
    lenseason(MoreSeasons).
    

% Findall to build a list then iterate until all done
methodone :-
    findall(Season, season(Season), AllSeasons),
    lenseason(AllSeasons),
    write('Done').
    
% -------------------------------------------------------------
% Method 2 - Use fail to force recursion
%--------------------------------------------------------------
methodtwo :-
    % Get one season and show it
    season(Season),
    showseason(Season),
    
    % Force prolog to backtrack to find another season
    fail.

% No more seasons, we have finished
methodtwo :-
    write('Done').

- magus

Answer 1

让我们看一下你的示例。它非常简单，所以我们将想象它更加复杂。但是，似乎你认为副作用是必不可少的。让我对此进行一些质疑：

在你的例子中，你发现了一个非常有趣的事实：所有季节的名称长度相同。这是一个多么惊人的洞见啊！但是请等一下，这真的是正确的吗？ 最直接验证这个事实的方法是：

?- season(S), atom_length(S,L). S = spring, L = 6 ; S = summer, L = 6 ; S = autumn, L = 6 ; S = winter, L = 6.

没有必要使用findall/3或write/1。

对于更多答案的情况，视觉检查是不可行的。想象一下有400个季节。但是我们可以通过以下方式进行验证：

?- season(S), atom_length(S,L), dif(L,6). false.

因此，我们现在确信没有长度不同的季节。

那就是我对你问题的第一个回答。

只要可以，尽量使用顶层shell而不是你自己的具有副作用的程序！尽可能避免副作用，这是从一开始就避免失败驱动循环的最佳方法。

坚持使用顶层shell还有更多原因：

- 如果你的程序可以在顶层轻松查询，那么添加测试用例将非常容易。 - 顶层shell被许多其他用户使用，因此经过了很好的测试。你自己编写的代码通常存在缺陷和未经测试。考虑约束条件。考虑浮点数的编写。你会对浮点数也使用write/1吗？编写浮点数的正确方式是什么，以便它们可以准确地读回来？在iso-prolog中有一种方法来做到这一点。答案如下：

在ISO中，writeq/1,2、write_canonical/1,2、write_term/2,3选项为quoted(true)可以保证浮点数的准确读取。也就是说，它们和(==)/2相等。

顶层shell显示有效的Prolog文本。事实上，答案本身就是一个查询！它可以被粘贴回到顶层 - 只会得到完全相同的答案。通过这种方式，您将学习Prolog更奇特但不可避免的细节，比如引用、转义和括号。否则，由于Prolog解析器通常非常宽容，学习语法几乎是不可能的。

你的程序很可能更适合声明性推理。

很可能，你的两个程序methodone和methodtwo是不正确的：你忘记在写完Done后换行了。所以methodone，methodone包含了一行错误的代码。如何轻松测试？

但让我们更深入地了解一下你的程序。对于失败驱动循环来说，典型的特点是它们最初只做“副作用”，但迟早会吸引更多的语义部分。在你的情况下，atom_length/2被隐藏在完全无法测试或推理的失败驱动循环中。

效率考虑

Prolog系统通常通过释放堆栈来实现失败。因此，失败驱动循环不需要垃圾收集器。这就是为什么人们认为失败驱动循环是高效的原因。然而，并非总是如此。对于像findall(A, season(A), As)这样的目标，每个A的答案都会被复制到某个空间中。对于类似原子的简单操作来说，这是一个微不足道的操作，但想象一下更大的术语。比如:

blam([]).
blam([L|L]) :- blam(L).
bigterm(L) :- length(L,64), blam(L).

在许多系统中，对于这个大项，使用findall/3或assertz/1会使系统冻结，因为观察到已经有一段时间了。

此外，像SWI、YAP、SICStus这样的系统确实拥有相当复杂的垃圾收集器。减少失败驱动循环的使用将有助于进一步改善这些系统，因为这会创造出更复杂的技术需求。

- false

Answer 2

方法一似乎很浪费，因为事实是已知的，为什么要构建它们的列表（尤其是一个大列表）。如果列表足够大，这肯定会有内存影响吧？

是的，方法一需要Θ(n)的内存。它的主要优点在于它是声明式的，即它具有明确的逻辑含义。

方法二，也称为“失败驱动循环”，使用常量内存，是过程性的，当您正在执行过程性（额外逻辑）任务时，可能更喜欢它；即，在I/O代码中使用它是可以的。

请注意，SWI-Prolog有第三种编写此循环的方式：

forall(season(S), showseason(S)).

只有当每个season(S)的绑定都成功时，此方法才有效。

- Fred Foo

---

谢谢 - 我不知道forall() - 那个我错过了。很好 - 那对我现在很有用。 - magus

@larsmans：但是forall/2本质上是一个失败驱动的循环。没有办法保留来自forall的绑定！也就是说，forall(A,B) ≡ \+ \+ forall(A,B)。 - false

@false: 是的，但不同的是FDL总是失败的，而“forall”可能会成功。对于实现循环来说，这已经足够了。 - Fred Foo

@larsmans：forall/2绝对比默认的失败驱动循环更好，后者无法区分成功和失败。也就是说，这个不可言状的doall(Goal) :- Goal, fail ; true.尽管如此，它仍然在本质上极其敏感于实例化。 - false

Answer 3

如果你已经在使用findall，为什么不也使用maplist呢：

findall(S, season(S), L), maplist( showseason, L).

两者都不属于纯逻辑Prolog核心。 使用这种方法，你需要为所有解决方案分配一个完整的列表。

你的第二种方法被称为“失败驱动循环”，这种方法没有什么问题，只是在回溯失败后无法获取先前的解决方案。这就是为什么findall是额外逻辑的原因。在内部，它可以通过断言存储其中间结果，并作为失败驱动循环进行实现。因此，第二种概念上更清晰，在不分配任何额外内存的情况下使用，通常用于顶级“驱动器”（即UI）谓词。

- Will Ness

---

maplist/2 是纯的和单调的（只要它仅调用纯的和单调的谓词），而 findall/3 则不是。 - false

你对maplist是纯粹的这一点是正确的，如果我们允许使用call/_的话。但从某种意义上说，使用特定目标调用maplist可以按照相同的框架在纯Prolog中编写。我不知道这里的"单调"是什么意思。 - Will Ness

call/1..8 是 ISO Prolog 中的概念。涉及到单调性：就像单调逻辑一样。例如，如果我们添加了一个新的事实，程序会发生什么？曾经为真的一切是否仍然保持为真？如果你使用了 findall/3 或否定，情况就不再是这样。Prolog 的纯粹内核是其单调子集，其中包括 call/1..8、dif/2 和许多约束条件。它不包含（==）/2、（+）/1、！、var/1、通用 if-then-else，以及所有那些我暂时想不起名字的具有副作用的内置函数... - false

为了完整起见，单调的另一个意义是什么？简单来说，如果 'G' 成立，那么 'G, ..., G' 也会成立吗？'var/1' 没有这种属性。但是 'nonvar/1' 和 'ground/1' 具有此属性（除了 Prolog 的所有纯部分）。 - false

谢谢你的答案，现在我明白了为什么在对它进行分析时，findall 是我代码中最慢的部分之一。因为它每次都在断言事实以建立列表。 - magus

@magus：许多实现不再将解决方案断言到数据库中。相反，它们会直接将它们复制到堆栈（也称为copystack）上。 - false