SWI-Prolog的：總名錄

Question

我開始與Prolog的，我有點糊塗了......

我有一個簡單的程序：

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

當我調試，我可以看到Prolog首先用Head和Tail分割列表，所以結果是0 +空列表，並且在它開始總結數字並將其添加到列表之後。

有人可以解釋爲什麼它不會先到Total is Head + Sum. 然後再將列表分割爲頭部和尾部？

編輯：這裏是跟蹤：

[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 . 

Answer 2

這是另一個版本。我一直在使用概念圖軟件來幫助設計代碼，我不能在腦海中做複雜的事情。

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


    1 ?- trace,sum(Total,[1,2,3],0). 
    Call: (7) sum(_G2090, [1, 2, 3], 0) ? creep 
    Call: (8) _G2221 is 1+0 ? creep 
    Exit: (8) 1 is 1+0 ? creep 
    Call: (8) sum(_G2090, [2, 3], 1) ? creep 
    Call: (9) _G2224 is 2+1 ? creep 
    Exit: (9) 3 is 2+1 ? creep 
    Call: (9) sum(_G2090, [3], 3) ? creep 
    Call: (10) _G2227 is 3+3 ? creep 
    Exit: (10) 6 is 3+3 ? creep 
    Call: (10) sum(_G2090, [], 6) ? creep 
    Exit: (10) sum(6, [], 6) ? creep 
    Exit: (9) sum(6, [3], 3) ? creep 
    Exit: (8) sum(6, [2, 3], 1) ? creep 
    Exit: (7) sum(6, [1, 2, 3], 0) ? creep 
Total = 6.