[程式] Coroutine: 入門篇

[littleshan (我要加入劍道社!)]

                                           圖文版 http://goo.gl/01f0e


很久以前就想要寫一篇介紹 coroutine 的文章。Coroutine 對於遊戲程式來說
是個非常有用的語言功能，不過學校課程幾乎不會介紹這個東西。最近藉由實作
上的經驗，整理出幾篇心得，請各位慢慢品嘗。

        *       *       *       *       *       *

Coroutine 一般翻譯作「協程」，對一般 programmer 來說可能有些陌生，但其
實這個想法早在 1963 年就被提出來了。近年來因為 multi-threading 的普及，
主流語言鮮少提供 coroutine 的功能，但即使 coroutine 與 thread 的概念相
似，卻有許多截然不同的特性，不少場合使用 coroutine 既能優雅地解決問題，
又能避免 multi-threading 的 race condition。本系列文章將會介紹 coroutine
的基本概念及應用場合，讓原本複雜的流程變得簡潔易懂。

Lua 是支援 coroutine 的語言之一，同時也具備簡單易學的特性，以下將會使用
Lua 程式碼作為 coroutine 的示範。對 Lua 不熟悉的讀者可以參考 Lua Tutorial
Dictionary 上的教學，實際學起來是很快的。

[Lua Tutorial Dictionary]: http://lua-users.org/wiki/TutorialDirectory


 Coroutine 基本概念

Coroutine 可以視為「可以中斷及繼續執行的函式呼叫」。在一般的程式語言中，
呼叫某個函式時，該函式一定是從頭開始執行：

    function foo(n)
        print("hello")
        print("world")
        print("n^2 = "..(n*n))
    end

    foo(10) -- 不間斷地印出三行字

然而 coroutine 允許函式執行到一半就中斷（yield），中斷時內部狀態會被保
留下來，呼叫端可以隨時在之後恢復（resume）這個 coroutine。

    function bar(n)
        print("hello")
        print("world")
        coroutine.yield()            -- 在這裡中斷 coroutine
        print("n^2 = "..(n*n))
    end

    local co = coroutine.create(bar) -- co 是保留 coroutine 內部狀態的變數

    coroutine.resume(co, 10)         -- 只印出前兩行 hello world
    print("this is the third line.") -- 中斷後主程式可以做其它事
    coroutine.resume(co)             -- 印出最後一行 n^2 = 100

上述的範例即為 coroutine 的呼叫方法：

  1. 呼叫端並非直接呼叫函式，而是使用 coroutine.create 來產生一個
     coroutine object。這個 object 將會儲存 coroutine 的執行狀態，
     包括區域變數的內容及中斷點的位置。

  2. 產生 coroutine object 的時候並不會呼叫函式，而是在第一次使用
     coroutine.resume 的時候，才會從函式的開頭開始執行。

  3. 在函式中使用 coroutine.yield 時，將會中斷函式執行並保留中斷時
     的狀態，控制權隨即轉移到呼叫端。

  4. 呼叫端再次執行 coroutine.resume 的時候，流程將會回到 coroutine
     上次中斷之處，繼續往下執行到 yield 或函式結束。


 任意中斷的特性

Coroutine 中的兩項操作：yield 及 resume，在 Lua 中只是基本的函式呼叫。
你可以使用任意數量的 yield 來中斷 coroutine，當然也可以放在迴圈之類的
控制結構當中。

    function fibb()
        local a = 1
        local b = 0
        while true do
            print(a)
            coroutine.yield()
            local tmp = a
            a = a + b
            b = tmp
        end
    end

    local co = coroutine.create(fibb)
    for i=1,20 do                     -- 印出費氏數列前20項
        coroutine.resume(co)
    end

當然，在 coroutine 中可以呼叫其它函式，而 yield 也能出現在更深層的函式
當中。我們會在下一篇文章中介紹這個應用。


 Coroutine 的資料傳遞

