[轉載]協程-cooperative multitasking

[轉載]協程三講

http://ravenw.com/blog/2011/08/24/coroutine-part-1-defination-and-classification-of-coroutine/

http://ravenw.com/blog/2011/09/01/coroutine-part-2-the-use-of-coroutines/

http://ravenw.com/blog/2011/09/06/coroutine-part-3-coroutine-and-continuation/

協程（一）協程的定義與分類

由於協程所帶來的便利，以及使用時產生的疑惑，我深入瞭解了一番這個概念。回頭來看，目前網上能查到的關於協程的資料實在不多，而且多數都會造 成一些迷惑和誤解（主要是下文提到的概念模糊問題）。於是我決定寫個系列來詳細介紹這個概念，一方面加深自己的理解，一方面培養點開放共用的精神，同時也 期待大牛的指正。

協程的定義

協程的概念最早由Melvin Conway在1963年提出並實現，用於簡化COBOL編譯器的詞法和句法分析器間的協作，當時他對協程的描述是“行為與主程式相似的子常式”。

Wiki的定義：協程是一種程式組件，是由子常式（過程、函數、常式、方法、子程式）的概念泛化而來的，子常式只有一個入口點且只返回一次，而協程允許多個入口點，可以在指定位置掛起和恢復執行。

這是從直觀上對協程的概念所做的理解，與1980年Marlin的論文中給出的定義類似，也是被廣為引用的協程定義：

• 協程的本地數據在後續調用中始終保持
• 協程在控制離開時暫停執行，當控制再次進入時只能從離開的位置繼續執行

來看Wiki舉出的，也是解釋協程時最常見的生產-消費者模型的例子：

 1 var q := new queue
 2 
 3 coroutine produce
 4     loop
 5         while q is not full
 6             create some new items
 7             add the items to q
 8         yield to consume
 9 
10 coroutine consume
11     loop
12         while q is not empty
13             remove some items from q
14             use the items
15         yield to produce

這個例子中容易讓人產生疑惑的一點就是yield的使用，它與我們通常所見的yield指令不同。這是因為我們常見的yield指令大都是基於生成器（Generator）這一概念的。下麵是基於生成器的生產-消費者模型實現（依然來自Wiki）：

 1 var q := new queue
 2 
 3 generator produce
 4     loop
 5         while q is not full
 6             create some new items
 7             add the items to q
 8         yield consume
 9 
10 generator consume
11     loop
12         while q is not empty
13             remove some items from q
14             use the items
15         yield produce
16 
17 subroutine dispatcher
18     var d := new dictionary (generator → iterator)
19     d[produce] := start produce
20     d[consume] := start consume
21     var current := produce
22     loop
23         current := next d[current] 

根據大部分網上資料（包括Wiki）的解釋，這是基於生成器實現了協程。但根據之前協程的定義：1）本地數據在後續調用中始終保持，2）控制離開時 掛起，重新進入時繼續執行。我們看這裡的produce與consume過程，完全符合協程的概念。也就是說，根據定義，生成器本身就是協程。

兩種明顯不同的控制結構，卻都符合協程的定義，問題出在哪裡？

協程的分類

之前的協程定義的問題在於，這個定義不夠精確，遺留下了開放的，關於協程結構的問題。這導致了協程概念的模糊，造成理解上的困擾。這個問題也部分導 致了主流語言一直缺乏對協程的支持。甚至在描述一些本質上屬於協程的機制時，如Windows的纖程（Fiber），連協程這個術語都很少被提起。

直到2004年由Lua的作者Ana Lucia de Moura和Roberto Ierusalimschy所發表的論文Revisiting Coroutines中，才正式對協程進行了分類，論文中依照三個問題區分協程：

• 控制傳遞（Control-transfer）機制
• 協程是否作為語言的第一類（First-class）對象提供
• 協程是否為棧式（Stackful）構造，即是否可以在內部的嵌套調用中掛起

對稱與非對稱協程

