I think that we moved away from the topic a bit. Not that it is bad, but let’s not confuse the CPS Programming and CPS Intermediate representation. The latter is used in compilers and is a representation which simplifies data relations and makes certain optimizations much easier. The idea that was inspired by CPS programming technique, which was used in different dialects of Lisp for many years before that. The compilation techniques had evolved since that time, and CPS IR was mostly superseded by ANF representation (see the CPS/ANF Saga for the brief summary).
And although it is an interesting topic on itself, it is more about writing a compiler, so it is rather a nice topic, unlike the CPS programming style which is a powerful technique that is practical and is used to (a non-exhaustive list):
- turn a general non tail recursive function into a tail-recursive;
- implement arbitrary control-flow (exceptions, co-routines, non-deterministic computations, call/cc);
- implement variadic functions;
- writing parsers (especially with backtracking);
- optimizing algorithms (to minimize allocations).
The essence of CPS programming, is that a function accepts one or more functions as arguments and use them to return values back to the caller. For example, this is a CPS style parser, which takes two continuations,
error and use one or another
let parse_digit input ~digit ~error = match input with
| '0'..'9' -> digit (Int.of_char input)
| _ -> error input
Note, that in the example above we could use an ADT, but using continuations here saved us an allocation.
A recurring pattern in the CPS style is when a function has only one continuation, e.g.,
let computation args k =
let result = <do-some-computation> args in
The type of such function is
'args -> ('a -> 'r) -> 'r. And it immediately hits us on an abstraction opportunity, as we can see that we have a computation parameterized with the type
('a -> 'r) -> 'r, which gives a rise to the Continuation Monad. Using the Continuation Monad it is very easy to chain computations without blowing your mind. This monad makes it easy to treat values of type
'a cont = ('a -> 'r) -> 'r as first-class routines which could be stored in data structures, resumed, scheduled, etc. So that we can implement lightweight threads, generators, resumptions, and other interesting techniques.
Going back to the CPS style map.
let rec mapk f xs k = match xs with
|  -> k 
| x :: xs -> mapk f xs (fun xs -> k (f x :: xs))
Here we use CPS (or Continuation monad) to turn a non-tail recursive call into tail-recursive. We don’t want to turn into CPS every call, as this would be the same as unnecessary wrapping into monad pure computations, e.g.,
let impure_purity =
return 2 >>= fun x ->
return 3 >>= fun y ->
return (x + y)
This won’t give us any benefits, since our values are pure. Now let’s rewrite
mapk using the monadic syntax,
let rec map' f xs = match xs with
|  -> return 
| x :: xs ->
map' f xs >>= fun xs ->
return (f x :: xs)
Here, it becomes obvious that functions
(::) are pure, while the
map' itself is a computation. \
To summarize, CPS is a very powerful technique for expressing both – non-trivial dynamic behaviors of programs and, when ML-style type inference is present, static properties.
- Continuation-passing, closure-passing style, 1989
- Reasoning about programs in continuation-passing style, 1993
- The CPS/ANF Saga, 2010
- The Discoveries of Continuations