函数式编程的另类指南(9)

By | December 24, 2013

The following part is not maintained anymore. Please go to 函数式程序设计的另类指南 for the whole translation.

以下内容不再更新,浏览全部翻译,请访问函数式程序设计的另类指南


原文链接:Functional Programming For The Rest of Us
原文作者:Vyacheslav Akhmechet

Continuations

Continuations对于程序设计的意义,就像《达芬奇密码》对人类历史的意义:揭露了人类有史以来最大的假象。恩,也许没那么牛。但它在概念上的突破性至少和开方负数的意义相同。

我们学习函数时,其实基于这样一个假设:函数只能将结果返回给调用者。在这个意义上continuation是广义的函数。一个函数不一定必须要返回到其调用者,它可以返回到程序的任何地方。continuation可以是函数的一个参数,我们通过这个参数指定函数返回位置。这个描述可能听起来很复杂,我们来看看下面的代码:

int i = add(5, 10);
int j = square(i);

函数add返回15,并赋值给i,即原始调用add的地方。然后在调用square的时候使用i。注意,延迟特性的编译器无法重新排列这些代码,因为第二行代码依赖于第一行的执行。但是我们可以用延续传递方式(Continuation Passing Style,CPS)重写这段代码,用它来指定add函数直接返回到square,而不是原来的调用者:

int j = add(5, 10, square);

这个例子中 add 有了另一个参数 —— 一个add在结束时需要调用的函数。这里square是add的continuation。这两段代码的结果都是j=225.

这个技巧可以用于迫使惰性语言顺序执行两个表达式。接下来我们看看这个(熟悉的)IO代码:

System.out.println("Please enter your name: ");
System.in.readLine();

这两行代码彼此独立,所以编译器会根据自己希望的顺序去执行他们。但是,如果我们用CPS来重写这段代码,它们之间便有了依赖关系,编译器会按顺序执行它们:

System.out.println("Please enter your name: ", System.in.readLine);

这里,println需要在结束后调用readLine并且返回readLine的结果。如此这两行就能保证被有序执行,并且readLine一定会被执行(因为整个运算以最后一个值作为返回值)。Java的println会返回void,但如果假设它返回的是一个readLine能接受的抽象值,我们就解决了这个问题!当然,像这样把函数串起来,会降低代码的可读性。不过这个可以避免。我们可以在程序语言中添加一些语法规则,使我们可以像原来那样按顺序输入代码,然后编译器自动把它们串起来。这样我们就可以按希望的顺序执行代码,并且保留一切函数式编程的好处(包括按数学逻辑来解释我们的代码)。如果说到这里还有点晕的话,那么记住,一个函数就是一个只有一个成员的类实例。如果将上面的代码重写成println和readline的类实例的话,可能就清楚多了。

如果我就此结束,那将仅仅涉及到continuation的皮毛。我们可以用CPS重写整个程序,使所有函数都有一个额外的continuation参数,然后将当前函数的执行结果传进去。我们也可以将函数看成一类特殊的continuation(函数总是返回值给调用者),然后将程序转换成CPS代码。这种转换很容易被自动化(事实上,许多编译器就是这么做的)。

当我们将一个程序转换为CPS以后,每一个指令都会有continuation,一个当前函数执行后调用的函数,也就是通常的程序中的返回地址。让我从上面的代码中挑一个指令,比如add(5,10)。在CPS中,add的continuation是add调用完毕后接下来要执行的函数,但是在非CPS的程序中,continuation是什么呢?我们当然可以把它转换成CPS后来解释,但有这个必要吗?

其实没有必要。仔细看一下CPS转换过程。如果你试着去为它写一个编译器,并且好好思考如何去做的话,你会意识到CPS根本不需要栈!没有函数会像传统程序那样“返回”,它只是在执行完毕之后调用另一个函数。因此我们不用在每次调用函数时把参数都压到栈中,然后再在调用结束时把它们弹出来。我们只需要把它们存到内存块中,然后使用跳转指令。我们永远不需要原始的参数。他们不会被再次用到,因为没有函数会返回!

所以,用CPS风格写成的程序没有栈,但每个函数却有一个额外的参数来调用下一个函数。而不以CPS方式写的程序没有额外的参数,但是有栈。栈中包含了什么?一些参数和一个指向函数返回地址的内存指针。看到关系了么?栈中包含的就是continuation信息!栈中指向返回地址的指针本质上和CPS里将被调用的函数是等价的。如果你想知道add(5,10)的continuation是什么,那么你只需要检查它被执行时的栈即可。

这的确很简单。continuation和栈上指向返回地址的指针是等价的。continuation被显式传递,所以它不一定必须是函数原来被调用的地方。如果你还记得continuation就是一个函数,并且函数在我们的程序语言被编译成一个类的实例的话,你会更理解二者是一样的。这意味着给定程序中任意时间和任意位置,你都可以得到一个当前的continuation(current continuation),即当前栈的信息。

好的,这样我们就知道了什么是current continuation。有什么用呢?当我们将current continuation保存在某处时,实际上是把程序的当前状态速冻起来。这类似于操作系统进入休眠状态。一个continuation对象包含在我们获得它的地方重新启动程序的必要信息。操作系统做线程间的上下文切换时也是如此。唯一的区别是它仍然继续保持着控制权。如果你需要一个continuation对象(在Scheme中,可以调用call-with-current-continuation函数),你就会得到一个包含current continuation的对象,即栈或者是在CPS中下一个要调用的函数)。你可以将这个对象存到变量中(或者磁盘上)。当你用这个continuation对象“重启”程序的时候,就可以将程序“转换”到你取得这个对象时的那个状态。这和切换回一个被挂起的线程或者唤醒休眠着的操作系统是一回事,而且你可以一遍又一遍的这样做。当操作系统被唤醒时,休眠信息就被销毁了。但如果那些信息没有被销毁,那么你也可以从同一个点一次又一次的唤醒操作系统。这就像时间停止一样。使用continuation,你就有了这个控制力!

Continuation应该在什么情况下使用呢?一般是在我们希望在一个先天就无状态的应用中模拟状态的时候。这样可以简化任务。Continuation很适合在Web应用程序中使用。微软的ASP.NET花了很大的功夫来模拟状态,以便在开发Web应用时少费周折。如果C#支持continuation,ASP.NET就不那么复杂了——你只需要保存一个continuation,当用户再次发送web请求时,重新启动它就可以了。对于程序员来说,web应用程序将不再有中断——程序只是简单的从下一行开始执行就可以了!

对于一些问题来说,continuation是一个非常有用的抽象工具。想到很多传统复杂的客户端将走向网络,continuation在未来会变得越来越重要。

Leave a Reply

Your email address will not be published. Required fields are marked *