Continuation Style confusioon

Learning
1

I was given a task, to create a cps version of fold_left, with its first argument being in continuation style aswell. So the signature should be:

(’a -> ’b -> (’a -> ’c) -> ’c) -> ’a -> ’b list -> (’a -> ’c) -> ’c

I managed to quite naturally come up with the following implementation:

let rec fold_left_cps f_cps acc xs k = match xs with  
    | [] -> k acc
    | x :: xs -> f_cps acc x (fun res -> (fold_left_cps f_cps res xs k))

It has the correct type, and it makes sense when I think about what it does. Problem is, I cannot figure out how to make use of it at all, for example I would like to create function which multiplies whole List but stops when it encounters 0 (I know how to do this using exceptions). I cannot even implement normal fold_left using it. My problem is with f_cps function, I do not see, what should be its third argument (it’s continuation). Is the above code even correct? If not, I would appreciate any help.

2

The fold_left_cps function looks correct to me. To solve this “short-circuit multiplication” problem, you need to look at the fold operation you’re passing to the function, not just the continuation function.

f_cps acc x (fun res -> (fold_left_cps f_cps res xs k))

Notice that the parameter f_cps is in tail position, meaning that f_cps is the last computation that needs to execute to finish the entire fold and there is no call stack to unwind. What would be the call stack in the non-CPS fold function instead gets reified as nested closures (the continuation) in the CPS version. Therefore, in CPS, f_cps has the ability to terminate the entire fold operation immediately if it just doesn’t call the continuation. How can you pass a function that stops the fold if 0 is encountered?

2 Likes
3

Exactly what @alan said! your implementation looks correct; it’s on the user of your function to supply a f_cps s.t it short circuits under some specific condition. Try coming up with an f_cps that short-circuits yourself, but if you’re super stuck, here’s what f_cps would look like for the example you mentioned (short circuiting when encountering 0):

(*
 * mul_opt : int list -> int option
 * returns Some x s.t x is prod of all elems in list
 * immediately returns None if it encounters 0.
 *)
let mul_opt l =
  fold_left_cps
    (fun x y k ->.   (* f_cps *)
       if y = 0
       then None     (* Terminate fold!    *)
       else k(x * y) (* Compute & continue *)
    )
    1
    l
    (fun x -> Some x)

let Some 6 = mul_opt [1;2;3]
let None   = mul_opt [1;2;3;0;1;2;3]

Additional note: if this was for a class, do consider using resources that are given to you by your class (OH/Question message boards).

1 Like
4

So i think when i encouter 0 i should just ditch the continuation and return 0 as a result. I think i get the idea, just having some tough time implementing it. I will attempt it once again and come back if I fail.

5

Alright, I managed to solve it, my mistake was trying to pass my own version of continuation in f_cps, instead of simply creating a lambda that actually calls this continuation - now seems obvious and silly. Thank you @alan and @aw0lambda0lambda