控制傳遞機制的不同區分出了對稱（Symmetric）和非對稱（Asymmetric）協程。對稱協程只提供一種傳遞操作，用於在協程間直接傳遞 控制。非對稱協程（常稱為半對稱（Semi-symmetric）協程或半（Semi）協程）提供調用和掛起兩種操作，掛起時控制返回給調用者。在我們的 生產-消費者模型的例子中，前者是對稱協程，生成器是一種非對稱協程。

出於支持併發而提供的協程通常是對稱協程，用於表示獨立的執行單元，如Modula-2中的協程。用於產生值序列的協程則為非對稱協程，如迭代器和 生成器。在很長一段時間里的普遍看法是，對稱與非對稱協程的能力不同。所以一些支持通用協程機制的語言同時提供了這兩類控制傳遞，如Simula和 BCPL。

事實上很容易證明這兩種控制傳遞機制可以相互表達，因此要提供通用協程時只須實現其中一種即可。但是，兩者表達力相同並不意味著在易用性上也相同。 對稱協程會把程式的控制流變得複雜而難以理解和管理，而非對稱協程的行為在某種意義上與函數類似，因為控制總是返回給調用者。使用非對稱協程寫出的程式更 加結構化。

第一類（First-class）與受限協程

協程是否作為語言的第一類對象提供對錶達力的影響極大。為特定用途而實現的協程，往往把協程對象限制在 指定的代碼結構中，無法由程式員直接控制。一些語言實現的迭代器（CLU，Sather）和生成器（Icon）被限制在某個迴圈內使用，屬於受限協程。只有實現為第一類對象的協程可以提供自定義控制結構的能力，而這種能力正是協程強大的表現力所在。

棧式（Stackful）構造

棧式協程允許在內部的嵌套函數中掛起，恢復時從掛起點繼續執行。非棧式協程只能在主體部分執行掛起操作，可以用來開發簡單的迭代器或生成器，但遇到 複雜些的控制結構時，會把問題搞得更加複雜。例如，如果生成器的生成項是通過遞歸或輔助函數生成的，必須創建出一系列相應層級結構的輔助生成器連續生成項 直到到達原始調用點。非棧式協程也不足以實現用戶級多任務。

完全協程

綜上所述可以認為，是否為第一類對象以及是否為棧式構造，這兩個問題決定了協程的能力。Revisiting Coroutines一文提出了完全協程的概念，即第一類、棧式的協程對象。隨後論證了完全協程的表達力等同於One-shot continuation，關於Continuation的概念及相關論證在隨後的文章中我會提到，Continuation的出現也一定程度上導致了對 協程研究的中止，因為普遍認為Continuation的表達力要遠超協程。

如今對協程的研究和應用有重新複蘇的趨勢，主要集中在兩個方向。一個是研究它在協作式多任務管理上相對於多線程的優勢，目前以程式庫和系統資源的方 式提供了一些此類協程。另一個就是用於迭代器和生成器的協程，如Perl、C#、Python等。而Lua基於Revisiting Coroutines的觀點，實現了完全非對稱協，事實也證明瞭這種機制在實現一些控制結構時異常方便和強大。

相關參考

關於協程的相關資料@sagasw有一篇相當全面的彙總，強烈推薦：關於線程Thread、協程Coroutine、生成器Generator、yield資料。

協程（二）協程的應用

上一篇中對協程的概念做出瞭解釋和澄清。總的來說，完全協程才算得上是真正意義上的協程，其它如生成器等只是部分實現了協程概念的非完全協程，我們之後主要討論完全協程。

本篇介紹一些協程的實際應用。協程本質是一種控制抽象，它的價值在於可以簡潔優雅地實現一些控制行為。在協程中，控制可以從當前執行上下文跳轉到程式的其它位置，並且可以在之後的任意時刻恢復當前執行上下文，控制從跳出點處繼續執行。這種行為與Continuation類似，但協程相比之下更容易理解，某些情況下還更加高效。之後會有一篇專門對比這兩個概念。

生產者-消費者模型

在前一篇中已有提及，這是協程最典型也最常見的應用場景。Conway提出協程這個概念時所解決的編譯器問題就屬於生產者-消費者問題。

