標籤：

考不上三本也能給自己心愛的語言加上Coroutine（一）

01-31

你現在所閱讀的並不是第一篇文章，你可能想看目錄和前言。

我發現發給了R菊苣的專欄之後再投稿給自己就好了，真機智！

終於要開始進入正題了。昨天在前言下面就看到有人問Coroutine是什麼，其實這也是正常的，雖然Coroutine很常見，但你不一定能直接用得上。像古時候Windows 3.x系列的協作式多線程，其實就是Coroutine的一種表達形式。你需要主動放棄對CPU的佔用，然後CPU就可以讓別人進來。所以你會發現很多古老的API都有提到這一點，譬如GetMessage函數。GetMessage在這裡就變成了Coroutine的一個operator。以前不能主動中斷的時候，如果API還不引誘你去調用這些函數，那整個系統就只有你一個程序可以運行了。

所以Coroutine滿大街都是，核心的想法就是你寫一個函數，然後函數自己決定什麼時候中斷自己的執行，等待別人喚醒。所以我們可以看到很多語言很直接粗暴地就這樣實現Coroutine了，譬如VC++早期的__await關鍵字，就是通過跑了一半把堆棧（其實就是一組寄存器）換掉來實現的。既然Coroutine本來就是要讓幾個函數交替執行，那我直接交替執行他們不就行了嘛？你們還可以從很多腳本語言裡面看到類似的東西。

這種做法有一個好處，就是Coroutine跟其他所有的feature都是正交的，你什麼代碼都不用改，直接在編譯器上做點手腳，然後改虛擬機就好了。但是如果你不是這一系列工具程序的owner，那你就會很蛋疼。萬一我hack了半天，結果人家上游下來一個改動，造成了一萬個conflict怎麼辦？或者說，我根本就不能決定語言用的是哪個runtime怎麼辦？所以只有當你真的擁有這門語言的時候，你才能這樣做。

既然不改虛擬機，那隻能改編譯器了。通常來講還有另一種辦法，就是要做全文CPS變換。當然這聽起來好像不知所云，其實核心思想很簡單，在我自己以前的vczh/tinymoe項目裡面就實現過。這是一門把自己編譯成C#的語言，語言本身暴露了continuation。所謂的continuation的意思就是說，你可以在任何地方下個「斷點」，然後編譯器會把「剩下的部分」包裝成一個閉包（或者通俗一點叫lambda表達式）給你。如果你直接問，那包裝到底是怎麼做的呢？很多人可能會讓你去看論文。但是如果你不在乎優雅的話，其實不看也罷，我也是做出來了之後才發現原來連這種東西也可以發論文的，真是大開眼界（逃

舉個簡單的例子，我有一個這樣的函數：

int Fuck(IEnumerable<int> xs)n{n int sum = 0;n foreach(var x in xs)n {n SHIT!n sum += x;n }n return sum;n}n

現在執行到SHIT!這裡，我打算做一個斷點，讓編譯器把剩下的部分包裝成一個閉包給你。那麼這個閉包長啥樣子呢？首先你要把foreach這個語法糖解開：

int Fuck(IEnumerable<int> xs)n{n int sum = 0;n var _xs = xs.CreateEnumerator();n while (_xs.Next())n {n var x = xs.Current;n SHIT!n sum += x;n }n return sum;n}n

那麼在執行到了SHIT!之後，如果你把剩下的部分寫成一段代碼（注意這個函數重新執行到SHIT!之後仍然要停止），自然就變成了：

片段1：（這是第一個SHIT!前面的部分）

int sum = 0;nint x;nvar _xs = xs.CreateEnumerator();nif (_xs.Next())n{n x = xs.Current;n /* SHIT! 向片段2 */n}nelsen{n return sum;n}n

片段2（這就是剩下的部分）：

sum += x;nif (_xs.Next())n{n x = xs.Current;n /* SHIT! 向片段2 */n}nelsen{n return sum;n}n

那麼你從片段1開始，每次遇到SHIT!的時候就停下來，等到恢復的時候，就執行當初SHIT!的目標。譬如說第一個片段，如果你狗屎運_xs.Next()返回false，直接return了，那也就沒有什麼SHIT!了。但是萬一你執行到了SHIT!，那麼函數到這裡也就結束了，等別人喚醒你的時候，你就從片段2開始執行，一直到什麼時候遇到return為止。這是不是很像給程序打了個斷點？

CPS變換的意思就是說，隨便給你一個SHIT!，然後你要照著原來的程序，把剩下的部分寫成上面那樣。當然實際情況比這個更複雜，因為你要考慮到這個SHIT!可能會出現在你要調用的函數的裡面，那事情就沒這麼好辦了。

所以vczh/tinymoe暴露continuation的意思也就是說，你可以在語言任意的地方寫上SHIT!，然後編譯器就想辦法把「剩下的部分」，通過全文CPS變換，編譯成一個閉包（也就是lambda表達式、函數對象、託管函數指針，etc），直接給你，然後你自己想辦法去調度。當初我也是為了練習編程才做成這樣的。直接的結果是什麼呢？看看這個文件就知道，語言只需要提供遞歸跟分支結構就可以了，剩下的部分全部都可以寫成庫，哪怕是循環和異常處理都能做出來。

