Осуществление `последний/2` в терминах` присоединять/3` или `реверс/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

Определение reverse/2 на самом деле менее распространено, а также реализация SWI лучше в то время как многие другие реализации заканчиваются только в том случае, если первым аргументом является список. Я вижу, по крайней мере, три различные реализации: 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.

Answer 2

На самом деле , система ведет себя точно так же, как того, что я ожидал:

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 использует в 2 раза распределение append/3. Использование глобальных и трейловых стеков является двойным для обратного/2, вследствие того, что реверс/2 умело скомпилирован для обратного/4 ....