C语言协程

原文链接：http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

引言

为大型程序设计一个良好的结构通常是一件困难的事情。其中一个经常出现的问题是：如果你有一段代码产生数据，另一段代码消费数据，那么谁应该作为调用者，谁应该作为被调用者？

下面是一段很简单的Run-Length（游程编码）解压缩代码（Decompressor）：

/* Decompression code */
while (1) {
    c = getchar();
    if (c == EOF)
        break;
    if (c == 0xFF) {
        len = getchar();
        c = getchar();
        while (len--)
            emit(c);
    } else
        emit(c);
}
emit(EOF);

以及一段同样简单的解析代码（Parser）：

/* Parser code */
while (1) {
    c = getchar();
    if (c == EOF)
        break;
    if (isalpha(c)) {
        do {
            add_to_token(c);
            c = getchar();
        } while (isalpha(c));
        got_token(WORD);
    }
    add_to_token(c);
    got_token(PUNCT);
}

上述这两段代码都非常简单，易读并且易懂。其中Decompressor调用emit()每次产生一个字符，Parser调用getchar()每次消费一个字符。只要对emit()和getchar()的调用可以互相传递数据，那么很容易将这两段代码连接起来，使得Decompressor的输出直接流入到Parser。

在很多现代操作系统中，你可以在两个进程或线程之间使用管道来达到这个目的。Decompressor中的emit()向管道写入数据，Parser中的getchar()从同一个管道读取数据。这个方案简单并且健壮，但是不够轻量级并且不可移植。通常你不会愿意为了完成这么简单的任务而将你的程序拆分成多个线程。

在这篇文章中，我为这种程序结构问题提供了一个创造性的解决方案。

重写

传统的解决方案是重写通信通道的某一端使得它成为一个可以被调用的函数。下面的示例代码展示了对上述两段代码进行改写的结果：

int decompressor(void) {
    static int repchar;
    static int replen;
    if (replen > 0) {
        replen--;
        return repchar;
    }
    c = getchar();
    if (c == EOF)
        return EOF;
    if (c == 0xFF) {
        replen = getchar();
        repchar = getchar();
        replen--;
        return repchar;
    } else
        return c;
}

void parser(int c) {
    static enum {
        START, IN_WORD
    } state;
    switch (state) {
        case IN_WORD:
            if (isalpha(c)) {
                add_to_token(c);
                return;
            }
            got_token(WORD);
            state = START;
            /* fall through */

        case START:
            add_to_token(c);
            if (isalpha(c))
                state = IN_WORD;
            else
                got_token(PUNCT);
            break;
    }
}

当然你不需要将它们两者都进行重写，只需要重写其中一个即可。如果你像示例中那样重写了Decompressor，让它在每次被调用时返回一个字符，那么最初的Parser代码可以将对getchar()的调用替换为对decompressor()的调用，程序将会正确运行。相反，如果你像示例中那样重写了Parser，使得它对每一个输入字符都调用一次，那么最初的Decompressor代码可以使用parser()调用替代emit()调用，没有任何问题。你只需要将其中一个函数改写为被调用都即可，除非你是受虐狂。

这就是问题的关键所在。这两个重写后的函数和它们的原始版本相比非常丑陋。这里的两个处理过程都是在被编写为调用者时更加易读。如果你尝试通过阅读代码来推断Parser能够识别的语法，或者Decompressor能够识别的压缩数据格式，你会发现原始版本的代码要比重写后的版本更加清晰。因此，如果我们不必对两者中的任何一个进行重写的话将会更好。

Knuth协程

在《The Art of Computer Programming》一书中，Donald Knuth针对这类问题提出了一个解决方案：抛弃栈的概念。不要再去想谁应该作为调用者，谁应该作为被调用者，而是把它们看作相互协作的对等方。

实际上，就是将传统的“调用（Call）”原语替换为一个新的稍微不同的“调用”原语。新的“调用”原语将返回值保存在其它某个地方，而不是保存在栈上，然后跳转到之前的某个保存的返回值指定的地方继续执行。因此，每当Decompressor产生一个字符，它就保存自己的程序计数器（Program Counter），跳转到Parser中上一次离开的地址继续执行；相应的，每当Parser需要一个字符，它就保存自己的程序计数器，跳转到Decompressor中上一次离开的地址继续执行。程序控制流在两个例程之间来回切换。

这在理论上看起来非常美好，但实际上你只能用汇编语言来完成这件事情，因为没有哪一种常用的高级语言支持这种协程的“调用”原语。像C这样的语言完全依赖于基于栈的结构，因此无论什么时候控制流从一个函数传递到另一个函数，其中一个函数必须作为调用者而另一个函数必须作为被调用者。所以，如果你想编写可移植的代码，那么上述这种技术至少像使用Unix管道一样是不可行的。