管道（Pipeline）也是由生產者-消費者模型擴展而來的，管道實際上是由一個生產者，加上一個或多個過濾器（Filter），再加上一個最終的消費者組成的生產者-消費者鏈。其中過濾器既是生產者又是消費者。以下是由Lua實現的過濾器^*：

 1 function filter(ant)
 2     return coroutine.wrap(function())
 3         while true do
 4             -- resume antecessor to obtain value
 5             local x = ant()
 6             -- yield transformed value
 7             coroutine.yield(f(x))
 8         end
 9     end
10 end

只需要一行語句把生產者、過濾器和消費者串聯起來就可以創建出一個管道：

consumer(filter(producer()))

生成器（Generator）

生成器實際上可以看作只有生產者的生產者-消費者模型。生成器的主要用途就是實現迭代器（Iterator）。需要提到的一點就是目前大多數語言提 供的生成器都是非棧式（Stackful）的，即不能在嵌套調用中直接yield，這樣在實現複雜的生成器時會非常麻煩。比如要實現一個二叉樹的先序遍 歷，先看Lua實現^*：

 1 function preorder(node)
 2     if node then
 3         preorder(node.left)
 4         coroutine.yield(node.key)
 5         preorder(node.right)
 6     end
 7 end
 8 
 9 -- create an iterator
10 function preorder_iterator(tree)
11     return coroutine.wrap(function()
12         preorder(tree)
13         return nil
14     end)
15 end

簡潔而直接，因為Lua的協程是完全協程，允許在嵌套調用中yield。如果用C#實現：

 1 public static class BinaryTree<T>
 2 {
 3     static IEnumerable<T> Preorder(Node<T> node)
 4     {
 5         if (node != null) {
 6             foreach (var key in Preorder(node.left))
 7                 yield return key;
 8 
 9             yield return node.key;
10 
11             foreach (var key in Preorder(node.right))
12                 yield return key;
13         }
14     }
15 
16     public static IEnumerable<T> PreorderIterator(Node<T> tree)
17     {
18         foreach (var key in Preorder(tree))
19             yield return key;
20     }
21 }

可以看到，在遞歸的每一級都需要一個迭代塊向上一級yield，直到最頂層。如果生成器更加複雜，比如需要調用一系列輔助方法，那麼在每個調用點處都要增加機械的yield代碼。

目標導向（Goal-oriented）編程

目標導向編程是指模式匹配 （Pattern-matching）或Prolog的查詢這樣的系統，由用戶提出一個形式化定義的目標（Goal），系統會在一系列可選的子目標中尋找 直到確認一個解決方案。在尋找過程中常常會需要回溯（Backtracking）機制，這種機制使用完全非對稱協程作為生成器很容易實現。

例如用Lua實現一個模式匹配系統，支持匹配常量、可選和序列三種模式的組合^*：

 1 -- matching a string literal
 2 function prim(str)
 3     return function(S, pos)
 4         local len = string.len(str)
 5         if string.sub(S, pos, pos+len-1) == str then
 6             coroutine.yield(pos + len)
 7         end
 8     end
 9 end
10 
11 -- alternative patterns (disjunction)
12 function alt(patt1, patt2)
13     return function(S, pos)
14         patt1(S, pos)
15         patt2(S, pos)
16     end
17 end
18 
19 -- sequence of sub-patterns (conjuction)
20 function seq(patt1, patt2)
21     return function(S, pos)
22         local btpoint = coroutine.wrap(function()
23             patt1(S, pos)
24         end)
25         for npos in btpoint do
26             patt2(S, npos)
27         end
28     end
29 end
30 
31 function match(S, patt)
32     local len = string.len(S)
33     local m = coroutine.wrap(function() patt(S, 1) end)
34     for pos in m do
35         if pos == len+1 then
36             return true
37         end
38     end
39     return false
40 end

使用時形如("abc"|"de")."x"的目標可以定義如下：

patt = seq(alt(prim("abc"), prim("de")), prim("x"))

在進行匹配時這個目標被封裝到一個協程中，通過迴圈逐一嘗試匹配每個子目標。實現中的每個模式函數接受目標字元串和起始位置作為參數，匹配成功時 yield下一個位置給後續匹配，無法繼續匹配時返回nil。我嘗試了一下使用C#來實現上述代碼，得到的編譯錯誤是：不能在匿名方法或lambda表達 式內部使用yield語句。於是我便沒有繼續了，因為已經可以想象最後的完成代碼會有多臃腫。這是C#生成器的又一使用限制，的確非常影響表達力。

