|
说起Continuation象我这样的大多数从C Basic Pascal起步的程序员可能都不清楚但是这个概念在functional language 社区却好象是常识一样很多人在讨论问题的时候总是假设你已经知道了continuation的基本概念什么CallCC什么的都不加解释就直接引用于是如果不知道continuation到底指的是什么简直就无法理解他们在说什么 于是最近花了点时间研究了continuation的概念 刚才恍然小悟了MonadCont的实现机制作为庆祝在此和大家共享一下我的理解然后再回头讨论一下continuation在imperative语言和C++中的可能应用 所谓continuation其实本来是一个函数调用机制 我们熟悉的函数调用方法都是使用堆栈采用Activation record或者叫Stack frame来记录从最顶层函数到当前函数的所有context一个frame/record就是一个函数的局部上下文信息包括所有的局部变量的值和SP PC指针的值（通过静态分析某些局部变量的信息是不必保存的特殊的如尾调用的情况则不需要任何stack frame不过逻辑上我们认为所有信息都被保存了）函数的调用前往往伴随着一些push来保存context信息函数退出时则是取消当前的record/frame恢复上一个调用者的record/frame 象pascal这样的支持嵌套函数的则需要一个额外的指针来保存父函数的frame地址不过无论如何在任何时候系统保存的就是一个后入先出的堆栈一个函数一旦退出它的frame就被删除了 Continuation则是另一种函数调用方式它不采用堆栈来保存上下文而是把这些信息保存在continuation record中这些continuation record和堆栈的activation record的区别在于它不采用后入先出的线性方式所有record被组成一棵树（或者图）从一个函数调用另一个函数就等于给当前节点生成一个子节点然后把系统寄存器移动到这个子节点一个函数的退出等于从当前节点退回到父节点 这些节点的删除是由garbage collection来管理如果没有引用这个record则它就是可以被删除的 这样的调用方式和堆栈方式相比的好处在哪里呢？ 最大的好处就是它可以让你从任意一个节点跳到另一个节点而不必遵循堆栈方式的一层一层的return方式比如说在当前的函数内你只要有一个其它函数的节点信息完全可以选择return到那个函数而不是循规蹈矩地返回到自己的调用者你也可以在一个函数的任何位置储存自己的上下文信息然后在以后某个适当的时刻从其它的任何一个函数里面返回到自己现在的位置 Scheme语言有一个CallCC (call with current continuation)的机制也就是说取得当前的continuation传递给要call的这个函数这个函数可以选择在适当的时候直接return到当前的continuation 经典的应用有exceptionbacktracking算法 coroutine等 应用continuation对付exception是很明显的只要给可能抛出异常的函数一个外面try的地方的continuation record这个函数就可以在需要的时候直接返回到try语句的地方 Exceptionhandling也可以利用continuationc++等语言普遍采用的是遇到exception就直接中止当前函数的策略但是还有一种策略是允许resume也就是说出现了异常之后有可能异常处理模块修复了错误发生的地方然后选择恢复执行被异常中断了的代码被异常中断的代码可以取得当前的continuation传递给异常处理模块这样当resume的时候可以直接跳到出现异常的地方 Backtracking算法也可以用类似的方法在某些地方保存当前的continuation然后以后就可以从其它的函数跳回当前的语句 Coroutine是一个并行计算的模型它让两个进程可以交替执行典型的coroutine的应用例子如consumerproducer比如说 Code:Producer ( c ): Loop: Produce; CallCC c Consumer( p ): Loop: Consume; Callcc p 这两个线程接受对方的continuation在需要交出控制的时候就把自己的continuation传递给对方如此两者就可以交替执行而不需要返回 Continuation机制的优化始终不是一个trivial的问题实际上采取continuation的语言不多而且continuation调用方式依赖垃圾收集也不是c/c++这类中低级的语言所愿意采用的 不过continuation的思想仍然是有其用武之地的有一种设计的风格叫做continuationpassingstyle它的基本思想是当需要返回某些数据的时候不是直接把它当作函数的返回值而是接受一个叫做continuation的参数这个参数就是一个callback函数 它接受这个数据并做需要做的事情 举个例子 Code:X = f(); Print x; 把它变成continuationpassingstyle 则是 f(print) F()函数不再返回x 而是接受一个函数然后把本来要返回的x传递给这个函数 这个例子也许看上去有点莫名其妙为什么这么做呢？对Haskell这样的语言一个原因是 当函数根据不同的输入可能返回不同类型的值时用返回值的话就必须设计一个额外的数据结构来处理这种不同的可能性比如 一个函数f(int)的返回值可能是一个int 两个float或者三个complex那么我们可以这样设计我们的函数f Code:F:: Int > (Int>a) > (Float>Float>a) > (Complex>Complex>Complex>a) > a 这个函数接受一个整形参数三个continuation回调用来处理三种不同的返回情况最后返回这三个回调所返回的类型 另一个原因对模拟imperative风格的monad可以在函数中间迅速返回（类似于C里面的return或者throw) 对于C++我想除了处理不同返回类型的问题另一个应用可以是避免返回值的不必要拷贝虽然c++现在有NRV优化但是这个优化本身就很含混各个编译器对NRV的实现也不同C++中的拷贝构造很多时候是具有副作用的作为程序员不知道自己写的的副作用到底是否被执行了被执行了几次总不是一个舒服事 而continuationpassingstyle不依赖于任何偏僻的语言特性也不会引入任何的模稜两可也许可以作为一个设计时的选择举个例子 对于字符串的拼接如果使用continuationpassingstyle如下 Code:Template<class F> Void concat(const string& s const string& s F ret){ String s(s); Sappend(s); ret(s);//此处本来应该是return(s)但是我们把它变成ret(s) } 我们就可以很安心地说我们此处没有引入任何不必要的拷贝不论什么编译器 当然continuation style的问题是它不如直接返回值直观类型系统也无法保证你确实调用了ret(s)而且它需要一个function objectc++又不支持lamda定义很多trivial的functor也会让程序变得很难看 利弊如何还要自己权衡 |
