根据 `append/3` 或 `reverse/2` 实现 `last/2`

Question

为什么 SWI-Prolog 文档建议 append(_, [Last], List) 作为可移植的 last/2 而不是说 reverse(List, [Last|_])（参见 here）？是不是 reverse/2 本身没有像 append/3 那样广泛实施？还是我从图片中遗漏了什么？

无论哪种方式，如果列表是循环的，所有三个都不会终止：

?- L = [z|L], last(L, Last).
^CAction (h for help) ? abort
% Execution Aborted
?- L = [z|L], append(_, [Last], L).
^CAction (h for help) ? abort
% Execution Aborted
?- L = [z|L], reverse(L, [Last|_]).
^CAction (h for help) ? abort
% Execution Aborted

但是，reverse/2至少不会在适当的列表中留下选择点：

?- append(_, [Last], [a]).
Last = a ;
false.

?- reverse([a], [Last|_]).
Last = a.

Answer 1

实际上，系统的行为与我预期的相反：

13 ?- length(L,1000000),time(reverse(L,[X|_])),statistics.
% 1,000,002 inferences, 0.422 CPU in 0.424 seconds (100% CPU, 2367605 Lips)
% Started at Tue Mar 10 14:31:08 2015
% 523.563 seconds cpu time for 7,770,847 inferences
% 13,661 atoms, 4,540 functors, 3,987 predicates, 81 modules, 214,610 VM-codes
% 
%                        Limit    Allocated       In use
% Local  stack:    268,435,456       12,288        1,904 Bytes
% Global stack:    268,435,456  100,659,184   72,011,904 Bytes
% Trail  stack:    268,435,456      129,016        2,280 Bytes
% 
% 8 garbage collections gained 1,837,408 bytes in 1.346 seconds.
% Stack shifts: 13 local, 68 global, 47 trail in 0.034 seconds
% 2 threads, 0 finished threads used 0.000 seconds
L = [_G1238, _G1241, _G1244, _G1247, _G1250, _G1253, _G1256, _G1259, _G1262|...].

14 ?- length(L,1000000),time(append(_,[X],L)),statistics.
% 999,999 inferences, 0.572 CPU in 0.574 seconds (100% CPU, 1747727 Lips)
% Started at Tue Mar 10 14:31:08 2015
% 536.544 seconds cpu time for 8,772,339 inferences
% 13,662 atoms, 4,540 functors, 3,987 predicates, 81 modules, 214,615 VM-codes
% 
%                        Limit    Allocated       In use
% Local  stack:    268,435,456       12,288        2,960 Bytes
% Global stack:    268,435,456   50,327,536   48,011,920 Bytes
% Trail  stack:    268,435,456       30,712        2,312 Bytes
% 
% 8 garbage collections gained 1,837,408 bytes in 1.346 seconds.
% Stack shifts: 13 local, 72 global, 50 trail in 0.036 seconds
% 2 threads, 0 finished threads used 0.000 seconds
L = [_G1240, _G1243, _G1246, _G1249, _G1252, _G1255, _G1258, _G1261, _G1264|...] 
.

似乎 reverse/2 使用了 append/3 的 2 倍分配。 reverse/2 的全局和跟踪堆栈使用量是双倍的，这是 reverse/2 被巧妙地编译为 reverse/4...

的结果

Answer 2

reverse/2 的定义实际上不太常见，而且 SWI 的实现具有更好的终止行为，而许多其他实现仅在第一个参数是列表时才终止。我看到至少 3 种不同的实现：一方面是 SWI，另一方面是 SICStus 和许多其他实现，然后是介于两者之间的 XSB。您可以通过以下目标来区分它们：

reverse(Xs, [a]).     % terminates for SWI and XSB
reverse([a|Xs], [a]). % terminates for SWI

在性能方面，我希望传统的 reverse/2（不是 SWI 的实现）应该更快一点，因为它完全确定性地运行。另一方面，它在堆上重新创建整个列表。

在当前的实现中，append(_, [L], Xs) 实现得并不理想：对于列表 Xs 的每个元素，都会创建一个选择点，然后将其删除，使最后一个选择点处于活动状态。有关更多信息，请参阅 this question。

根据 `append/3` 或 `reverse/2` 实现 `last/2`

Implementation of `last/2` in terms of `append/3` or `reverse/2`

prolog