logo标签列表

SWI-Prolog是否支持尾调用优化？

prologtail-call-optimization
5
step_n(0, I, I).
step_n(N, In, Out) :-
    N > 0, plus(N1, 1, N), phase_step(In, T),
    step_n(N1, T, Out).

phase_step是一种转换数据的函数。

这个step_n是否会在几乎与phase_step相同的内存中运行？如果不是，我应该如何改写它才能实现这一点？这是否取决于phase_step有一个解决方案？

编辑：使用prolog_current_frame进行调试后，我发现如果phase_step是像Out is In + 1这样的简单函数，则会发生优化，但在我的用例中不会。

为什么TCO取决于phase_step谓词？

1
感兴趣的内容：这个程序是否正在执行TCO，如果是，它是如何执行的？ - Guy Coder
1
@GuyCoder：你的意思是在调试、跟踪时关闭尾调用优化吗？ - rajashekar
请注意，使用调试器和跟踪会关闭（感谢@rajashekar）尾调用优化，因此不要依赖它来得出确定的答案。 - Guy Coder
那么如果prolog_current_frame对于所有递归实例都给出相同的值，那么它就被优化了吗？我检查了一个简单的“double”函数和我的“step_n”，“double”给出了相同的值，而我的“step_n”没有。 - rajashekar
SWI-Prolog有wrap_predicate/4，这可能是一个更实用的方法，例如编写一个包装所需谓词并检查框架的谓词。我不打算为这个问题甚至编写答案。其他人可以自由探索和回答。 - Guy Coder
显示剩余3条评论
2个回答
6
这是否取决于phase_step只有一个解决方案？
有点类似，但还要更强一些：它取决于phase_step是确定性的，这意味着不会留下任何“选择点”。 选择点是要探索的未来路径；不一定会产生进一步的解决方案，但仍是Prolog需要检查的内容。
例如，以下是确定性的：
phase_step_det(X, X).

它有一个唯一的解决方案，Prolog不会提示我们需要更多的解决方案：

?- phase_step_det(42, Out).
Out = 42.

以下有一个解决方案，但它不是确定性的：
phase_step_extrafailure(X, X).
phase_step_extrafailure(_X, _Y) :-
    false.

在看完解决方案后，Prolog仍然需要检查一些内容。即使我们能够通过查看代码知道那个东西（第二个子句）将会失败。
?- phase_step_extrafailure(42, Out).
Out = 42 ;
false.

以下有多个解决方案，因此它不是确定性的：
phase_step_twosolutions(X, X).
phase_step_twosolutions(X, Y) :-
    plus(X, 1, Y).

?- phase_step_twosolutions(42, Out).
Out = 42 ;
Out = 43.

为什么TCO取决于phase_step谓词？
如果还有其他路径需要探索，那么就必须在某个地方存储这些路径的数据。这个“某个地方”是一种堆栈数据结构，对于每条未来路径，都必须在堆栈上创建一个帧。这就是为什么内存使用量会增加。随着内存使用量的增加，计算时间也会相应增加（以下内容使用您的step_n的副本以及我上面相应的phase_step变体）。
?- time(step_n_det(100_000, 42, Out)).
% 400,002 inferences, 0.017 CPU in 0.017 seconds (100% CPU, 24008702 Lips)
Out = 42 ;
% 7 inferences, 0.000 CPU in 0.000 seconds (87% CPU, 260059 Lips)
false.

?- time(step_n_extrafailure(100_000, 42, Out)).
% 400,000 inferences, 4.288 CPU in 4.288 seconds (100% CPU, 93282 Lips)
Out = 42 ;
% 100,005 inferences, 0.007 CPU in 0.007 seconds (100% CPU, 13932371 Lips)
false.

?- time(step_n_twosolutions(100_000, 42, Out)).
% 400,000 inferences, 4.231 CPU in 4.231 seconds (100% CPU, 94546 Lips)
Out = 42 ;
% 4 inferences, 0.007 CPU in 0.007 seconds (100% CPU, 548 Lips)
Out = 43 ;
% 8 inferences, 0.005 CPU in 0.005 seconds (100% CPU, 1612 Lips)
Out = 43 ;
% 4 inferences, 0.008 CPU in 0.008 seconds (100% CPU, 489 Lips)
Out = 44 ;
% 12 inferences, 0.003 CPU in 0.003 seconds (100% CPU, 4396 Lips)
Out = 43 ;
% 4 inferences, 0.009 CPU in 0.009 seconds (100% CPU, 451 Lips)
Out = 44 .  % many further solutions

