現(xiàn)在，CPS作為非阻塞式(通常是分布式的)系統(tǒng)的編程風格而被再次發(fā)掘出來。

我對CPS很有好感，因為它是我獲取博士學位的一個秘密武器。它十有八九幫我消減掉了一兩年的時間和一些難以估量的痛苦。

本文介紹了CPS所扮演的兩種角色——作為JavaScript中的一種非阻塞編程風格，以及作為一種功能性語言的中間形式(簡要介紹)。

內(nèi)容包括：

◆JavaScript中的CPS

◆CPS用于Ajax編程

◆用在非阻塞式編程(node.js)中的CPS

◆CPS用于分布式編程

◆如何使用CPS來實現(xiàn)異常

◆極簡Lisp的一個CPS轉(zhuǎn)換器

◆如何用Lisp實現(xiàn)call/cc

◆如何用JavaScript實現(xiàn)call/cc

請往下閱讀以了解更多內(nèi)容。

什么是持續(xù)傳送風格?

如果一種語言支持后續(xù)(continuation)的話，編程者就可以添加諸如異常、回溯、線程以及構(gòu)造函數(shù)一類的控制構(gòu)造。

可惜的是，許多關(guān)于后續(xù)的解釋(我的也包括在內(nèi))給人的感覺是含糊不清，令人難以滿意。

后續(xù)傳遞風格是那么的基礎。

后續(xù)傳遞風格賦予了后續(xù)在代碼方面的意義。

更妙的是，編程者可以自我發(fā)掘出后續(xù)傳遞風格來，如果其受限于下面這樣的一個約束的話：

沒有過程被允許返回到它的調(diào)用者中——永遠如此。

存在的一個啟示使得以這種風格編程成為可能：

過程可以在它們返回值時調(diào)用一個回調(diào)方法。

當一個過程(procedure)準備要“返回”到它的調(diào)用者中時，它在返回值時調(diào)用“當前后續(xù)(current continuation)”這一回調(diào)方法(由它的調(diào)用者提供)

一個后續(xù)是一個初始類型(first-class)返回點。

例子：標識函數(shù)

考慮這個正常寫法的標識函數(shù)：

function id(x) {    
         return x ;  
} 

然后是后續(xù)傳遞風格的：

function id(x,cc) {  
   cc(x) ;  
} 

有時候，把當前后續(xù)參數(shù)命名為ret會使得其目的更為明顯一些：

function id(x,ret) {  
   ret(x) ;  
} 

例子：樸素階乘

下面是標準的樸素階乘：

function fact(n) {  
   if (n == 0)  
     return 1 ;  
   else 
    return n * fact(n-1) ;  
} 

下面是CPS風格實現(xiàn)的：

function fact(n,ret) {  
   if (n == 0)  
     ret(1) ;  
   else 
    fact(n-1, function (t0) {  
      ret(n * t0) }) ;  
} 

接下來，為了“使用”這一函數(shù)，我們把一個回調(diào)方法傳給它：

fact (5, function (n) {  
    console.log(n) ; // 在Firebug中輸出120  
})   

例子：尾遞歸階乘

下面是尾遞歸階乘：

function fact(n) {  
   return tail_fact(n,1) ;  
}    
function tail_fact(n,a) {  
   if (n == 0)  
     return a ;  
   else 
     return tail_fact(n-1,n*a) ;  
} 

然后，是CPS實現(xiàn)方式的：

function fact(n,ret) {  
   tail_fact(n,1,ret) ;  
}     
function tail_fact(n,a,ret) {  
   if (n == 0)  
     ret(a) ;  
   else 
     tail_fact(n-1,n*a,ret) ;  
}    

CPS和Ajax

