C語言是一種可移植的匯編語言，這從它的簡單的語言結構可以看出來，這里面沒有高級語言常見的嵌套子程序定義；沒有自動的對象分配和回收；沒有復雜的流程控制原語和類型定義原語。它的一切都是那么簡單直接和暴露，例如它允許指針和整數之間的直接轉換甚至是運算。這些都是匯編語言的特點，如果去掉針對特定處理器架構的指令集，匯編語言也就剩下這些了。
D. E. Knuth在他的名著《計算機程序設計的藝術》中使用了他自己定義的匯編語言對協同例程（coroutine）進行了比較純粹的討論。我們今天使用C語言來模擬協同例程，這比他的實現稍微困難一點，因為這涉及到了對C語言實現的具體技術的拆解，說白了，我們需要一些黑客的手段來取巧。這些黑客手段雖然對于大多數的C編譯器都是有效的，但是從理論上講并不是完全可以移植的。閱讀本文可以得到多方面的程序設計體驗，讀者也許會覺得某一部分比其它部分更有趣。
雖然用C語言模擬協同例程要比使用匯編語言困難，但是并不是太難，相比于其它的高級語言，比如Pascal。不過有些非常高級的語言卻直接支持某種類型的協同例程，這種類型的協同例程在實踐中被認為是簡化了程序的邏輯表達，故此新近的語言都試圖去支持它，例如C#2。這種協同例程就是所謂的迭代子（iterator）或者生成子（generator）。我們知道，在流行的語言里面，Python是支持它的，然而和計劃中的C#2一樣，支持的不夠好。支持協同例程方式迭代子的比較好的語言之一是Sather[1]，下面我主要通過這種語言來討論協同例程和迭代子。
當然，這里的重點并不在介紹Sather語言，只不過看看和題目相關的部分。實際上Sather已經是瀕臨滅絕的語言了，如今幾乎找不到可以使用的編譯器，像這樣的語言還很多。有時候我想，一種語言想要流行，一開始必定不能有太先進的概念，在人們的使用中慢慢加入會比較讓人容易適應，并誤以為該語言在不斷提出新概念，盡管也許十年前就已經在其它語言中實現得非常徹底了。Sather是一種過程式語言，支持面向對象的程序設計，這兩點都是廣為熟悉的，因此理解下面的程序片斷并不會非常困難。下面是Sather語言中的循環，看起來非常易懂：
sum: INT := 0; i: INT := 1;
loop while!(i <= 10);
sum := sum + i;
i := i + 1
end;
這樣子和C或Pascal的循環語句沒什么太大的不同，程序的意思也是一樣的。不過這里的關鍵字只有loop和end，while!并不是關鍵字，實際上它是一個迭代子，是一個協同例程。在Sather里面，迭代子是以嘆號（!）結尾的，而對迭代子協同例程的創建和調用是通過loop/end循環來完成的。那么什么是協同例程呢？
子例程（subroutine）是經常使用的一種程序流程，父例程在調用子例程的時候暫時中斷自身的流程，將控制轉到子例程的起點，然后一直到子例程返回才繼續父例程的流程。這是一種棧式的調用，就是說后進入的子例程，卻要先返回。因此許多程序都是用棧來存放子例程的局部運行環境，因為當子例程返回后，這個局部的運行環境就不需要了，也就是后進先出。
然而，有些例程之間并不是父例程調用子例程這種嵌套的關系，而是并行的協同關系，當一個例程運行時，需要另外一個例程所不斷產生的結果，例如兩個通過管道連接的程序就是這樣的關系。例程A需要數據，就把控制傳遞到例程B，而B產生一些數據，然后把控制返回給A，A處理完這些數據以后會需要更多的數據，于是又把控制傳給B，這時并不是A重新調用B，而是恢復B剛才運行的斷點，讓B可以按照自己原先的流程繼續運行。例程A和例程B的運行環境都需要保持，不存在誰必須先退出才能轉移控制的問題。控制在這兩個例程間跳來跳去，它們是協同的關系，例程B就成為例程A的協同例程，而不是子例程了。
range!(min, max: INT): INT is
i: INT := min;
loop until!(i > max);
yield i; --
i := i + 1;
end
end;
上面這個就是一個迭代子的定義，它產生從min到max的一系列整數，通過yield語句將中間結果和控制轉移給主例程，再次調用同一個迭代子會使控制返回到緊接著yield語句的地方繼續運行，繼續產生新的中間結果。主例程通過反復調用range!來啟動迭代子以及恢復迭代子的運行。而中間結果就稱為迭代子的返回值。
sum: INT := 0;
loop
i: INT := range!(1, 10);
-- 當range!結束時，循環在此退出。
sum := sum + i
end;
這段程序和第一個程序的作用是一樣的。我們發現while!沒有了，這使得它看上去像個死循環。實際上當然不是，loop/end循環中如果存在對迭代子的調用，那么一旦其中某個迭代子結束運行，循環就會在對該迭代子的調用處退出。從下圖可以看到主程序和迭代子的協同運行過程。
range!迭代子正是我們所描述的協同例程。迭代子通常都包含一個loop/end循環，就像range!那樣，那么這個循環又是怎樣退出的呢？它需要另一個迭代子until!結束的時候才能退出。不過until!迭代子也是包含循環的，最終我們需要某個不包含循環的迭代子，例如break!。
break! is end;
類似while!和until!這樣的基本迭代子通常需要通過break!來退出循環。例如while!可以如下定義：
while!(pred: BOOL) is
loop
if pred then yield
else break!
end
end
end;
可以看到，while!定義中的yield后面沒有返回值，它只是將控制轉移回主例程。迭代子的參數并不是只在開始有用，每次通過調用恢復迭代子的運行時，主例程都可以傳遞不同的參數，也就是說在yield的前后，迭代子的形式參數可以代表不同的實際值。while!的唯一作用就是根據所傳遞的條件參數來決定是否結束運行，從而使得調用它的主例程中的循環可以根據條件結束。類似的，until!也是這個作用。它們和我們通常認為的含義完全一樣，只不過更為靈活，迭代子可以出現在循環體中間，而不是必須在循環開始或結尾。
在每次恢復迭代子運行時可以傳遞參數（PARameter）是很有用的特性，這一點在Python語言中并不具有。我們已經看到while!和until!是怎樣使用這個特性了。事實上，作為迭代子調用的參數和迭代子每次通過yield產生的返回值（RETurn value）一樣，是兩個互相協同運行的例程動態交換數據的渠道。表面上迭代子作為協同例程處于被動的地位，但是實際上主例程和協同例程的區別并不是那么大，主例程通過參數傳遞數據，協同例程通過返回值傳遞數據，它們幾乎是對稱的。
有時候，我們也構造永不結束的迭代子，或者稱為生成子更合適，這種生成子通常被叫作流（stream）或者無限序列，它可以源源不斷的提供某種數據。下面是一個正整數的無限序列：
positives! : INT is
i: INT := 1;
loop
yield i;
i := i+1
end
end;
使用這種迭代子的循環，要么本身是另一個無限序列，要么就需要通過其它的迭代子來退出。也就是說，我們可以在同一個循環中使用多個迭代子。從上面簡單的例子中似乎看不到協同例程迭代子相對于子程序的優勢，例如上圖所示，流程可以很輕易轉為在單一例程中執行。然而，從基本的概念上講，迭代子可以很有效的避免兩種不同操作的耦合，把數據的使用和生成分別開來。對于更為復雜的問題，利用動態生成的迭代子，則可以非常簡潔的進行程序的描述。
到目前為止，迭代子看上去只是靜態的一段程序。不過，在程序實際運行過程中的迭代子則類似一個線程，它是一段程序的一次運行，只不過這個線程需要在指定的地方和其它協同例程進行同步，這個指定的地方成為中斷點或同步點。運行過程以及當時所在的運行環境被稱為一個例程閉包，這是動態的運行對象。因此，迭代子有一個創建的過程，這個過程構造了初始的運行環境，隨著例程的運行，運行環境在不斷的變化。同一個迭代子描述可以生成多個運行對象，如同多個線程共享同一段代碼一樣。例如：
i: INT := 1;
loop
while! ( f(i) );
i := i+1;
while! ( g(i) );
i := i+2
end;
while!創建了兩個迭代子。多線程確實是實現協同例程的一個選擇，不過后面的例子可能會讓你打消這個念頭。上面我們提到了無限序列，學過數論的人都知道素數序列就是一個無限序列。現在我們就來描述這個素數生成子。首先，我們設計一個判定素數的迭代子，這個迭代子將根據依次輸入的一系列整數不斷產生相應的布爾判斷結果。我們把這個迭代子稱為sieve!，因為事實上這個實現是篩法的一個變形。sieve!的一系列輸入參數符合下面三個條件：
第一個參數必須是一個素數，不妨稱為x；
后面的參數必須是嚴格遞增的，并且不能被小于x的所有素數整除；
所有滿足條件2的整數都必須依次傳入，沒有遺漏。
在符合這三個輸入參數條件的情況下，sieve!可以如下的返回判斷結果：
sieve!(cand: INT): BOOL is
x: INT := cand;
yield true;
loop
if x.divides(cand) then yield false;
else yield sieve!(cand)
end
end
end;
首先，在迭代子開始，由于第一個傳入的參數是素數，我們記錄這個素數為x并返回真值（為了區別起見，我們用第一個參數來命名sieve!，這里也就是sieve![x]）；接著，進入循環處理后來的輸入參數，對于任意的后來參數y，由于嚴格遞增的緣故，y肯定不等于x，這時如果x整除y（x|y）則y是合數，我們返回假值；否則我們遞歸創建和調用sieve![y]來進行進一步的判斷。需要證明的是，在sieve![x]的參數滿足上述條件的前提下，遞歸創建的sieve![y]的參數也滿足這些條件。第一條是滿足的，因為傳入sieve![y]的是所有不能被小于或等于x的素數整除的數，而這些數以嚴格遞增且無遺漏的方式傳入sieve![x]，除去那些被x整除的合數外，剩下的也是嚴格遞增無遺漏的傳給了sieve![y]，所以第一次傳入sieve![y]的數y必定是大于x的第一個素數；同時，我們也已經說明后面的兩條也是滿足的。
我們的數學歸納法還欠缺一個基礎，那就是對第一個sieve!如何傳遞參數。非常顯然，我們把從2開始的所有正整數依次傳遞給它就可以了。那么這個sieve![2]是不是能返回正確的判定結果呢？如果sieve![2]對于某個參數返回的話，我們可以看到返回布爾值的地方只有兩個，迭代子開始的地方返回真值，我們已經證明了任何層次開始的sieve!的第一個參數都是素數；另外就是在參數被一個素數整除時返回假值。顯然這兩種情況都是正確的。問題是，sieve![2]會不會一去不返？這不可能，因為內層的sieve!的第一個參數嚴格大于外層sieve!的第一個參數（它們都是素數），而且素數是無限的，對于任一有限的正整數n，總會存在某個素數z > n，也就是說n不可能被傳入sieve![z]，那么判斷值肯定在之前就返回了。綜上所述，我們的素數無限序列就是這樣的：
| primes!: INT is c: INT := 2; loop if sieve!(c) then yield c end; c := c+1 end end | quicker_primes!: INT is c: INT := 3; yield 2; loop if sieve!(c) then yield c end; c := c+2 end end |
右面那個會快一些，但是很輕微。仔細想一想就會知道我們使用了多少個協同例程，每個素數都有一個！無疑這樣的判定素數的方法開銷比較大，但不是在空間上的，因為即使我們用數組記錄素數也需要一個蘿卜一個坑，只不過例程閉包的坑大一些。這個算法的時間開銷比較大，因為判定一個數n是不是素數最多只要測試小于或等于n的平方根的所有素數就可以了，這個算法卻最多要測試到所有小于n的素數。如果我們使用線程來實現協同例程的話，那么操作系統就會負擔很重了。我計算了一百萬以內的素數，有78,498個，我真想試試操作系統的能力。盡管開銷較大，但是這種程序的表達卻是非常間潔的。下圖示意了素數迭代子的運行過程。
2
在缺乏原語支持的語言里，實現協同例程的關鍵是如何構造例程閉包。例程閉包是一個例程的代碼加上在運行到某一刻時的環境，代碼通常是不變的，環境則包含了該例程所用到的全局和局部的變量狀態和機器狀態。全局變量為所有例程所共享，它們是可以變化的，如果一個例程通過函數調用來中斷運行并轉移控制，那么在恢復運行后，從編譯器看來是從函數調用中返回，它不會假定全局變量仍具有原來的值。對于局部于例程的變量，因為語義上它們不能被其它例程所改變，因此我們必須保證它們在中斷以后可以保持不變。對于機器狀態，包括斷點和寄存器，也是需要保存的，它們和局部變量一起形成了例程的局部環境。因此，我們所說的例程閉包的構造主要是局部環境的保存和恢復。
C語言中有一對庫函數setjmp和longjmp，它們可以用來保存斷點處的機器狀態，因此我們的主要任務是保存局部變量。許多的C編譯器都是把局部變量放在棧上或者寄存器中，如果是后者，則在機器狀態中已有保存，如果是在棧上，因為棧是各個例程所共享，則需要我們把運行時例程所用到的局部棧空間復制到另外的地方保存起來，在斷點恢復以后再把棧中的數據恢復。因此，對于C編譯器如何使用棧必須準確了解，我們關于這點作出如下的假定，這些假定對于許多CPU架構上的C編譯器都是適用的。
棧使用的是普通的內存空間，它可以通過memcpy進行訪問；
函數的調用者的局部變量、返回地址和參數在棧上的空間先于被調用函數在棧上的局部變量、返回地址和參數所占的空間；
棧空間的分配和釋放都是是嚴格單向的（本文中假設棧是從高地址向低地址擴展，由反方向收縮，這適合于x86架構）；
對一個局部變量進行取地址操作將使得編譯器在棧上分配該局部變量，而不是只存放于寄存器中（這樣我們可以得到例程局部棧空間中的某個位置）；
對于longjmp函數，我們可以確定它使用的局部棧空間的上限。
只要我們知道例程的局部棧空間的位置（地址范圍），就可以在執行setjmp保存機器狀態之前利用memcpy來將局部棧中的內容保存起來。精確的范圍是不需要的，我們可以保存多一些。下圖展示了嵌套調用的三個例程的局部棧的關系，基于上面的假設。
| void f() { int i; void *hi = &i; g(hi); } void g(void *hi) { h(hi); } void h(void *hi) { int j; void *lo = &j; memcpy(st_save, lo, (char*)hi-(char*)lo); } | 
|
可以看到，通過f和h兩個函數，我們取得了g的局部棧范圍[2]，綠色部分就是要保存和恢復的g的局部棧。保存多一點顯然不礙事，但是恢復多一點又如何呢？如果我們把斷點設在g里面，也就是先調用h來保存局部棧，返回g以后再轉移控制到其它協同例程去，那么在g沒有退回f之前，f的局部棧是不會改變的，因此恢復f局部棧的一部分沒有影響；另一方面，由于h已經返回g了，h的局部棧已經沒有用了，往里面寫什么都沒關系了。因此通過這個技巧來保存局部棧數據是正確的。不難理解，g可以代表一系列嵌套的函數調用，并不局限在一個函數：g0調用g1，g1調用g2，...，最后gN調用h。
在恢復局部棧以后需要執行longjmp來恢復機器狀態（寄存器和斷點），而longjmp是一個函數，它需要建立自己的局部棧，無疑我們不能讓這個局部棧覆蓋剛剛恢復的數據。如果假設5成立，我們對于longjmp的局部棧有上限int[L]，這時可以通過一個子程序clean中的局部數組來進行判斷，看看主程序restore的棧位置和要恢復的局部棧之間有沒有足夠空間調用longjmp，如果有，那么clean退回，由restore主程序來恢復局部棧數據并調用longjmp；如果沒有，則遞歸調用clean，直到clean的棧完全跨越要恢復的局部棧，然后由clean來恢復局部棧及調用longjmp。這個分析如下圖所示。
通常假設5都是成立的，因為大多數的longjmp實現只是從一個數組中恢復所有寄存器和斷點，它的局部棧里幾乎沒有局部變量，只有參數和返回地址。當然，如果不愿意冒險去估計這個上限，那么無條件使用第二種方法也是可以的。
現在我們已經完全解決了例程局部環境的保存和恢復，下面就把這個過程正式書寫出來。首先，為局部環境定義一個結構，稱為局部環境塊，它完全代表了一個例程閉包：
typedef int par_s, ret_s;
typedef struct _S_env env_s, *env_p;
struct _S_env {
union {
par_s Par;
ret_s Ret;
char* St_hi;
env_p Env;
} V;
env_p Co;
int Signal;
char *St_hi, *St_lo;
void *St;
int St_size;
jmp_buf Buf;
};
里面有些域尚未說明，在后面將會進行討論。其中我們已經熟悉了St_hi和St_lo，它們儲存了例程中斷時的局部棧范圍，St則指向可以保存局部棧的內存空間，St_size是它的大小，兩次斷點處的局部棧可能是不一樣大的，故當St_size太小時，需要重新分配空間給St。保存和恢復局部環境的代碼如下：
void Save_stack(env_p E)
{
int Any;
E->St_lo = (char*)&Any;
if ( E->St_hi-E->St_lo > E->St_size ) {
free(E->St);
E->St_size = E->St_hi-E->St_lo;
E->St = malloc(E->St_size);
}
memcpy(E->St, E->St_lo, E->St_hi-E->St_lo);
}
int Save(env_p E)
{
Save_stack(E);
return setjmp(E->Buf);
}
void Clean_restore(env_p Co)
{
env_p Any[32];
if ( (char*)&Any[1] < Co->St_lo ) {
Any[0] = Co;
memcpy(Co->St_lo, Co->St, Co->St_hi-Co->St_lo);
longjmp(Any[0]->Buf, 1);
} else if ( (char*)&Any[1] <= Co->St_hi )
Clean_restore(Co);
}
void Restore(env_p Co)
{
Clean_restore(Co);
memcpy(Co->St_lo, Co->St, Co->St_hi-Co->St_lo);
longjmp(Co->Buf, 1);
}
St_hi只能在協同例程啟動時由上層調用者（也就是前面所說的f）設置，在例程運行過程中是無法得到的。這里我們假定longjmp最多使用31個機器字的棧空間，數組的第一個元素用來存放傳入的參數，這是因為雖然數組的首元素跨過了需要恢復的局部棧，但是函數的參數是先于局部數組的，它可能仍處于要恢復的局部棧范圍內，當局部棧恢復后，參數可能被覆蓋了。這個參數指向要恢復的局部環境塊，longjmp需要從中取得jmp_buf以便恢復機器狀態。使用數組的一個元素并不是為了省去一個變量的聲明，而是為了保證變量的位置確實不會被覆蓋。
在上面的代碼中有一個書寫習慣，我們把正在運行的例程的局部環境塊（指針）稱為E（這沒什么太多道理，我開始就這么用了），把將要轉移過去的協同例程的局部環境塊稱為Co（這就有些道理了）。在后面的代碼中也是保持這個習慣。
如果不保存局部棧，那么setjmp/longjmp是不能嵌在別的函數里面使用的。這對函數通常被用作異常處理，因此只是從內層函數向外層函數跳轉時是有效的（這里指的是調用層次，不是書寫層次，C語言中的函數沒有書寫層次），由于內層函數不會破壞外層函數的局部棧，因此從內往外跳不存在恢復局部棧的問題。像我們這樣使用，通過調用Save來setjmp，這等于保存了子程序Save的狀態，將來調用longjmp時是從外往內跳，如果不保存Save的局部棧，那么連Save的返回地址都可能丟失，通過longjmp返回到Save里面以后，很可能不知道再往什么地方返回。在其它場合使用setjmp/longjmp的時候要特別注意這個問題。
由于遞歸迭代子的存在，并且遞歸層次數量龐大，我們自然要關心棧的深度。如果我們在迭代子例程中直接啟動另外一個迭代子例程，那么后面的例程的局部棧必定位于前面的之后（在這里代表更低的地址），對于sieve!這樣遞歸的無限序列來說，棧很快就溢出了，因為預留給棧的地址空間是遠遠小于整個可用地址空間的。我們既然將每個協同例程的局部棧都保存了起來（在堆中），因此完全沒必要受棧空間限制。各個例程可以共用同一棧地址，因為它們不會同時運行，運行之前原先的局部棧都會被恢復。如何能做到共用棧地址呢？如果所有的協同例程都由同一處啟動就可以了，同樣這里的同一處是指運行時的，不是書寫上的。我們再次利用setjmp/longjmp，首先用setjmp靜態的保存一處地方A，在需要啟動協同例程時把參數存放在靜態變量中，通過longjmp回到斷點A繼續執行，然后取出靜態變量中的參數啟動協同例程。如果我們不再更新斷點A的機器狀態，就總能回到同一個地方去，也就是總能使用同一個棧地址。遞歸迭代子的數量就僅受堆空間的限制了。
typedef void (*coroutine_p) (env_p);
void Setup_iter_helper(coroutine_p R, env_p E)
{
static coroutine_p R_s;
static env_p E_s;
static jmp_buf Buf;
if ( R ) {
R_s = R;
E_s = E;
longjmp(Buf, -1);
} else if ( setjmp(Buf) != 0 ) {
int Any;
E_s->V.St_hi = (char*)&Any;
R_s(E_s);
assert(0);
}
}
這段程序寫得有點取巧，為的是把靜態變量藏在函數中以使名字簡單些。它有三個功能，首先當R=0時進行初始化，它用setjmp保存一個斷點A；當R不為空時，它指向我們要啟動的協同例程（上面定義了所有協同例程的原型），函數把參數轉存到靜態變量中后恢復斷點A；斷點A恢復后，函數取出靜態變量中的參數啟動協同例程（這里沒有使用任何棧里的內容，也不能使用，因為我們沒有保存這個函數的局部棧），注意由于這是啟動例程的直接調用者（就是那個f），它要負責設置例程局部棧的上限，使用我們已經討論過的技巧。局部環境結構env_s中的域V是一個聯合，它的作用是傳遞參數，當一個協同例程啟動另一個協同例程時，需要把自己的局部環境塊傳遞給被啟動者，可以看到被啟動例程的局部棧上限就是這樣作為參數通過啟動者的局部環境塊而傳遞的。啟動者首先保存自己的局部環境，然后調用上面的函數。
env_p Setup(coroutine_p R, env_p E)
{
if ( Save(E) == 0 )
Setup_iter_helper(R, E);
return E->V.Env;
}
當控制從被啟動的協同例程返回時，Setup得到一個結果，那就是被啟動例程的局部環境塊，利用它可以再把控制傳回去。這是啟動迭代子例程時啟動者和被啟動者的一個協議，當控制傳給被啟動例程后，被啟動者首先必須完成局部環境塊的設置，然后立即把控制返回給啟動例程，以便在其需要時進行迭代，被啟動的迭代子通過調用Ready來完成這個任務：
env_p Ready(env_p Co)
{
env_p E = (env_p)malloc(sizeof(env_s));
E->St = 0;
E->St_size = 0;
E->St_hi = Co->V.St_hi;
E->Signal = 0;
if ( Save(E) == 0 ) {
Co->V.Env = E;
Restore(Co);
}
if ( Is_stopped(E) )
Done(E);
return E;
}
Ready首先分配了局部環境塊，初始化其中的域，然后立即保存局部環境，將塊指針作為參數返回給啟動者。在啟動者進行首次迭代的時候，控制就會返回被啟動者（我們先不要管Is_stopped，后面再討論）。被啟動者于是從調用Ready返回，得到了自己的局部環境塊。
ret_s Iter(env_p E, env_p Co, par_s Par)
{
if ( Save(E) == 0 ) {
Co->Co = E;
Co->V.Par = Par;
Restore(Co);
}
return E->V.Ret;
}
雖然被啟動迭代子的函數參數是啟動者的局部環境塊指針，但是進行迭代的例程并不一定是啟動者（雖然大多數情況是，但后面也有不是的例子），因此被啟動者被迭代時，其局部環境塊里面有一個域Co記錄了調用者的局部環境塊，以便被迭代者可以將產生的結果返回給正確的調用者。調用者將迭代參數通過被迭代者的局部環境塊的域V傳遞，同樣被迭代的迭代子例程將結果放在調用者的局部環境塊里面，調用者從Iter返回時便得到這個結果。
par_s Yield(env_p E, ret_s Ret)
{
if ( Save(E) == 0 ) {
E->Co->V.Ret = Ret;
Restore(E->Co);
}
return E->V.Par;
}
這便是兩者之間的協同往復運行過程，我們的協同例程迭代子庫也就基本完成了。還剩下什么呢？一個好的程序應該可以正常的停下來，上面的機制似乎還不足以做到。迭代子的停止有兩種情況，一是自己迭代完畢，這時迭代子在自己的局部環境塊中設置一個信號，表明迭代已經完成，然后把控制傳遞回調用者，并不斷的循環等待調用者發給停止的信號：
#define ITER_S_NONE (0)
#define ITER_S_DONE (1)
#define ITER_S_STOP (2)
#define ITER_S_USER (0x00010000)
int Is_stopped(env_p E)
{
return E->Signal == ITER_S_STOP;
}
int Is_done(env_p E)
{
return E->Signal == ITER_S_DONE;
}
void Done(env_p E)
{
env_p Co;
while ( !Is_stopped(E) ) {
E->Signal = ITER_S_DONE;
Yield(E, E->V.Ret);
}
free(E->St);
Co = E->Co;
free(E);
Restore(Co);
}
接到停止信號后，協議就結束了，迭代子釋放掉局部環境塊，表明迭代子例程被析構，最后將控制返回給調用者。另一種情況就是調用者主動停止迭代子，這只需要在被迭代例程的局部環境塊中設置停止信號：
void Stop(env_p E, env_p Co)
{
Co->Signal = ITER_S_STOP;
Iter(E, Co, E->V.Par);
}
我們看到，迭代子需要不斷的等待停止信號并發送完成信號，而調用者只需要發送一次停止信號。這種非對稱的協議可以避免死鎖或者泄漏。由于這個協議，迭代子可能需要在每次控制返回后檢測停止信號，以便及時析構，否則控制再也不會回來了，這也是上面Ready最后那句話所要做的。
調用者通過Setup啟動迭代子，通過Stop停止，它們必須配對；另一方面，迭代子通過Ready創建就緒，通過Done完成析構，它們也必須配對。
不論是調用者還是迭代子都需要具有局部環境塊，如果調用者本身也是一個迭代子，那么這一要求就不是問題。然而萬事總有開頭，迭代子總是需要啟動者的。我們需要為主例程創建局部環境塊：
env_p Ready_main(void *P)
{
env_p E = malloc(sizeof(env_s));
Setup_iter_helper(0, 0);
E->St = 0;
E->St_size = 0;
E->St_hi = (char*)P;
return E;
}
由于主例程沒有啟動者，所以局部棧上限只能自己提供，這就是上面的參數P，顯然自己提供的上限不是真正的上限，有可能局部棧只被保存下面的部分，通常P指向主程序的某個局部變量。然后，我們在Ready_main這里面初始化協同例程的共用棧地址，以確保主例程可能被覆蓋的局部棧部分在保存之列。這個參數是我久思不能得以消除的一個遺憾。當然與就緒配對的是完成函數：
void Done_main(env_p E)
{
free(E->St);
free(E);
}
如果主例程要直接或間接的啟動迭代子，那么這些迭代子必須在這兩個函數調用之間啟動和停止，之后主例程當然可以再次調用這一對函數。到此，整個迭代子庫就完成了，從代碼看上去很簡單，不是嗎？下面舉一些使用的例子。
3
我們先把那個素數序列翻譯成C語言吧，畢竟它還算有趣。首先是判斷迭代子Sieve：
void Sieve(env_p Co)
{
env_p E, Co_rec;
int X, Y;
E = Ready(Co);
X = (int)E->V.Par;
Y = (int)Yield(E, (ret_s)1);
Co_rec = Setup(&Sieve, E);
while ( !Is_stopped(E) ) {
if ( Y%X == 0 )
Y = (int)Yield(E, 0);
else
Y = (int)Yield(E, (ret_s)Iter(E, Co_rec, (par_s)Y));
}
Stop(E, Co_rec);
Done(E);
}
按照協議，首先調用了Ready，并從返回值取得自己的局部環境塊，注意，在調用Ready之前不應該干太多事，尤其是分配資源，因為，如果Ready檢測到停止信號就不會再返回了。從Ready返回就代表著尚未被停止，由此調用者傳入的參數有效，這是第一個參數，所以是一個素數，函數通過Yield返回真值1。控制從Yield返回到迭代子以后便得到了再次迭代所傳來的新參數，于是遞歸啟動新的迭代子Co_rec，然后進入循環，根據前面討論過的邏輯不斷返回迭代結果和取得新參數，這個過程直到調用者叫停為止，在退出循環后，向遞歸的迭代子Co_rec發送停止消息，最后通過Done自行析構。類似的，迭代子Primes也很簡單：
void Primes(env_p Co)
{
env_p E, Co_sieve;
int C = 2;
E = Ready(Co);
Co_sieve = Setup(&Sieve, E);
while ( !Is_stopped(E) ) {
if ( (int)Iter(E, Co_sieve, (par_s)C) )
Yield(E, (ret_s)C);
++C;
}
Stop(E, Co_sieve);
Done(E);
}
它啟動迭代子Sieve，通過它對2以上整數依次進行判斷，如果是素數就產生迭代結果，它不需要迭代參數。這幾乎是原封不動的程序翻譯。下面就是主例程main的定義，我們可以看到它是怎樣使用迭代子的：
int main(int argc, char** argv)
{
env_p E, Co;
int N, P;
if ( argc < 2 )
return 1;
E = Ready_main(&E);
Co = Setup(&Primes, E);
N = atoi(argv[1]);
while ( (P = (int)Iter(E, Co, 0)) <= N )
printf("%d\n", P);
Stop(E, Co);
Done_main(E);
return 0;
}
與迭代子不同的是，它需要將一個局部變量的地址傳給Ready_main作為局部棧的上限，這個地址肯定是在迭代子共用棧地址之上（注意條件2），因此保護它以下的部分就足夠了，main啟動的所有迭代子都不可能破壞這個上限之上的棧。這個程序接受一個參數N，當Primes返回的素數大于N時就停止迭代子，程序打印了不大于N的所有素數。
當一個迭代過程很簡單時，通常不需要使用作為協同例程的迭代子，例如依次訪問數組或鏈接表的所有元素。有的迭代過程較為復雜，比如中序訪問二叉樹的所有節點，這時迭代子的方便就顯示出來了。對于復雜的數據結構，一般來說在迭代過程中是不宜對數據結構作出修改的，比如增加或刪除一個節點，使用迭代子的程序應該把被迭代的數據結構當成一個快照，試圖對數據結構作出修改會大大增加迭代子的復雜性，甚至消除了使用迭代子的優點。下面就是一個中序遍歷二叉樹的迭代子：
typedef struct _S_node node_s, *node_p;
struct _S_node {
int Val;
node_p Left, Right;
};
void Traverse(env_p Co)
{
env_p E, Co_rec;
node_p Root;
int X;
E = Ready(Co);
Root = (node_p)E->V.Par;
if ( Root == 0 )
Done(E);
Co_rec = Setup(&Traverse, E);
while ( X = (int)Iter(E, Co_rec, (par_s)Root->Left), !Is_done(Co_rec) )
Yield(E, (ret_s)X);
Stop(E, Co_rec);
Yield(E, (ret_s)Root->Val);
Co_rec = Setup(&Traverse, E);
while ( X = (int)Iter(E, Co_rec, (par_s)Root->Right), !Is_done(Co_rec) )
Yield(E, (ret_s)X);
Stop(E, Co_rec);
Done(E);
}
這個迭代子的參數（E->V.Par）是要遍歷的樹的根節點指針，它只在第一次傳入時有用，以后傳入的值都是被忽略的。這樣的情形很常見，在Sather語言中有專門的關鍵字once來描述這樣的迭代子參數，例如前面的例子range!，它所接受的參數是要生成的整數序列的上下界，這只需要傳遞一次。
range! (once min, max: INT): INT is ...
當然，在我們的C語言模擬庫中就沒有這樣的設施了，一切靠自己處理。中序遍歷二叉樹非常簡單，它首先遞歸迭代左子樹，把迭代到的結果返回出去，然后返回根節點，最后再同樣遞歸迭代右子樹。由于二叉樹并不是無限序列，所以迭代的時候要注意判斷迭代子是否已經結束，這是通過迭代后判斷Is_done(Co_rec)來完成的。使用這個迭代子的主程序也同樣要判斷這一點：
void Print_tree(node_p Root)
{
env_p E, Co;
int X;
E = Ready_main(&E);
Co = Setup(&Traverse, E);
while ( X = (int)Iter(E, Co, (par_s)Root), !Is_done(Co) )
printf("%d\n", X);
Stop(E, Co);
Done_main(E);
}
這是一個函數，它可能由main直接或間接的調用。問題出現了，如果main里面已經調用了Ready_main而尚未調用Done_main，那么就出現了嵌套的調用。我們知道在Setup_iter_helper里面設置共用棧地址的時候，機器狀態被存放在靜態變量中，嵌套調用是不能允許的。那么干脆只在main里面調用這對函數，因為所有的其它C函數都將從main里面調用，所以這樣做是正確的，但是可能引起效率上的問題：在嵌套調用中積累起來的局部棧可能很大，特別是中間夾著的無關函數有可能在桟上定義諸如int[65536]這樣的大型局部數據。故此，如果可以允許嵌套調用Ready_main/Done_main的話，就能在不同的層次指定不同的公用棧地址，只要保證在某一層中啟動的迭代子也在該層結束就可以了。值得注意的是，在外層啟動的迭代子不能在內層使用，因為內層所規定的主例程局部棧上限會低于外層的上限，甚至有可能低于外層規定的共有棧地址，這樣一來，使用外層啟動的迭代子會覆蓋內層主例程沒有保存的局部棧部分。
怎樣支持嵌套的Ready_main調用呢？其實也不難，這是個后進先出的棧式調用模式，我們動態分配jmp_buf結構，正好利用最簡單的后進先出式鏈接表就可以把它們串起來，這種做法是非常標準的。我們只需要修改Setup_iter_help以及Done_main就可以了。
void Setup_iter_helper(coroutine_p R, env_p E)
{
typedef struct _S_node node_s, *node_p;
struct _S_node {
node_p Next;
jmp_buf Buf;
};
static node_p Env_stack = 0;
static coroutine_p R_s;
static env_p E_s;
node_p P;
if ( R ) {
R_s = R;
E_s = E;
longjmp(Env_stack->Buf, 1);
} else if ( E == 0 ) {
P = (node_p)malloc(sizeof(node_s));
P->Next = Env_stack;
Env_stack = P;
if ( setjmp(Env_stack->Buf) != 0 ) {
int Any;
E_s->V.St_hi = (char*)&Any;
R_s(E_s);
assert(0);
}
} else {
P = Env_stack;
Env_stack = P->Next;
free(P);
}
}
void Done_main(env_p E)
{
Setup_iter_helper(0, (env_p)1);
free(E->St);
free(E);
}
這里我們增加了一個數據結構，用來存放機器狀態，在每次初始化調用時分配空間并壓入鏈接表，與此對應，我們給Setup_iter_helper增加一個新的功能，它需要在一個層次結束時把節點從鏈接表中彈出來釋放掉，這個功能由Done_main來調用。現在，迭代子庫可以支持嵌套的主例程局部環境了。
關于協同例程迭代子的應用，我再舉最后一個例子[3]，在這個例子里面將涉及高階迭代子，也就是說將其它迭代子作為參數的迭代子。例如，給定兩個返回值類型相同的無限序列迭代子，我們可以構造一個新的迭代子交替的產生兩個序列的結果，也就是將[1,3,5,7,...]和[2,4,6,8,...]合成為[1,2,3,4,...]。這個迭代子接受兩個迭代子作為參數，它稱為Interleave（交替）:
typedef union _U_variant variant_s, *variant_p;
union _U_variant {
int Int;
env_p Env;
variant_p Var;
coroutine_p Routine;
};
variant_p Alloc_v(int N) {return (variant_p)malloc(sizeof(variant_s)*N);}
void Free_v(variant_p P) {free(P);}
void Interleave(env_p Co)
{
env_p E;
variant_p P;
E = Ready(Co);
P = (variant_p)E->V.Par;
while (1) {
if ( Is_stopped(E) ) break;
Yield(E, (ret_s)Iter(E, P[0].Env, (par_s)P[1].Var));
if ( Is_stopped(E) ) break;
Yield(E, (ret_s)Iter(E, P[2].Env, (par_s)P[3].Var));
}
Done(E);
}
兩個作為參數的迭代子是已經啟動了的，它們的局部環境塊和參數是通過一個參數塊傳遞的，這是因為環境塊中用于傳遞參數的域只有一個整數大小，我們在里面放置指向參數塊的指針。上面的迭代子有4個參數，分別是第一個迭代子的環境塊和參數以及第二個迭代子的環境塊和參數。每個參數都是存放在上面聲明的聯合變體中的。使用者可以根據自己的需要聲明和使用類似的變體。Interleave很簡單，它交替的迭代兩個迭代子并返回結果，中間不要忘了隨時檢查是否被停止。由于Interleave不負責啟動迭代子，因此它也不負責停止它們。
假設我們有很多很多，無限多的無限序列，怎樣迭代其中的元素呢？顯然我們不可能迭代完一個再迭代另一個，上面的交替給我們提供了方法。如何交替無限多個無限序列呢？假定我們有一個枚舉迭代子Enumerate可以生成它們的枚舉序列，那么我們可以取出第一個無限序列，然后和剩下的無限多個無限序列的枚舉序列進行交替，這個遞歸過程將可以枚舉無限多個無限序列中的任何元素（當然，如果時間和空間都是足夠的話），嚴格的說，就是任給這些序列中的元素，Enumerate都將在有限的時間內將它枚舉出來。
void Enumerate(env_p Co)
{
env_p E, Co_i;
variant_p P, P_i, P_ls;
E = Ready(Co);
P = (variant_p)E->V.Par;
P_ls = (variant_p)Iter(E, P[0].Env, (par_s)(P+1));
P_i = Alloc_v(4);
P_i[0].Env = Setup(P_ls[0].Routine, E);
P_i[1].Var = P_ls+1;
P_i[2].Env = Setup(&Enumerate, E);
P_i[3].Var = P;
Co_i = Setup(&Interleave, E);
while ( !Is_stopped(E) )
Yield(E, Iter(E, Co_i, (par_s)P_i));
Stop(E, Co_i);
Stop(E, P_i[2].Env);
Stop(E, P_i[0].Env);
Free_v(P_i);
Done(E);
}
Enumerate接受一個無限序列的迭代子作為參數（P[0].Env），這個迭代子本身還可能有其它的參數，Enummerate將這些參數原封不動傳給它（P[1],P[2],...）。首先Enumerate利用這個迭代子迭代出一個無限序列（P_ls[0].Routine），然后啟動這個序列，這個序列可能有其它參數（P_ls[1],P_ls[2],...）。由于迭代子已經迭代過一次，因此再迭代就會返回下一個無限序列。于是Enumerate遞歸的啟動自身來準備枚舉剩下所有無限序列的元素。Enumerate將這兩個啟動好的迭代子交給Interleave進行交替，然后不斷將Interleave的迭代結果返回出去。
好了，現在可以準備使用Enumerate迭代子了。首先需要構造無限序列的迭代子，哪里來呢？一個整數無限序列和另一個整數無限序列的笛卡爾乘積就是無限多個的整數對無限序列，比如之前定義的Positives×Primes。為了產生整數對的無限序列，我們需要一個配對迭代子，它把一個整數和一個無限序列中的所有整數配對：
void Pairs(env_p Co)
{
env_p E, Co_l;
variant_p P, P_ints;
E = Ready(Co);
P = (variant_p)E->V.Par;
P_ints = Alloc_v(2);
P_ints[0].Int = P[0].Int;
Co_l = Setup(P[1].Routine, E);
while ( !Is_stopped(E) ) {
P_ints[1].Int = (int)Iter(E, Co_l, (par_s)0);
Yield(E, (ret_s)P_ints);
}
Stop(E, Co_l);
Free_v(P_ints);
Done(E);
}
由于Pairs的迭代結果是一對整數，所以要通過參數塊來返回。Pairs接受兩個參數，一個是整數（P[0].Int），另一個是尚未啟動的無限序列（P[1].Routine），它啟動這個無限序列，并不斷的將迭代結果與第一個整數配對返回。它實現了一個數的集合和一個無限序列的笛卡爾乘積。
于是，無限序列和無限序列的笛卡兒乘積Lists也可以定義了，它被表示成無限序列的無限序列，它接受兩個無限序列，啟動其中一個來不斷生成配對的第一個整數。Lists每迭代一次就可以返回一個未啟動的Pairs，這正是Enumerate所需要的：
void Lists(env_p Co)
{
env_p E, Co_l;
variant_p P, P_ls;
E = Ready(Co);
P = (variant_p)E->V.Par;
Co_l = Setup(P[0].Routine, E);
P_ls = Alloc_v(3);
P_ls[0].Routine = &Pairs;
P_ls[2].Routine = P[1].Routine;
while ( !Is_stopped(E) ) {
P_ls[1].Int = (int)Iter(E, Co_l, (par_s)0);
Yield(E, (ret_s)P_ls);
}
Free_v(P_ls);
Stop(E, Co_l);
Done(E);
}
最后我們把Lists交給Enumerate去枚舉：
int main(int argc, char **argv)
{
env_p E, Co_e;
variant_p P_e, P_ints;
int i, N;
if ( argc < 2 )
return 1;
E = Ready_main(&E);
P_e = Alloc_v(3);
P_e[1].Routine = &Positives;
P_e[2].Routine = &Primes;
Co_e = Setup(&Enumerate, E);
P_e[0].Env = Setup(&Lists, E);
for ( i = 0, N = atoi(argv[1]); i < N; ++i ) {
P_ints = (variant_p)Iter(E, Co_e, (par_s)P_e);
printf("(%d, %d)\n", P_ints[0].Int, P_ints[1].Int);
}
Stop(E, P_e[0].Env);
Stop(E, Co_e);
Free_v(P_e);
Done_main(E);
return 0;
}
這個程序輸出Enumerate無限序列的前N個元素（N由命令行參數指定）。它首先啟動Enumerate（Co_e）和Lists（P_e[0].Env），然后把Lists和它的參數傳給Enumerate去迭代，上面的參數設置過程可能看上去比較混亂，實際上它是這個意思：
Iter Enumerate Lists Positives Primes
運行的結果也是很有意思的，第一行首先被交替，所以出現的頻率最高，越往后面的行交替的機會越少，少到什么程度呢？第M行的第一個元素出現在Enumerate無限序列的第2M-1個位置，例如第17行的第一個元素(17,2)將出現在第65536位。關于這個結論，不難從Enumerate和Interleave的算法中推導出來。如下圖所示，這些無限序列可以組成一棵完全二叉樹，位于上面的一行的元素是下面一行相應元素的子節點，而枚舉的順序正如同中序遍歷這棵無限的二叉樹。
注意從4到19這條線，如果我們把整個圖再往下延展的話，將畫出一條對數曲線的包絡線，從這一方面也知道，這種枚舉方法往右上數得太快，往下數太慢。熟悉數學的人都知道另外一種對角線枚舉法，這個迭代子的構造更為容易，一個想法就是，當知道緊跟下面的一行輸出了該行一個元素以后，這上面的一行也要輸出本行的一個元素：
void Diagonal(env_p Co)
{
env_p E, Co_ls, Co_rec;
variant_p P, P_ls;
E = Ready(Co);
P = (variant_p)E->V.Par;
P_ls = (variant_p)Iter(E, P[0].Env, (par_s)(P+1));
Co_ls = Setup(P_ls[0].Routine, E);
Co_rec = Setup(&Diagonal, E);
E->Signal = ITER_S_USER;
do {
if ( E->Signal == ITER_S_USER ) {
E->Signal = ITER_S_NONE;
E->Co->Signal = ITER_S_USER;
Yield(E, (ret_s)Iter(E, Co_ls, (par_s)(P_ls+1)));
} else
Yield(E, (ret_s)Iter(E, Co_rec, (par_s)P));
} while ( !Is_stopped(E) );
Stop(E, Co_rec);
Stop(E, Co_ls);
Done(E);
}
這里Diagonal首先輸出本行的一個元素，然后遞歸的輸出后面的那些行的元素，當緊跟下面的一行通過Signal域通知這次迭代的結果是屬于該行時，Diagonal就迭代本行一次，然后同樣的通知上面一行。這段程序并不難懂，這里就簡而帶過了。
最后這個例子實際上頗為復雜，最多時我們同時使用了Lists、Enumerate、Interleave、Pairs、Positives、Primes以及Sieve共7種迭代子，其中幾個還是遞歸迭代子，可以想象程序運行起來同時存在多少的協同例程。協同例程迭代子為我們提供了非常有力的程序設計方式，它的思想方法和函數式語言的函數閉包（function closure），延續（continuation）有直接的對應，有興趣的讀者可以進一步去研究。本文主要討論協同例程迭代子的概念，以及如何利用編譯器的特點在C語言中模擬它。我寫這個文章的動機是聽說C#2將引進迭代子的語言支持，我希望這一改進能讓更多的程序員可以實踐豐富多彩的程序設計思想。選擇C語言來模擬是因為它的簡單，不用去考慮其它語言較為復雜的控制語義，例如C++的異常處理和自動析構函數。這可以使我得到更簡潔的程序。
本文中的保存和恢復局部棧的技術參考了'A Portable C++ Library for Coroutine Sequencing'一文中的實現，不過進行了相應的簡化；而例子部分則參考了函數式程序設計的教材。在設計迭代子C庫的過程中筆者也遇到很多問題，不過一一解決起來還是非常有趣的。有時候我想，簡單的程序寫出來可能很長，而復雜的程序可能很短，程序中蘊涵的信息似乎不能用字節數來衡量，然而，我們卻正在這么做。
這個協同例程庫現在只適用于從高地址向低地址分配棧空間的機器，對Save_stack、Restore和Clean_restore稍作修改就可以適用于另一種方向分配棧空間的機器，甚至可以做到兩種機器通用。文中提及的C程序的源代碼可以通過gcc3或msvc6的編譯，可以使用-O2優化編譯。但是gcc的-O3優化編譯則會導致程序崩潰，這也許是-O3會使編譯器inline展開函數，失去了函數的局部棧，令文中保存局部棧的技巧失效。
參考文獻
[1] Benedict Gomes, David Stoutamire, Boris Vaysman, Holger Klawitter(1996): A Language Manual For Sather 1.1, Online Material.
[2] Keld Helsgaun: A Portable C++ Library for Coroutine Sequencing, Online Material.
[3] L. C. Paulson (1996): ML for the Working Programmer, 2nd Edition, Cambridge University Pr