SWI-Prolog:Sum-List

Question

我是从Prolog开始的,我有点困惑......

我有一个简单的程序:

sum(0, []).
sum(Total, [Head|Tail]) :- sum(Sum, Tail), Total is Head + Sum.

当我调试时,我可以看到Prolog首先使用Head和Tail分割列表,因此结果是0 +空列表,并且它开始对数字求和并将其再次添加到列表中.

有人可以解释为什么它不会先到Total is Head + Sum. 然后再将列表拆分为Head and Tail吗？

编辑:这是跟踪:

[trace]  ?- sum(X, [1,2,3]).
Call: (6) sum(_G345, [1, 2, 3]) ? creep
Call: (7) sum(_G424, [2, 3]) ? creep
Call: (8) sum(_G424, [3]) ? creep
Call: (9) sum(_G424, []) ? creep
Exit: (9) sum(0, []) ? creep
Call: (9) _G430 is 3+0 ? creep
Exit: (9) 3 is 3+0 ? creep
Exit: (8) sum(3, [3]) ? creep
Call: (8) _G433 is 2+3 ? creep
xit: (8) 5 is 2+3 ? creep
Exit: (7) sum(5, [2, 3]) ? creep
Call: (7) _G345 is 1+5 ? creep
Exit: (7) 6 is 1+5 ? creep
Exit: (6) sum(6, [1, 2, 3]) ? creep
X = 6.

Answer 1

你的定义在栈上添加了.避免放弃添加的优化将是称为尾递归的一般技术的特殊情况.

以下定义可以使用尾递归:

sum(X,L):-sum(0,L,X).
sum(X,[],X).
sum(N, [Head|Tail],Y) :- N1 is Head + N, sum(N1,Tail,Y).

它为部分和的值引入了一个累加器,并将其与列表的尾部一起携带.以下是sum(X,[1,2,3])查询执行的跟踪.

?- trace, sum(S,[1,2,3]),notrace,nodebug.
   Call: (7) sum(_G584, [1, 2, 3]) ? creep
   Call: (8) sum(0, [1, 2, 3], _G584) ? creep
^  Call: (9) _G792 is 1+0 ? creep
^  Exit: (9) 1 is 1+0 ? creep
   Call: (9) sum(1, [2, 3], _G584) ? creep
^  Call: (10) _G795 is 2+1 ? creep
^  Exit: (10) 3 is 2+1 ? creep
   Call: (10) sum(3, [3], _G584) ? creep
^  Call: (11) _G798 is 3+3 ? creep
^  Exit: (11) 6 is 3+3 ? creep
   Call: (11) sum(6, [], _G584) ? creep
   Exit: (11) sum(6, [], 6) ? creep
   Exit: (10) sum(3, [3], 6) ? creep
   Exit: (9) sum(1, [2, 3], 6) ? creep
   Exit: (8) sum(0, [1, 2, 3], 6) ? creep
   Exit: (7) sum(6, [1, 2, 3]) ? creep
S = 6 .