歡迎光臨
每天分享高質量文章

尾呼叫、優化和 ES6 | Linux 中國

當一個函式 F 呼叫另一個函式作為它的結束動作時,就發生了一個尾呼叫。
— Gustavo Duarte


致謝
編譯自 | https://manybutfinite.com/post/tail-calls-optimization-es6/ 
 作者 | Gustavo Duarte
 譯者 | qhwdw ? ? ? ? ? 共計翻譯:117 篇 貢獻時間:212 天

在探秘“棧”的倒數第二篇文章中,我們提到了尾呼叫tail call、編譯優化、以及新發佈的 JavaScript 上合理尾呼叫proper tail call

當一個函式 F 呼叫另一個函式作為它的結束動作時,就發生了一個尾呼叫。在那個時間點,函式 F 絕對不會有多餘的工作:函式 F 將“球”傳給被它呼叫的任意函式之後,它自己就“消失”了。這就是關鍵點,因為它打開了尾呼叫優化的“可能之門”:我們可以簡單地重用函式 F 的棧幀,而不是為函式呼叫 創建一個新的棧幀[1],因此節省了棧空間並且避免了新建一個棧幀所需要的工作量。下麵是一個用 C 寫的簡單示例,然後使用 mild 優化[2] 來編譯它的結果:

  1. int add5(int a)

  2. {

  3.    return a + 5;

  4. }

  5. int add10(int a)

  6. {

  7.    int b = add5(a); // not tail

  8.    return add5(b); // tail

  9. }

  10. int add5AndTriple(int a){

  11.    int b = add5(a); // not tail

  12.    return 3 * add5(a); // not tail, doing work after the call

  13. }

  14. int finicky(int a){

  15.    if (a > 10){

  16.        return add5AndTriple(a); // tail

  17.    }

  18.    if (a > 5){

  19.        int b = add5(a); // not tail

  20.        return finicky(b); // tail

  21.    }

  22.    return add10(a); // tail

  23. }

簡單的尾呼叫 下載[3]

在編譯器的輸出中,在預期會有一個 呼叫[4] 的地方,你可以看到一個 跳轉[5] 指令,一般情況下你可以發現尾呼叫優化(以下簡稱 TCO)。在運行時中,TCO 將會引起呼叫棧的減少。

一個通常認為的錯誤觀念是,尾呼叫必須要 遞迴[6]。實際上並不是這樣的:一個尾呼叫可以被遞迴,比如在上面的 finicky() 中,但是,並不是必須要使用遞迴的。在呼叫點只要函式 F 完成它的呼叫,我們將得到一個單獨的尾呼叫。是否能夠進行優化這是一個另外的問題,它取決於你的編程環境。

“是的,它總是可以!”,這是我們所希望的最佳答案,它是著名的 Scheme 中的方式,就像是在 SICP[7]上所討論的那樣(順便說一聲,如果你的程式不像“一個魔法師使用你的咒語召喚你的電腦精靈”那般有效,建議你讀一下這本書)。它也是 Lua[8] 的方式。而更重要的是,它是下一個版本的 JavaScript —— ES6 的方式,這個規範清晰地定義了尾的位置[9],並且明確了優化所需要的幾個條件,比如,嚴格樣式[10]。當一個編程語言保證可用 TCO 時,它將支持合理尾呼叫proper tail call

現在,我們中的一些人不能拋開那些 C 的習慣,心臟出血,等等,而答案是一個更複雜的“有時候”,它將我們帶進了編譯優化的領域。我們看一下上面的那個 簡單示例[11];把我們 上篇文章[12] 的階乘程式重新拿出來:

  1. #include  <stdio.h>

  2. int factorial(int n)

  3. {

  4.    int previous = 0xdeadbeef;

  5.    if (n == 0 || n == 1) {

  6.        return 1;

  7.    }

  8.    previous = factorial(n-1);

  9.    return n * previous;

  10. }

  11. int main(int argc)

  12. {

  13.    int answer = factorial(5);

  14.    printf("%d\n", answer);

  15. }

遞迴階乘 下載[13]