Ajax是一種web編程技術(shù)，其使用JavaScript中的一個XMLHttpRequest對象來從服務器端(異步地)提取數(shù)據(jù)。(提取的數(shù)據(jù)不必是XML格式的。)CPS提供了一種優(yōu)雅地實現(xiàn)Ajax編程的方式。使用XMLHttpRequest，我們可以寫出一個阻塞式的過程fetch(url)，該過程抓取某個url上的內(nèi)容，然后把內(nèi)容作為串返回。這一方法的問題是，JavaScript是一種單線程語言，當JavaScript阻塞時，瀏覽器就被暫時凍結(jié)，不能動彈了。這會造成不愉快的用戶體驗。一種更好的做法是這樣的一個過程fetch(url, callback)，其允許執(zhí)行(或是瀏覽器呈現(xiàn)工作)的繼續(xù)，并且一旦請求完成就調(diào)用所提供的回調(diào)方法。在這種做法中，部分CPS轉(zhuǎn)換變成了一種自然的編碼方式。

實現(xiàn)fetch

實現(xiàn)fetch過程并不難，至于其以非阻塞模式或是阻塞模式操作則取決于編程者是否提供回調(diào)方法：

/*  
 對于客戶端—>服務器端的請求來說，  
 fetch是一個可選阻塞的過程。  
   
 只有在給出url的情況下，過程才會阻塞并返回該url上的內(nèi)容。  
   
 如果提供了onSuccess回調(diào)方法，  
 則過程是非阻塞的，并使用文件的  
 內(nèi)容來調(diào)用回調(diào)方法。  
   
 如果onFail回調(diào)方法也提供了的話，  
 則過程在失敗事件出現(xiàn)時調(diào)用onFail。  
   
*/ 
   
function fetch (url, onSuccess, onFail) {  
     // 只有在定義回調(diào)方法的情況下才是異步的  
    var async = onSuccess ? true : false ;   // （別抱怨此行代碼的效率低下，    
                                                                                  
   // 否則你就是不明白關(guān)鍵所在。)  
     var req ; // XMLHttpRequest對象.  
   
// XMLHttpRequest的回調(diào)方法:  
   function processReqChange() {  
     if (req.readyState == 4) {  
       if (req.status == 200) {  
         if (onSuccess)  
            onSuccess(req.responseText, url, req) ;  
        } else {  
         if (onFail)  
            onFail(url, req) ;  
       }  
     }  
   }  
   
// 創(chuàng)建XMLHttpRequest對象:  
   if (window.XMLHttpRequest)  
      req = new XMLHttpRequest();  
   else if (window.ActiveXObject)  
      req = new ActiveXObject("Microsoft.XMLHTTP");  
   
// 如果是異步的話，設定回調(diào)方法:  
   if (async)  
      req.onreadystatechange = processReqChange;  
   
// 發(fā)起請求:  
   req.open("GET", url, async);  
   req.send(null);  
   
// 如果是異步的話,  
// 返回請求對象，否則  
//  返回響應.  
   if (async)  
      return req ;  
   else 
    return req.responseText ;  
} 

例子：提取數(shù)據(jù)

考慮一個程序，該程序需要從UID中抓取一個名字

下面的兩種做法都要用到fetch：

