By example: Continuation-passing style in JavaScript

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

• JavaScript: The Definitive Guide, the best book on JavaScript.
• JavaScript: The Good Parts, the only other good JavaScript book.
• Andrew Appel's timeless classic Compiling with Continuations.
• The Lambda Papers.
• My post on programming with continuations by example.
• Jay McCarthy et al.'s papers on a continuation-based web-server.

---