協作式多任務（Cooperative multitasking）

併發編程所涉及的範圍太廣，這裡僅討論線程與協程的對比。在併發編程中，協程與線程類似，每個協程表示一個執行單元，有自己的本地數據，與其它協程 共用全局數據和其它資源。目前主流語言基本上都選擇了多線程作為併發設施，與線程相關的概念是搶占式多任務（Preemptive multitasking），而與協程相關的是協作式多任務。

由於搶占式調度執行順序無法確定的特點，使用線程時需要非常小心地處理同步問題，而協程完全不存在這個問題（事件驅動和非同步程式也有同樣的優點），因此非常容易使用。下麵是一段Lua實現多任務的代碼^*：

 1 -- list of "live" tasks
 2 tasks = {}
 3 
 4 -- create a task
 5 function create_task(f)
 6     local co = coroutine.wrap(function() f(); return "ended" end)
 7     table.insert(tasks, co)
 8 end
 9 
10 -- task dispatcher
11 function dispatcher()
12     while true do
13         local n = table.getn(tasks)
14         if n == 0 then break end -- no more tasks to run
15         for i = 1, n do
16             local status = tasks[i]()
17             if status == "ended" then
18                 table.remove(tasks, i)
19                 break
20             end
21         end
22     end
23 end

協作式多任務的缺點之一是進行阻塞（Blocking）操作如IO時會阻塞掉整個程式，解決方案是提供一個輔助函數，初始化IO操作之後如果操作不能立即完成就掛起當前協程，Programming in Lua中給出了一個多任務下載的例子：

 1 function download(host, file)
 2     local c = assert(socket.connect(host, 80))
 3     local count = 0
 4     c:send("GET " .. file .. " HTTP/1.0\r\n\r\n")
 5     while true do
 6         local s, status, partial = receive(c)
 7         count = count + #(s or partial)
 8         if status == "closed" then break end
 9     end
10     c:close()
11     print(file, count)
12 end
13 
14 function receive(connection)
15     connection:settimeout(0)
16     local s, status, partial = connection:receive(2^10)
17     if status == "timeout" then
18         coroutine.yield(connection)
19     end
20     return s or partial, status
21 end
22 
23 threads = {}
24 
25 function get(host, file)
26     local co = coroutine.create(function()
27         download(host, file)
28     end)
29     table.insert(threads, co)
30 end
31 
32 function dispatch()
33     local i = 1
34     while true do
35         if threads[i] == nil then
36             if threads[1] == nil then break end
37             i = 1
38         end
39         local status, res = coroutine.resume(threads[i])
40         if not res then
41             table.remove(threads, i)
42         else
43             i = i + 1
44         end
45     end
46 end

這個例子把每個下載任務放在一個協程中，通過settimeout(0)使獲取操作不會阻塞，再由調度函數逐一喚醒協程執行，如果獲取還未完成就掛起，直到所有下載完成。

協作式多任務的另一個缺點是無法利用多核資源，這一點我認為我們日常所編寫的絕大部分應用都沒有這個必要，除非是實時性要求非常高（如操作系統）或 需要儘可能地榨取機器性能（如Web伺服器）的情況下（即使這時多線程也並非唯一選擇）。所以在你打算使用多線程時先認真考慮一下是否協程就已經足夠。在這篇採訪中也有一些關於協程和併發的觀點供參考。

異常處理

支持異常處理的語言需要實現兩個基礎原語：try和raise。try原語包含兩項表達：主體和異常處理器。若主體正常返回，則返回值作為try的 值，忽略異常處理器。若主體遇到異常條件，則引發（raise）一個異常並立即送給異常處理器，主體的剩餘部分被忽略。異常處理器可以返回一個值作為 try的值，或重新引發一個異常給更外層的異常處理器。

使用完全非對稱協程來實現異常處理很簡單：try原語由一個函數實現，此函數接受兩個函數（主體和異常處理器）作為參數，然後在一個協程中執行主體函數；raise原語也是一個函數，在其中yield出一個異常即可。