探究这个问题的一种方法是使用SWI-Prolog调试器，它可以展示选择点（即未来要探索的路径）：

?- trace, step_n_det(5, 42, Out).
   Call: (9) step_n_det(5, 42, _1496) ? skip           % I typed 's' here.
   Exit: (9) step_n_det(5, 42, 42) ? alternatives      % I typed 'A' here.
 [14] step_n_det(0, 42, 42)
   Exit: (9) step_n_det(5, 42, 42) ? no debug          % I typed 'n' here.
Out = 42 ;
false.

?- trace, step_n_extrafailure(5, 42, Out).
   Call: (9) step_n_extrafailure(5, 42, _1500) ? skip
   Exit: (9) step_n_extrafailure(5, 42, 42) ? alternatives
 [14] step_n_extrafailure(0, 42, 42)
 [14] phase_step_extrafailure(42, 42)
 [13] phase_step_extrafailure(42, 42)
 [12] phase_step_extrafailure(42, 42)
 [11] phase_step_extrafailure(42, 42)
 [10] phase_step_extrafailure(42, 42)
   Exit: (9) step_n_extrafailure(5, 42, 42) ? no debug
Out = 42 ;
false.

以上所有替代方法都对应于额外的解释器帧。如果您使用SWI-Prolog的可视化调试器，它还将向您显示栈的图形表示，包括所有打开的选择点（尽管我始终发现这很难理解）。

所以，如果你想要TCO并且不增加堆栈，你需要让你的阶段步骤执行确定性。你可以通过使 phase_step谓词本身变得确定性来实现这一点。你也可以在 step_n内调用phase_step后添加一个cut。

以下是上面的调用，在每个phase_step后面加一个cut：

?- time(step_n_det(100_000, 42, Out)).
% 400,001 inferences, 0.017 CPU in 0.017 seconds (100% CPU, 24204529 Lips)
Out = 42 ;
% 7 inferences, 0.000 CPU in 0.000 seconds (83% CPU, 737075 Lips)
false.

?- time(step_n_extrafailure(100_000, 42, Out)).
% 400,000 inferences, 0.023 CPU in 0.023 seconds (100% CPU, 17573422 Lips)
Out = 42 ;
% 5 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 220760 Lips)
false.

?- time(step_n_twosolutions(100_000, 42, Out)).
% 400,000 inferences, 0.023 CPU in 0.023 seconds (100% CPU, 17732727 Lips)
Out = 42 ;
% 5 inferences, 0.000 CPU in 0.000 seconds (94% CPU, 219742 Lips)
false.

不要盲目放置剪切符号，只有在了解需要何时和为什么需要它们之后再使用。请注意，在extrafailure情况下，该剪切符号仅移除失败内容，但在twosolutions情况下，它会移除实际的解决方案。
谢谢，非确定性是原因。 - rajashekar
2

了解代码性能问题，特别是不必要的非确定性问题，一个有用的工具是端口分析器工具，如ECLiPSe和Logtalk。Logtalk ports_profiler 工具是可移植的，所以我们可以在这里使用它。我们从包装您的代码开始（来自您的 gist 链接）：

:- use_module(library(lists), []).


:- object(step).

    :- public(step_n/3).
    :- use_module(lists, [reverse/2]).

    % pattern for the nth digit mth-coeffcient
    digit_m(N, M, D) :-
        divmod(M, N, Q, _),  divmod(Q, 4, _, C),
        (C = 0, D = 0; C = 1, D = 1; C = 2, D = 0; C = 3, D = -1).
    
    calculate_digit_n(N, In, D) :-
        calculate_digit_n_(N, In, D, 1, 0).
    calculate_digit_n_(_, [], D, _, Acc) :- D1 is abs(Acc), divmod(D1, 10, _, D).
    calculate_digit_n_(N, [I | Is], D, M, Acc) :-
        digit_m(N, M, C), P is C*I, M1 is M+1, Acc1 is Acc+P,
        calculate_digit_n_(N, Is, D, M1, Acc1).
    
    phase_step(In, Out) :-
        length(In, L), L1 is L + 1, phase_step_(In, Out, L1, 1, []).
    phase_step_(_, Out, L, L, Acc) :- reverse(Out, Acc).
    phase_step_(In, Out, L, N, Acc) :-
        N < L, calculate_digit_n(N, In, D), N1 is N + 1,
        phase_step_(In, Out, L, N1, [D | Acc]).
    
    step_n(0, I, I).
    step_n(N, In, Out) :-
        prolog_current_frame(Fr), format('~w ', Fr),
        N > 0, N1 is N - 1, phase_step(In, T),
        step_n(N1, T, Out).

