CPS

also: continuation-passing style, continuation

Continuation-passing style: instead of returning, a function takes an extra continuation argument and calls it with the result. Every call becomes a tail call, which is what lets a CPS-transformed program run in constant stack space wherever tail calls are eliminated, and it makes control flow a value that can be stored and resumed.

In direct style a call returns and the caller resumes, so the caller's frame has to survive the call. In continuation-passing style the caller instead hands over a function describing what to do with the result, and never resumes: every call is a tail call, and control flow has become a value.

let rec fact n = if n = 0 then 1 else n * fact (n - 1)
 
let rec fact_k n k =
  if n = 0 then k 1 else fact_k (n - 1) (fun r -> k (n * r))

Making the continuation explicit also makes it discardable, which is what a non-local exit is. Nothing in the CPS version forces k to be called:

let rec product_k l k =
  match l with
  | [] -> k 1
  | 0 :: _ -> 0                  (* abandon k *)
  | x :: rest -> product_k rest (fun r -> k (x * r))

fact 10                       ->  3628800
fact_k 10 (fun x -> x)        ->  3628800
product_k [1;2;3;4] id        ->  24
product_k [1;0;3;4] id        ->  0

The stack does not disappear, it changes shape: the frames become a chain of heap-allocated closures. That is a real win where tail calls are eliminated and the heap is cheap to allocate in, and it is the transformation that exception handlers, generators, and schedulers are all special cases of.

• Tail CallsWhich languages guarantee them, which only sometimes deliver them, how to check, and what to do when you do not have them.