編譯自： https://manybutfinite.com/post/tail-calls-optimization-es6/
譯者： qhwdw
在探秘“棧”的倒數第二篇文章中，我們提到了 尾調用(tail call)、編譯優化、以及新發布的 JavaScript 上 合理尾調用(proper tail call)。
當一個函數 F 調用另一個函數作為它的結束動作時，就發生了一個尾調用。在那個時間點，函數 F 絕對不會有多餘的工作：函數 F 將“球”傳給被它調用的任意函數之後，它自己就“消失”了。這就是關鍵點，因為它打開了尾調用優化的“可能之門”：我們可以簡單地重用函數 F 的棧幀，而不是為函數調用 創建一個新的棧幀 ，因此節省了棧空間並且避免了新建一個棧幀所需要的工作量。下面是一個用 C 寫的簡單示例，然後使用 mild 優化 來編譯它的結果：
int add5(int a)
{
return a + 5;
}
int add10(int a)
{
int b = add5(a); // not tail
return add5(b); // tail
}
int add5AndTriple(int a){
int b = add5(a); // not tail
return 3 * add5(a); // not tail, doing work after the call
}
int finicky(int a){
if (a > 10){
return add5AndTriple(a); // tail
}
if (a > 5){
int b = add5(a); // not tail
return finicky(b); // tail
}
return add10(a); // tail
}
簡單的尾調用 下載
在編譯器的輸出中，在預期會有一個 調用 的地方，你可以看到一個 跳轉 指令，一般情況下你可以發現尾調用優化（以下簡稱 TCO）。在運行時中，TCO 將會引起調用棧的減少。
一個通常認為的錯誤觀念是，尾調用必須要 遞歸 。實際上並不是這樣的：一個尾調用可以被遞歸，比如在上面的 finicky() 中，但是，並不是必須要使用遞歸的。在調用點只要函數 F 完成它的調用，我們將得到一個單獨的尾調用。是否能夠進行優化這是一個另外的問題，它取決於你的編程環境。
“是的，它總是可以！”，這是我們所希望的最佳答案，它是著名的 Scheme 中的方式，就像是在 SICP 上所討論的那樣（順便說一聲，如果你的程序不像“一個魔法師使用你的咒語召喚你的電腦精靈”那般有效，建議你讀一下這本書）。它也是 Lua 的方式。而更重要的是，它是下一個版本的 JavaScript —— ES6 的方式，這個規範清晰地定義了 尾的位置 ，並且明確了優化所需要的幾個條件，比如， 嚴格模式 。當一個編程語言保證可用 TCO 時，它將支持 合理尾調用(proper tail call)。
現在，我們中的一些人不能拋開那些 C 的習慣，心臟出血，等等，而答案是一個更復雜的“有時候”，它將我們帶進了編譯優化的領域。我們看一下上面的那個 簡單示例 ；把我們 上篇文章 的階乘程序重新拿出來：
#include
int factorial(int n)
{
int previous = 0xdeadbeef;
if (n == 0 || n == 1) {
return 1;
}
previous = factorial(n-1);
return n * previous;
}
int main(int argc)
{
int answer = factorial(5);
printf("%d\n", answer);
}
遞歸階乘 下載
像第 11 行那樣的，是尾調用嗎？答案是：“不是”，因為它被後面的 n 相乘了。但是，如果你不去優化它，GCC 使用 O2 優化 的 結果 會讓你震驚：它不僅將階乘轉換為一個 無遞歸循環 ，而且 factorial(5) 調用被整個消除了，而以一個 120 (5! == 120) 的 編譯時常數 來替換。這就是調試優化代碼有時會很難的原因。好的方面是，如果你調用這個函數，它將使用一個單個的棧幀，而不會去考慮 n 的初始值。編譯算法是非常有趣的，如果你對它感興趣，我建議你去閱讀 構建一個優化編譯器 和 ACDI 。
但是，這裡沒有做尾調用優化時到底發生了什麼？通過分析函數的功能和無需優化的遞歸發現，GCC 比我們更聰明，因為一開始就沒有使用尾調用。由於過於簡單以及很確定的操作，這個任務變得很簡單。我們給它增加一些可以引起混亂的東西（比如，getpid()），我們給 GCC 增加難度：
#include
#include
#include
int pidFactorial(int n)
{
if (1 == n) {
return getpid(); // tail
}
return n * pidFactorial(n-1) * getpid(); // not tail
}
int main(int argc)
{
int answer = pidFactorial(5);
printf("%d\n", answer);
}
遞歸 PID 階乘 下載
優化它，unix 精靈！現在，我們有了一個常規的 遞歸調用 並且這個函數分配 O(n) 棧幀來完成工作。GCC 在遞歸的基礎上仍然 為 getpid 使用了 TCO 。如果我們現在希望讓這個函數尾調用遞歸，我需要稍微變一下：
#include
#include
#include
int tailPidFactorial(int n, int acc)
{
if (1 == n) {
return acc * getpid(); // not tail
}
acc = (acc * getpid() * n);
return tailPidFactorial(n-1, acc); // tail
}
int main(int argc)
{
int answer = tailPidFactorial(5, 1);
printf("%d\n", answer);
}
tailPidFactorial.c 下載
現在，結果的累加是 一個循環 ，並且我們獲得了真實的 TCO。但是，在你慶祝之前，我們能說一下關於在 C 中的一般情形嗎？不幸的是，雖然優秀的 C 編譯器在大多數情況下都可以實現 TCO，但是，在一些情況下它們仍然做不到。例如，正如我們在 函數序言 中所看到的那樣，函數調用者在使用一個標準的 C 調用規則調用一個函數之後，它要負責去清理棧。因此，如果函數 F 帶了兩個參數，它只能使 TCO 調用的函數使用兩個或者更少的參數。這是 TCO 的眾多限制之一。Mark Probst 寫了一篇非常好的論文，他們討論了 在 C 中的合理尾遞歸 ，在這篇論文中他們討論了這些屬於 C 棧行為的問題。他也演示一些 瘋狂的、很酷的欺騙方法 。
“有時候” 對於任何一種關係來說都是不堅定的，因此，在 C 中你不能依賴 TCO。它是一個在某些地方可以或者某些地方不可以的離散型優化，而不是像合理尾調用一樣的編程語言的特性，雖然在實踐中可以使用編譯器來優化絕大部分的情形。但是，如果你想必須要實現 TCO，比如將 Scheme 轉譯(transpilation)成 C，你將會 很痛苦 。
因為 JavaScript 現在是非常流行的轉譯對象，合理尾調用比以往更重要。因此，對 ES6 及其提供的許多其它的重大改進的讚譽並不為過。它就像 JS 程序員的聖誕節一樣。
這就是尾調用和編譯優化的簡短結論。感謝你的閱讀，下次再見！
via: https://manybutfinite.com/post/tail-calls-optimization-es6/
閱讀更多 Linux技術 的文章
關鍵字: Scheme GCC JavaScript
