More on Continuation

December 10, 2007 – 1:19 pm

我在前一篇文章中用构造二叉树的 iterator 的例子来介绍了一下 Continuation 。Jack评论中向我提了两个问题:

  1. many people know about the CPS transformation, and callcc as a means to get hold of the implicit continuation (”the rest of the computation”), but we often have a hard time using continuations: there’s a large gap between understanding code which uses callcc and the ability to actually synthesize a solution to a problem using callcc. We lose easy-understanding in using callcc, what we get? If we get a lot, how?
  2. When should we adopt callcc and how can we express callcc idea using pencil and paper easily.

我发现我好像是自己沉醉在了 Continuation 的奇妙之中,却没有把事情说清楚。在这篇文章中我会回答他提出的这两个问题,并希望借此推广 Continuation 的思想。 :)

首先是关于 Continuation 的可用性,Continuation 打破了我们常规的关于“函数”的理解。常规的函数只有一个入口,虽然可以有多个出口,但是每次只会从其中一个出口出来。而有了 Continuation 一切都不一样了,一个函数可以有多个入口,不只是函数的头部,你可以从任意地方“潜入”函数之中,同时你可以从一个函数中返回多次,多个出口可以全部用上。

虽然从这样来看 Continuation 只是在原来的基础上做了一下推广,但是要想很容易地去理解这种推广还是相当不容易的,特别是在“经典”的函数的行为已经深深地印在我们脑海中之后尤为困难。既然无法理解自然就不能好好地应用,甚至会得不偿失。是这样的吗?当然不是!

一方面,Continuation 本身可以是处于比较底层的概念,如果你不喜欢追根究底的话,完全可以站在更高层面来把玩它而不必理解它的工作流程,就像前面那篇文章中讲的 iterator 那样,如果你不考虑 ContinuationIteratorImpl 是如何实现的(比如说,这是由别人写的一个库),你得到的将是更加简洁的编写 iterator 的方式,而不是把你绕晕的调用跳转。微软在 C# 2.0 中也引入了类似的特性,好让用户更方便地编写 iterator ,一个典型的二叉树中序遍历的 iterator 看起来像这样:

IEnumerable<t> ScanInOrder(Node<t> root)
{
   if(root.LeftNode != null)
   {
      foreach(T item in ScanInOrder(root.LeftNode))
      {
         yield return item;
      }
   }
 
   yield return root.Item;
 
   if(root.RightNode != null)
   {
      foreach(T item in ScanInOrder(root.RightNode))
      {
         yield return item;
      }
   }
}

yield return 是新引入的语法。事实上,我们完全可以对 ContinuationIteratorImpl 稍加修改就可以实现这样的东西。也许 C# 并不一定是用 Continuation 来实现(比如,可能是编译器在编译的时候就做了手脚,改装成状态机之类的)这个功能的,不过我在这里举 C# 的例子的目的是要说明拥有 Continuation 确实能让我们的 coding 工作变得更加惬意一些。

另一方面,难于理解其实更多的是来源于我们固有的成见,比如说多线程,如果我们一直都认为程序本来就是单线程的,一开始接触多线程总是会会诸如同步之类的问题搞晕;在一段时间里,我们又假定多线程都是一个 CPU 在调度,现在多个 CPU 又走入百姓家,于是我们的思考方式又得变了,一个简单的程序也可能漏洞百出,还得到处加 memory barrier 。

其实这里举线程的例子也并非偶然。回想我们在前一篇文章中想要解决的问题:只有一个堆栈无法保存多条执行线路。而线程是有各自独立的栈的,正好解决了这个问题,不过有一点不同:线程通常接受系统的调度,而我们这里是在做自己的调度。事实上,有一种叫做“纤程”的东西更加类似——它需要我们自己来进行调度。

正好 Ruby 1.9 预计将在今年圣诞节发布(如果不跳票的话,不过似乎最近跳票之风正盛行呢 -,-bb ),不妨来看看 Ruby 1.9 中引入的纤程(Fiber)类,这是一个 Fibonacci 数列的例子:

fib = Fiber.new do
  x, y = 0, 1
  loop do
    Fiber.yield y
    x,y = y,x+y
  end
end
20.times { puts fib.resume }

上一个篇文章中那棵二叉树的迭代器用 Fiber 就可以这样写:

  def fiber_iterator(method)
    Fiber.new do
      send "fiber_iterator_#{method}"
    end
  end
 
  private
  def fiber_iterator_inorder
    # Note that in Ruby 1.9, send doesn't always call
    # private method anymore
    @left.send! :fiber_iterator_inorder unless @left.nil?
    Fiber.yield @value
    @right.send! :fiber_iterator_inorder unless @right.nil?
  end

写起来和我们先前的那个实现非常像吧? :D 事实上,在 Ruby 1.9 考虑迁移到 Native Thread 的时候,Continuation 在 Native Thread 上有些过于昂贵而被去掉了(不过后来又加了进来,应该是会保留下去的吧,至少是作为一个库支持)而 JRuby (它一开始就是用 Native Thread 的实现)根本就是没有实现 callcc 的(似乎 Continuation 给 JRuby 的实现带来了许多痛苦 :) )。

