协同程序

**共常式**（英語：coroutine）是電腦程式的一類組件，推廣了協同運作式多工的次常式，允許執行被掛起與被恢復。相對次常式而言，共常式更為一般和靈活，但在實踐中使用沒有次常式那樣廣泛。共常式更適合於用來實現彼此熟悉的程式組件，如協同運作式多工、例外處理、事件迴圈、迭代器、無限列表和管道。

根據高德納的說法，馬爾文・康威於 1958 年發明了術語「coroutine」並用於構建組譯程式 ，關於共常式的最初解說在 1963 年發表。

## 同次常式的比較

共常式可以通過 `yield`（取其「讓步」之義而非「出產」）來呼叫其它共常式，接下來的每次共常式被呼叫時，從共常式上次 `yield` 返回的位置接著執行，通過 `yield` 方式轉移執行權的共常式之間不是呼叫者與被呼叫者的關係，而是彼此對稱、平等的。由於共常式不如次常式那樣被普遍所知，下面對它們作簡要比較：

* 次常式可以呼叫其他次常式，呼叫者等待被呼叫者結束後繼續執行，故而次常式的生命期遵循後進先出，即最後一個被呼叫的次常式最先結束返回。共常式的生命期完全由對它們的使用需要來決定。
* 次常式的起始處是惟一的入口點，每當次常式被呼叫時，執行都從被呼叫次常式的起始處開始。共常式可以有多個入口點，共常式的起始處是第一個入口點，每個 `yield` 返回出口點都是再次被呼叫執行時的入口點。
* 次常式只在結束時一次性的返回全部結果值。共常式可以在 `yield` 時不呼叫其他共常式，而是每次返回一部份的結果值，這種共常式常稱為生成器或迭代器。
* 現代的指令集架構通常提供對呼叫棧的指令支援，便於實現可遞迴呼叫的次常式。在以 Scheme 為代表的提供續體的語言環境下，恰好可用此控制狀態抽象表示來實現共常式。

次常式可以看作是特定狀況的共常式，任何次常式都可轉寫為不呼叫 `yield` 的共常式。

## 範例

這裡是一個簡單的例子證明共常式的實用性。假設這樣一種生產者－消費者的關係，一個共常式生產產品並將它們加入佇列，另一個共常式從佇列中取出產品並消費它們。偽碼表示如下：

```
_var_ q := 新建队列

**coroutine** 生产者
    **loop**
        **while** q 不满载
            建立某些新产品
            向 q 增加这些产品 
        **yield** 消费者

**coroutine** 消费者
    **loop**
        **while** q 不空载
            从 q 移除某些产品
            使用这些产品
        **yield** 生产者
```

佇列用來存放產品的空間有限，同時制約生產者和消費者：為了提高效率，生產者共常式要在一次執行中儘量向佇列多增加產品，然後再放棄控制使得消費者共常式開始執行；同樣消費者共常式也要在一次執行中儘量從佇列多取出產品，從而倒出更多的存放產品空間，然後再放棄控制使得生產者共常式開始執行。儘管這個例子常用來介紹多執行緒，實際上簡單明了的使用共常式的 `yield` 即可實現這種協同運作關係。

## 同執行緒的比較

共常式非常類似於執行緒。但是共常式是協同運作式多工的，而執行緒典型是搶占式多工的。這意味著共常式提供並行性而非並列性。共常式超過執行緒的好處是它們可以用於硬性即時的語境（在共常式之間的切換不需要涉及任何系統呼叫或任何阻塞呼叫），這裡不需要用來守衛關鍵區段的同步性原語（primitive）比如互斥鎖、號誌等，並且不需要來自作業系統的支援。有可能以一種對呼叫代碼透明的方式，使用搶占式排程的執行緒實現共常式，但是會失去某些利益（特別是對硬性即時操作的適合性和相對廉價的相互之間切換）。

執行緒是協同運作式多工的輕量級執行緒，本質上描述了同共常式一樣的概念。其區別，如果一定要說有的話，是共常式是語言層級的構造，可看作一種形式的控制流，而執行緒是系統層級的構造，可看作恰巧沒有並列執行的執行緒。這兩個概念誰有優先權是爭議性的：執行緒可看作為共常式的一種實現，也可看作實現共常式的基底。

## 生成器

生成器，也叫作「半共常式」，是共常式的子集。儘管二者都可以 `yield` 多次，掛起（`suspend`）自身的執行，並允許在多個入口點重新進入，但它們特別差異在於，共常式有能力控制在它讓位之後哪個共常式立即接續它來執行，而生成器不能，它只能把控制權轉交給呼叫生成器的呼叫者。在生成器中的 `yield` 語句不指定要跳轉到的共常式，而是向父常式傳遞返回值。

