JavaScript中的持续传递风格 [每日前端夜话(0x1B)]

翻译：疯狂的技术宅
原文：http://matt.might.net/articles/by-example-continuation-passing-style/

持续传递风格( CPS)是起源于20世纪70年代的一种编程风格，它在20世纪80和90年代成为高级程序设计语言中的特色之一。

现在，CPS作为非阻塞式(通常是分布式的)系统的编程风格而被再次发掘出来。

我对CPS很有好感，因为它是我获取博士学位的一个秘密武器。它十有八九帮我消减掉了一两年的时间和一些难以估量的痛苦。

本文介绍了CPS所扮演的两种角色作为JavaScript中的一种非阻塞编程风格，以及作为一种功能性语言的中间形式(简要介绍)。

内容包括：

JavaScript中的CPS
CPS用于Ajax编程
用在非阻塞式编程(node.js)中的CPS
CPS用于分布式编程
如何使用CPS来实现异常
极简Lisp的一个CPS转换器
如何用Lisp实现call/cc
如何用JavaScript实现call/cc

什么是持续传递风格?

如果一种语言支持持续传递(continuation)的话，编程者就可以添加诸如异常、回溯、线程以及构造函数一类的控制构造。

可惜的是，许多关于持续的解释(我的也包括在内)给人的感觉是含糊不清，令人难以满意。

持续传递风格是那么的基础。

持续传递风格赋予了后续在代码方面的意义。

更妙的是，编程者可以自我发掘出持续传递风格来，如果其受限于下面这样的一个约束的话：

  没有任何过程可以返回给他的调用者。

一个提示使得这种风格的编程成为可能：

     过程可以在它们返回值时调用一个回调方法。

当一个过程(procedure)准备要返回到它的调用者中时，它在返回值时调用当前后续(current continuation)这一回调方法(由它的调用者提供)。

一个后续是一个初始类型(first-class)返回点。

例子：标识函数

考虑这个正常写法的标识函数：

然后是持续传递风格的：

有时候，把当前后续参数命名为ret会使得其目的更为明显一些：

例子：朴素阶乘

下面是标准的朴素阶乘：

下面是CPS风格实现的：

接下来，为了使用这一函数，我们把一个回调方法传给它：

例子：尾递归阶乘

下面是尾递归阶乘：

然后，是CPS实现：

CPS和Ajax

Ajax是一种web编程技术，其使用JavaScript中的一个XMLHttpRequest对象来从服务器端(异步地)提取数据。(提取的数据不必是XML格式的。)

CPS提供了一种优雅地实现Ajax编程的方式。

使用XMLHttpRequest，我们可以写出一个阻塞式的过程fetch(url)，该过程抓取某个url上的内容，然后把内容作为串返回。

这一方法的问题是，JavaScript是一种单线程语言，当JavaScript阻塞时，浏览器就被暂时冻结，不能动弹了。这会造成不愉快的用户体验。

一种更好的做法是这样的一个过程fetch(url, callback)，其允许执行(或是浏览器呈现工作)的继续，并且一旦请求完成就调用所提供的回调方法。

在这种做法中，部分CPS转换变成了一种自然的编码方式。
　　

实现fetch

实现fetch过程并不难，至于其以非阻塞模式或是阻塞模式操作则取决于编程者是否提供回调方法：

例子：提取数据

考虑一个程序，该程序需要从UID中抓取一个名字

下面的两种做法都要用到fetch：

CPS和非阻塞式编程

node.js是一个高性能的JavaScript服务器端平台，在该平台上阻塞式过程是不允许的。

巧妙的是，通常会阻塞的过程(比如网络或是文件I/O)利用了通过结果来调用的回调方法。

对程序做部分CPS转换促成了自然而然的node.js编程。

例子：简单的web服务器

node.js中的一个简单的web服务器把一个持续传递给文件读取过程。相比于非阻塞式IO的基于select的方法，CPS使非阻塞I/O变得更加的简单明了。

CPS用于分布式计算

CPS简化了把计算分解成本地部分和分布部分的做法。

假设你编写了一个组合的choose函数;开始是一种正常的方式：

现在，假设你想要在服务器端而不是本地计算阶乘。

你可以重新把fact写成阻塞的并等待服务器端的响应。

那样的做法很糟糕。

相反，假设你使用CPS来写choose的话：

现在，重新把fact定义成在服务器端的异步计算阶乘就是一件很简单的事情了。

(有趣的练习：修改node.js服务器端以让这一做法生效。)

使用CPS来实现异常

一旦程序以CPS风格实现，其就破坏了语言中的普通的异常机制。幸运的是，使用CPS来实现异常是一件很容易的事情。

异常是后续的一种特例。

通过把当前异常后续(current exceptional continuation)与当前后续一起做传递，你可以实现对try/catch代码块的脱糖处理。

考虑下面的例子，该例子使用异常来定义阶乘的一个完全版本：

通过使用CPS来添加异常后续，我们就可以对throw、try和catch做脱糖处理：

CPS用于编译

三十年以来，CPS已经成为了功能性编程语言的编译器的一种强大的中间表达形式。

CPS脱糖处理了函数的返回、异常和初始类型后续;函数调用变成了单条的跳转指令。

换句话说，CPS在编译方面做了许多繁重的提升工作。

把lambda演算转写成CPS

lambda演算是Lisp的一个缩影，只需足够的表达式(应用程序、匿名函数和变量引用)来使得其对于计算是通用的。

下面的Racket代码把这一语言转换成CPS：

对于感兴趣的读者来说，Olivier Danvy有许多关于编写有效的CPS转换器的文章。

使用Lisp实现call/cc

原语call-with-current-continuation(通常称作call/cc)是现代编程中最强大的控制流结构。

CPS使得call/cc的实现成为了小菜一碟;这是一种语法上的脱糖：

这一脱糖处理(与CPS转换相结合)是准确理解call/cc所做工作的最好方式。

其所实现的正是其名称所说明的：其使用一个已经捕捉了当前后续的过程来调用被作为参数指定的过程。

当捕捉了后续的过程被调用时，其把计算返回给计算创建点。

使用JavaScript实现call/cc

如果有人要把JavaScript中的代码转写成持续传递风格的话，call/cc有一个很简单的定义：