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(
that grabs the contents of a url as a string, and then returns it.url)
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(
which allows execution (or browser rendering) to continue, and calls the provided callback once the request is completed. url,callback)
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 + “(See the example.)
”) ; // Does not block: fetch(”./1030/name”, function (name) { document.getElementById(“name”).innerHTML = name ; }) ;
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 ; // ”
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::= (expexp) ; 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 (,e) (,e ,cont))))))] [(lambda (,v) ,e) ; => (let (($k (gensym 'k))) (,cont (lambda (,v ,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.