協程

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

根據高德納的說法，馬爾文·康威於1958年發明了術語「coroutine」並用於構建彙編程序，關於協程的最初解說在1963年發表。

## 同子例程的比較

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

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

子例程可以看作是特定狀況的協程，任何子例程都可轉寫為不調用`yield`的協程。

## 偽碼示意

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

```
'''var''' q := '''new''' 队列

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

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

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

## 同線程的比較

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

使用者級線程是協作式多任務的輕量級線程，本質上描述了同協程一樣的概念。其區別，如果一定要說有的話，是協程是語言層級的構造，可看作一種形式的控制流程，而線程是系統層級的構造。

## 生成器

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

儘管如此，仍可以在生成器設施之上實現協程，這需要通過頂層的分派器（dispatcher）例程（實質上是彈跳床 (電腦術語)）的援助，它顯式的把控制權傳遞給由生成器傳回的記號/令牌（token）所標定的另一個生成器：

```
'''var''' q := '''new''' 队列

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

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

'''subroutine''' 分派器
    '''var''' d :=  '''new''' 字典(生成器 → 迭代器)
    d[生产者] := '''start''' 生产者
    d[消费者] := '''start''' 消费者
    '''var''' 当前 := 生产者
    '''loop'''
        '''call''' 当前
        当前 := '''next''' d[当前]

'''call''' 分派器
```

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

## 同尾調用互遞歸的比較

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

## 協程之常見用例

協程有助於實現：

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

## 支持協程的程式語言

協程起源於一種彙編語言方法，但有一些高級程式語言支持它。早期的例子包括Simula、Smalltalk和Modula-2。更新近的例子是Ruby、Lua、Julia和Go。

- Aikido
- AngelScript
- Ballerina (程式語言)
- BCPL
- Pascal（Borland Turbo Pascal 7.0帶有uThreads模塊）
- BETA
- BLISS
- C++（自從C++20）
- C#（自從2.0）
- ChucK
- CLU
- D
- Dynamic C
- Erlang
- F#
- Factor
- GameMonkey Script
- GDScript（Godot的腳本語言）
- Go
- Haskell
- 高級彙編語言
- Icon
- Io
- JavaScript（自從1.7，標準化於ECMAScript 6，ECMAScript 2017還包括async/await支持）
- Julia
- Kotlin（自從1.1）
- Limbo
- Lua
- Lucid
- µC++
- Modula-2
- Nemerle
- Perl 5（使用Coro模塊）
- PHP（帶有hiphop-php，原生支持自從PHP 5.5）
- Picolisp
- Prolog
- Python（自從2.5，帶有改進支持自從3.3，帶有顯式語法自從3.5）
- Raku
- Ruby
- Sather
- Scheme
- Self
- Simula 67
- Smalltalk
- Squirrel (程式語言)
- Stackless Python
- SuperCollider
- Tcl（自從8.6）
- urbiscript

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

## 實現

直到2003年，很多最流行的程式語言，包括C語言和它的後繼者，都未在語言內或其標準庫中直接支持協程。這在很大程度上是受基於堆棧的子例程實現的限制。C++的Boost.Context庫是個例外，它是Boost C++庫的一部分，它在POSIX、Mac OS X和Windows上支持多種CPU架構的上下文切換。可以在Boost.Context之上建造協程。

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

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

### C

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

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

由於缺乏直接的語言支持，很多作者寫了自己的含藏上述技術細節的協程庫，以Russ Cox的libtask協程庫為代表，其目標是讓人「寫事件驅動程序而沒有麻煩的事件」，它可用各種類Unix系統上。知名的實現還有：libpcl、lthread、libconcurrency、libcoro、libdill、libaco、libco等等。

此外人們做了只用C語言的子例程和宏實現協程的大量嘗試，並取得了不同程度的成功。受到了達夫設備的啟發，Simon Tatham寫出了很好的協程示範，它利用了swtich語句「穿透」（fallthrough）特性，和ANSI C提供的包含了原始碼的當前行號的特殊宏名字``，它也是Protothreads和类似实现的基础。在这种不为每个协程维护独立的栈帧的实现方式下，局部变量在经过从函数`yield`之后是不保存的，控制权只能从顶层例程`yield`。

### C++

C++20介入了作為無棧函數的標準化的協程，它可以在執行中間暫停並在後來某點上恢復。協程的暫停狀態存儲在堆之上。這個標準的實現正在進行中，目前G++和MSVC在新近版本中完全支持了標準協程。

### C#

C# 2.0通過迭代器模式增加了半協程（生成器）功能並增加了`yield`關鍵字，C# 5.0包括了await語法支持。

### Go

Go擁有內建的「goroutine」概念，它是輕量級的、無關於進程並由Go運行時系統來管理。可以使用`go`關鍵字來啟動一個新的goroutine。每個goroutine擁有可變大小的能在需要時擴展的棧。goroutine一般使用Go的內建通道來通信。

### Python

Python 2.5基於增強的生成器實現對類似協程功能的更好支持。Python 3.3通過支持委託給子生成器增進了這個能力。Python 3.4介入了綜合性的異步I/O框架標準化，在其中擴展了利用子生成器委託的協程，這個擴展自從版本3.11已經被移除了。Python 3.5通過async/await語法介入了對協程的顯式支持。從Python 3.7開始async/await成為保留關鍵字。例如：

```Python
import asyncio
import random

async def produce(queue, n):
    for item in range(n):
        # 生产一个项目，使用sleep模拟I/O操作
        print(f'producing item {item} ->') 
        await asyncio.sleep(random.random())
        # 将项目放入队列
        await queue.put(item)
    # 指示生产完毕
    await queue.put(None)

async def consume(queue):
    while True:
        # 等待来自生产者的项目
        item = await queue.get()
        if item is None:
            break
        # 消费这个项目，使用sleep模拟I/O操作
        print(f'consuming item {item} <-')
        await asyncio.sleep(random.random())

async def main():
    queue = asyncio.Queue()
    task1 = asyncio.create_task(produce(queue, 10))
    task2 = asyncio.create_task(consume(queue))
    await task1
    await task2

asyncio.run(main())
```

實現協程的第三方庫：

- Eventlet
- Greenlet
- gevent
- Stackless Python

### Perl

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

### Scheme

Scheme提供了對頭等續體的完全支持，實現協程是很輕易的，在續體條目中有使用頭等續體將協程實現為線程的示例。

### Smalltalk

在大多數Smalltalk環境中，執行堆棧是頭等公民，實現協程不需要額外的庫或VM支持。

### Tcl

從 Tcl 8.6 開始，Tcl 核心內置協程支持，成為了繼事件循環、線程後的另一種內置的強大功能。

## 外部連結

- Softpanorama coroutine page – 包含很多彙編協程連結