简介延续“Continuation”

作者: Denys Duchier

翻译: Shining Ray @ Nirvana Studio

写本文旨在回应comp.lang.python新闻组中关于延续的讨论。


对于call/cc(call with current continuation)的情结和关于他的操作解释粗糙的细节内容,至今一直掩盖了延续的简洁和优雅。在本文中,我想用两个方式来纠正这个问题:

  • 首先用一个简单且直观的方式展示延续的概念。
  • 第二通过提供_可运行的_Python代码,来描述如何使用延续而不用call/cc来实现搜索引擎。

我将展示:

  1. 一个针对命题公式确定性检查工具。
  2. 一个基本的带回溯和裁剪的prolog引擎。

我希望这能帮助那些对于这个论题有些迷惑的人搞清这个问题。我还想指出上面讲到的两个程序是我在今天晚上花了几个小时写的,他们应该可以给你关于下面将要讲述的技术的能力的一些衡量尺度。


1. 简化延续

习惯上一般来说,一个函数返回一个值是这样的:

这隐含了它的值返回的地方。而延续的想法是通过添加一个延续参数来明确要返回的地方。函数不“返回”值,而是通过把值作为一个参数传递给延续“继续”处理值。在基于延续的程序中,以上函数foo变成了:

从这个角度看,函数从不使用返回“return”。取代的是它“继续”。正因为这个原因,延续有时候会被描述为“带参数的goto”。

上面描述的想法是。更精确地说,它是CPS(Continuation Passing Style,延续传送风格)的一个初步代码转换。基本的想法是给每个函数添加一个额外的“延续”参数,并进一步转化函数体以便不用返回他的值,而是把值传送给这个额外的延续参数。

在foo函数的例子中已经大体描述了这个概念。然而,更确切的,要注意CPS转换同时展开了所有的非lambda算子的嵌套表达式(换句话说,就是他显式地连接了所有子表达式的计算)。让我们看一个例子:

在延续传送的观点中,甚至像*+之类的基本操作符都要带一个额外的延续参数。我们通过以下定义进行模拟:

现在,CPS可以把上面的baz函数转换成:

换句话说,2*x的计算现在使用了一个延续来接收结果v并使用它来计算 v+y并最终把这个结果传给总的延续c

当在这个上下文中理解了call/cc之后,它就不再神秘了。它只是一个特殊的手段,能让我们的双手去接触那个不可见的由CPS引入的额外的延续参数,并让我们像程序中其他函数值那样使用它。思考call/cc(f),其中f需要接受当前延续作为参数。其实说到底,call/cc(f)可以通过CPS转换成call_cc(f,c),而c就是CPS所引进的延续参数同时call_cc可以按照以下方式定义:

即,f的普通参数和由CPS引入的额外的延续参数都是当前的延续c

还有一些细节,不过以上部分是基础。

CPS转换是很多针对函数式语言的编译器的基础。它的缺点是它引入了很多lambda算子(即闭包),同时,必要的是,编译器要尽可能多得把他们优化出去。在这方面,Scheme的Rabbit编译器的Steele,T的Orbit编译器的Kelsey etal. 和SML/NJ编译器的Apple有着很多的研究。有一个优点是,如果lambda表达式是你唯一的控制结构而且你把他们优化到了极限,那么你同时也优化了所有的控制结构。

然而应该注意的是,也正如很多人已经注意到的,由于编译器的工作恰是常常要把CPS引入的东西删除,所以有些人对将CPS转换作为编译过程基础的价值提出了质疑。

2. 将延续作为一个普通的编程技术

你可能已经注意到一些人对于不可思议难懂的延续的应用极其狂热。但事实上还是有着很多“非不可思议”的延续的应用,他们也不要求call/cc的存在。你可以在Python中书写延续传递程序,或者在任何支持闭包的部分形式和有自动垃圾收集的语言中写。

我最了解的应用程序是关注于“搜索”。它和正在进行的关于迭代子的讨论有很大的关系。很多年以前,我从我以前的导师Drew McDermott那里学习了这个技术,我会在下面讲述它。然而,我得指出,和Tim的特性记述相反,生成器(generator,在Drew的观点上)不需要以“类栈方式”进行表现;尽管很少有提出不这样用的 :-)

这个概念是通过传递两个延续来进行搜索:

  1. 一个成功延续,用于进一步进行搜索
  2. 一个失败延续,用于回溯到第一个更早的选择点

用Python来表达它,常常是以下面的形式出现:

“info”是在搜索中传送的一些信息。“yes”是成功延续,“no”是失败延续。“yes”以当前的“info”状态和当前的失败延续作为参数。而“no”则没有参数。

如果self.check(info)为真,则Foo对象满足了搜索条件。

一个有两个Foo“one”和“two”属性的类Baz。定义一个Baz对象来满足搜索条件,只要“one”属性满足它或者“two”属性满足(换句话说就是一个Baz对象是一种析取式)。我们通过调用“one”属性的搜索方法来表达,同时还给他传递一个尝试“two”属性的失败延续。

很明显,在上面的内容中,由于Python缺乏对于闭包的真正支持,使得要按照函数式语言中简洁和优雅的写法书写有些困难。

3. 检查命题公式的确定新

命题逻辑的公式如下:

它表示

p,q,r 是可以被赋以真值得命题变量。你可以证明不管你给p,q,r赋什么值,上面这个公式总是为真的。看一个更加简单的公式会更清楚,如(p | !p)也就是“p或非p”。这样一个公式是所谓的“确定的”:它总是为真,无论你如何解释他的变量。

下面的Python程序实现了针对命题公式的确定性检验工具,它使用了前面描述的延续传送风格。这个程序仅仅只是要描述一个例子而已。对于这种人物有更加有效的方法。然而,我相信它可以很好地表达关于使用延续传送实现搜索的一个通用的想法。

两个程序(确定性检查工具和前面提到的prolog引擎)都可以在下面的URL中获得:

“简介延续“Continuation””的4个回复

  1. “CPS转换是很多针对函数式语言的编译器的基础。它的缺点是它引入了很多lambda算子(即闭包),同时,必要的是,编译器要尽可能多得把他们优化出去。在这方面,Scheme的Rabbit编译器的Steele,T的Orbit编译器的Kelsey etal. 和SML/NJ编译器的Apple有着很多的研究。有一个优点是,如果lambda表达式是你唯一的控制结构而且你把他们优化到了极限,那么你同时也优化了所有的控制结构。

    然而应该注意的是,也正如很多人已经注意到的,由于编译器的工作恰是常常要把CPS引入的东西删除,所以有些人对将CPS转换作为编译过程基础的价值提出了质疑。” 个人觉得本文中最有价值的部分。

发表评论

电子邮件地址不会被公开。 必填项已用*标注