Continuation Passing Style

Continuation-passing style, or CPS more shortly, is a style of programming sometimes employed in FunctionalProgramming languages. Its idea is, instead of having a function return a value, let a function take as an argument another function (the continuation, see ContinuationExplanation) to which the result is given as an argument. The following code (in Caml) illustrates the difference: 

 let myfunc x = dosomethingwith x
 let myfunc_CPS x cont = cont (dosomethingwith x)
[Or, equivalently in Scheme,] 

  (define myfunc (lambda (x) (do-something-with x)))
  (define myfunc_CPS (lambda (x k) (k (do-something-with x))))
Obviously, CPS quickly fills the stack or has to be given hand-coded infrastructure in languages that don't support the automatic merging of unneeded stack frames (see TailCallOptimization). In languages that have both FirstClassFunctions and TailCallOptimization and are thus well suited for CPS, the style permits to code some tasks very elegantly. For example, if you (god forbid) have a routine that might return an integer or a string, it is often better to use CPS with two alternative continuations rather than a variant return value or a return type tag: 

 let gives_int_or_str x y z cont_int cont_str = ...
    if .... then cont_int someintvalue
            else cont_str somestrvalue
[Or in Scheme:] 

  (define gives-int-or-str (lambda (x y z cont_int cont_str)
      (if ... (cont_int someintvalue) (cont_str somestrvalue))))
Or if you want to return multiple values, you can use CPS instead of tuple / list: 

 (* tuple version and usage in ML *)
 let divmod x y = (x / y, x mod y)
 let (quot, rem) = divmod 235 7 in ...


 (* CPS version and usage in ML *)
 let divmod x y cont = cont (x / y) (x mod y)
 divmod 235 7 (fun quot rem -> ... )
Or in Scheme: 

 ; tuple version and usage in Scheme
 (define divmod (lambda (x y) (list (quotient x y) (remainder x y))))
 (define use-divmod (let* ((tuple (divmod 235 7)) (quot (car tuple)) (rem (cadr tuple))) ...))


 ; CPS version and usage in Scheme
 (define divmod (lambda (x y k) (k (quotient x y) (remainder x y))))
 (define use-divmod (divmod 235 7 (lambda (quot rem) ...)))
CPS also lets you to represent first class continuations with FirstClassFunctions (because that is what they are in CPS). First class continuations can be used to implement exceptions, coroutines, threads, generator functions, CallWithCurrentContinuation, and all kinds of other constructs, some of which are quite esoteric.

Any "traditional" function or function call can be rewritten in CPS, so it is possible to throw away stack completely and only use continuations (StacklessPython and most SchemeImplementations do this internally). This might actually make the implementation simpler, because two operations, call and return, are replaced by "goto with parameters".

CPS is also a way to represent data by functions (often used in LambdaCalculus): a datum is represented by a function that calls its continuation with the value of the datum: 

 let pair_of_one_and_two cont = cont 1 2
It makes more sense with LexicalClosures: 

 let pair x y cont = cont x y
-- PanuKalliokoski

Put another way:

CPS is a programming style where no function is ever allowed to return. A function "A" must emulate returning by passing its would-be-return value to a continuation function that was passed into "A" as an explicit parameter. Thus, all function calls are tail calls, which means, all function calls are instances of "goto with parameters."

If a function "A" wants to call another function "B", "A" has to pass "B" a continuation "rest of A" that will receive the return value of "B" and then perform the rest of A's operations. If a function "A" wants to tail-call "B", it can simply pass "B" the same continuation that "A" itself received.

CPS is useful from a theoretical standpoint because it gives you all the power of CallWithCurrentContinuation, while making a CallWithCurrentContinuation function unnecessary. All functions are called with their continuations. In fact, it is possible to write an automatic translator that converts functions from ordinary style into this style.

Functions written in CPS also do not require a call stack; they effectively create one manually, by using lambda expressions to build new continuations overtop of old ones.

If a language required full ContinuationPassingStyle, then even the primitive functions would have to be passed continuations. This would make it difficult to write ordinary expressions.

