C 协程技术

By guenchi at 2017-12-17 • 0人收藏 • 239人看过

http://www.oschina.net/translate/coroutines-in-c?lang=chs&page=1#

介绍 

我们都知道构建一个大型的程序是一件非常困难的工作。一个经常面临的问题来自于此:如果你有一个代码片段用来生产数据,另一个代码片段来调用它,哪一个是调用者,哪一个是被调用者呢? 

这里有一个简单的解压过程的代码片段和一个同样简单的解析代码片段: 

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

每个代码片段都很简单,通俗易懂。一个通过调用emit()方法每次产生一个字节;另一个调用getchar()每次获取一个字节。如果只通过调用emit()和getchar()就能彼此间提交数据,那么就能简单的把两个代码片段连接到一起,因此也就能把解压的输出直接传递到解析部分。 

在很多现在操作系统中,你可以使用管道在两个进程间通信或者两个线程emit()——在解压代码中写入管道,在解析代码中使用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;
    }
}

当然你不需要两个都重写;只修改一个就可以。如果把解压片段重写为以上形式,那么每次调用它都返回一个字符,原始的解析代码片段中就可以把调用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操作来查看它当前进行到哪里。


虽然这样,它还是比较丑。最糟糕的的部分是,这一组标签必须手动维护,并且在函数体和初始的switch语句之间保持一致。每次新增一个返回语句,我们必须引进一个新表签名并把它加到switch列表中;而每次删除一个返回语句,我们又必须移除相应的标签。刚刚我们只是考虑一个因素增加的两倍维护工作量。


达夫设备(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;
}


这差不多就是我们想要的了。我们可以通过这种一返回就控制下一个调用回复的方式,用crReturn从函数返回。当然,我们必须遵守一些基本规则(用crBegin和crFinish包住函数体;声明所需的所有保存在acrReturn中的静态局部变量;绝不要在一个显式switch语句中设置一个crReturn);但那些并不会限制我们太多。 

剩下的唯一问题是传给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;
}

我们已经重写了解码器和解析器都作为了被调用者,不需要像最后一次那样大规模的重写。每个函数的结构恰好是原始结构的镜像,读者能够通过解析器推断出相应的语法,或者通过解码器了解到解压数据格式,比起读那些状态机代码简单多了。一旦你适应了新的格式,你就会发现控制流程非常直观:当解压器产生一个字符,它就调用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语句把这些重要的东西隐藏到“不清晰”的宏中,从编程标准角度来看你已经破坏了程序的语法结构,违背了代码清晰的要求。但是我们这样做是为了突出程序的算法结构,而算法结构也正好是读者想要了解的! 

任何的编码规范坚持语法的清晰度而牺牲了算法的清晰度都应该被重写。如果你的老板因为使用这个技巧而解雇你,当安保人员把你拖走时要不断告诉他们。

风骚般的编码 

在正儿八经的应用程序中,协程很少使用,因为它依赖于静态变量,因此不能重入或者支持多线程。理想情况下,在真实应用程序中,你可能想在多个不同的上下文中调用同一个函数,并且在给定的一个上下文中每次调用时,都能在这个上下文中上一次返回的位置继续执行。 

这很容易做到,我们增加一个新的函数参数——一个上下文结构的指针;我们将所有的局部变量和协程用到的状态变量都声明成结构体中的元素.

这儿包含的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。

参考文献 

  • Donald Knuth,计算机编程艺术, 卷 1. Addison-Wesley, ISBN 0-201-89683-4. Section 1.4.2 describes coroutines in the "pure" form. 

  • http://www.lysator.liu.se/c/duffs-device.html 是 Tom Duff's自己关于Duff策略的讨论。注意,右下角,暗示着Duff有可能独立的完成这样的协程技巧或者其他类似的东西。 

    更新与, 2005-03-07Tom Duff 在一篇博客评论中证实了这一点。“revolting way to use switches to implement interrupt driven state machines”这篇文章中和他最初在邮件中说的确实一样. 

  • PuTTY是一个 Win32 Telnet 和 SSH 客户端。SSH协议其中一部分使用了协程技巧.,据我所知,这是一个在生产代码中最糟糕的C代码片段的轮子。


登录后方可回帖

登 录
信息栏

Scheme中文社区

推荐实现 ChezScheme / r6rs / r7rs large
theschemer.org
Q群: 724577239

精华导览

社区项目

包管理器:Raven
HTTP服务器:Igropyr (希腊火)
官方插件:vscode-chez

社区目标:

完善足以使Scheme工程化和商业化的库,特别是开发极致速度的Web服务器和ANN模块。

一直以来Scheme缺少一个活跃的中文社区,同时中文资料的稀少,导致大多数因为黑客与画家和SICP而接触Scheme的朋友,在学完SICP后无事可做,不能将Scheme转换为实际的生产力。最后渐渐的放弃。
同时Chicken等实现,却因效率问题无法与其他语言竞争。本社区只有一个目的,传播Scheme的文明之火,在最快的编译器实现上,集众人之力发展出足够与其他语言竞争的社区和库。


友情链接:

Clojure 中文论坛
函数式·China


Loading...