引用: http://www.oschina.net/translate/coroutines-in-c 這里有一個簡單的解壓過程的代碼片段和一個同樣簡單的解析代碼片段:
|
![]()
繆斯的情人
|
每個代碼片段都很簡單,通俗易懂。一個通過調用emit()方法每次產生一個字節;另一個調用getchar()每次獲取一個字節。如果只通過調用emit()和getchar()就能彼此間提交數據,那么就能簡單的把兩個代碼片段連接到一起,因此也就能把解壓的輸出直接傳遞到解析部分。
在很多現在操作系統中,你可以使用管道在兩個進程間通信或者兩個線程emit()——在解壓代碼中寫入管道,在解析代碼中使用getchar()從另一端相同的管道中讀取。簡單強壯,但是也重量不可移植。通常你不想把你的一個簡單程序分到線程中。 在這篇文章中我提供了一個創造性的解決方案來處理這個構造的問題。 |
![]()
繆斯的情人
|
重寫常見的方式是重寫末端的通信管道,把它作為一個可調用的函數。這有個簡單的例子。
當然你不需要兩個都重寫;只修改一個就可以。如果把解壓片段重寫為以上形式,那么每次調用它都返回一個字符,原始的解析代碼片段中就可以把調用getchar()改為調用decompressor(),這樣程序看起來舒心多了。相反的,如果把解析代碼重寫為上面的形式,那么每次調用都會輸入一個字符,原始的解壓代碼中可以通過調用parser()替換掉了調用emit()。如果你是個貪婪的人你可以把兩個函數都重寫,都作為被調用者。 |
![]()
繆斯的情人
|
這就是我的真實觀點。和兩個重寫后的函數相比原始的代碼丑陋無比,在這里當兩個進程被寫為調用者而不是被調用者時更易讀了。如果你試圖通過解析器推斷出語法,或者通過解壓器了解解壓數據格式,只需閱讀下代碼就可以,同時你會發現原始的代碼清晰些,重寫后的代碼格式上不太清晰,如果沒有嵌入另外一者的代碼這會更好些。 |
![]()
繆斯的情人
|
Knuth協程在《計算機程序設計藝術》中,Donald Knuth提供了一個解決這類問題的方法。他的方法是徹底丟掉堆棧的概念,不要再想一個進程作為調用者,另一個作為被調用者,把他們當做平等的協作者關系。 實際上就是:把傳統的“調用”稍微改為一個不同的方式。新的“調用”將在某個地方保存返回值而不是堆棧上,并且還能跳轉到另一個保存返回值的指定位置上。因此,解碼器每次生成一個字符,就保存它的程序計數器并且跳轉到上次解析器的位置-解析器每次都需要一個新的字符,它保存自己的程序計數器并且跳轉到上次解碼器的位置。程序可以在兩個函數之間來回自如的傳遞需要的數據了。 |
![]()
繆斯的情人
|
理論上看起來很美,但實際中你卻只能在匯編語言中使用,因為通用的高級語言沒有一個支持調用原始的協程。像類似于C的都是依賴于基礎的堆棧結構,因此當在函數間進行數據傳遞時,一個必須作為調用者,領一個必須作為被調用者。所以如果你想寫可移植的代碼,這種技術和Unix管道一樣不切實際。
|
![]()
繆斯的情人
|
基于棧的協程我們真正想要的是在C中模仿Knuth協程調用原語的能力。我們必須接受這個現實,在C語言中,一個函數將作為調用者,另一個作為被調用者。對于調用者我們沒有任何問題;我們按照原始算法寫代碼就可以,無論什么時候,如果它生成一個字符那么它就需要調用另一個函數。 被調用者有很多問題。對于被調用者,我們想要一個函數,該函數具有“返回并繼續”的操作:從函數返回后,當再次調用它,只需要在上次位置繼續執行就可以。比如,我們希望寫這樣一個函數 int function(void) { int i; for (i = 0; i < 10; i++) return i; /* won't work, but wouldn't it be nice */ } 連續調用這個函數10次,返回0-9的數字。 |
![]()
繆斯的情人
|
我們怎么能實現這個呢?好吧,我們可以用一個goto語句將控制跳轉到這個函數中的任何一點。所以如果我們有一個狀態變量,我們可以這樣做: int function(void) { static int i, state = 0; switch (state) { case 0: goto LABEL0; case 1: goto LABEL1; } LABEL0: /* start of function */ for (i = 0; i < 10; i++) { state = 1; /* so we will come back to LABEL1 */ return i; LABEL1:; /* resume control straight after the return */ } }這個方法可以奏效。在一些我們可能需要恢復控制的地方,我們擁有一組標簽:一個在開始位置,其他的緊跟著每個返回語句。我們有一個保留在函數調用之間的狀態變量,它指明了下一步我們需要恢復控制那個標簽。在任何返回之前,我們會更新狀態變量到正確的標簽位;任何調用之后,我們會對這個變量的值做一個switch操作來查看它當前進行到哪里。 |
![]()
jimmyjmh
|
雖然這樣,它還是比較丑。最糟糕的的部分是,這一組標簽必須手動維護,并且在函數體和初始的switch語句之間保持一致。每次新增一個返回語句,我們必須引進一個新表簽名并把它加到switch列表中;而每次刪除一個返回語句,我們又必須移除相應的標簽。剛剛我們只是考慮一個因素增加的兩倍維護工作量。
|
![]()
jimmyjmh
|
達夫設備(Duff's Device)
C語言中著名的"達夫設備"利用case語句在其匹配switch語句子塊中也是合法的這一事實。Tom Duff利用這個方法優化輸出回路: switch (count % 8) { case 0: do { *to = *from++; case 7: *to = *from++; case 6: *to = *from++; case 5: *to = *from++; case 4: *to = *from++; case 3: *to = *from++; case 2: *to = *from++; case 1: *to = *from++; } while ((count -= 8) > 0); }我們可以稍加變動將它應用到協同程序技巧上。我們可以用switch語句本身執行跳轉,而不是用它來確定跳到哪里去執行。 int function(void) { static int i, state = 0; switch (state) { case 0: /* start of function */ for (i = 0; i < 10; i++) { state = 1; /* so we will come back to "case 1" */ return i; case 1:; /* resume control straight after the return */ } } }現在這看起來更理想了。我們現在需要做的只是構造一些精確宏,并且可以把細節隱藏到這些似是而非的定義里: #define crBegin static int state=0; switch(state) { case 0: #define crReturn(i,x) do { state=i; return x; case i:; } while (0) #define crFinish } int function(void) { static int i; crBegin; for (i = 0; i < 10; i++) crReturn(1, i); crFinish; } |
![]()
jimmyjmh
|
這差不多就是我們想要的了。我們可以通過這種一返回就控制下一個調用回復的方式,用crReturn從函數返回。當然,我們必須遵守一些基本規則(用crBegin和crFinish包住函數體;聲明所需的所有保存在acrReturn中的靜態局部變量;絕不要在一個顯式switch語句中設置一個crReturn);但那些并不會限制我們太多。 剩下的唯一問題是傳給crReturn的第一個參數。就像在上一節引進一個新標簽一樣,我們必須避免與已存在的標簽名沖突,確保所有給crReturn的狀態參數都是不同的。這影響是相當小的 -- 編譯器會抓住它并并不讓它在運行時出錯 -- 但我們還是要避免這樣做。 |
![]()
jimmyjmh
|
雖然這可以解決,ANSI C還是提供了擴展到當前行號的專門的宏名:__LINE__,因此我們可以把crReturn重寫成:
#define crReturn(x) do { state=__LINE__; return x; \ case __LINE__:; } while (0)而且只要遵守第四條基本規則,我們就不再需要擔心這些狀態參數了(決不在同一行寫兩個crReturn語句)。 |
![]()
jimmyjmh
|
評估現在我們有了這個畸形的東西,讓我們來重寫下原始的代碼片段吧。
我們已經重寫了解碼器和解析器都作為了被調用者,不需要像最后一次那樣大規模的重寫。每個函數的結構恰好是原始結構的鏡像,讀者能夠通過解析器推斷出相應的語法,或者通過解碼器了解到解壓數據格式,比起讀那些狀態機代碼簡單多了。一旦你適應了新的格式,你就會發現控制流程非常直觀:當解壓器產生一個字符,它就調用crReturn將這個字符傳給調用函數,并等待當需要下一個字符時再次被調用。當解析器需要一個新字符時,它通過crReturn返回,并等待下一次被調用時通過參數c傳入新的字符。 |
![]()
繆斯的情人
|
這里代碼里還有一個小的結構變化:parser()中getchar()放在了循環的結尾而不是開頭了,這是因為當進入函數時,第一個字符已經通過c傳進來了。我們應該可以接受這個小的結構改變,或者如果我們真的對此抱有輕盈態度,我們可以認為在parse()傳入數據前,需要一次“初始化”調用。 當然像前面一樣,我們不必把兩個函數都使用協程的宏重寫,修改一個足矣;另一個可以作為他的被調用者。 我們已經取得了我們想要達到的目標:一個可移植的ANSI C在生產者和消費者之間傳遞數據,而不用狀態機重寫代碼。我們已經通過把一個switch語句的生僻的功能結合C的預處理創建一個隱式的狀態機。 |
![]()
繆斯的情人
|
編碼規范當然,這種方式違背了書上的編碼規范,在公司代碼中嘗試這樣使用你會受到嚴厲的警告!在宏定義中,你的大括號沒有完全匹配,子區塊中使用了case,至于crReturn宏中內容不完整···使用這種不負責任的編碼實踐你沒有被解雇真是一種奇跡。你應該感到自行慚愧。 我需要聲明下編碼規范在這里不適用。在這篇文章里我展示的例子不是很長,也不復雜,即使使用狀態機重寫也能看懂。但是隨著函數變長,重寫的難度越來愈大,并且失去了代碼清晰度,越來越糟糕。 |
![]()
繆斯的情人
|
考慮下,如果一個函數有下面的代碼塊構成 case STATE1: /* perform some activity */ if (condition) state = STATE2; else state = STATE3; 對于讀者來說從函數建立下面的小模塊也不是很難 LABEL1: /* perform some activity */ if (condition) goto LABEL2; else goto LABEL3; 一個調用者,一個被調用者。是的,這兩個函數在可視結構上是一樣的,它們提供的底層算法都非常少。因為使用協程宏想要解雇你的人同樣會因為你寫的連接goto語句的小塊函數而怒斥你!這次它們做對了,因為這樣的函數布局破壞了算法的結構。 |
![]()
繆斯的情人
|
編程規范目標就是為了清晰。像switch,return和case語句把這些重要的東西隱藏到“不清晰”的宏中,從編程標準角度來看你已經破壞了程序的語法結構,違背了代碼清晰的要求。但是我們這樣做是為了突出程序的算法結構,而算法結構也正好是讀者想要了解的! 任何的編碼規范堅持語法的清晰度而犧牲了算法的清晰度都應該被重寫。如果你的老板因為使用這個技巧而解雇你,當安保人員把你拖走時要不斷告訴他們。 |
![]()
繆斯的情人
|
風騷般的編碼在正兒八經的應用程序中,協程很少使用,因為它依賴于靜態變量,因此不能重入或者支持多線程。理想情況下,在真實應用程序中,你可能想在多個不同的上下文中調用同一個函數,并且在給定的一個上下文中每次調用時,都能在這個上下文中上一次返回的位置繼續執行。 這很容易做到,我們增加一個新的函數參數——一個上下文結構的指針;我們將所有的局部變量和協程用到的狀態變量都聲明成結構體中的元素. |
![]()
繆斯的情人
|
這樣寫丑了點,因為突然間你不得不使用ctx->i作為循環計數器而不是之前使用的i;事實上所有重要的變量都成了協程上下文結構體中的元素。但是這消除了重入的問題,并且沒有影響到程序的結構。 (當然,要是C有Pascal語言的with語句,我們就可以將這個間接的引用隱藏掉,但是很遺憾沒有這些。對于C++語言,我們可以把協程的兩個函數設計成類的成員函數,所有的局部變量設計成類的成員變量,從而將作用域的問題隱藏掉) |
![]()
繆斯的情人
|
這兒包含的C語言頭文件實現了一套預定義的協程使用的宏。在文件中定義了二套宏函數,前綴分別是scr和ccr。scr宏是一套簡單的實現,用于可以使用靜態變量的情況;ccr宏更高級一些,能支持重入。在頭文件的注釋中有完整的說明。 需要注意的是,VC++ 6并不喜歡這種協程技巧,因為其默認的debug狀態(Program Database for Edit and Continue)對__LINE__宏的支持有點兒怪。如果想用VC++ 6編譯一個使用了協程的宏,你就要關掉Edit and Continue。(在project settings中,選擇c/c++標簽,在General中,將Debug info改為Program Database for Edit and Continue之外的其他值)。 (這個頭文件是MIT許可的,所以你可以任意使用,沒有任何限制。如果你發現MIT對你的使用方式有限制,可以給我發郵件,我會考慮給你授權。) 使用 這個鏈接 獲得coroutine.h。 感謝您的閱讀。分享才有快樂! |
![]()
繆斯的情人
|
參考文獻
|