Continuation-Passing Style

Continuation-Passing Style, aka CPS, is a paradigm for expressing programs in terms of primitives that explicitly build, pass around and invoke continuations.

In CPS, all the "function calls" are actually jumps to continuations that never return (so you asymptotically better not waste stack space with them). You can macro-express "normal" function calls into CPS by having the caller jump to the subroutine while giving to it an explicit continuation as an extra argument, and returning for the callee will consist in jumping to that continuation with the return value as argument. That continuation itself refers to the caller's continuation argument, and thus recursively reifies the whole call chain; at each element of the chain, it also includes the bit of work that has to be done to finish the current function before to return. In other words, the system call stack can be viewed as a continuation, and each return addresses (together with the code it points to) can be seen as the static "bit of work remaining to be done" part of a continuation.

CPS is notably used to build compiler representations or to extend a language with reifiable continuations. These continuations can then be used to express synchronous remote procedure call in an asynchronous distributed or concurrent system, non-deterministic computations, persistent computations, seamless web interface (see Paul Graham paper below), GUIs (see Matthew Fuchs paper below), etc.

Note that CPS builds the sequencing of computations into the representation, so it is rather low-level with respect to pure high-level computations that you'd like to parallelize. On the other hand, this low level of abstraction makes CPS well suited to producing assembly code: indeed, machine code instructions can be viewed as CPS combinators. A particular Scheme compiler using CPS and targetting C is chicken.

See also FOO-passing Style?, Monads, etc.

This page is linked from: CPS   Microkernel Debate   Screamer   UnCommon Web