註：SHIT!在某些Lisp語言裡面叫call-cc。

所以大家就會在項目的一開始看到，這個語言的其中一個例子就是如何幾十行就地做出一個yield return。這也是如何添加Coroutine的一個例子。如果語言本身提供continuation，那實現Coroutine根本不是事。

只不過這個文章的標題是給自己心愛的語言加上Coroutine，而且除了Lisp以外，估計不會有任何一門提供continuation的語言會成為誰心目中心愛的語言，那麼這個方法也就行不通了。

那最後剩下什麼呢？這也是除了修改虛擬機以外，大部分語言的做法，特別是自從C#做出了await之後，被各種語言廣泛抄走，用的也是我現在要講的最後一種辦法，這要求你規定SHIT!不能默默地在你調用的函數裡面出現，如果他一定要出現，那麼你要用特殊的語法來調用這個函數（譬如說使用await關鍵字）

這是什麼意思呢？考慮一下下面這個程序：

int Shit(int x, int sum)n{n SHIT!n return sum + x;n}nnint Fuck(IEnumerable<int> xs)n{n int sum = 0;n var _xs = xs.CreateEnumerator();n while (_xs.Next())n {n var x = xs.Current;n sum = Shit(x, sum);n }n return sum;n}n

這裡的SHIT!就出現在了Fuck調用的Shit函數裡面。那麼你說這樣的函數我要怎麼解continuation呢？我在看Fuck的時候我怎麼會知道Shit裡面會有SHIT!？萬一Shit函數是個虛函數怎麼辦？萬一這個虛函數還是另外的dll提供的怎麼辦？是吧，這就是語言不提供continuation，你也不能修改虛擬機（其實修改虛擬機也就等於提供continuation）的時候，你要給調用Shit函數的地方打一個標記的原因。那麼我們可以把代碼改成這樣：

SHIT_CALLABLE! int Shit(int x, int sum)n{n SHIT!n return sum + x;n}nnSHIT_CALLABLE! int Fuck(IEnumerable<int> xs)n{n int sum = 0;n var _xs = xs.CreateEnumerator();n while (_xs.Next())n {n var x = xs.Current;n sum = SHIT_CALL! Shit(x, sum);n }n return sum;n}n

就可以了！其實想想很容易明白，如果一個返回int的函數執行到SHIT!的時候就會停下來等我再次喚醒它，那麼它怎麼可以返回int呢，返回成int我要上哪喚醒？這就像yield return要求你返回IEnumerable<T>，await要求你返回Task<T>一樣，我們也可以要求包含SHIT!的函數返回一個我們定義的介面：

interface IShitCallable<T>n{n T Result {get;}n bool ShitCall();n}nnSHIT_CALLABLE! IShitCallable<int> Shit(int x, int sum)n{n SHIT!n return sum + x;n}nnSHIT_CALLABLE! IShitCallable<int> Fuck(IEnumerable<int> xs)n{n int sum = 0;n var _xs = xs.CreateEnumerator();n while (_xs.Next())n {n var x = xs.Current;n sum = SHIT_CALL! Shit(x, sum);n }n return sum;n}n

這樣我們調用它Fuck，他就返回一個IShitCallable<int>。我們拿到這個IShitCallbale<int>，就不斷地ShitCall它，直到返回true為止，然後去取Result屬性。當我們解開Fuck函數的時候，由於Shit函數返回的也是一個IShitCallable<int>，我們也就可以完美地做出continuation了。

現在我們就來嘗試一下解語法糖，把SHIT!、SHIT_CALL!和SHIT_CALLABLE!從代碼裡面拿掉，變成普通的C#代碼！

首先我們要對付的是Shit函數，Shit函數其實比較簡單，因為沒有分支也沒有循環，那麼我們粗暴的拆成兩半就可以了。根據之前提到的做法，SHIT!前和SHIT!後是兩段不同的代碼，中間的SHIT!會告訴你下一段代碼是什麼，所以我們用一個int給他們編號就好了。然後就變成這樣：