:- end_object.

%:- step_n(10, [1, 2, 3, 4, 5, 6, 7, 8], X).

接下来（使用SWI-Prolog作为后端，因为您告诉我们您正在使用Prolog系统）：

$ swilgt
...
?- {ports_profiler(loader)}.
% [ /Users/pmoura/logtalk/tools/ports_profiler/ports_profiler.lgt loaded ]
% [ /Users/pmoura/logtalk/tools/ports_profiler/loader.lgt loaded ]
% (0 warnings)
true.

?- logtalk_load(step, [debug(on), source_data(on)]).
% [ /Users/pmoura/step.pl loaded ]
% (0 warnings)
true.

?- step::step_n(10, [1, 2, 3, 4, 5, 6, 7, 8], X).
340 15578 30816 46054 61292 76530 91768 107006 122244 137482 
X = [3, 6, 4, 4, 0, 6, 7, 8] .

?- ports_profiler::data.
------------------------------------------------------------------------------
Entity  Predicate               Fact  Rule  Call  Exit *Exit  Fail  Redo Error
------------------------------------------------------------------------------
step    calculate_digit_n/3        0    80    80     0    80     0     0     0
step    calculate_digit_n_/5       0   720   720     0   720     0     0     0
step    digit_m/3                  0   640   640    40   600     0     0     0
step    phase_step/2               0    10    10     0    10     0     0     0
step    phase_step_/5              0    90    90     0    90     0     0     0
step    step_n/3                   1    10    11     0    11     0     0     0
------------------------------------------------------------------------------
true.
*Exit列用于表示从过程框中的非确定性退出。如需有关工具和表格结果解释的帮助，请参见https://logtalk.org/manuals/devtools/ports_profiler.html。但仅通过一眼查看表格就可以清楚地看出，phase_step/2和step_n/3都是非确定性的。 更新 请注意，尾递归优化（TCO）并不意味着或要求谓词是确定性的。在您的情况下，当step_n/3谓词的规则中的最后一个调用是对自身的调用时，Prolog编译器可以应用TCO。这意味着可以在特定的递归调用上保存堆栈帧。这并不意味着在递归调用之前没有创建选择点。使用once/1（如您在评论中提到的）只是丢弃了调用phase_step/2时创建的选择点，因为该谓词本身是非确定性的。这就是表格所显示的内容。step_n/3谓词也是非确定性的，因此在第一个参数为0时调用它会创建一个选择点，这发生在您使用零作为第一个参数调用谓词时或者当查询的证明达到此递归定义的基本情况时。
我正在尝试使用您的Logtalk程序，但不明白为什么使用_once/1_不能使程序进行尾调用优化。在普通的swi-prolog中，它被优化了https://gist.github.com/k3ut0i/8e0db10915d5a59d13d79b5a3e5a2005。相应的Logtalk程序仍然显示不同的堆栈帧和*Exit列https://gist.github.com/k3ut0i/14d2e25b513a6b4645eb1782c8955436，为什么？ - rajashekar
@rajashekar 我更新了我的答案，解释了当你使用 once/1 时发生了什么。 - Paulo Moura
我理解phase_step/2本身是不确定性的。我的意思是，swi-prolog和logtalk版本的行为不相似。使用once/1，我在swi-prolog中获得了尾递归优化，但在logtalk中却没有。 - rajashekar
1
使用Logtalk版本确实可以获得TCO。只需加载对象（不带debug(on)标志），并尝试查询：{step}，step::step_n(10, 1, X)。您将获得与TCO预期相同的堆栈帧打印。但是，使用ports_profiler工具对代码进行了仪器化，并且与大多数调试器（包括Prolog调试器）一样，这会阻止TCO。 - Paulo Moura
谢谢，我忘记了打开调试模式。是的，关闭调试模式后，我可以使用尾递归优化。 - rajashekar
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接