Continuation Passing Style in ocaml

Question

I am a bit confused on the concept. So I have the following function

    let rec sumlist lst =
          match lst with
             | [] -> 0
             | (h::t) -> h + (sumlist t)

With continuation, it can be written as

let rec cont_sumlist lst c =
match lst with
| [] -> (c 0)
| (h::t) -> cont_sumlist t (fun x -> c (h + x))

I am still confused on what the c means and what it does

Answer 1

A general answer is already given, but specifically, for cont_sumlist,

• in case of [] we "return" (i.e. feed) 0 into c that we're given (0 is the sum of an empty list), and

• in case of (h::t) we construct the continuation for cont_sumlist t so that after the result for t (i.e. x) is ready, it will be combined with h (by h + x) and fed further into c given to us for (h::t).

This is thus expressing the equation sumlist (h::t) = h + sumlist t, but the evaluation chain is made explicit as the chain of these continuation functions, each feeding its result to the continuation function above it; as opposed to being implicit in the stack-based evaluation mechanism.

In other words fun x -> c (h + x) = c ∘ (h +), so as we go along the list [h1; h2; h3; ...], the continuation is being progressively constructed as c0 ∘ (h1 +) ∘ (h2 +) ∘ (h3 +) ∘ ..., and is finally called with 0 when the list has been searched through completely; where c0 is the top-most continuation given by a user to the top-most call, e.g.

cont_sumlist [1,2] (fun x -> x) 
= 
 (fun x -> (fun x -> (fun x -> x) (1 + x)) (2 + x)) 0
=
                     (fun x -> x) 
           (fun x ->              (1 + x)) 
 (fun x ->                                 (2 + x)) 0
=
                                  (1 +     (2 +     0))

So overall cont_sumlist [x; y; z; ... ; n] c turns into

 (c ∘ (x +) ∘ (y +) ∘ (z +) ∘ ... ∘ (n +) ) 0
= 
  c (  x +  (  y +  (  z +  ( ... (  n +   0) .... ))))

with the crucial difference that there's no stack winding and unwinding involved and the sum is calculated from right to left directly, given in a C-like pseudocode as a sequence of simple steps

    r = 0; 
    r += n; 
    .......
    r += z;
    r += y;
    r += x;
    call c(r);
    // call c with r, without expecting c to return; 
    // like a jump into c, supplying it the value r;
    // c must expect to receive a value

One might say that the construction of the overall continuation is similar to winding up the stack, and its application -- to the unwinding of the stack under conventional stack-based evaluation.

Another way of putting it is that CPS defines a special kind of function call protocol, unlike the usual C-like one which expects every function call to return.

Each case in the CPS definition can be interpreted as giving a small-step semantics transition rule for the function: { [] } --> 0 ; { (h::t) } --> h + { t }.