Continuation在JS中的應用
正文從這開始~~
React 新近發布的 Hooks、Suspense、Concurrent Mode 等新功能讓人眼前一亮，甚至驚嘆 JS 居然有如此魔力。同時，這幾個功能或多或少附帶一些略顯奇怪的規則，沒有更深層次理解的話難以把握。其實這里面并沒有什么“黑科技”，就大的趨勢來講，前端整體上還是在不斷借鑒計算機其它領域的優秀實踐，來幫助我們更方便地解決人機交互問題。本文著眼于支撐這些功能的一個底層編程概念 Continuation（譯作“續延”），期望能夠在了解它之后，大家對這幾個功能有進一步的理解和掌握。當然，Continuation 在 React 之外也有很多的應用，可以一眼窺豹。
Continuation 是什么？
有些人對 continuation 并不陌生，因為有時候在談到 Callback Hell（回調地獄）時會有提到這一概念。但其實它和回調函數大相徑庭。
維基百科對它的定義是：
A continuation is an abstract representation of the control state of a computer program.
即，continuation 是計算機程序控制狀態的抽象表示。一個坊間更通俗的說法是：它代表程序的剩余部分。像 continue、break 這類控制流操作符一樣，continuation 能夠暴露給用戶程序從而可以在恰當時機恢復執行，這種基本能力大大擴展了編程語言使用者的發揮空間，也為 excpetion handling、generators、coroutines、algebraic effects 等提供了堅實基礎。
相信很多人和我一樣，對這樣不明就里的官方解釋迷惑不解。沒關系，我們首先舉一個現實生活中的例子——Continuation 三明治：
默認 Continuation
事實上，所有的程序都自帶一個默認的 continuation，那就是調用棧（Call Stack）。調用棧中存放著當前程序的一系列剩余任務，每個任務在調用棧中表示為一個棧幀（Stack Frame），用以存放任務的數據、變量和調用信息。當調用棧為空時，意味著整個程序執行結束了。
- function main() {
- foo();
- bar();
- }
- function foo() {
- bar();
- }
- function bar() {
- // do something
- }
可以看出，調用棧是嚴格按照后進先出的方式運行的，無法靈活調整執行順序。此外，控制流的控制權也被運行環境牢牢掌握，程序員無能為力。
現在，讓我們設想下，如果未來有一天我們能夠將調用任務以鏈表的方式存儲在堆中，是不是就可以突破調用棧的限制了呢？
首先，因為任務以調用楨的形式存儲在堆中，并通過指針相互關聯，形成一個調用幀鏈表。當前任務完成時，運行時可以使用這些指針跳到下一個調用幀。得益于鏈表這一組織形式，執行程序有能力調整調用幀之間的結構順序。
Continuation-Passing Style (CPS)
為了獲得更多控制權，廣大程序員們進行了艱苦卓絕的努力。CPS 即是第一種有意義的嘗試。簡單來說，它是將程序控制流通過 continuation 的形式進行顯示傳遞的一種編程方式，具體有三個典型特征：
- 每個函數的最后一個參數都是它的 continuation
- 函數內部不能顯示地使用 return
- 函數只能通過調用 continuation 以傳遞它完成的計算結果
舉個栗子：
- function double(x, next) {
- next(x * 2);
- }
- function add(x, y, next) {
- next(x + y);
- }
- function minus(x, y, next) {
- next(x - y);
- }
- // ((1 + 2) - 5) * 2
- add(1, 2, resultAdd => {
- minus(resultAdd, 5, resultMinus => {
- double(resultMinus, resultDouble => {
- console.log(`result: ${resultDouble}`);
- });
- });
- });
這不就是我們前端工程師耳熟能詳的回調函數么，最后的調用也再次讓我們想起了恐怖的回調地獄。表面上看的確如此，但是從控制流的角度來進一步考慮，這種模式的確賦予了程序員更多控制權，因為所有的計算步驟（函數）的 continuation 都是顯示傳遞的。
例如，假設我們希望能夠在計算的中間點進行檢查，一旦計算結果小于 0 則直接返回該結果?；?CPS 的三點特征，我們可以定義如下一個 evaluate 的計算過程：
- function evaluate(frames, operate, next) {
- let output;
- const run = (index) => {
- // Finish all frames, go to run the top level continuation
- if (index === frames.length) return next(output);
- // Pick up the next frame and run it with assembled arguments
- const { fn, args = [] } = frames[index];
- const fnArgs = index > 0 ? [output, ...args] : [...args];
- fnArgs.push((result) => {
- output = result;
- operate(output, next, () => run(++index));
- });
- fn(...fnArgs);
- };
- // Kick off
- run(0);
- }
- // ((1 + 2) - 5) * 2
- evaluate(
- [
- { fn: add, args: [1, 2] },
- { fn: minus, args: [5] },
- { fn: double },
- ],
- (output, abort, next) => {
- if (output < 0) return abort(`the intermedia result is less than zero: ${output}`);
- next(output);
- },
- (output) => {
- console.log(`output: ${output}`);
- },
- );
示例：https://jsbin.com/bidayeg/3/edit?js,console
可以看出，一方面，通過合理組織計算步驟模型，evaluate 可以幫助避免回調地獄的問題，另一方面，evaluate 的第二個參數會在每個計算步驟完成時進行檢查，并且有能力 abort 后續所有計算步驟，直接調用頂層 continuation 返回中間結果。
這個示例展示了 CPS 為我們拓展的控制流操作能力，除此之外，CPS 還有如下優點：
- 尾調用。每個函數都是在最后一個動作調用 continuation 返回計算結果，因此執行上下文不需要被保存到當前調用棧，編譯器可以針對這種情況做尾調用消除（Tail Call Elimination）的優化，這種優化在函數式語言編譯器中大量應用
- 異步友好。眾所眾知，JavaScript 是單線程的，如果使用直接函數調用來處理遠程請求等操作，那么我們將不得不暫停這唯一的線程直到異步操作結果返回，這意味著用戶的其它交互得不到及時響應。CPS 或者換言之的回調模式提供了一種有效易用的方式來處理這類問題
然而，程序終究是人來編寫和維護的，CPS 雖然有眾多好處，但讓所有人都遵循這樣嚴格的方式編程非常困難，目前這種技術更多地在編譯器中作為中間表示層應用。
CallCC
目前 Continuation 的主流應用方式是通過形如 callCC（call with current continuation）的過程調用以捕獲當前 continuation，并在之后適時執行它以恢復到 continuation 所在上下文繼續執行后續計算從而實現各種控制流操作。
Scheme、Scala 等語言提供了 call/cc 或等效控制流操作符，JS 目前并沒有原生支持，但是通過后續介紹的兩種方式可以間接實現。
現在假設我們已經可以在 JS 中使用 callCC 操作符，讓我們試試看它都能為我們帶來什么樣的頭腦風暴吧。
小試牛刀
讓我們從一個非常簡單的例子開始，了解下 callCC 如何運作：
- const x = callCC(function (cont) {
- for (let i = 0; i < 10; i++) {
- if (i === 3) {
- cont('done');
- }
- console.log(i);
- }
- });
- console.log(x);
- // output:
- // 0
- // 1
- // 2
- // done
從輸出結果可以看出，程序的 for 循環并沒有全部完成，而是在 i 為 3 時執行 callCC 捕獲的 continuation 過程時直接退出了整個 callCC 調用，并將 'done' 返回給了變量 x。我們可以總結下 callCC 方法的邏輯：
- 接受一個函數為唯一參數
- 該函數也有唯一一個參數 cont，代表 callCC 的后續計算，在這個例子中，即將 callCC 的計算結果賦值給 x，然后執行最后的 console.log(x) 打印結果
- callCC 會立即調用其函數參數
- 在該函數參數執行過程中，cont 可以接受一個參數作為 callCC 的返回值，一旦調用，則忽略后續所有計算，程序控制流跳轉會 callCC 的調用處繼續執行
得益于 James Long 開發的 Unwinder 在線編譯工具，非常推薦各位去 Simple 示例 嘗試在瀏覽器里執行下，你甚至可以打斷點然后單步執行哦~
重新實現列表 some 方法
進一步地，讓我們檢驗下剛剛介紹的對 callCC 的理解，重新實現下列表的 some 方法：
- function some(predicate, arr) {
- const x = callCC(function (cont) {
- for (let index = 0; index < arr.length; index++) {
- console.log('testing', arr[index]);
- if (predicate(arr[index])) {
- cont(true);
- }
- }
- return false;
- });
- return x;
- }
- console.log(some(x => x >= 2, [1, 2, 3, 4]));
- console.log(some(x => x >= 2, [1, -5]));
- // output:
- // testing 1
- // testing 2
- // true
- // testing 1
- // testing -5
- // false
在第一個 some 函數調用中，當 predicate 返回為 true 時，cont(true) 執行后程序控制流跳轉到 callCC 調用處，然后 some 函數返回 true 并被打印。然而在第二個 some 調用中，因為所有 predicate 都為 false，沒有 cont 被調用，因此 callCC 返回了其函數參數的最后一個 return 語句的結果。
在這個例子中，我們進一步了解了 callCC 的運行原理，并能用它實現一些工具方法。
重新實現 Try-Catch
接下來，讓我們挑戰一個難度更大的 callCC 應用：重寫 try-catch。
- const tryStack = [];
- function Try(body, handler) {
- const ret = callCC(function (cont) {
- tryStack.push(cont);
- return body();
- });
- tryStack.pop();
- if (ret.__exc) {
- return handler(ret.__exc);
- }
- return ret;
- }
- function Throw(exc) {
- if (tryStack.length > 0) {
- tryStack[tryStack.length - 1]({ __exc: exc });
- }
- console.log("unhandled exception", exc);
- }
Try 函數接受兩個參數：body 是接下來準備執行的主體邏輯，handler 是異常處理邏輯。關鍵點在于 Try 內部在執行 body 前會先將捕獲的 cont 壓入到堆棧 tryStack 中，以便在 Throw 時獲取 cont 從而繼續從 callCC 調用處恢復，從而實現類似 try-catch 語句的功能。
下面是一個 Try-Catch 的應用示例：
- function bar(x) {
- if (x < 0) {
- Throw(new Error("error!"));
- }
- return x * 2;
- }
- function foo(x) {
- return bar(x);
- }
- Try(
- function () {
- console.log(foo(1));
- console.log(foo(-1));
- console.log(foo(2));
- },
- function (ex) {
- console.log("caught", ex);
- }
- );
- // output:
- // 2
- // caught Error: error!
和我們預期的效果一致，異常處理函數可以捕獲 Throw 拋出的異常，同時主體邏輯 body 中的剩余部分也不再執行。另外，Throw 也像 JavaScript 原生的 throw 一樣，能夠擊穿多層函數調用，直到被 Try 語句的異常處理邏輯處理。
可恢復的 Try-Catch
基于上一小節中 Try-Catch 實現，我們現在嘗試一個真正的能體現 continuation 魔力的改造：讓 Try-Catch 在捕獲異常后，能夠從拋出異常的地方恢復執行。
為了實現這一效果，我們只需要對 Throw 進行改造，使其也通過 callCC 過程捕獲調用 Throw 時的 continuation，并將該 continuation 賦值給異常對象以供 Resume 過程調用從而實現異?；謴停?nbsp;
- function Throw(exc) {
- if (tryStack.length > 0) {
- return callCC(function (cont) {
- exc.__cont = cont;
- tryStack[tryStack.length - 1]({ __exc: exc });
- });
- }
- throw exc;
- }
- function Resume(exc, value) {
- exc.__cont(value);
- }
實際使用的例子如下：
- function double(x) {
- console.log('x is', x);
- if (x < 0) {
- x = Throw({ BAD_NUMBER: x });
- }
- return x * 2;
- }
- function main(x) {
- return double(x);
- }
- Try(
- function () {
- console.log(main(1));
- console.log(main(-2));
- console.log(main(3));
- },
- function (ex) {
- if (typeof ex.BAD_NUMBER !== 'undefined') {
- Resume(ex, Math.abs(ex.BAD_NUMBER));
- }
- console.log('caught', ex);
- }
- );
- // output:
- // x is 1
- // 2
- // x is -2
- // 4
- // x is 3
- // 6
從上例輸出中，我們可以清晰地注意到，在執行 main(-2) 時拋出的錯誤被準確地識別并且恢復為正確的正整數，并最終執行完所有主體邏輯。
Algebraic Effects
這種異?；謴偷臋C制，也被稱作 Algebraic Effects。它有一個非常核心的優勢：將主體邏輯與異?；謴瓦壿嫹蛛x。例如我們可以在 UI 組件中拋出一個數據讀取的異常，然后在更上層的異常處理邏輯中嘗試獲取該數據后恢復執行，這樣既簡化了 UI 組件的復雜度，也將數據獲取的邏輯交給了調用方，更加靈活高效。
實際上 Algebraic Effects 還有著諸多的應用，Eff、Ocaml 等編程語言對 Algebraic Effects 有著豐富的支持。React 有不少團隊成員是 Ocaml 的擁躉，新近推出的 Hooks、Suspense 都深受這種思想啟發，能夠讓我們類似線性同步地調用各種狀態讀取、數據獲取等異步過程。
下面我們來分析一個 Suspense 示例，體會下背后解決思路的相似之處：
- function ProfilePage() {
- return (
- <Suspense fallback={<h1>Loading profile...</h1>}>
- <ProfileDetails />
- </Suspense>
- );
- }
- function ProfileDetails() {
- // Try to read user info, although it might not have loaded yet
- const user = resource.user.read();
- return <h1>{user.name}</h1>;
- }
- const rootElement = document.getElementById("root");
- ReactDOM.createRoot(rootElement).render(
- <ProfilePage />
- );
在 ProfileDetails 組件中，執行 resource.user.read() 時，由于當前數據并不存在，所以需要 throw 一個 promise 實例。位于上層的 Suspense 在捕獲這個 promise 后會先展示 fallback 指定的 UI，然后等待 promise resolve 后再次嘗試渲染 ProfileDetails 組件。雖然對比基于 Continuation 實現的異常恢復仍然有一定差距，并不能精確地從主體邏輯中拋出異常的語句處恢復，而是將主體邏輯重新執行一遍。不過 React 內部做了大量優化，盡最大可能地避免不必要開銷。
CallCC 實現
相信很多讀者在一覽 callCC 的強大能力之后，已經忍不住想要盡快了解下它的實現方式，很難想象土鱉的 JS 是如何能做到這一切的。這一章節我們就為大家揭開它的神秘面紗。
編譯
類似 Babel 幫助我們將各種 JS 新標準甚至是草案階段的語言特性轉化為主流瀏覽器都能運行的最終代碼一樣，我們可以借助增加一個編譯階段將含有 callCC 調用的代碼轉化為普通瀏覽器都能運行的代碼。
Prettier 作者 James Long 早些年開發網頁游戲編輯器時曾打算制作一款交互式代碼調試工具，種種嘗試之后，他在友人的指導下學習了 Exceptional Continuations in JavaScript 論文中介紹的高性能方法，并基于當時 Facebook 剛剛開源不久的編譯 generator 利器 Regenerator，開發了 Unwinder 來編譯 callCC，同時還提供了一個運行時以及實時在線 debug 工具。
Unwinder 或者說 Regenerator 的核心是狀態機，即將源代碼中的所有計算步驟打散，相互之間的跳轉通過狀態變換來進行。例如下面這段簡短的代碼：
- function foo() {
- var x = 5;
- var y = 6;
- return x + y;
- }
在經過狀態機轉換后，變成了如下形式：
- function foo() {
- let $__next = 0, x, y;
- while (1) {
- switch($__next) {
- case 0:
- x = 5;
- $__next = 1;
- break;
- case 1:
- y = 6;
- $__next = 2;
- break;
- case 2:
- return x + y;
- }
- }
- }
基于這種核心能力，輔以 Exceptional Continuations 特有的 try-catch、restore 等邏輯支持，Unwinder 能夠很好地實現 Continuation。不過后續作者并沒有再對其進行維護，同時它在異步操作方面的支持有一定缺陷，導致目前并不是非常流行。
Generator
另外一派是直接采用 Generator 來實現，這非常符合直覺，畢竟 Generator 就是一種轉移控制流的非常獨特的方式。
Yassine Elouafi 在系列文章 Algebraic Effects in JavaScript 中系統性地介紹了 Continuation、CPS、使用 Generator 改造 CPS 并實現 callCC、進一步支持 Delimited Continuation 以及最終支持 Algebraic Effects 等內容，行文順暢，內容示例夯實，是研究 JS Continuation 上乘的參考資料。
限于篇幅，本文不再對其原理進行深入介紹，感興趣的同學可以讀一下他的系列文章。下面是非常核心的 callcc 實現部分：
- function callcc(genFunc) {
- return function(capturedCont) {
- function jumpToCallccPos(value) {
- return next => capturedCont(value);
- }
- runGenerator(genFunc(jumpToCallccPos), null, capturedCont);
- };
- }
為了支持類似上文中提到的 Try-Catch，我們可以定義如下方法：
- const handlerStack = [];
- function* trycc(computation, handler) {
- return yield callcc(function*(k) {
- handlerStack.push([handler, k]);
- const result = yield computation;
- handlerStack.pop();
- return result;
- });
- }
- function* throwcc(exception) {
- const [handler, k] = handlerStack.pop();
- const result = yield handler(exception);
- yield k(result);
- }
從實現層面來看，Generator 方式比編譯方式更加簡單，核心代碼不到百行。但是因為 Generator 本身的認知復雜度導致一定門檻，另外所有調用 callCC 的相關代碼都必須使用 Generator 才能夠順利運行，這對于應用開發來說太過艱難，更不必說需要改造的海量的第三方模塊。
缺點
Continuation 并非銀彈，究其本質，它是一個高級版本的能夠處理函數表達式的 Goto 語句。眾所眾知，由于高度靈活導致的難以理解和調試，Goto 語句在各個語言中都屬于半封禁甚至封禁狀態。Continuation 面臨類似的窘境，需要使用者思慮周全，慎之又慎，將其應用控制在一定合理范圍，甚至像 React 這樣完全封裝在自身實現內部。
結語
Continuation 是個非常復雜的概念，為了能夠由淺入深、結合 JS 實際地來系統性闡述這一概念，筆者花費了自專欄開設以來最長的時間做各種梳理準備。不期望大家讀過這篇文章后就馬上開始使用 Continuation 或者 Algebraic Effects。如前文所述，目前 Continuation 還存在各方面的問題，應該實事求是，因地制宜，取其精華去其糟粕。正如 React Hooks、Suspense 一樣，它們并沒有真的搞了內部的編譯器或者引入 Generator，而是結合實際，神似而形不同，最大限度地滿足了設計目標。此外，期望這篇長文能幫助大家理解一些設計背后的思路，拓展一點前端工程師的技術視野，了解到整個編程領域內的優秀實踐。
彩蛋
React Fiber 是 React 16 引入的最為重要的底層變化，主要解決阻塞渲染的問題。為了實現這一目標，Fiber 化整為零，將組件中的每一個子組件或者子元素都視為一個 Fiber，通過類似 DOM Tree 的組織方式形成一個 Fiber Tree：
每個 Fiber 都有獨立的 render 過程和狀態存儲，在渲染時，我們可以把整個 Fiber Tree 的渲染過程理解成遍歷整個 Fiber Tree 的過程，每個 Fiber 的渲染工作可以理解為一個函數調用，為了不阻塞頁面交互，React 核心的任務調度算法是這樣的：
- function workLoop(deadline) {
- let shouldYield = false;
- while (nextUnitOfWork && !shouldYield) {
- nextUnitOfWork = performUnitOfWork(
- nextUnitOfWork
- );
- shouldYield = deadline.timeRemaining() < 1;
- }
- if (!nextUnitOfWork && wipRoot) {
- commitRoot();
- }
- requestIdleCallback(workLoop);
- }
- requestIdleCallback(workLoop);
在每個瀏覽器 idle 的時間片內，workLoop 會盡可能多地執行 Fiber 渲染任務，如果時間到期且仍然有未完成任務時，nextUnitOfWork 會更新到最后一個待執行任務，然后等待下一個 idle 時間片繼續執行。
雖然這部分代碼并沒有明確地使用我們前文提到的種種 Continuation 方式，但是究其本質，React 是將 Fiber 引入之前的遞歸調用實現一次性完整渲染改變成以 Fiber Tree 為基礎的虛擬任務堆棧（或許不應該稱為棧，因為它是一個樹形結構），從而實現了對渲染任務的靈活調度。因此，nextUnitOfWork 在這里可以視作某種程度上的 Continuation，它代表著 React 渲染任務的“剩余部分”。
聯想到前面提到的 React Hooks、Suspense 背后借鑒的 Algebraic Effects 思想，難怪 React 團隊核心成員 Sebastian Markbåge 曾經放言：
React is operating at the level of a language feature
