Currently I’m trying to convert different function from tail recursive to cps (continuation passing style) using OCaml language.

Normally, I managed to do a sum and factorial function:

Sum function:

Tail recursive:

let sum n =
  let rec subSum n acc =
    match n with
    |0 -> acc
    |_ -> subSum (n-1) (n+acc)
  in subSum n 0;;

Printf.printf "%un" (sum 5);; (*returns 15*)

cps version:

let sum2 n =
  let rec sum_cps n acc =
    match n with
    |0 -> acc 0
    |_ -> sum_cps (n-1) (fun r -> acc (n+r))
  in sum_cps n (fun n -> n);;

Printf.printf "%un" (sum2 5);; (*returns 15*)

factorial (same style as sum):

tail recursive:

let fact n =
  let rec subFact n acc =
    match n with
    |0 -> acc
    |1 -> acc
    |_ -> subFact (n-1) (n*acc)
  in subFact n 1;;

Printf.printf "%un" (fact 6);; (*returns 720*)

cps version:

let fact2 n =
  let rec fact_cps n acc =
    match n with
    |0 -> acc 1
    |1 -> acc 1
    |_ -> fact_cps (n-1) (fun r -> acc (n*r))
  in fact_cps n (fun n -> n);;

Printf.printf "%un" (fact2 6);; (*returns 720*)

However, in fibonacci, there is another argument in addition to the accumulator and that disturbs me a little bit:

tail recursive version:

let fibo n =
  let rec fibon n acc prev =
    match n with
    |0 -> acc
    |_ -> fibon (n-1) (prev+acc) acc
  in fibon n 0 1;;

Printf.printf "%un" (fibo 6);; (*returns 8*)

cps attempt (not working):

let fibo n =
  let rec fibo_cps n acc prev =
    match n with
    |0 -> 0
    |_ -> fibo_cps (n-1) (fun r -> acc (prev+r)) acc
  in fibo_cps n (fun n -> n) 1L;;

I would just like to understand how to make a working cps version of fibonacci.