儘管如此，仍可以在生成器設施之上實現共常式，這需要通過頂層的分派器（dispatcher）常式（實質上是彈跳床）的援助，它顯式的把控制權傳遞給由生成器傳回的權杖（token）所標識出的後代生成器：

```
_var_ q := 建立新队列

**generator** 生产者
    **loop**
        **while** q 不满载
            建立某些新产品
            向 q 增加这些产品
        **yield** 消费者

**generator** 消费者
    **loop**
        **while** q 不空载
            从 q 移除某些产品
            使用这些产品
        **yield** 生产者

**subroutine** 分派器
    _var_ d := 创建新字典(**generator** → **iterator**)
    d[生产者] := **start** 生产者
    d[消费者] := **start** 消费者
    _var_ 当前 := 生产者
    **loop**
        **call** 当前
        当前 := **next** d[当前]

**call** 分派器
```

在不同作者和語言之間，術語「生成器」和「迭代器」的用法有著微妙的差異。有人說所有生成器都是迭代器，生成器看起來像函式而表現得像迭代器。在 Python 中，生成器是迭代器構造子：它是返回迭代器的函式。

## 同尾呼叫互遞迴的比較

使用共常式用於狀態機或並行執行類似於使用經由尾呼叫的互遞迴，在二者情況下控制權都變更給一組常式中的另一個不同常式。但是，共常式更靈活並且一般而言更有效率。因為共常式是 `yield` 而非 `return` 返回，接著恢復執行而非在起點重新開始，它們有能力保持狀態，包括變數（同於閉包）和執行點二者，並且 `yield` 不限於位於尾部位置；互遞迴次常式必須要麼使用共享變數，要麼把狀態作為參數傳遞。進一步的說，每一次次常式的互遞迴呼叫都需要一個新的堆疊框（除非實現了尾呼叫消去），而在共常式之間傳遞控制權使用現存上下文並可簡單地通過跳轉來實現。

## 共常式之常見用例

共常式有助於實現：

* 狀態機：在一個次常式里實現狀態機，這裡狀態由該過程當前的出口 / 入口點確定；這可以產生可讀性更高的代碼。
* 演員模型：並行的演員模型，例如電腦遊戲。每個演員有自己的過程（這又在邏輯上分離了代碼），但他們自願地向順序執行各演員過程的中央排程器交出控制（這是合作式多工的一種形式）。
* 生成器：可用於串流，特別是輸入 / 輸出流，和對資料結構的通用遍歷。
* 交談循序程式：這裡每個子行程都是共常式。通道輸入 / 輸出和阻塞操作會 `yield` 共常式，並由排程器在有完成事件時對其解除阻塞（unblock）。可作為替代的方式是，每個子行程可以是在資料管道中位於其後的子行程的父行程（或是位於其前者之父，這種情況下此模式可以表達為巢狀的生成器）。

## 支援共常式的程式語言

共常式起源於一種組合語言方法，但有一些高階程式語言支援它。早期的例子包括 Simula、Smalltalk 和 Modula-2。更新近的例子是 Ruby、Lua、Julia 和 Go。

由於續體可被用來實現共常式，支援續體的程式語言也非常容易就支援共常式。

## 實現

到 2003 年，很多最流行的程式語言，包括 C 語言和它的後繼者，都未在語言內或其標準庫中直接支援共常式。（這在很大程度上是受基於堆疊的次常式實現的限制）。C++ 的 Boost.Context 庫是個例外，它是 Boost C++ Libraries 的一部分，它在 POSIX、Mac OS X 和 Windows 上支援 ARM、MIPS、PowerPC、SPAR 和 x86 的上下文交換。可以在 Boost.Context 之上建造共常式。

在共常式是某種機制的最自然的實現方式，卻不能獲得可用共常式的情況下，典型的解決方法是使用閉包，它是用狀態變數（靜態變數常為布林標誌值）來在呼叫之間維持內部狀態，並轉移控制權至正確地點的次常式。基於這些狀態變數的值，在代碼中的條件語句導致在後續呼叫時有著不同代碼路徑的執行。另一種典型的解決方法實現一個顯式狀態機，採用某種形式的大量而複雜的 switch 語句或 goto 語句特別是「計算 goto」。這種實現被認為難於理解和維護，更是想要有共常式支援的動機。