總結

協程還適於實現狀態機（每對入口/出口點表現一個狀態），參與者模型（Actor model）（實質上也是協作式多任務）等。重要的是理解協程所表達的控制抽象，在此之上能夠靈活運用的話，原本一些棘手的控制問題也許就可以簡潔優雅地實現出來。

_{* 代碼來自Revisiting Coroutines}

協程（三）協程與Continuation

Continuation表示一個運算在其指定位置的剩餘部分。 當Continuation作為語言的第一類（First-class）對象時，可用於實現多種控制結構。同樣作為控制結構，First-class continuation的表達力比協程更加強大，而且有著明確定義的語義，以至於在它出現之後對協程的研究就幾乎完全停止了。但後來Revisiting Coroutines中證明瞭完全協程與One-shot continuation的表達力是完全相同的，而且協程更容易理解和使用，在某些情況下也更加高效。

理解Continuation

Continuation是一種描述程式的控制狀態的抽象，它用一個數據結構來表示一個執行到指定位置的計算過程；這個數據結構可以由程式語言訪問 而不是隱藏在運行時環境中。Continuation在生成之後可作為控制結構使用，在調用時會從它所表示的控制點處恢復執行。

註意Continuation所保存的控制狀態中並不包括數據。關於這一點有個很有趣的“Continuation三明治”的描述：

假設你在廚房裡的冰箱前面，正打算做一個三明治。這時你獲取一個Continuation放進兜里。然後從冰箱拿了些火雞 和麵包做了個三明治，放在了桌子上。現在調用兜里的那個Continuation，你會發現你又站在了冰箱前，正打算做個三明治。但這時桌子上已經有個三 明治了，而且火雞和麵包也不見了。於是你吃掉了三明治。

Continuation以及與相關的call/cc（Call-with-current-continuation）、CPS（Continuation-passing style）這幾個概念比較難理解也容易混淆，要徹底把它們搞明白還真得花一番功夫。Continuation的資料也不多，這裡列出幾篇中文資料供參考：

• 從Continuation概念說到它在開發中的應用，這篇文章對Continuation的實現和CPS講解得非常清楚。
• Continuations Made Simple and Illustrated，早年Python社區的討論，有中文翻譯簡介延續“Continuation”。
• 尾遞歸與Continuation，老趙（@jeffz_cn）在C#中使用CPS的演示。

First-class continuation

Continuation這個術語很多時候也用於表示First-class continuation。這時它表示一種語言構造，使語言可以在任意點保存執行狀態並且在之後的某個點返回。這裡與協程做比較的正是First-class continuation（或者說是call/cc機制），而不是Continuation結構或CPS編程風格。

調用call/cc時，會把當前Continuation打包成一個第一類對象。然後這個捕獲的Continuation被傳給call/cc的參 數——此參數必須是帶一個參數的過程。如果在這個過程中沒有調用Continuation就返回了，則返回值作為call/cc的值。如果在其中調用了 Continuation並傳給它一個值，則這個值立即返回到call/cc處。

基於First-class continuation很容易實現完全協程，主要思路是在切換協程時保存當前Continuation並調用目標協程的Continuation。以下是由Marc De Scheemaecker基於Ruby call/cc實現的完全對稱協程：

 1 class Coroutine
 2     def initialize(&block)
 3         # Creates a coroutine. The associated block does not run yet.
 4         @started = false
 5         @finished = false
 6         @block = Proc::new {
 7             callcc{|@cc|}
 8             block.call
 9             @finished = true
10             @started = false
11         }
12     end
13 
14     def start
15         # Starts the block. It's an error to call this method on a coroutine
16         # that has already been started.
17         raise "Block already started" if @started
18 
19         @started = true
20         @block.call
21     end
22 
23     def switch(coroutine)
24         # Switches context to another coroutine. You need to call this method
25         # on the current coroutine.
26         switch = true
27 
28         if not coroutine.finished? then
29             callcc{|@cc|}
30 
31             if switch then
32                 switch = false
33 
34                 if coroutine.running? then
35                     coroutine.continuation.call
36                 else
37                     coroutine.start
38                 end
39             end
40         end
41     end
42 
43     def running?
44         # Returns true if the associated block is started and has not yet
45         # finished
46         @started and not @finished
47     end
48 
49     def finished?
50         # Returns true if the associated block is finished
51         @finished
52     end
53 
54     def continuation
55         # Returns the associated continuation object
56         @cc
57     end
58 end