像第 11 行那樣的,是尾呼叫嗎?答案是:“不是”,因為它被後面的 n 相乘了。但是,如果你不去優化它,GCC 使用 O2 優化[14] 的 結果[15] 會讓你震驚:它不僅將階乘轉換為一個 無遞迴迴圈[16],而且 factorial(5) 呼叫被整個消除了,而以一個 120 (5! == 120) 的 編譯時常數[17]來替換。這就是除錯優化代碼有時會很難的原因。好的方面是,如果你呼叫這個函式,它將使用一個單個的棧幀,而不會去考慮 n 的初始值。編譯演算法是非常有趣的,如果你對它感興趣,我建議你去閱讀 構建一個優化編譯器[18] 和 ACDI[19]

但是,這裡沒有做尾呼叫優化時到底發生了什麼?通過分析函式的功能和無需優化的遞迴發現,GCC 比我們更聰明,因為一開始就沒有使用尾呼叫。由於過於簡單以及很確定的操作,這個任務變得很簡單。我們給它增加一些可以引起混亂的東西(比如,getpid()),我們給 GCC 增加難度:

  1. #include <stdio.h>

  2. #include <sys/types.h>

  3. #include <unistd.h>

  4. int pidFactorial(int n)

  5. {

  6.    if (1 == n) {

  7.        return getpid(); // tail

  8.    }

  9.    return n * pidFactorial(n-1) * getpid(); // not tail

  10. }

  11. int main(int argc)

  12. {

  13.    int answer = pidFactorial(5);

  14.    printf("%d\n", answer);

  15. }

遞迴 PID 階乘 下載[20]

優化它,unix 精靈!現在,我們有了一個常規的 遞迴呼叫[21] 並且這個函式分配 O(n) 棧幀來完成工作。GCC 在遞迴的基礎上仍然 為 getpid 使用了 TCO[22]。如果我們現在希望讓這個函式尾呼叫遞迴,我需要稍微變一下:

  1. #include <stdio.h>

  2. #include <sys/types.h>

  3. #include <unistd.h>

  4. int tailPidFactorial(int n, int acc)

  5. {

  6.    if (1 == n) {

  7.        return acc * getpid(); // not tail

  8.    }

  9.    acc = (acc * getpid() * n);

  10.    return tailPidFactorial(n-1, acc); // tail

  11. }

  12. int main(int argc)

  13. {

  14.    int answer = tailPidFactorial(5, 1);

  15.    printf("%d\n", answer);

  16. }

tailPidFactorial.c 下載[23]

現在,結果的累加是 一個迴圈[24],並且我們獲得了真實的 TCO。但是,在你慶祝之前,我們能說一下關於在 C 中的一般情形嗎?不幸的是,雖然優秀的 C 編譯器在大多數情況下都可以實現 TCO,但是,在一些情況下它們仍然做不到。例如,正如我們在 函式序言[25] 中所看到的那樣,函式呼叫者在使用一個標準的 C 呼叫規則呼叫一個函式之後,它要負責去清理棧。因此,如果函式 F 帶了兩個引數,它只能使 TCO 呼叫的函式使用兩個或者更少的引數。這是 TCO 的眾多限制之一。Mark Probst 寫了一篇非常好的論文,他們討論了 在 C 中的合理尾遞迴[26],在這篇論文中他們討論了這些屬於 C 棧行為的問題。他也演示一些 瘋狂的、很酷的欺騙方法[27]

“有時候” 對於任何一種關係來說都是不堅定的,因此,在 C 中你不能依賴 TCO。它是一個在某些地方可以或者某些地方不可以的離散型優化,而不是像合理尾呼叫一樣的編程語言的特性,雖然在實踐中可以使用編譯器來優化絕大部分的情形。但是,如果你想必須要實現 TCO,比如將 Scheme 轉譯transpilation成 C,你將會 很痛苦[28]

因為 JavaScript 現在是非常流行的轉譯物件,合理尾呼叫比以往更重要。因此,對 ES6 及其提供的許多其它的重大改進的贊譽並不為過。它就像 JS 程式員的聖誕節一樣。

這就是尾呼叫和編譯優化的簡短結論。感謝你的閱讀,下次再見!


via:https://manybutfinite.com/post/tail-calls-optimization-es6/

作者:Gustavo Duarte[30] 譯者:qhwdw 校對:wxy

本文由 LCTT 原創編譯,Linux中國 榮譽推出

赞(0)

分享創造快樂

© 2022 知識星球   网站地图