• 函数式编程与Continuation/CPS

    Continuation是什么?
    服务器君一共花费 28.302 ms 进行了 4 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

    Continuations 对于程序设计的意义,就像达芬奇密码对人类历史的意义:即对人类最大秘密的惊人揭示。也许不是,但他在概念上的突破性至少和负数平方根的意义等同。

    我们在学习函数时只了解了一半事实,因为我们基于一个错误的假定:函数只能将结果返回到它的调用端。从这个意义上说 continuation 是广义的函数,函数不必返回到其调用端而可以返回到程序的任何地方。我们把 “continuation” 作为参数传给一个函数,它指定了这个函数返回的位置。这个描述可能听起来挺复杂,看看下面的代码:

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

    函数 add 在其被调用的位置将结果 15 赋给了 i,接下来 i 的值被用来调用 square。注意所有的惰性求值编译器都不能调整这几行代码因为第二行依赖着第一行的成功求值。下面用 continuation 风格又称 CPS(Continuation Programming Style)来重写这段代码,这里函数 add 会将结果返回到 square 而不是原来的调用函数。

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

    这个例子中 add 有了另一个参数——一个 add 必须在它求值结束时用其返回值调用的函数。这里 square 是 add 的一个 continuation。这两种情况下,j 都将等于 255。

    这就是强制使惰性语言有序地求值两个表达式的第一个技巧。考虑下面这个(熟悉的)IO 代码:

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

    这两行不相依赖所以编译器会自由的重新调整他们的执行顺序。然而,如果我们用 CPS 来重写这段代码,就会有一个依赖,编译器会因此而强制对这两行代码有序执行。

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

    这里(我们假定改造过的) println 需要用自己的返回结果作为参数去调用 readLine 并将 readLine 返回值作为自己的返回值。这样就能确保这两行被有序执行而且 readLine 一定被执行(因为整个计算期望最后的结果为结果)。Java 的 println 返回 void 但如果它返回的是一个抽象值(readLine 所期待的),我们就解决了这个问题。这样串接的函数调用很快会让代码难以读懂,不过这可以避免,比如我们可以给语言添加些语法糖(syntactic sugar)将其变成按正常顺序输入的表达式,然后由编译器自动为我们串接这些函数调用。这样就可以如愿地强制求值顺序并保留一切函数式编程的好处(包括数学地对我们程序进行推理的能力)。如果还是不明白,试着把函数看作只有一个成员的类的实例,重写上述代码使得 println 和 readLine 成为类的实例,就比较容易清楚了。

    如果我在此结束本节,那将仅仅涉及到 continuation 最浅显的应用,我们可以用 CPS 重写整个程序,所有的函数都增加一个额外的 continuation 参数并把函数结果传给它;也可以用另一种方法来重写:简单地把函数当作 continuation 的总是返回到调用端的特例。这种转换很容易自动化(事实上,许多编译器就是这么做的)。

    一旦我们将一个程序转为了 CPS,那么很明显每个指令都将有些 continuation, 这是一个该指令在执行结束时会用其执行结果调用的函数(在通常的非 CPS 程序中,就是跳转到调用端的指令)。从上面随便选个例子,比如 add(5, 10),在用 CPS 风格写的程序里,add 的 continuation 是一个 add 执行结束时会调用的函数,那么在非 CPS 的程序里它是什么呢?我们可以把程序转为 CPS,但有必要这么做吗?

    其实没有必要。仔细看一下我们的 CPS 转换过程,如果尝试为它写一个编译器,那么经过长久思考后,你会意识到这个 CPS 的版本根本不需要栈!没有函数会以传统的意义“返回”,它只是用结果调用了另一个函数。我们无需在调用时将函数参数压栈再于调用结束时弹出栈,而只是简单的把他们保存在一大块内存中,然后使用跳转指令。不再需要原来的参数——他们不会再次被用到,因为没有函数会返回。

    所以,用 CPS 风格写成的程序没有堆栈,但每个函数却有一个额外的参数可被调用;非 CPS 风格的程序没有可以被调用的这个参数,但却有栈;栈中存放着什么?只是参数和一个指向函数返回地址的指针。你看出端倪了吗?栈中只是放着 continuation 的信息! 栈中指向返回指令的指针本质上和 CPS 程序里将被调用的函数是等价的。如果你想探究 add(5,10) 的 continuation,只要简单地检查它在堆栈的执行点!

    所以,continuation 和栈上指向返回地址的指针是等价的,只是 continuation 被显式传递,所以不必和函数被调用点是同一位置。如果还记得 continuation 就是一个函数,并且在我们的语言里,函数被编译为一个类的实例,你就会理解指向栈中返回指令的指针实际就是 continuation。因为我们的函数(就像一个类的实例)只是一个指针,这意味着给定程序中任意时间和任意位置,你都可以去请求一个“当前 continuation”(current continuation,它就是当前的栈的信息)。

    这样我们就知道了什么是“当前 continuation”。它有什么意义?一旦我们得到了当前的 continuation 并将它保存在某处,我们就最终将程序当前的状态保存了下来——及时地冷冻下来。这就像操作系统进入休眠状态。一个 continuation 对象里保存了从我们获得它的地方重新启动程序的必要信息。操作系统在每次发生线程间的上下文切换时也是如此。唯一的区别是它保留着全部控制。请求一个 continuation 对象(在 Scheme 里,可以调用 call-with-current-continuation 函数)后,你就会获得一个包括了当前 continuation 的对象,也就是堆栈信息(在 CPS 程序里就是下一个要调用的函数),可以把这个对象保存在一个变量(或者是磁盘)里。当你用这个 continuation “重启”程序时,就会转回到你取得这个对象的那个状态,这就象切换回一个被挂起的线程或唤醒休眠的操作系统,区别是用 continuation,你可以多次地重复这一过程,而当操作系统被唤醒时,休眠信息就被销毁了,如果那些信息没有被销毁,你也就可以一次次地将它唤醒到同一点,就象重返过去一样。有了 continuation 你就有了这个控制力!

    Continuation 应该在什么情况下使用呢?通常在尝试模拟一个本质上是无状态的应用时可以简化你的任务。Continuation 很适合在 Web 应用程序中使用。微软公司的 ASP.NET 技术极尽苦心地模拟状态以便你在开发 Web 应用时少费周折,可如果 C# 支持了 continuation,ASP.NET 的复杂度就可以减半,你只需要保存一个 continuation,当用户下次发出 Web 请求时重启它即可。对程序员来说,web 应用程序将不再有中断,程序只是简单的从下一行重启!利用 continuation 这一抽象解决问题真是令人难以置信的便利,考虑到越来越多的胖客户端应用程序正在向服务器端转移,将来 continuation 也会变得越来越重要。

更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [Python程序设计] 标准库:urllib/urllib2 14 个条目
  2. [PHP程序设计] httpd.conf设置相关 3 个条目
  3. [移动开发] Android View注入框架Butter Knife 3 个条目
  4. [智力开发与知识管理] 整体性学习步骤 9 个条目
  5. [数据库技术] 数据库范式篇 5 个条目
  6. [PHP程序设计] PHP数组的遍历 7 个条目
  7. [软件工程与项目管理] 浏览器与CSS渲染技巧 2 个条目
  8. [C语言程序设计] 结构体基本知识 1 个条目
  9. [PHP程序设计] PHP数组探索 4 个条目
  10. [PHP程序设计] 对输入文件类型的检测 1 个条目
  11. [移动开发] Android里的ContentValues 2 个条目
  12. [Python程序设计] Django数据库模型 6 个条目
窗口 -- [资讯]