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

我對(duì)CPS很有好感，因?yàn)樗俏耀@取博士學(xué)位的一個(gè)秘密武器。它十有八九幫我消減掉了一兩年的時(shí)間和一些難以估量的痛苦。

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

內(nèi)容包括：

◆JavaScript中的CPS

◆CPS用于Ajax編程

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

◆CPS用于分布式編程

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

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

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

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

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

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

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

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

后續(xù)傳遞風(fēng)格是那么的基礎(chǔ)。

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

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

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

存在的一個(gè)啟示使得以這種風(fēng)格編程成為可能：

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

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

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

例子：標(biāo)識(shí)函數(shù)

考慮這個(gè)正常寫法的標(biāo)識(shí)函數(shù)：

function id(x) {    
         return x ;  
} 

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

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

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

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

例子：樸素階乘

下面是標(biāo)準(zhǔn)的樸素階乘：

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

下面是CPS風(fēng)格實(shí)現(xiàn)的：

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

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

實(shí)現(xiàn)fetch

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

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

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

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

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

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

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

CPS和非阻塞式編程

node.js是一個(gè)高性能的JavaScript服務(wù)器端平臺(tái)，在該平臺(tái)上阻塞式過程是不允許的。

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

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

#p#

例子：簡單的web服務(wù)器

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

var sys = require('sys') ;  
var http = require('http') ;  
var url = require('url') ;  
var fs = require('fs') ;  
   
// Web服務(wù)器的根目錄:  
 var DocRoot = "./www/" ;  
   
// 使用一個(gè)處理程序回調(diào)來創(chuàng)建web服務(wù)器:  
 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,".") ;  
   
   // 讀入被請(qǐng)求的文件，并把它發(fā)送回去.  
   // 注：readFile用到了當(dāng)前后續(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)容類型的話,  
     // 就由客戶來猜測(cè).  
       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] ; }  
   
// 啟動(dòng)服務(wù)器，監(jiān)聽端口8000:  
 httpd.listen(8000) ; 

CPS用于分布式計(jì)算

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

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

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

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

你可以重新把fact寫成阻塞的并等待服務(wù)器端的響應(yīng)。

那樣的做法很糟糕。

相反，假設(shè)你使用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定義成在服務(wù)器端的異步計(jì)算階乘就是一件很簡單的事情了。

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

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

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

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

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

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

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ù)，我們就可以對(duì)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)成為了功能性編程語言的編譯器的一種強(qiáng)大的中間表達(dá)形式。

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

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

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

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

exp ::= (exp exp)           ; 函數(shù)應(yīng)用  
      |  (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))) 

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

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

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

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

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

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

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

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

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

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

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é)與解決辦法