// 阻塞直到請求完成:  
 var someName = fetch("./1031/name") ;  
   
 document.write ("someName: " + someName + "  
") ; 

//不做阻塞的:  
 fetch("./1030/name", function (name) {  
  document.getElementById("name").innerHTML = name ;  
 }) ;  
  

CPS和非阻塞式編程

node.js是一個高性能的JavaScript服務器端平臺，在該平臺上阻塞式過程是不允許的。

巧妙的是，通常會阻塞的過程(比如網(wǎng)絡或是文件I/O)利用了通過結(jié)果來調(diào)用的回調(diào)方法。

對程序做部分CPS轉(zhuǎn)換促成了自然而然的node.js編程。

#p#

例子：簡單的web服務器

node.js中的一個簡單的web服務器把一個后續(xù)傳遞給文件讀取過程。相比于非阻塞式IO的基于select的方法，CPS使非阻塞I/O變得更加的簡單明了。

var sys = require('sys') ;  
var http = require('http') ;  
var url = require('url') ;  
var fs = require('fs') ;  
   
// Web服務器的根目錄:  
 var DocRoot = "./www/" ;  
   
// 使用一個處理程序回調(diào)來創(chuàng)建web服務器:  
 var httpd = http.createServer(function (req, res) {  
   sys.puts(" request: " + req.url) ;  
          
         // 解析url:  
   var u = url.parse(req.url,true) ;  
   var path = u.pathname.split("/") ;  
   
         // 去掉路徑中的..:  
   var localPath = u.pathname ;  
   //  "  
/.." => ""  
   var localPath =  
        localPath.replace(/[^/]+\/+[.][.]/g,"") ;  
   //  ".." => "."  
   var localPath = DocRoot +  
                     localPath.replace(/[.][.]/g,".") ;  
   
   // 讀入被請求的文件，并把它發(fā)送回去.  
   // 注：readFile用到了當前后續(xù)（current continuation）:  
   fs.readFile(localPath, function (err,data) {  
     var headers = {} ;  
   
     if (err) {  
       headers["Content-Type"] = "text/plain" ;  
       res.writeHead(404, headers);  
       res.write("404 File Not Found\n") ;  
       res.end() ;  
     } else {  
       var mimetype = MIMEType(u.pathname) ;  
   
    // 如果沒有找出內(nèi)容類型的話,  
     // 就由客戶來猜測.  
       if (mimetype)  
         headers["Content-Type"] = mimetype ;  
         res.writeHead(200, headers) ;  
        
            res.write(data) ;  
       res.end() ;  
        }  
    }) ;  
 }) ;  
   
// 映射后綴名和MIME類型:  
 var MIMETypes = {  
  "html" : "text/html" ,  
  "js"   : "text/javascript" ,  
  "css"  : "text/css" ,  
  "txt"  : "text/plain" 
} ;  
   
function MIMEType(filename) {  
  var parsed = filename.match(/[.](.*)$/) ;  
  if (!parsed)  
    return false ;  
  var ext = parsed[1] ;  
  return MIMEType[ext] ; }  
   
// 啟動服務器，監(jiān)聽端口8000:  
 httpd.listen(8000) ; 

CPS用于分布式計算

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

假設你編寫了一個組合的choose函數(shù);開始是一種正常的方式：

function choose (n,k) {  
 return       fact(n) /  
          (fact(k) * fact(n-k)) ;  
 } 

現(xiàn)在，假設你想要在服務器端而不是本地計算階乘。

你可以重新把fact寫成阻塞的并等待服務器端的響應。

那樣的做法很糟糕。

相反，假設你使用CPS來寫choose的話：

function choose(n,k,ret) {  
   fact (n,   function (factn) {  
   fact (n-k, function (factnk) {  
   fact (k,   function (factk) {  
   ret  (factn / (factnk * factk)) }) }) })  
  } 

現(xiàn)在，重新把fact定義成在服務器端的異步計算階乘就是一件很簡單的事情了。

(有趣的練習：修改node.js服務器端以讓這一做法生效。)

使用CPS來實現(xiàn)異常

一旦程序以CPS風格實現(xiàn)，其就破壞了語言中的普通的異常機制。 幸運的是，使用CPS來實現(xiàn)異常是一件很容易的事情。

異常是后續(xù)的一種特例。

通過把當前異常后續(xù)(current exceptional continuation)與當前后續(xù)一起做傳遞，你可以實現(xiàn)對try/catch代碼塊的脫糖處理。

考慮下面的例子，該例子使用異常來定義階乘的一個“完全”版本：

function fact (n) {  
   if (n < 0)  
     throw "n < 0" ;  
   else if (n == 0)  
     return 1 ;  
   else 
     return n * fact(n-1) ; }  
   
function total_fact (n) {  
   try {  
     return fact(n) ;  
   } catch (ex) {  
     return false ;    
   }  
}  
   
document.write("total_fact(10): " + total_fact(10)) ;  
document.write("total_fact(-1): " + total_fact(-1)) ; 

通過使用CPS來添加異常后續(xù)，我們就可以對throw、try和catch做脫糖處理：

function fact (n,ret,thro) {  
  if (n < 0)  
    thro("n < 0")  
   else if (n == 0)  
    ret(1)  
  else 
    fact(n-1,  
         function (t0) {  
           ret(n*t0) ;  
         },  
         thro)  
 }  
   
function total_fact (n,ret) {  
   fact (n,ret,  
     function (ex) {  
       ret(false) ;  
     }) ;  
 }  
   
total_fact(10, function (res) {  
   document.write("total_fact(10): " + res)  
}) ;  
   
total_fact(-1, function (res) {  
   document.write("total_fact(-1): " + res)  
}) ; 

CPS用于編譯

三十年以來，CPS已經(jīng)成為了功能性編程語言的編譯器的一種強大的中間表達形式。

CPS脫糖處理了函數(shù)的返回、異常和初始類型后續(xù);函數(shù)調(diào)用變成了單條的跳轉(zhuǎn)指令。

換句話說，CPS在編譯方面做了許多繁重的提升工作。

把lambda演算轉(zhuǎn)寫成CPS

lambda演算是Lisp的一個縮影，只需足夠的表達式(應用程序、匿名函數(shù)和變量引用)來使得其對于計算是通用的。

exp ::= (exp exp)           ; 函數(shù)應用  
      |  (lambda (var) exp)  ; 匿名函數(shù)  
      |  var              ; 變量引用 

下面的Racket代碼把這一語言轉(zhuǎn)換成CPS：

(define (cps-convert term cont)  
  (match term  
    [`(,f ,e)  
     ; =>  
     (let (($f (gensym 'f))  
           ($e (gensym 'e)))  
       (cps-convert f `(lambda (,$f)  
         ,(cps-convert e `(lambda (,$e)  
             (,$f ,$e ,cont))))))]  
     
    [`(lambda (,v) ,e)  
     ; =>  
     (let (($k (gensym 'k)))  
       `(,cont (lambda (,v ,$k)  
                 ,(cps-convert e $k))))]  
     
    [(? symbol?)  
     ; =>  
     `(,cont ,term)]))  
   
(define (cps-convert-program term)  
  (cps-convert term '(lambda (ans) ans))) 

對于感興趣的讀者來說，Olivier Danvy有許多關(guān)于編寫有效的CPS轉(zhuǎn)換器的文章。

使用Lisp實現(xiàn)call/cc

原語call-with-current-continuation(通常稱作call/cc)是現(xiàn)代編程中最強大的控制流結(jié)構(gòu)。

CPS使得call/cc的實現(xiàn)成為了小菜一碟;這是一種語法上的脫糖：

call/cc => (lambda (f cc) (f (lambda (x k) (cc x)) cc)) 

這一脫糖處理(與CPS轉(zhuǎn)換相結(jié)合)是準確理解call/cc所做工作的最好方式。

其所實現(xiàn)的正是其名稱所說明的：其使用一個已經(jīng)捕捉了當前后續(xù)的過程來調(diào)用被作為參數(shù)指定的過程。

當捕捉了后續(xù)的過程被調(diào)用時，其把計算“返回”給計算創(chuàng)建點。

使用JavaScript實現(xiàn)call/cc

如果有人要把JavaScript中的代碼轉(zhuǎn)寫成后續(xù)傳遞風格的話，call/cc有一個很簡單的定義：
 

function callcc (f,cc) {  
  f(function(x,k) { cc(x) },cc)  
} 

原文鏈接：http://article.yeeyan.org/view/213582/179432

【編輯推薦】

1. 如何編寫高質(zhì)量的JavaScript代碼
2. 深入理解JavaScript的閉包特性
3. 淺析JavaScript繼承方式
4. 淺析JavaScript的寫類方式
5. JavaScript跨域總結(jié)與解決辦法