C 协程 已翻译 100%

chishaxie 投递于 2013/03/19 09:28 (共 21 段, 翻译完成于 03-26)
阅读 14787
收藏 35
7
加载中

介绍

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

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

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


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

在很多现在操作系统中,你可以使用管道在两个进程间通信或者两个线程emit()——在解压代码中写入管道,在解析代码中使用getchar()从另一端相同的管道中读取。简单强壮,但是也重量不可移植。通常你不想把你的一个简单程序分到线程中。

在这篇文章中我提供了一个创造性的解决方案来处理这个构造的问题。
缪斯的情人
翻译于 2013/03/25 09:15
1

重写

常见的方式是重写末端的通信管道,把它作为一个可调用的函数。这有个简单的例子。

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()。如果你是个贪婪的人你可以把两个函数都重写,都作为被调用者。

缪斯的情人
翻译于 2013/03/25 09:45
1

这就是我的真实观点。和两个重写后的函数相比原始的代码丑陋无比,在这里当两个进程被写为调用者而不是被调用者时更易读了。如果你试图通过解析器推断出语法,或者通过解压器了解解压数据格式,只需阅读下代码就可以,同时你会发现原始的代码清晰些,重写后的代码格式上不太清晰,如果没有嵌入另外一者的代码这会更好些。

缪斯的情人
翻译于 2013/03/25 10:06
1

Knuth协程

在《计算机程序设计艺术》中,Donald Knuth提供了一个解决这类问题的方法。他的方法是彻底丢掉堆栈的概念,不要再想一个进程作为调用者,另一个作为被调用者,把他们当做平等的协作者关系。

实际上就是:把传统的“调用”稍微改为一个不同的方式。新的“调用”将在某个地方保存返回值而不是堆栈上,并且还能跳转到另一个保存返回值的指定位置上。因此,解码器每次生成一个字符,就保存它的程序计数器并且跳转到上次解析器的位置-解析器每次都需要一个新的字符,它保存自己的程序计数器并且跳转到上次解码器的位置。程序可以在两个函数之间来回自如的传递需要的数据了。

缪斯的情人
翻译于 2013/03/25 21:47
1
理论上看起来很美,但实际中你却只能在汇编语言中使用,因为通用的高级语言没有一个支持调用原始的协程。像类似于C的都是依赖于基础的堆栈结构,因此当在函数间进行数据传递时,一个必须作为调用者,领一个必须作为被调用者。所以如果你想写可移植的代码,这种技术和Unix管道一样不切实际。
缪斯的情人
翻译于 2013/03/25 22:09
1

基于栈的协程

我们真正想要的是在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的数字。

缪斯的情人
翻译于 2013/03/25 22:21
2

我们怎么能实现这个呢?好吧,我们可以用一个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
翻译于 2013/03/25 22:41
1
虽然这样,它还是比较丑。最糟糕的的部分是,这一组标签必须手动维护,并且在函数体和初始的switch语句之间保持一致。每次新增一个返回语句,我们必须引进一个新表签名并把它加到switch列表中;而每次删除一个返回语句,我们又必须移除相应的标签。刚刚我们只是考虑一个因素增加的两倍维护工作量。
jimmyjmh
翻译于 2013/03/25 22:51
1

达夫设备(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
翻译于 2013/03/25 23:10
1
本文中的所有译文仅用于学习和交流目的,转载请务必注明文章译者、出处、和本文链接。
我们的翻译工作遵照 CC 协议,如果我们的工作有侵犯到您的权益,请及时联系我们。
加载中

评论(8)

jander
jander
太不好用了。
Cobbage
Cobbage
顶一个
张三alpha
张三alpha
赞一个!
霡霂
霡霂

引用来自“缪斯的情人”的评论

好累人

樯橹间灰飞烟灭
chishaxie
chishaxie

引用来自“jimmyjmh”的评论

引用来自“缪斯的情人”的评论

好累人

这么勤奋肯定累啊。

你们好猛啊……
chishaxie
chishaxie

引用来自“缪斯的情人”的评论

好累人

你们好猛啊……
jimmyjmh
jimmyjmh

引用来自“缪斯的情人”的评论

好累人

这么勤奋肯定累啊。
缪斯的情人
缪斯的情人
好累人
返回顶部
顶部