有界连续

By guenchi at 2017-12-11 • 0人收藏 • 185人看过

有界连续,不是要讲数学里面的"有界连续",而是编程语言里面的"delimited continuation",姑且将它翻译成"有界连续",不过后面还是尽量使用英文单词。

continuation表示的是"剩下的计算"。CPS(continutation-passing style)里面的C,就是单词continuation的缩写,CPS的意义在于它提供了一种机制将continuation暴露出来。可能continuation这个概念比较陌生,但其实当里写回调风格的代码时,就已经在接触continuation的概念了。

rendor(button_click_callback)

假设这是一个模态的窗口,点击以后在button_click_callback里面会处理接下来的逻辑。其实button_click_callback就是一个continuation,因为它代表的正是“剩下的计算”。

为了暴露控制流而将整个程序做CPS变换,这种方式获得continuation是不怎么友好的。正如回调风格的代码是比较反人类的一样。

有少数语言提供了机制将continuation暴露出来,scheme里面著名的call/cc就是其中一种。区别于delimited continuation,call/cc是一种undelimited continuation。就是说由call/cc得到的连续,是一种完全没什么限制的continuation。可以回到程序执行的任意时刻,可以实现异常、coroutine等等任何东西。

scheme的call/cc虽然方便了用户,但是引出了一些问题,或者我认为它带来的问题比好处多。

首先是性能问题。传统的函数,进入时产生一个栈,返回时这个栈就退出了,将来是没办法再重新回到这个函数的现场的。而在scheme中,既然够将continuation保存下来,将来任意时刻再重回现场,那必然程序的控制结构相对于传统模型会有巨大的变化。其中一种方式是做CPS变换,chicken scheme是这么干的,CPS变换之后的函数永不返回,于是栈只会一直增长不加回收,必须再引入蹦床之类的机制。另一种方式是使用不同的虚拟机模型,比如SECD。这样的模型由于存储环境是基于堆而不是栈,性能都不靠谱。

其次是实现复杂。SECD不靠谱啊,怎么办?想办法优化。比如想办法优化成stack/heap混合存储模型,但优化的代价就是过高的实现复杂度,难以理解,难以实现。

还有个问题是实用性低。call/cc的那种undelimited continuation,虽然理论上说是非常强大,可以实现异常,非局部跳转,生成器,coroutine等等等,但哪个用户又是真正祼的使用call/cc呢?你看lua的coroutine大家都知道吧,其实比起sheme的continuation那是相当的low,但是...resume/yield明显比call/cc好用。

这是关于continuation和undelimited continuation,而接下来才是真正的主题:delimited continuation。

举个例子,一个简单的算术表达式:3 + 5 * 2 - 1,如果我们要执行5 * 2,那当前的表达式就是5 * 2,我们写成3 + [5 * 2] - 1来表示。那么continuation(当前连续)就是3 + [.] - 1。换句话说,它的意思是"当[.]接受一个值之后,它会继续将这个值加上一个3,然后减去一个1",这就是continuation所谓“剩下的计算”的含义。很类似于一个函数,当它接受一个值之后,继续完成函数体里面的计算。[.]可以换成其它东西,比如说抛出异常,那就是3 + [raise Abort] - 1。

delimited continuation就是多了一个界,即是给[.]会回到哪里定了一个"界",比如<3 + [5 * 2]> - 1,我们用<>来表示"界",那么当前的有界继续[5 * 2]是<3 + [.]>,而不包含后面的那个减1。

为了方便研究,我们引入shift和reset两个关键字。

(reset E)在一个delimited的上下文中执行E,如果在E的执行期间有捕获continuation,那么捕获的连续将以reset为界。(reset E)表达式的返回值等于E的返回值。

(reset (- (+ 3 (* 5 2) 1)))

返回的是12。

(shift (lambda (k) E))将当前的有界连续捕获为k,执行表达式E。

3 + [5 * 2] - 1,放到reset和shift里面:

(reset (- (+ 3 (shift (lambda (k) (* 5 2)) 1))))

这个直接返回10,因为我们是丢弃了连续直接返回的。而

(reset (- (+ 3 (shift (lambda (k) (k (* 5 2))) 1))))

返回的是12。这是正常的执行逻辑,5乘2的结果被返回给 3 + [.] - 1 这个continuation,继续执行后得到12。

(- (reset (+ 3 (shift (lambda (k) (* 5 2))))) 1)

返回的是9。5乘2作为reset表达式的值返回之后,再减去1。

甚至我们可以返回不一样的类型:

(reset (- (+ 3 (shift (lambda (k) "hello")) 1)))

返回字符串"hello"。

通过shift和reset, <3 + [5 * 2]> - 1 映射起来非常直接,简单来说界就是用reset来限制,而连接就用shift来捕获。

异常用delimited continuation描述也是十分方便的:

try {
  3 + (if 1=1 5 else throw error) - 1
} catch {
}

(reset (- (+ 3 (shift (lambda (k) (if 1=1 (k 5) else error)))) 1))

最后简单提一下delimited continuation的实现。实现方式其实是很多的,比如用undelimited continuation是可以实现出delimited continuation的,那么call/cc就可以实现shift和reset,当然这样子违背初衷了。或者用CPS变换,可以只做局部的CPS。

感觉比较靠谱的一种实现是拷贝栈。在reset的时候在栈上加一个标记,当出现shift的时候,将栈顶到标记之间的内存,保存到堆上,同时连上返回地址之类的上下文信息抽象成一个函数闭包,接着以这个闭包为参数k调用shift的函数。如果之后k被调用了,则将保存的堆现场恢复到栈上,继续完成这个连续,而如果k没有被调用,也就是直接被丢弃了。

由于保存下来的现场只是一段的栈,所以这个continuation是有界的,只能恢复到reset时的位置。


登录后方可回帖

登 录
信息栏

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...