Sometimes functions have multiple continuations. (When a function has multiple continuations, it can choose which one to return through.)

For example, imagine an LL parser where every parsing rule, whether simple or compound, has three continuations -- success, failure, and catastrophe. Success indicates, well, success. Failure indicates that no input symbols have been consumed and some other rule can be tried. "Catastrophe" indicates that a failure was encountered after input symbols had been consumed. It is easy to write "combinators" which take two rules A and B and produce a rule for "A followed by B", or for "A or B"; these combinators call A and B, passing them continuations which may make use of the rule's own continuations. (I once wrote such a parser in Scheme.) It is easier to make all three continuations explicit, than to use the "default continuation" and two others.

-- EdwardKiser

(See also the Java RequestForEnhancement?, http://developer.java.sun.com/developer/bugParade/bugs/4726340.html, which proposes to add tail-call optimization to Java. This would make it possible to write in Java in ContinuationPassingStyle. Yes, I submitted the RFE.)

This is very interesting. I would like to explore this more if I may. Please let me know if I misunderstand. The essential feature is that functions may not return. In a thread sense, the execution just disappears from one part of the program and continues elsewhere. The original object can go out of scope immediately. Obviously if we wish to preserve state then we must put it somewhere else. In this case we simply pass it as a parameter to the destination function/object.

In a functional language this can be the rest of the program. In a non-functional language this can be emulated by passing a state-machine initializer which instantiates an equivalent predefined 'tail' object (usually using a constructor). The point is that contextual state is being made explicit, and passed between functions. This allows the implicit global state to be ignored, and this allows scope to be limited to the locally executing functions.

So you can do without global scope! No stacks needed. Heaps can collect immediately and safely since the only necessary objects are the ones which are active.

This can be emulated in Java etc. by using multiple threads and a void return. All the elegance of language support is missing of course. The 'tail' function will need to be explicitly defined as an external class, and I can't see a way around the runt return and thread logic. Automatic class building factories are popping up in Java, however. If this feature is generalised to an inline compiler then there might be a glimmer of hope.

Vectorized processing systems can be made optimal for space, and I'm guessing time. I need to chew on this fact a bit. Optimal state machines. Hmmm. --RichardHenderson

I implemented continuation-passing style in Java once using RunAndReturnSuccessor. -- EdwardKiser

The book EssentialsOfProgrammingLanguages covers this topic in depth with Scheme. It also covers writing programs that automatically transform other programs into continuation passing style. Also see CpsTransformation.

I was thinking recently that ContinuationPassingStyle has some similarity to MonadicProgramming. Then I found out that other folks have already made the connection and implemented it in HaskellLanguage. See http://haskell.org/wikisnapshot/MonadicContinuationPassingStyle.html .

I do not know who wrote the above, but it has inspired me to attempt to implement ContinuationPassingStyleInCeePlusPlus using the methods of FunctoidsInCpp. This is, I stress, a style as the function does have to return eventually. -- JohnFletcher

Example and discussion moved to ContinuationPassingStyleInCeePlusPlus.

See also LogicProgrammingInCpp which implements the ContinuationPassingStyle for logical queries.

Here's a simple ContinuationPassingStyle transformation implemented in JavaScript -- SteveYen. See http://levelplusplus.blogspot.com/2004/07/continuations-in-mozilla.html

CPS is very helpful in JavaScript, actually. It's a good solution to the fact that there's no "wait for event" style primitives available in the standard library. I often end up writing code like: 

  loadModule("some_additional_module_to_load.js", function () {
      // do something that depends on the additional module
    });
where loadModule is a function that causes a module to be loaded and stores the function to be executed in a list, and the loaded module causes the function to be executed after it has finished loading. Code with dependencies on multiple modules ends up being nested quite deeply, but it works fine. -- JulesH

CategoryScheme CategoryFunctionalProgramming CategoryCodingConventions CategoryContinuation

EditText of this page (last edited February 10, 2010) or FindPage with title or text search