有没有人能详细讲解一下cps

freearth

下面是“函数式编程另类指南”一文中的一节，我觉得它讲的CPS浅显易懂：

Continuations

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 来重写这段代码，就会有一个依赖，编译器会因此而强制对这两行代码有序执行！

System.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 风格。这种转换很容易被自动化（事实上，许多编译器就是这么做的）。

一旦我们将一个程序转为了CPS，那么很明显每个指令都将有些 continuation, 这是一个该指令在执行结束时会用其执行结果调用的函数，通常的程序中，这是一个它要返回的地址。从上面的例子中随便举个例子，比如 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)（它就是当前的栈的信息）。

好的，这样我们就知道了什么是 current 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 也会变得越来越重要。

[ 本帖最后由 freearth 于 2009-4-30 09:52 编辑 ]