这会是在 SWI-Prolog 中优化的尾调用吗
Will this be tail call optimized in SWI-Prolog
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 谓词？
Will this depend on phase_step having a single solution?
有点，但仍然更强：这取决于 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.
Why is TCO dependent on phase_step predicate?
如果还有更多路径需要探索，那么一定有关于这些路径的数据存储在某处。 “某处”是某种堆栈数据结构，对于未来的每条路径，堆栈上都必须有一个帧。这就是您的内存使用量增加的原因。以及计算时间（以下使用你的 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 调用之后进行剪切
以下是上面的调用，每个调用后都有一个截断 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 的情况下，它会删除实际的解决方案。
一个有助于理解代码性能问题的工具，特别是不需要的 non-determinism，是一个 ports profiler 工具，例如在ECLiPSe 和 Logtalk。 Logtalk ports_profiler 工具是 portable 所以我们可以在这里使用它。我们首先包装您的代码（来自您的要点 link）：
:- 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 列用于 non-deterministic 存在于 程序框 中。有关该工具和解释 table 结果的帮助，请参阅 https://logtalk.org/manuals/devtools/ports_profiler.html 但是只要看一眼 table 就可以清楚地知道 phase_step/2 和 step_n/3 都是non-deterministic.
更新
请注意，尾调用优化 (TCO) 并不意味着或要求谓词是确定性的。在您的情况下，TCO can 由 Prolog 编译器应用，因为 last 调用 step_n/3 谓词的规则是调用本身。这意味着堆栈帧可以保存在 that 特定的递归调用中。这并不意味着递归调用之前没有创建 choice-points 。使用 once/1（正如您在评论中提到的那样）只是丢弃在调用 phase_step/2 时创建的 choice-point，因为该谓词本身是 non-deterministic。这就是 table 显示的内容。 step_n/3 谓词也是 non-deterministic，因此当第一个参数为 0 时调用它会创建一个 choice-point，这在您调用第一个参数为零的谓词时发生或 当查询证明达到此递归定义的基本情况时。
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 谓词？
Will this depend on phase_step having a single solution?
有点，但仍然更强：这取决于 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.
Why is TCO dependent on phase_step predicate?
如果还有更多路径需要探索，那么一定有关于这些路径的数据存储在某处。 “某处”是某种堆栈数据结构，对于未来的每条路径，堆栈上都必须有一个帧。这就是您的内存使用量增加的原因。以及计算时间（以下使用你的 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 调用之后进行剪切
以下是上面的调用，每个调用后都有一个截断 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 的情况下，它会删除实际的解决方案。
一个有助于理解代码性能问题的工具，特别是不需要的 non-determinism，是一个 ports profiler 工具，例如在ECLiPSe 和 Logtalk。 Logtalk ports_profiler 工具是 portable 所以我们可以在这里使用它。我们首先包装您的代码（来自您的要点 link）：
:- 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 列用于 non-deterministic 存在于 程序框 中。有关该工具和解释 table 结果的帮助，请参阅 https://logtalk.org/manuals/devtools/ports_profiler.html 但是只要看一眼 table 就可以清楚地知道 phase_step/2 和 step_n/3 都是non-deterministic.
更新
请注意，尾调用优化 (TCO) 并不意味着或要求谓词是确定性的。在您的情况下，TCO can 由 Prolog 编译器应用，因为 last 调用 step_n/3 谓词的规则是调用本身。这意味着堆栈帧可以保存在 that 特定的递归调用中。这并不意味着递归调用之前没有创建 choice-points 。使用 once/1（正如您在评论中提到的那样）只是丢弃在调用 phase_step/2 时创建的 choice-point，因为该谓词本身是 non-deterministic。这就是 table 显示的内容。 step_n/3 谓词也是 non-deterministic，因此当第一个参数为 0 时调用它会创建一个 choice-point，这在您调用第一个参数为零的谓词时发生或 当查询证明达到此递归定义的基本情况时。