在當今的主流編程環境裡，共常式的合適的替代者是執行緒和適用範圍較小的執行緒。執行緒提供了用來管理「同時」執行的代碼段即時協同運作互動的功能，在支援 C 語言的環境中，執行緒是廣泛有效的，POSIX.1c（IEEE Std 1003.1c-1995）規定了被稱為 pthreads 的一個標準執行緒 API，它在類 Unix 系統中被普遍實現。執行緒被很好地實現、文件化和支援，很多程式設計師對其也比較熟悉。但是，執行緒包括了許多強大和複雜的功能用以解決大量困難的問題，這導致了困難的學習曲線，當任務僅需要共常式就可完成時，使用執行緒似乎就是用力過猛了。GNU Pth 可被視為類 Unix 系統上執行緒的代表，有人嘗試過用 Windows 的執行緒機制實現共常式。

### C 語言實現

C 標準庫里有「非局部跳轉」函式 setjmp 和 longjmp，它們分別儲存和恢復：棧指標、程式計數器、被呼叫者儲存的暫存器和 ABI 要求的任何其他內部狀態。在 C99 標準中，跳轉到已經用 `return` 或 `longjmp` 終止的函式是未定義的，但是大多數 `longjmp` 實現在跳轉時不專門銷毀呼叫棧中的局部變數，在被後續的函式呼叫等覆寫之前跳轉回來恢復時仍是原樣，這允許在實現共常式時謹慎的用到它們。

POSIX.1-2001/SUSv3 和此前的 SUSv2 進一步提供了操縱上下文的強力設施：setcontext、getcontext、makecontext 和 swapcontext，可方便地用來實現共常式，但是由於 `makecontext` 的參數定義不符合 C99 標準要求，這些函式在 POSIX.1-2004 中被廢棄，並在 POSIX.1-2008 中被刪除。POSIX.1-2001/SUSv3 和此前的 SUSv2 定義了 `sigaltstack`，可用來在不能獲得 `makecontext` 的情況下稍微迂迴的實現共常式。極簡實現不採用有關的標準 API 函式進行上下文交換，而是寫一小塊內聯組譯只對換棧指標和程式計數器故而速度明顯的要更快。

由於缺乏直接的語言支援，很多作者寫了自己的含藏上述技術細節的共常式庫，以 Russ Cox 的 libtask 共常式庫為代表，它自稱能夠「寫事件驅動程式而沒有麻煩的事件」，並可用在 FreeBSD、Linux、Mac OS X 和 SunOS 之上。知名的實現還有：libpcl、lthread、libCoroutine、libconcurrency、libcoro、ribs2、libdill、libaco、libco 等等。

此外人們做了用 C 語言的次常式和宏實現共常式的大量嘗試，並取得了不同程度的成功。Simon Tatham 作出的貢獻是這一方法的很好範例，它受到了達夫裝置利用 swtich 語句「掉落」特性的啟發，並且是 Protothreads 和類似實現的基礎。這種方法的確可以提高代碼段的可寫性、可讀性，但可維護性是存在爭議的。這種不為每個共常式維護獨立的堆疊框的實現方式主要缺點是，局部變數在經過從函式 `yield` 之後是不儲存的，控制權只能從頂層常式 `yield`。

### Python 實現

Python 2.5 基於增強的生成器實現對類似共常式功能的更好支援。Python 3.3 通過支援委託給子生成器增進了這個能力。Python 3.4 介入了綜合性的非同步 I/O 框架標準化，在其中擴充了利用子生成器委託的共常式，這個擴充在 Python 3.8 中被棄用。Python 3.5 通過 async/await 語法介入了對共常式的顯式支援。從 Python 3.7 開始 async/await 成為保留關鍵字。例如：

實現共常式的第三方庫：

### Perl 實現

* Coro，它是 Perl5 中的一種共常式實現，使用 C 作為底層，所以具有良好的執行效能，而且可以配合 AnyEvent 共同使用，極大的彌補了 Perl 線上程上劣勢。

### Scheme 實現

Scheme 提供了對續體的完全支援，實現共常式是很輕易的，只需維護一個續體的佇列。在續體條目中有使用續體將共常式實現為獨立執行緒的一個用例。

### Smalltalk 實現

在大多數 Smalltalk 環境中，執行堆疊是頭等公民，實現共常式不需要額外的庫或 VM 支援。

### Tcl 實現

從 Tcl 8.6 開始，Tcl 核心內建共常式支援，成為了繼事件迴圈、執行緒後的另一種內建的強大功能。

## 參照

## 參見

* 生成器
* 管道 (軟體)
* 通道 (編程)
* 綠色執行緒
* Future 與 promise

## 延伸閱讀

* Ana Lucia de Moura; Roberto Ierusalimschy. Revisiting Coroutines (PDF). ACM Transactions on Programming Languages and Systems. 2004, **31** (2): 1–31 [2019-11-27]. doi:10.1145/1462166.1462167. （原始內容存檔 (PDF) 於 2019-05-13）.

## 外部連結

* Softpanorama coroutine page（頁面存檔備份，存於網際網路檔案館） – 包含很多組譯共常式連結