AI tools
Loading AI tools

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

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

同次常式的比較

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

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

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

偽碼示意

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

var q := new 队列

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

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

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

同線程的比較

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

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

生成器

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

儘管如此，仍可以在生成器設施之上實現共常式，這需要通過頂層的分派器（dispatcher）常式（實質上是彈跳床（英語：trampoline (computing)））的援助，它顯式的把控制權傳遞給由生成器傳回的記號/權杖（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 分派器

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

同尾呼叫互遞歸的比較

參見：互遞歸和尾呼叫

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

共常式之常見用例

共常式有助於實現：

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

支援共常式的程式語言

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

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

實現

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

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

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

C

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

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

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

此外人們做了只用C語言的次常式和宏實現共常式的大量嘗試，並取得了不同程度的成功。受到了達夫裝置的啟發，Simon Tatham寫出了很好的共常式示範[36]，它利用了swtich陳述式（英語：Switch statement）「穿透」（fallthrough）特性[37]，和ANSI C提供的包含了原始碼的當前行號的特殊宏名字__LINE__，它也是Protothreads和類似實現的基礎[38]。在這種不為每個共常式維護獨立的堆疊幀的實現方式下，局部變數在經過從函數yield之後是不儲存的，控制權只能從頂層常式yield[39]。

C++

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

C#

C# 2.0通過迭代器模式增加了半共常式（生成器）功能並增加了yield關鍵字[42][43]，C# 5.0包括了await語法支援。

Go

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

Python

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

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())

實現共常式的第三方庫：

Perl

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

Scheme

Scheme提供了對頭等續體的完全支援，實現共常式是很輕易的，在續體條目中有使用頭等續體將共常式實現為線程的範例[57]。

Smalltalk

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

Tcl

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

參照

參見

延伸閱讀

外部連結

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Chrome
Wikiwand for Chrome
Edge
Wikiwand for Edge
Firefox
Wikiwand for Firefox