One-shot continuation

所謂One-shot continuation，即只允許調用一次的Continuation。標準的Continuation是允許多次調用（Multi-shot）的，但 是很難高效地實現這樣的Continuation，因為每次調用之前都必然要生成一個副本，而且在絕大多數情況下Continuation都只會被調用一 次，受此啟發Bruggeman et al.提出了One-shot continuation的概念和控制符call/1cc。One-shot continuation幾乎可以所有應用中替換標準Continuation（包括上面協程的實現）。多次調用One-shot continuation會引發錯誤，無論是隱式調用（從傳給call/1cc的過程中返回）還是顯式調用（直接調用由call/1cc創建的 Continuation）。

前面提到過完全協程與One-shot continuation的表達力是相同的，證明方式便是它們可以相互實現。從對稱協程的視角來看，捕獲一個One-shot continuation相當於新建一個協程並把控制傳遞給它。調用時相當於把控制返回給創建者。這種相似性使得基於對稱協程可以很簡潔地實現 call/1cc。

下麵是Revisiting Coroutines中使用Lua實現One-shot continuation的代碼，首先實現一個完全對稱協程：

 1 coro = {}
 2 coro.main = function() end
 3 coro.current = coro.main
 4 
 5 -- function to create a new coroutine
 6 function coro.create(f)
 7     local co = function(val)
 8         f(val)
 9         error("coroutine ended")
10     end
11     return coroutine.wrap(co)
12 end
13 
14 -- function to transfer control to a coroutine
15 function coro.transfer(co, val)
16     if coro.current == coro.main then
17         return coroutine.yield(co, val)
18     end
19 
20     -- dispatching loop
21     while true do
22         coro.current = co
23         if co == coro.main then
24             return val
25         end
26         co, val = co(val)
27     end
28 end

然後是call/1cc：

 1 function call1cc(f)
 2     -- save the continuation "creator"
 3     local ccoro = coro.current
 4     -- invoking the continuation transfers control
 5     -- back to its creator
 6     local cont = function(val)
 7         if ccoro == nil then
 8             error("one shot continuation called twice")
 9         end
10         coro.transfer(ccoro, val)
11     end
12     -- when a continuation is captured,
13     -- a new coroutine is created and dispatched
14     local val
15     val = coro.transfer(coro.create(function()
16         local v = f(cont)
17         cont(v)
18     end))
19     -- when control is transfered back, the continuation
20     -- was "shot" and must be invalidated
21     ccoro = nil
22     -- the value passed to the continuation
23     -- is the return value of call1/cc
24     return val
25 end

效率問題

可以看到，Continuation可以實現協程，同時協程也可以實現One-shot continuation，但這兩種相反實現的效率並不相同。

在Bruggeman et al.描述的One-shot continuation實現中，控制棧由棧段（Stack segment）組成的鏈表表示，整個控制棧被構造成棧幀（Stack of frame）或活動記錄（Activation record）。捕獲Continuation時，當前棧段被保存到Continuation中，然後分配一個新的棧段。調用Continuation 時，丟棄當前棧段，控制返回到之前保存的棧段。

創建一個協程同樣包括分配一個單獨的棧，但掛起和恢復協程的代價只比標準的函數調用略高。

使用協程實現One-shot continuation時，創建一個單獨的協程——即棧“段”——就足以表示一個Continuation。因此，通過協程實現的One-shot continuation與直接實現效率幾乎相同。而以Continuation實現協程時，通常每次協程掛起時都需要捕獲一個新的 Continuation。這導致每次控制轉換都需要重新分配一個棧段，相比直接實現的協程效率要大大降低並且需要更多記憶體。

這裡有一篇Lua、LuaJIT Coroutine和Ruby Fiber的切換效率對比，我猜測大概就是因為Ruby是在call/cc之上實現的Fiber。