By example: Continuation-passing style in JavaScript

[article index] [] [@mattmight] [+mattmight] [rss]

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


[article index] [] [@mattmight] [+mattmight] [rss]