prolog - 这将是 SWI-Prolog 中优化的尾调用吗

Question

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 , 然后优化发生但不在 my use case .
为什么 TCO 取决于 phase_step谓词？

Answer 1

Will this depend on phase_step having a single solution?

有点，但更强大:它取决于 phase_step具有确定性，这意味着不留下任何“选择点”。一个选择点是 future 要探索的路径；不一定会产生进一步的解决方案，但 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.

Why is TCO dependent on phase_step predicate?

如果有更多的路径需要探索，那么必须有关于这些路径的数据存储在某个地方。那个“某处”是某种堆栈数据结构，对于每个 future 的路径，堆栈上都必须有一个框架。这就是您的内存使用量增加的原因。有了它，计算时间(以下使用您的 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 调试器，它可以向您展示替代方案(= 选择点 = future 要探索的路径):

?- 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 来做到这一点。谓词本身是确定性的。您也可以在 phase_step 之后进行删减。调用内线 step_n .
以下是来自上方的调用，每个 phase_step 后面都有一个删减。 :

?- 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如果它删除了实际的解决方案。