Continuation Passing Style in JS
By example: Continuation-passing style in JavaScript


 

 

  Continuation-passing style (CPS) originated as a style of programming in
the 1970s, and it rose to prominence as an intermediate representation for
compilers of advanced programming languages in the 1980s and 1990s.  

 It's now being rediscovered as a style of programming for
non-blocking (usually distributed) systems.  

 There's a warm spot in my heart for CPS, because it was the secret weapon
in my Ph.D. 

It probably shaved off a couple years and immeasurable agony.



 This article introduces CPS in both of its roles--as a style for
non-blocking programming in JavaScript, and (briefly) as an intermediate form
for a functional language.  


Topics covered:



 CPS in JavaScript
 CPS for Ajax programming
 CPS for non-blocking programming (in node.js)
 CPS for distributed programming
 How to implement exceptions using CPS
 A CPS converter for a minimal Lisp
 How to implement call/cc in Lisp
 How to implement call/cc in JavaScript



Read on for more.




  


  


What is continuation-passing style?

 If a language supports continuations, the programmer can add control
constructs like exceptions, backtracking, threads and generators. 

 Sadly, many explanations of continuations 
 (mine
included) feel vague and unsatisfying. 

Such power deserves a solid pedagogical foundation.



Continuation-passing style is that foundation.


 Continuation-passing style gives continuations meaning in terms of code.



 Even better, a programmer can discover continuation-passing style 
by themselves if subjected to one constraint: 


 No procedure is allowed to return to its caller--ever.



One hint makes programming in this style possible:



 Procedures can take a callback to invoke upon their return value.


 When a procedure is ready to "return" to its caller, it invokes the
"current continuation" callback (provided by its caller) on the return value.




A continuation is a first-class return point. 





Example: Identity function


Consider the identity function written normally:


function id(x) {
  return x ;
}



and then in continuation-passing style:


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



Sometimes, calling the current continuation argument ret makes its purpose more obvious:


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




Example: Naive factorial


Here's the standard naive factorial:


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



Here it is in CPS:


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




And, to "use" the function, we pass it a callback:


fact (5, function (n) { 
  console.log(n) ; // Prints 120 in Firebug.
})




Example: Tail-recursive factorial


Here's tail-recursive factorial:


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) ;
}




And, in 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 and Ajax

 Ajax is a web programming technique which uses an
XMLHttpRequest object in JavaScript to fetch data
(asynchronously) from a server.  


(That data need not be XML.)




CPS provides an elegant way to do Ajax programming.


 With XMLHttpRequest, we could write a blocking procedure
fetch(url) that grabs the contents of a url as a string, and then returns it.

 The problem with this approach is that JavaScript is a single-threaded
language, and when JavaScript blocks, the browser is momentarily frozen.



It makes for an unpleasant user experience.


 A better approach is a procedure
fetch(url,callback) which allows execution (or
browser rendering) to continue, and calls the provided callback once the
request is completed.  



In this approach, partial CPS-conversion becomes a natural way to code.


Implementing fetch

 It's not hard to implement fetch so that it operates in non-blocking mode
or blocking mode, depending on whether the programmer supplied a callback: 

/*
 fetch is an optionally-blocking 
 procedure for client->server requests.

 If only a url is given, the procedure 
 blocks and returns the contents of the url.

 If an onSuccess callback is provided, 
 the procedure is non-blocking, and the
 callback is invoked with the contents 
 of the file.

 If an onFail callback is also provided, 
 the procedure calls onFail in the event of 
 a failure.

*/

function fetch (url, onSuccess, onFail) {

  // Async only if a callback is defined: 
  var async = onSuccess ? true : false ;
  // (Don't complain about the inefficiency
  //  of this line; you're missing the point.)

  var req ; // XMLHttpRequest object.

  // The XMLHttpRequest callback:
  function processReqChange() {
    if (req.readyState == 4) {
      if (req.status == 200) {
        if (onSuccess) 
          onSuccess(req.responseText, url, req) ; 
      } else {
        if (onFail) 
          onFail(url, req) ;
      }
    }
  }

  // Create the XMLHttpRequest object:
  if (window.XMLHttpRequest) 
    req = new XMLHttpRequest();
  else if (window.ActiveXObject) 
    req = new ActiveXObject("Microsoft.XMLHTTP");

  // If asynchronous, set the callback:
  if (async) 
    req.onreadystatechange = processReqChange;

  // Fire off the request:
  req.open("GET", url, async);
  req.send(null);

  // If asynchronous,
  //  return request object; or else
  //  return the response.
  if (async) 
    return req ;
  else
    return req.responseText ;
} 




