Continuation-passing Style - Use and Implementation

Use and Implementation

Continuation passing style can be used to implement continuations and control flow operators in a functional language that does not feature first-class continuations but does have first-class functions and tail-call optimization. Without tail-call optimization, techniques such as trampolining, i.e. using a loop that iteratively invokes thunk-returning functions, can be used; without first-class functions, it is even possible to convert tail calls into just gotos in such a loop.

Writing code in CPS, while not impossible, is often error-prone. There are various translations, usually defined as one- or two-pass conversions of pure lambda calculus, which convert direct style expressions into CPS expressions. Writing in trampolined style, however, is extremely difficult; when used, it is usually the target of some sort of transformation, such as compilation.

Functions using more than one continuation can be defined to capture various control flow paradigms, for example (in Scheme):

It is of note that CPS transform is conceptually a Yoneda embedding. It is also similar to the embedding of π-calculus in lambda calculus.