事实上,关于 iterator ,Ruby 自带了一个 Generator 类来帮助我们搞定这些东西,用 Generator 的话,代码会这样写:

  def generator_iterator(method)
    Generator.new do |generator|
      send "generator_iterator_#{method}", generator
    end
  end
 
  def generator_iterator_inorder(generator)
    @left.send! :generator_iterator_inorder, generator unless @left.nil?
    generator.yield @value
    @right.send! :generator_iterator_inorder, generator unless @right.nil?
  end

都是大同小异了。不过 Generator 其实是使用 callcc 来实现的,差不多就是我们前面做的工作了。听说 Ruby 1.9 里的 Generator 改用 Fiber 来实现了,可是我现在的代码里面却是用的线程(而且运行时会出现一大堆 Warning),等圣诞节 Ruby 1.9 发布的时候再看了。

再看 Fiber 与 Continuation ,会发现 Fiber 可以算作是 Continuation 的一个特殊情况:同样可以在各条线之间跳转,只是 Fiber 会在每一条线中保持一个“从上往下”的执行顺序,看起来更像(由自己来调度的)线程(事实上就是这样的)一些,而 Continuation 则不会拘泥于这种顺序,你可以跳转到执行线的任意一点,或者是多次跳到同一点重新执行。

既然 Fiber 是一个特殊化的 Continuation ,那么就直接用更强大的 Continuation 好了,干嘛还要搞一个 Fiber 出来呢?其实这样的特殊化是非常有用的。事实上,Continuation 的大部分应用都可以用 Fiber (和 Fiber::Core 用于实现 Coroutine )表达出来,换句话说,Fiber 作为一个“精简”的 Continuation 实现了大部分常用的功能,而 Fiber 所不能很好地表达的那些 Continuation 的特性却是很少用到的。而这样一个特化至少有两个方面的好处:

  1. Fiber 更像一个线程(这是我们熟悉的东西),因此我们更容易明白它的工作方式,也更容易用它来写出有用的程序来。虽然我们可以很轻松地用 Continuation 做出一个 Fiber 的实现来,但是这样一个包装其实是非常有用的,即使只是一个语法糖。如果你觉得只要语法无关紧要的话,建议你去试试 Unlambda 语言,反正我是觉得对于我来说,用英语来算乘法远比用汉语算要困难得多。

    关于这种语法上的特化,我想还有一个很类似的地方:我一直觉得 Lisp 的那种把函数作为一个基本对象来处理的方法很不错,通过传递 lambda 函数,可以很方便地完成许多事情,而 Ruby 让我惊喜的是,它发现大部分情况下通常只需要传递一个 lambda 函数,于是它把这种特殊情形特化出来发明了 block ,让许多代码不管是看起来还是写起来都清晰了许多!

  2. 特化之后许多原来可变的因素就会固定下来,这样就可以做许多优化了。这和 Unix 里的哲学是差不多的,与其挖空心思找一个复杂无比的大统一理论来把所有的情况包含进来,他们更喜欢使用 20% 的代码来完成 80% 的工作,剩下的 20% 的工作特殊对待。虽然科学家们也许不太喜欢这样的方法,但是对于程序员来说,这样写出来的代码通常会更加明晰——如果抽象出来的情形复杂无比的话,还不如不抽象呢。

    再回到 Fiber 的问题上来,事实上 Ruby 里的 Fiber 就不是用 Continuation 来实现的,这样做不仅会有性能上的好处,而且对于实现者来说也是一件好事情:Continuation 的实现工作虽然给 JRuby 团队带来了无尽的痛苦,然而他们却实现了 Fiber 。对于这个我并没有做过性能测试,不过对于前面提到的 block 之于传递 lambda 函数(Proc)的特化有人做过性能测试,结果是特化之后性能提升了至少 10 倍。

如果把问题特化到 Fiber 上,似乎就觉得熟悉了很多了,回答前面的第二个问题也更容易了。直接把 Fiber 看作是一个由我们自己调度的轻量级线程就可以了。例如 C++ 的异步 IO 网络库 boost::asio 里面的编码方式通常都是一种类似于 CPS 的方式来进行。例如,调用 io_service 提供的 async_connect 将把函数传递 handle_connect 传递过去,io_service 在连接上之后,会调用传递过去的 handle_connect 。如下图所示:

asio.png

正常的程序后面应该还有很多过程,例如调用 async_read 并传递 handle_read 、调用 async_write 并传递 handle_write 等。可以看到这里也本来是两条线在走,只是 C++ 没有 Continuation 的支持,只能手工模拟 CPS 的方式,这样非 io_service 这条线就被打断成一个个的小片段,如果有状态需要保存的话,只有通过成员变量或者参数传递的方式手工保存起来才行。

如果利用 Fiber (或者 Continuation),情景就清晰许多了,上图唯一需要更改的就是把右边的小片段全部连接起来,而右边的线也不需要手工保存各种状态信息了。两条独立的执行线,在必要的时候(这个由我们自己明确的控制,而不是像线程那样由系统来调度)切换到另外一条线去。

我想,这样的图用笔和纸画起来应该是很方便的了,而且特化到 Fiber 这样的模型以后应该是不会再像原来那么晕头转向,而是应该有助于理解才是。 :D

  1. One Response to “More on Continuation”

  2. 终于到了Fiber,看来我应该写blog了 :)

    By Jack on Dec 10, 2007

Post a Comment