你不懂JS：ES6與未來之元編程（下）

尾部調用優化（TCO）

通常來說，當從一個函數內部發起對另一個函數的調用時，就會分配一個 棧幀 來分離地管理這另一個函數調用的變數/狀態。這種分配不僅花費一些處理時間，還會消耗一些額外的內存。

一個調用棧鏈從一個函數到另一個再到另一個，通常至多擁有10-15跳。在這些場景下，內存使用不太可能是某種實際問題。

然而，當你考慮遞歸編程（一個函數頻繁地調用自己） —— 或者使用兩個或更多的函數相互調用而構成相互遞歸 —— 調用棧就可能輕易地到達上百，上千，或更多層的深度。如果內存的使用無限制地增長下去，你可能看到了它將導致的問題。

JavaScript引擎不得不設置一個隨意的限度來防止這樣的編程技術耗盡瀏覽器或設備的內存。這就是為什麼我們會在到達這個限度時得到令人沮喪的「RangeError: Maximum call stack size exceeded」。

警告： 調用棧深度的限制是不由語言規範控制的。它是依賴於具體實現的，而且將會根據瀏覽器和設備不同而不同。你絕不應該帶著可精確觀察到的限度的強烈臆想進行編碼，因為它們還很可能在每個版本中變化。

一種稱為 尾部調用 的特定函數調用模式，可以以一種避免額外的棧幀分配的方法進行優化。如果額外的分配可以被避免，那麼就沒有理由隨意地限制調用棧的深度，這樣引擎就可以讓它們沒有邊界地運行下去。

一個尾部調用是一個帶有函數調用的return語句，除了返回它的值，函數調用之後沒有任何事情需要發生。

這種優化只能在strict模式下進行。又一個你總是應該用strict編寫所有代碼的理由！

這個函數調用 不是 在尾部：

"use strict";

functionfoo(x){

returnx*2;

}

functionbar(x){

// 不是一個尾部調用

return1+foo(x);

}

bar(10);// 21

在foo(x)調用完成後必須進行1 + ..，所以那個bar(..)調用的狀態需要被保留。

但是下面的代碼段中展示的foo(..)和bar(..)都是位於尾部，因為它們都是在自身代碼路徑上（除了return以外）發生的最後一件事：

"use strict";

functionfoo(x){

returnx*2;

}

functionbar(x){

x=x+1;

if(x>10){

returnfoo(x);

}

else{

returnbar(x+1);

}

}

bar(5);// 24

bar(15);// 32

在這個程序中，bar(..)明顯是遞歸，但foo(..)只是一個普通的函數調用。這兩個函數調用都位於 恰當的尾部位置。x + 1在bar(..)調用之前被求值，而且不論這個調用何時完成，所有將要放生的只有return。

這些形式的恰當尾部調用（Proper Tail Calls —— PTC）是可以被優化的 —— 稱為尾部調用優化（TCO）—— 於是額外的棧幀分配是不必要的。與為下一個函數調用創建新的棧幀不同，引擎會重用既存的棧幀。這能夠工作是因為一個函數不需要保留任何當前狀態 —— 在PTC之後的狀態下不會發生任何事情。

TCO意味著調用棧可以有多深實際上是沒有限度的。這種技巧稍稍改進了一般程序中的普通函數調用，但更重要的是它打開了一扇大門：可以使用遞歸表達程序，即使它的調用棧深度有成千上萬層。

我們不再局限於單純地在理論上考慮用遞歸解決問題了，而是可以在真實的JavaScript程序中使用它！

作為ES6，所有的PTC都應該是可以以這種方式優化的，不論遞歸與否。

重寫尾部調用

然而，障礙是只有PTC是可以被優化的；非PTC理所當然地依然可以工作，但是將造成往常那樣的棧幀分配。如果你希望優化機制啟動，就必須小心地使用PTC構造你的函數。

如果你有一個沒有用PTC編寫的函數，你可能會發現你需要手動地重新安排你的代碼，使它成為合法的TCO。

考慮如下代碼：

"use strict";

