routine, subroutine and coroutine

routine 这个单词表示类似 procedure 的意思,

fixed and regular way of doing things

而衍生词 subroutine 的前缀 sub 表示在 … 之下,子 … 的意思,常被翻译为“子过程”、

When subroutines are invoked, execution begins at the start and once a subroutine exits, it is finished; an instance of a subroutine only returns once.

这似乎对应着写程序里面时常写的函数。而 coroutine 的前缀 co 表示协同的意思,看起来就有了那么点“并行”的意味了,

Coroutines are similar except they can also exit by calling other coroutines, which may later return to the point of calling in the original coroutine; from the coroutine’s point of view, it is not exiting at all but simply calling another coroutine.

这是 D.E.Knuth 给的定义。从某种角度来说 coroutine 是对 subroutine 的推广。

从实现的角度来看,subroutine 和 coroutine 的意思更加明确。对于一个仅仅有 subrtouine 的程序,我们知道通常我们有一个 call stack,每次调用一个 subroutine,我们的栈都需要记录栈顶信息,这样保证我们 subroutine return 的时候堆栈能够正确的回退,如果这个 stack 向下生长,subroutine 也是在下面咯。而实现 coroutine 往往需要 continuation,一个比较常见的实现方式是使用若干个 call stack(每个 coroutine 都有自己的 call stack),coroutine 之间通常使用 yield 将对 CPU 的执行权利交给调用它的 coroutine,这样一来两者并不像 subroutine 那样有个 caller-callee 的关系,而是对称的。

continuation 的实现

实际操作中,continuation 并不一定要求多个 call stack 乃至与 garbage collector 协同工作才能实现,存在一些替代性的策略,如预先在 stack 上开辟足够的内存分给多个 coroutine。某些语言甚至直接支持对 continuation 的操纵,通常者都会提供所谓的 callcc 操作(call with current continuation)。

与 generator 的关系

generator 也可以认为是 subroutine 类似的一种扩展,因为它也支持“记住状态”的效果,python 里面通过 yield 可以产生 iterator,反复调用时就会延续上次调用的位置继续执行那个写了 yield 的 function。generator 很明显可以用 coroutine 来实现,但是却相对来说更有局限性。

coroutine 的作用

coroutine 有下面几个用途:

  • 写 generator
  • 实现 actor model
  • 实现 state machines

python 是不支持 coroutine 的,但是可以通过 yield 实现一些简单的 generator,据说 2.5 之后也用到了 continuation。

boost 中的 coroutine

boost 的 asio 可能是最早开始涉及 coroutine 的 boost 组件,而现在还出现了单独的 coroutine,写这篇 blog 也是为了读懂这篇 blog。文中所说的 stackful coroutine 前一段时间也收到了 review 过程的提醒,不过似乎一直没看到结果。感觉这些东西还是很神奇的,就跟 exception 一样,如何实现出来的尚未完全想清楚,大概都跟前面那个该死的 continuation 有关系吧,倒是 stackless coroutine 看起来是个比较常见的 macro 把戏。似乎倒是 functional programming languages 这些支持得很早,比如 Scheme、Scala 一流的东西。

写了这么长时间的程序,发现其实写程序这件事情知道的还是太少了啊…

——————
And the damsel was very fair to look upon, a virgin, neither had any man known her: and she went down to the well, and filled her pitcher, and came up.

Advertisements
routine, subroutine and coroutine

一个有关“routine, subroutine and coroutine”的想法

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s