基于栈的协程

因此我们真正想要的是用C语言模拟Knuth的协和“调用”原语。我们必须接受一个现实，从C的层面来讲，必然有一个函数是调用者而另一个函数是被调用者。对于调用者来说，不会有任何问题；我们完全按照原始的算法进行编码，每当它产生（或者需要）一个字符的时候，它就调用另外一个函数。

问题都在被调用者身上。我们希望被调用者拥有一个“从返回处继续”的操作：从函数返回，下一次它被调用的时候，控制流从return语句的下一行开始恢复执行。比如，我们希望可以写一个像这样的函数：

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 */
    }
}

这种方法可以正常工作。我们在需要恢复控制流的地方打上一系列标号：在开始的地方打上一个，在每个return语句后面也打上一个。我们使用一个状态变量，它的值可以在多次函数调用之间保留，这个变量的值告诉我们下一次函数被调用时控制流应该在哪个标号那里恢复执行。每次返回之前，更新这个状态变量指向正确的标号；每当函数被调用，就在这个状态变量上做一个switch操作来查找应该跳转到哪个位置恢复执行。

尽管这个方法可以正常工作，但是它十分丑陋。最糟糕的地方在于必须手工维护一系列标号，并且必须在整个函数体中与最初的switch语句保持一致。每次新增一个return语句，就必须定义一个新的标号并且加入到switch语句中；每次移除一个return语句，就必须移除它对应的标号。这使得维护工作量拉回了一倍。

Duff设备

C语言中著名的Duff设备利用了这样一个事实：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来决定执行哪条goto语句，我们可以直接使用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;
}

（注意使用do...while(0)来确保当crReturn直接出现在if和else语句中时不需要用大花括号括起来）

这基本上就是我们想要的全部了。我们可以使用crReturn从函数中返回，并且下一次调用时控制流将从返回点的下一条语句恢复执行。当然我们必须遵守几条基本原则：使用crBegin和crFinish将函数体包起来；将所有的局部变量声明为static，如果它的值需要在多次crReturn之间被保留；crReturn绝不能出现在显式的switch语句中；但这些对我们来说并不是什么太大的限制。

现在唯一的问题就是crReturn的第一个参数。在上一节中我们必须定义新的标号并且确保它和已有的标号不冲突，而现在我们必须保证crReturn的状态参数（第一个参数）是不同的。就算相同结果也不会太严重——编译器会检测到冲突从而不会在运行时造成破坏——但我们还是要想办法避免这一点。

这个问题也是可以被解决的。ANSI C提供了一个名为__LINE__的特殊的宏，它将展开为源码中的当前行号。因此可以重写crReturn：

#define crReturn(x) do { state=__LINE__; return x; \
    case __LINE__:; } while (0)

现在再也不用担心状态参数了，与此同时我们必须遵守第四个基本原则：同一行中不要出现两个crReturn语句。

评估

现在有了这个“神器”，我们用它来重写本文最开始的代码片段：

int decompressor(void) {
    static int c, len;
    crBegin;
    while (1) {
        c = getchar();
        if (c == EOF)
            break;
        if (c == 0xFF) {
            len = getchar();
            c = getchar();
            while (len--)
                crReturn(c);
        } else
            crReturn(c);
    }
    crReturn(EOF);
    crFinish;
}

void parser(int c) {
    crBegin;
    while (1) {
        /*  first char already in c */
        if (c == EOF)
            break;
        if (isalpha(c)) {
            do {
                add_to_token(c);
                crReturn( );
            } while (isalpha(c));
            got_token(WORD);
        }
        add_to_token(c);
        got_token(PUNCT);
        crReturn( );
    }
    crFinish;
}

我们将Decompressor和Parser都重写成了被调用者，并不需要像上一次重写一样进行大量的重构。函数的结构与它们的最初形式完全相应。比起晦涩的状态机代码，阅读代码的人可以更容易推断出Parser能够识别的语法，以及Decompressor可以处理的数据压缩格式。一旦你熟悉了这种新的方法，就会发现控制流是相当直观的：当Decompressor产生了一个字符，它就通过crReturn返回给调用者，然后等待调用者需要另一个字符时再调用它。当Parser需要一个字符时，它通过crReturn返回，然后等待再次被调用，并且将新的字符通过参数c传递给它。

这里对代码的结构进行了一个小小的修改：parser()将在循环结束的地方（而不是在开始的地方）调用getchar()（对应改写后的crReutrn），因为当控制流进入函数的时候第一个字符已经在参数c里面了。这一点点结构上的小改动是可以接受的，或者如果你对此感受非常强烈，可以认为在向parser()传入数据之前需要进行一次初始化调用。

