使用手动列表迭代与通过失败递归的优缺点是什么

Question

我一直反对这一点,我无法确定攻击它的方法.以下是处理一些季节事实的两种方法.

我想弄清楚的是,是否使用方法1或方法2,以及每种方法的利弊是什么,特别是大量的事实.

methodone因为事实是可用的,所以似乎很浪费,为什么还要建立一个列表(特别是一个大的列表).如果列表足够大,这也必须有内存含义吗？它没有利用Prolog的自然回溯功能.

methodtwo利用回溯来为我做递归,我猜想会有更多的内存效率,但是通常这样做是不是很好的编程习惯呢？这可以说是更难以理解,可能还有其他副作用吗？

我可以看到的一个问题是每次fail调用时,我们都失去了将任何东西传递回调用谓词的能力,例如.如果是的话methodtwo(SeasonResults),因为我们故意不断地破坏谓词.所以methodtwo需要断言事实来存储状态.

大概(？)方法2会更快,因为它没有(大)列表处理吗？

我可以想象,如果我有一个清单,那么methodone将是要走的路......还是总是如此？在任何情况下都可以将列表声明为事实,methodone然后使用方法二处理它们？完全疯了吗？

但话说回来,我读到断言事实是一项非常"昂贵"的业务,所以列表处理可能是要走的路,即使是大型列表？

有什么想法吗？或者有时候使用一个而不是另一个更好,这取决于(什么)情况？例如.对于内存优化,使用方法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').

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.

所以我们现在肯定知道没有不同长度的季节.

这是我对你问题的第一个答案:

只要你可以,使用顶层外壳而不是你自己的副作用程序!进一步拉伸事物以完全避免副作用.这是从一开始就避免故障驱动循环的最佳方法.

为什么坚持顶级壳是一个好主意的原因有很多:

• 如果您的程序可以在顶层轻松查询,那么为它们添加测试用例将是微不足道的.

• 顶级外壳被许多其他用户使用,因此经过了很好的测试.你自己的写作往往是有缺陷的,没有经过考验.想一想约束.想想写浮标.你也会用write/1漂浮物吗？编写浮点数的正确方法是什么,以便可以准确地回读它们？这里是一个方式做这个异序言.这是答案:

在ISO, ,,writeq/1,2 与选项保证彩车可以准确地读回.也就是说,它们是相同的write_canonical/1,2write_term/2,3quoted(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这样的系统确实拥有相当复杂的垃圾收集器.使用较少的故障驱动循环将有助于进一步改进这些系统,因为这产生了对更复杂技术的需求.

Answer 2

方法一看起来很浪费,因为事实是可用的,为什么还要建立一个列表(特别是一个大的列表).如果列表足够大,这也必须有内存含义吗？

是的,方法1采用Θ(n)内存.它的主要好处是它是声明性的,即它具有直接的逻辑意义.

方法2,Prolog程序员称之为"故障驱动循环",需要恒定的内存,是程序性的,当你正在进行程序性(非逻辑)事物时可能是首选; 即,在I/O代码中,可以使用它.

请注意,SWI-Prolog有第三种编写此循环的方法:

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

这仅适用showseason于每个绑定的成功season(S).