class Shit_IShitCallable : IShitCallable<int>n{n public int state = 0;n public int x;n public int sum;nn public int Result {get; set;}nn bool ShitCall()n {n while (true) // 其實每一個分支都會退出所以這個while (true)等於沒寫n {n switch (state)n {n case 0:n {n /* SHIT! 就編譯成下面兩行 */n state = 1;n return false;n }n break;n case 1:n {n /* return 就編譯成下面三行 */n Result = sum + x;n state = -1;n return true;n }n break;n default:n throw EatShitException();n }n }n }n}nnIShitCallable<int> Shit(int x, int sum)n{n return new Shit_IShitCallable() { x=x, sum=sum };n}n

然後我們要對所有的SHIT_CALL!都解開變成普通的函數調用，其實就是把它弄成一個帶SHIT!的循環：

SHIT_CALLABLE! IShitCallable<int> Fuck(IEnumerable<int> xs)n{n int sum = 0;n var _xs = xs.CreateEnumerator();n while (_xs.Next())n {n var x = xs.Current;n var _Shit = Shit(x, sum);n while (!_Shit.ShitCall())n {n SHIT!n }n sum = _Shit.Result;n }n return sum;n}n

你們看，只要加上了特殊的語法（SHIT_CALL!），那麼其實我們根本就不關心Shit裡面到底長什麼樣子，因為所有的SHIT!都只會直接出現在函數裡面，出現在被調用的函數裡面的SHIT!我們都可以置之不理。

因此剩下來就很簡單了，基本上就是每個while變成兩個片段。這裡要注意的是，由於我們有多個互相嵌套的while，所以不能直接展開，需要添加一些「軟SHIT!」，可以大大降低演算法的腦力負擔：

while (CONDITION)n{n STATEMENTS;n}n==>nwhile (true)n{n 軟SHIT! // 也就是雖然打了個斷點，但是如果命中了它，就立刻繼續執行n if (!CONDITION) break;n STATEMENTS;n}n

展開完成後就變成這樣：

class Fuck_IShitCallable : IShitCallable<int>n{n public int state = 0;n public IEnumerable<int> xs;n public int sum;n public IEnumerator<int> _xs;n public int x;n public IShitCallable<int> _Shit;nn public int Result {get; set;}nn void ShitCall()n {n while (true)n {n switch (state)n {n case 0:n {n sum = 0;n _xs = xs.CreateEnumerator();n /* 其實這相當於我們認為在每一個while的最前面插入SHIT!，然後不中斷，不然直接展開會陷入死循環。SHIT!只出現在嵌套的while裡面就會這樣。這種軟SHIT!就是跟著continue語句的，代表我們並不想中斷，這也是最外面while (true)的作用 */n state = 1;n continue;n }n break;n case 1:n {n if (_xs.Next())n {n x = xs.Current;n _Shit = Shit(x, sum);n state = 2;n continue;n }n elsen {n Result = sum;n /* 這是硬的return */n state = -1;n return true;n }n }n break;n case 2:n {n if (!_Shit.ShitCall())n {n /* 這是硬的SHIT! */n state = 3;n return false;n }n elsen {n sum = _Shit.Result;n state = 1;n continue;n }n }n break;n case 3:n {n state = 2;n continue;n }n break;n default:n throw EatShitException();n }n }n }n}nnIShitCallable<int> Fuck(IEnumerable<int> xs)n{n return new Fuck_IShitCallable{ xs=xs };n}n

到了這裡，相比大家已經明白了SHIT!、SHIT_CALL!和SHIT_CALLABLE!是怎麼回事了，應該很快就可以把它們對應到各種語言的牛逼的功能裡面去了（譬如await）。

總結一下，實現Coroutine主要有三種方法：

  1. 改虛擬機
    1. 好處：實現簡單，跟語言的其他功能是正交的
    2. 壞處：只要你的改動不能merge回主分支，你就會一輩子蛋疼地conflict下去
  2. 語言直接提供continuation
    1. 好處：有continuation可以實現非常強大的控制流語句，Coroutine也只是其中的一個作用而已，你不需要專門為Coroutine做什麼
    2. 壞處：這樣的語言並不常見
  3. 要求SHIT!只能出現在SHIT_CALLABLE!函數裡面，並且調用SHIT_CALLABLE!函數要用特殊的語法SHIT_CALL!，然後解開成一個大switch
    1. 好處：continuation畢竟是閉包，各種閉包群P容易給GC造成壓力（這是Don Syme告訴我的，當初我發郵件問他為什麼F#的computation expression的循環不支持break，他說這樣就不能編譯成狀態機了），而直接改狀態機並沒有這個問題，甚至是像C++這樣沒有GC只有shared_ptr的語言也可以完美支持
    2. 壞處：需要改語法

第一篇就講到這裡了，現在你們應該學會人肉實現Coroutine了吧？這也是考不上三本的人所應該具有的基本能力。人肉實現總歸是比較簡單的，但是你們能不能寫一個程序來代替自己人肉實現Coroutine呢？這就是接下來的幾篇要講的內容。

除此之外，我還將介紹GacUI的Workflow腳本語言是如何在提供基本的Coroutine語法結構的情況下，可以讓你自己來實現yield return和async await的。這樣你就可以創造自己無窮多的Coroutine類型，而不用等語言來幫你做。

最後大家可能會有個疑問，如果我要實現方法2，那這到底有多難？這當然是非常難，要考上三本才會做！


推薦閱讀：

※libco協程庫上下文切換原理詳解
※介紹一下call_in_stack(1)
※協程初步筆記
※使用coroutine實現狀態機（2）
※Kotlin雜談(五) - Coroutines(三): 基本語法

TAG:编程 | 成人教育 | 协程 |