Example: Fetching data


Consider a program that needs to grab a name for a UID.



Using fetch, both of the following work:


// Blocks until request in finished:
var someName = fetch("./1031/name") ;

document.write ("someName: " + someName + "") ;

// Does not block:
fetch("./1030/name", function (name) {
 document.getElementById("name").innerHTML = name ;
}) ;


(See the example.)


CPS and non-blocking programming

 node.js is a high-performance, server-side
platform for JavaScript in which blocking procedures are banned.  

 Cleverly, procedures which ordinarily would block (e.g. network or file
I/O) take a callback that to be invoked with the result.  

 Partially CPS-converting a program makes for natural node.js 
programming.


Example: Simple web server


A simple web server in node.js passes a continuation to the file-reading procedure.

Compared to the select-based approach to non-blocking IO, CPS
makes non-blocking I/O straightforward.  

var sys = require('sys') ;
var http = require('http') ;
var url = require('url') ;
var fs = require('fs') ;

// Web server root:
var DocRoot = "./www/" ;

// Create the web server with a handler callback:
var httpd = http.createServer(function (req, res) {
  sys.puts(" request: " + req.url) ;

  // Parse the url:
  var u = url.parse(req.url,true) ;
  var path = u.pathname.split("/") ;

  // Strip out .. in the path:
  var localPath = u.pathname ;
  //  "<dir>/.." => ""
  var localPath = 
      localPath.replace(/[^/]+\/+[.][.]/g,"") ;
  //  ".." => "."
  var localPath = DocRoot +  
                  localPath.replace(/[.][.]/g,".") ;

  sys.puts(" local path: " + localPath) ;
  
  // Read in the requested file, and send it back.
  // Note: readFile takes the 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 we can't find a content type, 
      // let the client guess.
      if (mimetype)
        headers["Content-Type"] = mimetype ;

      res.writeHead(200, headers) ;
      res.write(data) ;
      res.end() ;   
    }
   }) ;
}) ;

// Map extensions to MIME Types:
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 MIMETypes[ext] ;
}

// Start the server, listening to port 8000:
httpd.listen(8000) ;




CPS for distributed computation

 CPS eases factoring a computation into local and
distributed portions.  

 Suppose you wrote the combinatorial choose function; first normally: 

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



Now, suppose you want to compute factorial on a server, instead of locally.


 You could rewrite fact to block and wait
for the server to respond.  


That's bad.



Instead, assume you wrote choose in CPS:


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



Now, it's straightforward to redefine fact
to asynchronously compute factorial on the server:


function fact(n,ret) {
 fetch ("./fact/" + n, function (res) {
   ret(eval(res))
 }) ;
}



(Fun exercise: modify the node.js server so that this works.)




Implementing exceptions in CPS


Once a program is in CPS, it breaks the standard exception mechanisms in the language.

Fortunately, it's easy to implement exceptions in CPS.



An exception is a special case of a continuation.



 By passing the current exceptional continuation alongside the current
continuation, one can desugar try/catch blocks. 


 Consider the following example, which uses exceptions to define a "total"
version of factorial: 

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)) ;



 By adding an exceptional continuation in CPS, we can desugar the
throw, try and 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 for compilation

 For three decades, CPS has been a powerful intermediate representation for
compilers of functional programming languages.  


 CPS desugars function return, exceptions and first-class
continuations; function call turns into a single jump instruction. 



In other words, CPS does a lot of the heavy lifting in compilation.



Translating the lambda calculus to CPS

 The lambda calculus is a miniature Lisp, with just enough expressions
(applications, anonymous functions and variable references) to make it
universal for computation:  

 exp ::= (exp exp)           ; function application
      |  (lambda (var) exp)  ; anonymous function
      |  var                 ; variable reference


 The following Racket code converts this language into
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)))




For those interested, 
Olivier Danvy has plenty of papers on writing efficient CPS converters.



Implementing call/cc in Lisp

 The primitive call-with-current-continuation (commonly called
call/cc) is the most powerful control-flow construct in
modern programming.  



CPS makes implementing call/cc trivial;
it's a syntactic desugaring:


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


 This desugaring (in conjunction with the CPS transformation) is
the best way to understand exactly what call/cc does.


 It does exactly what it's name says it will: it calls the procedure
given as an argument with a procedure that has captured the current
continuation.


 When that procedure capturing the continuation gets invoked, it "returns"
the computation to the point at which the computation was created.  



Implementing call/cc in JavaScript

 If one were to translate to continuation-passing style in JavaScript,
call/cc has a simple definition: 

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





More resources





  

 

 


  
