Ocaml continuation passing style

Question

I'm new to ocaml and tryin to write a continuation passing style function but quite confused what value i need to pass into additional argument on k

for example, I can write a recursive function that returns true if all elements of the list is even, otherwise false.

so its like

let rec even list = .... 

on CPS, i know i need to add one argument to pass function so like

let rec evenk list k = .... 

but I have no clue how to deal with this k and how does this exactly work

for example for this even function, environment looks like

val evenk : int list -> (bool -> ’a) -> ’a = <fun>

evenk [4; 2; 12; 5; 6] (fun x -> x)  (* output should give false *)

Answer 1

The continuation k is a function that takes the result from evenk and performs "the rest of the computation" and produces the "answer". What type the answer has and what you mean by "the rest of the computation" depends on what you are using CPS for. CPS is generally not an end in itself but is done with some purpose in mind. For example, in CPS form it is very easy to implement control operators or to optimize tail calls. Without knowing what you are trying to accomplish, it's hard to answer your question.

For what it is worth, if you are simply trying to convert from direct style to continuation-passing style, and all you care about is the value of the answer, passing the identity function as the continuation is about right.

A good next step would be to implement evenk using CPS. I'll do a simpler example. If I have the direct-style function

let muladd x i n = x + i * n

and if I assume CPS primitives mulk and addk, I can write

let muladdk x i n k =
  let k' product = addk x product k in
  mulk i n k'

And you'll see that the mulptiplication is done first, then it "continues" with k', which does the add, and finally that continues with k, which returns to the caller. The key idea is that within the body of muladdk I allocated a fresh continuation k' which stands for an intermediate point in the multiply-add function. To make your evenk work you will have to allocate at least one such continuation.

I hope this helps.

Answer 2

Whenever I've played with CPS, the thing passed to the continuation is just the thing you would normally return to the caller. In this simple case, a nice "intuition lubricant" is to name the continuation "return".

let rec even list return =
  if List.length list = 0
    then return true
    else if List.hd list mod 2 = 1
      then return false
      else even (List.tl list) return;;

let id = fun x -> x;;

Example usage: "even [2; 4; 6; 8] id;;".

Answer 3

Since you have the invocation of evenk correct (with the identity function - effectively converting the continuation-passing-style back to normal style), I assume that the difficulty is in defining evenk.

k is the continuation function representing the rest of the computation and producing a final value, as Norman said. So, what you need to do is compute the result of v of even and pass that result to k, returning k v rather than just v.

Answer 4

You want to give as input the result of your function as if it were not written with continuation passing style.

Here is your function which tests whether a list has only even integers:

(* val even_list : int list -> bool *)
let even_list input = List.for_all (fun x -> x mod 2=0) input

Now let's write it with a continuation cont:

(* val evenk : int list -> (bool -> 'a) -> 'a *)
let evenk input cont =
  let result = even_list input in
  (cont result)

You compute the result your function, and pass resultto the continuation ...