Ocaml Continuation Continuation Style

Question

I am new to ocaml and trying to write a continuation of the transfer style function, but am rather confused about what value I need to pass in an extra argument in k

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

so its like

let rec even list = .... 

on CPS, I know that I need to add one argument to pass the function so that

 let rec evenk list k = .... 

but i have no idea how to handle this k and how it works exactly

for example, for this even function, the 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 of k is a function that takes the result from evenk and does the "rest of the calculation" and produces a "response". What type of response has and what you mean by “the rest of the calculation” depends on what you use CPS for. CPS, as a rule, is not an end in itself, but is done for a specific purpose. For example, in the form of a CPS, it is very easy to implement control statements or optimize tail calls. Not knowing what you are trying to achieve, it is difficult to answer your question.

What is it worth if you are just trying to convert from a direct style to a continuation-transfer style, and all you care about is the value of the answer, which conveys the identification function, since the continuation has the right.

A good next step would be to implement evenk using CPS. I will make a simpler example. If I have a direct style function

 let muladd xin = x + i * n 

and if I accept CPS mulk and addk , I can write

 let muladdk xink = let k' product = addk x product k in mulk ink' 

And you will see that mractioniplication is executed first, and then “continues” with k' , which adds, and finally, continues with k , which is returned to the caller. The main idea is that in the body of muladdk I highlighted a new continuation k' , which denotes an intermediate point in the function of multiple additions. To make your evenk work, you will have to select at least one such continuation.

Hope this helps.

Answer 2

Whenever I played with CPS, the thing referred to in the sequel is what you usually return to the caller. In this simple case, a pleasant “lubricant for intuition” means the name “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 correct evenk call (with an identification function - effectively converting the continuation-return style to a regular style), I assume that the difficulty lies in defining evenk .

k is a continuation function representing the rest of the calculation and creating the final value, as Norman said. So, you need to calculate the result v of even and pass that result to k , returning kv , not just v .

Answer 4

You want to specify the result of your function as the result, as if it were not written with the continuation of the transition style.

Here is your function that checks if the 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 write it with the continuation of cont :

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

You calculate the result of your function and pass result to continue ...