与之前一样，我们不必使用协程的宏同时重写这两个函数。重写其中一个即可，另一个函数作为它的调用者。

我们已经达到了目标：一种可移植的基于ANSI C的方法在生产者和消费者之前传递数据，并且不需要将其中一个重写为显式的状态机。通过结合C语言的预处理器和switch语句的一个不常用的功能，我们构造了一个隐式的状态机。

编码规范

当然，这个技巧与各种书里的编码规范都不相符。如果你尝试在公司的代码中使用这个技巧的话，很可能会招致严厉的指责，甚至受到处罚。在宏里面嵌入不匹配的花括号，在子代码块中使用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、case和return语句隐藏在一些“不太容易理解”的宏里，编码规范认为这样扰乱了程序的语法结构，并且违背了对代码清晰的需求。但是这样做更好的展现了程序的算法结构，这才是阅读代码的人更想知道的。

任何编码规范，如果以牺牲算法结构的清晰性来追求语法结构上的清晰，都应该重写。如果你的老板因为你用了本文所述的技巧而炒了你，那么在保安将你拖出大楼的时候要不断向他们重申这一点。

改进和代码

在正规的应用中，这个简单的协程实现基本上没什么用，因为它依赖于静态变量，因此不是可入的，也不能支持多线程。在真实的应用程序中，你会希望在不同的上下文中调用同一个函数，每次在给定的上下文中调用函数时，控制流将从这个上下文中上一次返回的地方恢复执行。

这很容易实现。我们为函数添加一个额外的参数，这个参数是一个指向上下文结构的指针；并且把局部状态和协程的状态变量都声明为上下文结构的成员。

看起来会有点丑陋，因为你以前只需要使用i作为循环的计数器，而现在你得使用ctx->i；事实上，所有重要的变量都将变成协程上下文结构的成员。但是它解决了可重入问题，并且没有对程序的结构造成负面影响。

（当然了，如果C语言支持Pascal的with语句，那么我们可以把这个间接层隐藏起来。很遗憾。不过，C++可以将协程声明为类的成员，这样就可以把局部变量声明为类的成员，从而将作用域的问题隐藏起来。）

这里提供了一个C语言头文件，用一系列预定义的宏实现了本文所述的协程技巧。文件中定义了两套宏，分别以scr和ccr开头。以scr开头的宏是这个技巧的简单实现形式，用于可以使用静态变量的场景；以ccr开头的宏提供了可重入的实现。头文件的注释中包含了完整的文档。

注意这个协程技术在Visual C++ 6中可能不能工作，因为在默认设置（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。

Thanks for reading. Share and enjoy!

参考文献

Donald Knuth, The Art of Computer Programming, Volume 1. Addison-Wesley, ISBN 0-201-89683-4. 章节1.4.2描述了协程的原始形式。
http://www.lysator.liu.se/c/duffs-device.html 是Tom Duff自己关于Duff设备的讨论。注意，在文章的最后，有个线索表明Duff可能也发明了这种协程技巧或是与之非常相似的东西。

更新，2005-03-07：Tom Duff在一条博客评论中确认了这一点。他在原始邮件中写到的“一种反叛的使用switch的方式来实现中断驱动的状态机”，与我在这里描述的技巧是一样的。
PuTTY是一个Win32平台的Telnet和SSH客户端。其中SSH协议实现的代码中使用了这个协程技巧。据我所知，这是目前正规应用代码中最难Hack的C代码。

译后记

在参考文献中提到的博客评论中，Tom Duff指出这种协程技巧存在的问题：难以实现一个协程多个不同实例；协程只能在最顶层的例程中放弃控制流。而汇编语言实现的基于stack-switching的协程可以做到这两点。

通过传递上下文对象可以解决协程的多实例问题。而在同一个博客评论中，Simon Tatham回复说当他需要在子例程中放弃控制流时，通常是这么做的：

while (subroutine(ctx, params) == NOT_FINISHED_YET) 
    return NOT_FINISHED_YET;

Simon Tatham同意这个协程技巧的效率不如汇编实现的stack-switching的方式高，但是他喜欢这个技巧的可移植性。

[译]C语言协程

C语言协程

引言

重写

Knuth协程

基于栈的协程

Duff设备

评估

编码规范

改进和代码

参考文献

译后记

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

[译]C语言协程

C语言协程

引言

重写

Knuth协程

基于栈的协程

Duff设备

评估

编码规范

改进和代码

参考文献

译后记

热门文章

最新文章

相关课程

相关电子书