在上面費氏數列的例子中，我們都是把數字印出來後才呼叫 coroutine.yield，
這顯然彈性不夠－－呼叫端可能想把數字寫到檔案、或是塞進陣列中。我們能直
接把數值在 yield 的同時直接傳回到主程式嗎？答案是肯定的，而且方法非常
簡單：直接當作參數丟給 coroutine.yield。

    function fibb()
        local a = 1
        local b = 0
        while true do
            coroutine.yield(a)
            local tmp = a
            a = a + b
            b = tmp
        end
    end

    local co = coroutine.create(fibb)
    local array = {}                  -- 建立空陣列
    local state                       -- 表示 coroutine 的狀態
    for i=1,20 do                     -- 把費氏數列前20項填進陣列中
        state, array[i] = coroutine.resume(co)
    end

coroutine.resume 的第一個回傳值皆為 true 或 false，表示該 coroutine 是否
正確執行。而第二個以後的回傳值則是 coroutine 在中斷時傳進 coroutine.yield
的參數，因此在第 15 行我們需要用兩個變數來接 coroutine 的回傳值。

反過來說，主程式也可以在呼叫 coroutine.resume 的時候添加參數，這些參數會
被傳遞到 coroutine 當中，作為 coroutine.yield 的回傳值。

    function foo(n)
        print("n = " .. n)
        while true do
            print("received " .. coroutine.yield())
        end
    end

    local co = coroutine.create(foo)
    coroutine.resume(co, 10)         -- 印出 n = 10
    coroutine.resume(co, 20)         -- 印出 received 20
    coroutine.resume(co, 30)         -- 印出 received 30
    coroutine.resume(co, 40)         -- 印出 received 40

第一次呼叫 coroutine.resume 時，添加的參數會被當作是函式的參數，也就是 n。
第二次以後的 resume 其參數則會被當作 yield 的回傳值送進 coroutine 之中。

籍由資料傳遞的功能，我們可以利用 coroutine 輕鬆實作出 iterator pattern。
我會在下一篇文章介紹這項應用。


 Coroutine 與 Generator

嚴格說來，Lua 所提供的 coroutine 應該要稱之為 generator。根據 wikipedia
的說法，coroutine 在進行 yield 操作時需指定另一個 coroutine 作為參數，
因此多個 coroutine 之間可以隨意跳來跳去。而在 Lua 的 coroutine 中，yield
必然回到上次呼叫 resume 的地方。

這是 wikipedia 上的例子，注意 yield 時要同時指定流程跳躍的目地。

    var q := new queue

    coroutine produce
        loop
            while q is not full
                create some new items
                add the items to q
            yield to consume

    coroutine consume
        loop
            while q is not empty
                remove some items from q
                use the items
            yield to produce


嚴格定義下的 coroutine 實際上可以用 generator 來達成，而許多語言似乎也
沒有很精確地區分這兩者。在接下來的文章中，我會繼續用 coroutine 來稱呼。


 Coroutine 與 Thread

在系統層面上，coroutine 通常和 fiber 是一樣的意思。Fiber 是一種特別的
user thread，如同一般的 thread 那樣具有自己的 call stack 與 program
counter，但具備了以下的特性：

  * Thread 不需自己定義中斷點（也就是呼叫 yield 的地方），而是讓 OS 或
    thread library 來決定是否進行 context switch，通常由執行時間來判斷。
    然而 fiber 需要自行定義中斷點，context switch 只會發生在明確呼叫
    yield 的地方。

  * 因為 context switch 是由使用者自行控制，因此 fiber 通常不需要 mutex
    之類的東西來避免 race condition。

  * Kernel thread 會進入 OS 的排程中，在多核心的 CPU 上可能會使用不同的
    核心同時執行許多 kernel thread。但 fiber 屬於特別種類的 user thread，
    它無法利用多核心進行平行處理。

        *       *       *       *       *       *

下一篇文章中，我將以 iterator 作為例子，介紹簡單的 coroutine 應用方式。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 202.39.238.241
推 s3748679:支持~ 加油~ -w-"
推 adxis:GJ!
推 gpmm:push
※ 編輯: littleshan      來自: 202.39.238.241       (07/08 17:54)
推 wangm4a1:push
推 SamMa: 感謝分享 受益良多