functionfoo(x){

if(x

return(x/2)+foo(x-1);

}

foo(123456);// RangeError

對foo(x-1)的調用不是一個PTC，因為在return之前它的結果必須被加上(x / 2)。

但是，要使這段代碼在一個ES6引擎中是合法的TCO，我們可以像下面這樣重寫它：

非TCO優化

有另一種技術可以重寫代碼，讓調用棧不隨每次調用增長。

一個這樣的技術稱為 蹦床，它相當於讓每一部分結果表示為一個函數，這個函數要麼返回另一個部分結果函數，要麼返回最終結果。然後你就可以簡單地循環直到你不再收到一個函數，這時你就得到了結果。考慮如下代碼：

這種返工需要一些最低限度的改變來將遞歸抽出到trampoline(..)中的循環中：

首先，我們將return _foo ..這一行包裝進函數表達式return partial() {..。

然後我們將_foo(1,x)包裝進trampoline(..)調用。

這種技術之所以不受調用棧限制的影響，是因為每個內部的partial(..)函數都只是返回到trampoline(..)的while循環中，這個循環運行它然後再一次循環迭代。換言之，partial(..)並不遞歸地調用它自己，它只是返回另一個函數。棧的深度維持不變，所以它需要運行多久就可以運行多久。

蹦床表達的是，內部的partial()函數使用在變數x和acc上的閉包來保持迭代與迭代之間的狀態。它的優勢是循環的邏輯可以被抽出到一個可重用的trampoline(..)工具函數中，許多庫都提供這個工具的各種版本。你可以使用不同的蹦床演算法在你的程序中重用trampoline(..)多次。

當然，如果你真的想要深度優化（於是可復用性不予考慮），你可以摒棄閉包狀態，並將對acc的狀態追蹤，與一個循環一起內聯到一個函數的作用域內。這種技術通常稱為 遞歸展開：

演算法的這種表達形式很容易閱讀，而且很可能是在我們探索過的各種形式中性能最好的（嚴格地說）一個。很明顯它看起來是一個勝利者，而且你可能會想知道為什麼你曾嘗試其他的方式。

這些是為什麼你可能不想總是手動地展開遞歸的原因：

與為了復用而將彈簧（循環）邏輯抽出去相比，我們內聯了它。這在僅有一個這樣的例子需要考慮時工作的很好，但只要你在程序中有五六個或更多這樣的東西時，你將很可能想要一些可復用性來將讓事情更簡短、更易管理一些。

這裡的例子為了展示不同的形式而被故意地搞得很簡單。在現實中，遞歸演算法有著更多的複雜性，比如相互遞歸（有多於一個的函數調用它自己）。

你在這條路上走得越遠，展開 優化就變得越複雜和越依靠手動。你很快就會失去所有可讀性的認知價值。遞歸，甚至是PTC形式的遞歸的主要優點是，它保留了演算法的可讀性，並將性能優化的任務交給引擎。

如果你使用PTC編寫你的演算法，ES6引擎將會實施TCO來使你的代碼運行在一個定長深度的棧中（通過重用棧幀）。你將在得到遞歸的可讀性的同時，也得到性能上的大部分好處與無限的運行長度。

元？

TCO與元編程有什麼關係？

正如我們在早先的「特性測試」一節中講過的，你可以在運行時判定一個引擎支持什麼特性。這也包括TCO，雖然判定的過程相當粗暴。考慮如下代碼：

"use strict";

try{

(functionfoo(x){

if(x

})(1);

TCO_ENABLED=true;

}

catch(err){

TCO_ENABLED=false;

}

在一個非TCO引擎中，遞歸循環最終將會失敗，拋出一個被try..catch捕獲的異常。否則循環將由TCO輕易地完成。

討厭，對吧？

但是圍繞著TCO特性進行的元編程（或者，沒有它）如何給我們的代碼帶來好處？簡單的答案是你可以使用這樣的特性測試來決定載入一個你的應用程序的使用遞歸的版本，還是一個被轉換/轉譯為不需要遞歸的版本。

自我調整的代碼

但這裡有另外一種看待這個問題的方式：

這個演算法試圖儘可能多地使用遞歸來工作，但是通過作用域中的變數x和acc來跟蹤這個進程。如果整個問題可以通過遞歸沒有錯誤地解決，很好。如果引擎在某一點終止了遞歸，我們簡單地使用try..catch捕捉它，然後從我們離開的地方再試一次。

我認為這是一種形式的元編程，因為你在運行時期間探測著引擎是否能（遞歸地）完成任務的能力，並繞過了任何可能制約你的（非TCO的）引擎的限制。

一眼（或者是兩眼！）看上去，我打賭這段代碼要比以前的版本難看許多。它運行起來還相當地慢一些（在一個非TCO環境中長時間運行的情況下）。

它主要的優勢是，除了在非TCO引擎中也能完成任意棧大小的任務外，這種對遞歸棧限制的「解法」要比前面展示的蹦床和手動展開技術靈活得多。

實質上，這種情況下的_foo()實際上是任意遞歸任務，甚至是相互遞歸的某種替身。剩下的內容是應當對任何演算法都可以工作的模板代碼。

唯一的「技巧」是為了能夠在達到遞歸限制的事件發生時繼續運行，遞歸的狀態必須保存在遞歸函數外部的作用域變數中。我們是通過將x和acc留在_foo()函數外面這樣做的，而不是像早先那樣將它們作為參數值傳遞給_foo()。

幾乎所有的遞歸演算法都可以採用這種方法工作。這意味著它是在你的程序中，進行最小的重寫就能利用TCO遞歸的最廣泛的可行方法。

這種方式仍然使用一個PTC，意味著這段代碼將會 漸進增強：從在一個老版瀏覽器中使用許多次循環（遞歸批處理）來運行，到在一個ES6+環境中完全利用TCO遞歸。我覺得這相當酷！

複習

元編程是當你將程序的邏輯轉向關注它自身（或者它的運行時環境）時進行的編程，要麼為了調查它自己的結構，要麼為了修改它。元編程的主要價值是擴展語言的普通機制來提供額外的能力。

在ES6以前，JavaScript已經有了相當的元編程能力，但是ES6使用了幾個新特性及大地提高了它的地位。

從對匿名函數的函數名推斷，到告訴你一個構造器是如何被調用的元屬性，你可以前所未有地在程序運行期間來調查它的結構。通用Symbols允許你覆蓋固有的行為，比如將一個對象轉換為一個基本類型值的強制轉換。代理可以攔截並自定義各種在對象上的底層操作，而且Reflect提供了模擬它們的工具。

特性測試，即便是對尾部調用優化這樣微妙的語法行為，將元編程的焦點從你的程序提升到JS引擎的能力本身。通過更多地了解環境可以做什麼，你的程序可以在運行時將它們自己調整到最佳狀態。

你應該進行元編程嗎？我的建議是：先集中學習這門語言的核心機制是如何工作的。一旦你完全懂得了JS本身可以做什麼，就是開始利用這些強大的元編程能力將這門語言向前推進的時候了！

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！