示例：JavaScript中的后續傳遞風格

作者：Elaine.Ye 2011-03-15 13:45:49

后續傳遞風格(continuation-passing style，CPS)最初在1970年代作為一種編程風格出現，在1980年代到1990年代期間，其作為高級編程語言的編譯器的一種中間表達形式開始嶄露頭角。本文介紹了CPS所扮演的兩種角色——作為JavaScript中的一種非阻塞編程風格，以及作為一種功能性語言的中間形式(簡要介紹)。

現在，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)返回點。

例子：標識函數

考慮這個正常寫法的標識函數：

function id(x) {    
         return x ;  
}

然后是后續傳遞風格的：

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

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

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

例子：樸素階乘

下面是標準的樸素階乘：

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

下面是CPS風格實現的：

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

接下來，為了“使用”這一函數，我們把一個回調方法傳給它：

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實現方式的：

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

實現fetch

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

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

例子：提取數據

考慮一個程序，該程序需要從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服務器端平臺，在該平臺上阻塞式過程是不允許的。

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

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

#p#

例子：簡單的web服務器

node.js中的一個簡單的web服務器把一個后續傳遞給文件讀取過程。相比于非阻塞式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/" ;  
   
// 使用一個處理程序回調來創建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,".") ;  
   
   // 讀入被請求的文件，并把它發送回去.  
   // 注：readFile用到了當前后續（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) ;  
   
    // 如果沒有找出內容類型的話,  
     // 就由客戶來猜測.  
       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] ; }  
   
// 啟動服務器，監聽端口8000:  
 httpd.listen(8000) ;

CPS用于分布式計算

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

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

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

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

你可以重新把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)) }) }) })  
  }

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

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

使用CPS來實現異常

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

異常是后續的一種特例。

通過把當前異常后續(current exceptional continuation)與當前后續一起做傳遞，你可以實現對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來添加異常后續，我們就可以對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已經成為了功能性編程語言的編譯器的一種強大的中間表達形式。

CPS脫糖處理了函數的返回、異常和初始類型后續;函數調用變成了單條的跳轉指令。

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

把lambda演算轉寫成CPS

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

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

下面的Racket代碼把這一語言轉換成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有許多關于編寫有效的CPS轉換器的文章。

使用Lisp實現call/cc

原語call-with-current-continuation(通常稱作call/cc)是現代編程中最強大的控制流結構。

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

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

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

其所實現的正是其名稱所說明的：其使用一個已經捕捉了當前后續的過程來調用被作為參數指定的過程。

當捕捉了后續的過程被調用時，其把計算“返回”給計算創建點。

使用JavaScript實現call/cc

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

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

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

【編輯推薦】

如何編寫高質量的JavaScript代碼
深入理解JavaScript的閉包特性
淺析JavaScript繼承方式
淺析JavaScript的寫類方式
JavaScript跨域總結與解決辦法

責任編輯：陳貽新來源：譯言網

JavaScript 后續傳遞