尾呼叫

在計算機學裡，尾呼叫是指一個函數里的最後一個動作是返回一個函式的呼叫結果的情形，即最後一步新呼叫的返回值直接被當前函式的返回結果。此時，該尾部呼叫位置被稱為尾位置。尾呼叫中有一種重要而特殊的情形叫做尾遞迴。經過適當處理，尾遞迴形式的函式的執行效率可以被極大地最佳化。尾呼叫原則上都可以透過簡化函式呼叫棧的結構而獲得性能最佳化，但是最佳化尾呼叫是否方便可行取決於執行環境對此類最佳化的支援程度如何。概述.在計算機科學裡，尾呼叫是指一個函數里的最後一個動作是一個函式呼叫的情形：即這個呼叫的返回值直接被當前函式返回的情形。這種情形下稱該呼叫位置為尾位置。若這個函式在尾位置呼叫本身，則稱這種情況為尾遞迴，是遞迴的一種特殊情形。尾呼叫不一定是遞迴呼叫，但是尾遞迴特別有用，也比較容易實現。在程式執行時，計算機會為應用程式分配一定的記憶體空間；應用程式則會自行分配所獲得的記憶體空間，其中一部分被用於記錄程式中正在呼叫的各個函式的執行情況，這就是函式的呼叫棧。常規的函式呼叫總是會在呼叫棧最上層新增一個新的堆疊幀，造成程式嚴重卡頓或意外崩潰。尾呼叫的呼叫棧則特別易於最佳化，從而可減少記憶體空間的使用，也能提高執行速度。其中，對尾遞迴情形的最佳化效果最為明顯，尤其是遞迴演算法非常複雜的情形。一般來說，尾呼叫消除是可選的，可以用，也可以不用。然而，在函式程式語言中，語言標準通常會要求編譯器或執行平臺實現尾呼叫消除。這讓程式設計師可以用遞迴取代迴圈而不喪失效能。定義與說明.定義.尾呼叫 。特徵與簡單示例.尾呼叫可能位於一個函式語法上最後的位置：function foo(data) {a(data);return b(data);在這裡，codice_1、codice_2 都是函式呼叫，但是 codice_2 是函式返回前的最後執行的東西，所以也是所謂的尾位置。然後，並非所有的尾呼叫都必須在一個函式語法上最後的位置。考慮：function bar(data) {if ( a(data) ) {return b(data);return c(data);在這裡，codice_4、codice_5 的呼叫都在尾位置。這是因為儘管 codice_2 不在 codice_7 語法上最後的位置，它是 codice_8 敘述其中一個分支最後的位置。現在考慮以下程式碼：function foo1(data) {return a(data) + 1;function foo2(data) {var ret = a(data);return ret;function foo3(data) {var ret = a(data);return (ret === 0) ? 1 : ret;在這裡，codice_1 處於 codice_10 的尾位置，但不處於 codice_11 或 codice_12 的尾位置。這是因為程式必須返回這2個 codice_13 函式的呼叫以檢查、更動 codice_13 的返回值。說明.傳統模式的編譯器對於尾呼叫的處理方式就像處理其他普通函式呼叫一樣，總會在呼叫時建立一個新的棧幀並將其推入呼叫棧頂部，用於表示該次函式呼叫。當一個函式呼叫發生時，電腦必須 “記住” 呼叫函式的位置 —— 返回位置，才可以在呼叫結束時帶著返回值回到該位置，返回位置一般存在呼叫棧上。在尾呼叫這種特殊情形中，電腦理論上可以不需要記住尾呼叫的位置而從被呼叫的函式直接帶著返回值返回呼叫函式的返回位置由於當前函式幀上包含區域性變數等等大部分的東西都不需要了，當前的函式幀經過適當的更動以後可以直接當作被尾呼叫的函式的幀使用，然後程式即可以跳到被尾呼叫的函式。產生這種函式幀更動程式碼與 “jump”的過程稱作尾呼叫消除(Tail Call Elimination)或尾呼叫最佳化(Tail Call Optimization, TCO)。尾呼叫最佳化讓位於尾位置的函式呼叫跟 codice_15 語句效能一樣高，也因此使得高效的結構程式設計成為現實。然而，對於 C++ 等語言來說，在函式最後 return g(x); 並不一定是尾遞迴——在返回之前很可能涉及到物件的解構函式，使得 g(x) 不是最後執行的那個。這可以透過返回值最佳化來解決。尾遞迴.若函式在尾位置呼叫自身，則稱這種情況為尾遞迴。尾遞迴也是遞迴的一種特殊情形。尾遞迴是一種特殊的尾呼叫，即在尾部直接呼叫自身的遞迴函式。對尾遞迴的最佳化也是關注尾呼叫的主要原因。尾呼叫不一定是遞迴呼叫，但是尾遞迴特別有用，也比較容易實現。特點.尾遞迴在普通尾呼叫的基礎上，多出了2個特徵：最佳化尾遞迴的分析與示例.對函式呼叫在尾位置的遞迴或互相遞迴的函式，由於函式自身呼叫次數很多，遞迴層級很深，尾遞迴最佳化則使原本 O(n) 的呼叫棧空間只需要 O(1)。因此一些程式語言的標準要求語言實現進行尾呼叫消除，例如 Scheme與 ML 家族的語言。在 Scheme 中，語言標準還將尾位置形式化，指定了各種語法中允許尾呼叫的地方。以 Python 為例，主要區分普通遞迴和尾遞迴對棧空間的使用#重定向 ：def recsum(x):if x == 1:return xelse:return x + recsum(x - 1)呼叫codice_16為例，SICP中描述了相應的棧空間變化：recsum(5)5 + recsum(4)5 + (4 + recsum(3))5 + (4 + (3 + recsum(2)))5 + (4 + (3 + (2 + recsum(1))))5 + (4 + (3 + (2 + 1)))5 + (4 + (3 + 3))5 + (4 + 6)5 + 1015可觀察，堆疊從左到右，增加到一個峰值後再計算從右到左縮小，這往往是我們不希望的，所以在C語言等語言中設計codice_17等特殊結構語句，使用迭代、尾遞迴，對普通遞迴進行最佳化，減少可能對記憶體的極端消耗。修改以上程式碼，可以成為尾遞迴：def tailrecsum(x, running_total=0):if x == 0:return running_totalelse:return tailrecsum(x - 1, running_total + x)或者使用迭代：for i in range(6):sum += i對比後者尾遞迴對記憶體的消耗：tailrecsum(5, 0)tailrecsum(4, 5)tailrecsum(3, 9)tailrecsum(2, 12)tailrecsum(1, 14)tailrecsum(0, 15)15則是線性的。最佳化尾呼叫的不同方式.要方便地實現尾呼叫最佳化，一般需藉助編譯器或執行環境提供的現成的尾遞迴最佳化特性，或是依賴所用程式語言能直接支援更底層的指令跳轉。利用執行平臺的支援直接實現.在 Perl 裡，程式設計師可以直接用一種帶有函式名稱的 “goto” 敘述變體：codice_18 直接使用尾呼叫。在程式語言實現中，消除尾遞迴裡的尾呼叫比消除一般的尾呼叫容易很多。舉例來說，Java 虛擬機器。Scala 等同樣基於 JVM 平臺的語言可以有效地實現單個函式的尾遞迴最佳化，但是對於多個函式的相互尾遞迴就無法優化了。JavaScript則原本不支援尾呼叫最佳化，到其第6代語言核心標準“ECMAScript 6”開始規定程式引擎應在嚴格模式下使用尾呼叫最佳化。而且ECMAScript 6限定了尾位置不含閉包的尾呼叫才能進行最佳化。動手實現的方案.彙編重組.對於直接生成彙編的編譯器，尾部呼叫消除很簡單：只要校正棧上的形參之後把 “call” 的機器碼換成一個 “jump” 的就行了。從編譯器的觀點，以下程式碼function foo()return a()先會被翻譯成：foo:call aret然後，尾部呼叫消除指的是將最後兩個指令以一個 “jump” 指令替換掉：foo:jmp a在 codice_13 函式完成的時候，它會直接返回到 codice_20 的返回地址，省去了不必要的 codice_21 指令。函式呼叫可能帶有引數，因此生成的彙編必須確保被呼叫函式的函式幀在跳過去之前已設定好。舉例來說，若是平臺的呼叫棧除了返回位置以外還有函式引數，編譯器需要輸出調整呼叫棧的指令。在這類平臺上，考慮程式碼：function foo(data1, data2)a(data1)return b(data2)其中 codice_22、codice_23 是引數。編譯器會把這個程式碼翻譯成以下彙編：foo:mov reg,[sp+data1] ; 透過棧指標取得 data1 並放到暫用暫存器。push reg ; 將 data1 放到棧上以便 a 使用。call a ; a 使用 data1。pop ; 把 data1 從棧上拿掉。mov reg,[sp+data2] ; 透過棧指標取得 data2 並放到暫用暫存器。push reg ; 將 data2 放到棧上以便 b 使用。call b ; b 使用 data2。pop ; 把 data2 從棧上拿掉。ret尾部呼叫最佳化會將程式碼變成：foo:mov reg,[sp+data1] ; 透過棧指標取得 data1 並放到暫用暫存器。push reg ; 將 data1 放到棧上以便 a 使用。call a ; a 使用 data1。pop ; 把 data1 從棧上拿掉。mov reg,[sp+data2] ; 透過棧指標取得 data2 並放到暫用暫存器。mov [sp+data1],reg ; 把 data2 放到 b 預期的位置。jmp b ; b 使用 data2 並返回到呼叫 foo 的函式。更改後的程式碼不管在執行速度或是棧空間的使用上的效能都比較好。透過彈跳床.由於很多 Scheme 的編譯器使用 C 作為中間目標語言，問題可轉化為如何在 C 裡在不讓棧向上增長的前提下實現尾部遞迴。很多實現透過一種叫做 (trampoline)的裝置，也就是一塊不斷進行函式呼叫的程式碼。所有函式程式碼的載入過程都透過這個彈跳床。當一個函式需要呼叫另一個函式時，它不是直接呼叫該函式，而是將該函式的位置、該呼叫使用的引數等資訊傳遞給彈跳床，讓愛插手的彈跳床去代為執行。這樣就可以確保 C 的棧不會向上增長並且可以讓迭代無限地繼續。用 Groovy、Visual Basic .NET、C# 等等支援高階函式的語言實現彈跳床是可能的。對所有函式呼叫使用蹦床，相比常規的C呼叫有著高昂的開銷，所以至少有一個Scheme編譯器即Chicken，使用了首先由聽從未發表建議而描述的一種技術。在其中使用常規的C呼叫，但是在每次呼叫前檢查棧的大小。當棧達到它的最大允許大小的時候，在棧上的物件經由Cheney演算法而被垃圾回收，所有存活資料都將移動到分立的堆之內。隨後棧被回縮，而程式恢復到緊鄰垃圾回收之前儲存的狀態。Baker聲稱：“Appel的方法透過偶爾的跳下帝國大廈而避免了大量的小型蹦床彈跳”。垃圾回收確保了相互尾遞迴可以無限的繼續。但是這種方法要求C函式呼叫都永不返回，因為不能保證它的呼叫者的棧幀仍然存在；故而它涉及到對程式程式碼的更加戲劇性的內部重寫，即將其改為。更多例項.通常被用於解釋遞迴的程式是計算階乘。以下計算階乘的 Scheme 程式不是尾端遞迴，而只是一般遞迴：(if (= n 1)1(* n (factorial (- n 1)))))因此，如果呼叫 codice_24 時的引數 codice_25 足夠大，這一程式會出現堆疊溢位。然而，如果將同一程式寫作尾端遞迴，按 Scheme 的標準將不會出現溢位：(define (iter product counter)(if (&gt; counter n)product(iter (* counter product)(+ counter 1))))(iter 1 1))在第2個程式中，注意 codice_26 函式直接返回其遞迴呼叫，而沒有對其進行運算。因此，這是一個尾端遞迴，這讓直譯器或編譯器將本來是call factorial (3)call iter (3 1)call iter (2 3)call iter (1 6)call iter (0 6)return 6return 6return 6return 6return 6的執行過程組合成在時間、空間上效能都較好的型態：call factorial (3)call iter (3 1)將引數變為 (2 3)，跳至 "iter"將引數變為 (1 6)，跳至 "iter"將引數變為 (0 6)，跳至 "iter"return 6return 6因為在中間過程中重複使用 codice_26 的函式幀，這種重組節省了空間。這也代表程式設計師不需要為了擔心棧空間或是堆空間用完。在一般的實現中，尾部遞迴的型態也比其他型態更快速，不過僅僅是常量倍數的差異。很多使用函式語言的程式設計師會為了使用這個最佳化將遞迴的程式碼寫成為尾部遞迴的形式。這通常需要一個多出來代表 “蒐集器” 的形參，如果要使用尾部遞迴則需要將本來沒有副作用的純函式改寫成會更動其他參引的形式。