这会是 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，那么优化会发生，但不会发生在我的用例中。

为什么 TCO 依赖于phase_step谓词？

Answer 1

这将取决于具有单一解决方案的 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谓词本身具有确定性来做到这一点。你也可以在phase_stepcall 里面放一个 cut 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情况下，它会消除实际解决方案。