fibonacci cps implementation

Question

I'm trying to convert different function from tail recursive to cps (continuation passing style).

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 "%u\n" (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 "%u\n" (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 "%u\n" (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 "%u\n" (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 "%u\n" (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) 1;;

explainations of the problem:

problematic line (according to the interpretor):

|_ -> fibo_cps (n-1) (fun r -> acc (prev+r)) acc

error message:

Line 5, characters 49-52: Error: This expression has type int -> 'a but an expression was expected of type int

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

there is probably a problem with the arguments used during recursion. In the interpretor, the acc (l5) is underlined and I have this message: Line 5, characters 49-52: Error: This expression has type int -> 'a but an expression was expected of type int — mxbr236, Sep 18 '22 at 17:03
To clarify, please edit to add details like error messages to the question. :) — Chris, Sep 18 '22 at 17:05
@Chris, I add informations in my question, but this error message is my own message. Personally I think it's concerning the many arguments of fun — mxbr236, Sep 18 '22 at 17:12

Mulan · Accepted Answer · 2022-09-18T17:28:01.553

2

I think this is what you're looking for -

let fibo n =
  let rec fibo_cps n acc =
    match n with
    |0 -> acc 0
    |1 -> acc 1
    |_ -> fibo_cps (n-1) (fun x -> fibo_cps (n-2) (fun y -> acc (x+y)))
  in fibo_cps n (fun x -> x)

Please note that while the computation above is tail-recursive, it's still a very inefficient way to compute fibonacci numbers. Consider a linear iterative algorithm -

let fibo2 n =
  let rec aux n a b =
    match n with
    |0 -> a 
    |_ -> aux (n-1) b (a+b)
  in aux n 0 1

edited Sep 18 '22 at 17:28

answered Sep 18 '22 at 17:13

Mulan

129,518
31
228
259

It's work, but I notice the result is shifted by one rank. e.g. fibo 5 returns fibo 6 (8), fibo 4 returns fibo 5 (5)... – mxbr236 Sep 18 '22 at 17:20
1

then change the base case `0 -> acc 0` – Mulan Sep 18 '22 at 17:24
While testing on my computer with ocamlopt, I notice that using int64, tail recursive (fibonacci 999999L) executes faster than the cps version, but this is maybe normal. In a course, I thought I read that it was more efficient in general. – mxbr236 Sep 18 '22 at 17:37
No, cps functions are less efficient than tail-recursive one in the general case, since they require to allocate more memory in the intermediary closures. – octachron Sep 18 '22 at 18:20

octachron · Answer 2 · 2022-09-18T21:00:01.037

2

A direct translation of the tail-recursive version to cps-style would be

let rec fib_cps n k =
  if n <= 1 then k
  else fib_cps (n-1) (fun (prev,n) -> k (n, prev+n))
let fib n = snd @@ fib_cps n Fun.id (0,1)

edited Sep 18 '22 at 21:00

answered Sep 18 '22 at 18:28

octachron

17,178
2
16
23

wouldn't just `let fib n = fib_cps n snd (0,1)` work as well? – Will Ness Sep 19 '22 at 15:18
Indeed, that would be a better implementation. – octachron Sep 19 '22 at 15:25
is it considered better to use the uncurried or the curried "continuation" functions in OCaml? i.e. using `(fun a b -> b)` as the top continuation, with the corresponding change to the `fib_cps`? – Will Ness Sep 19 '22 at 15:31
1

Since partial application on continuation are not that useful, I tend to use single-argument continuation. I am not sure if there are real idioms in this case. Moreover in this specific case, the mathematical model hints that it is better to use a tuple, since that makes it easier to realize that the right approach is to use fast-exponentiation on 2×2 matrices. – octachron Sep 19 '22 at 17:03

fibonacci cps implementation

2 Answers2