Using continuation / CPS to implement tail-recursive MergeSort in OCaml

Question

I am trying to implement a tail-recursive MergeSort in OCaml.

Since Mergesort naturally is not tail-recursive, so I am using CPS to implement it.

Also my implementation is inspired by Tail-recursive merge sort in OCaml

Below is my code

---

let merge compare_fun l1 l2 = 
  let rec mg l1 l2 acc =
    match l1, l2 with
      | ([], []) -> List.rev acc
      | ([], hd2::tl2) -> mg [] tl2 (hd2::acc)
      | (hd1::tl1, []) -> mg tl1 [] (hd1::acc)
      | (hd1::tl1, hd2::tl2) ->
         let c = compare_fun hd1 hd2
         in 
         if c = 1 then mg l1 tl2 (hd2::acc)
         else if c = 0 then mg tl1 tl2 (hd2::hd1::acc)
         else mg tl1 l2 (hd1::acc)
  in 
  mg l1 l2 [];;

let split_list p l = 
  let rec split_list p (acc1, acc2) = function
    | [] -> (List.rev acc1, List.rev acc2)
    | hd::tl ->
      if p > 0 then split_list (p-1) (hd::acc1, acc2) tl
      else split_list (p-2) (acc1, hd::acc2) tl
  in 
  split_list p ([], []) l;;

let mergeSort_cps compare_fun l =
  let rec sort_cps l cf =  (*cf = continuation func*)
    match l with 
      | [] -> cf []
      | hd::[] -> cf [hd]
      | _ ->
        let (left, right) = split_list ((List.length l)/2) l
        in 
        sort_cps left (fun leftR -> sort_cps right (fun rightR -> cf (merge compare_fun leftR rightR)))
  in 
  sort_cps l (fun x -> x);;

---

When I compile it, and run it with a 1,000,000 integers, it gives the error of stackoverflow. Why?

---

Edit

Here is the code I used for testing:

let compare_int x y =
  if x > y then 1
  else if x = y then 0
  else -1;;

let create_list n = 
  Random.self_init ();
  let rec create n' acc =
    if n' = 0 then acc
    else 
      create (n'-1) ((Random.int (n/2))::acc)
  in 
  create n [];;

let l = create_list 1000000;;

let sl = mergeSort_cps compare_int l;;

in http://try.ocamlpro.com/, it gave this error: Exception: RangeError: Maximum call stack size exceeded.

in local ocaml top level, it didn't have any problem

Answer 1

Adding another answer to make a separate point: it seems that much of the confusion among answerers is caused by the fact that you don't use the standard OCaml compiler, but the TryOCaml website which runs a distinct OCaml backend, on top of javascript, and has therefore slightly different optimization and runtime characteristics.

I can reliably reproduce the fact that, on the TryOCaml website, the CPS-style function mergeSort_cps you show fails on lists of length 1_000_000 with the following error:

Exception: InternalError: too much recursion.

My analysis is that this is not due to a lack of tail-rec-ness, but by a lack of support, on the Javascript backend, of the non-obvious way in which the CPS-translated call is tailrec: recursion goes through a lambda-abstraction boundary (but still in tail position).

Turning the code in the direct, non-tail-rec version makes the problem go away:

let rec merge_sort compare = function
  | [] -> []
  | [hd] -> [hd]
  | l ->
    let (left, right) = split_list (List.length l / 2) l in
    merge compare (merge_sort compare left) (merge_sort compare right);;

As I said in my other answer, this code has a logarithmic stack depth, so no StackOverflow will arise from its use (tail-rec is not everything). It is simpler code that the Javascript backend handles better.

Note that you can make it noticeably faster by using a better implementation split (still with your definition of merge) that avoids the double traversal of List.length then splitting:

let split li =
  let rec split ls rs = function
    | [] -> (ls, rs)
    | x::xs -> split rs (x::ls) xs in
  split [] [] li;;

let rec merge_sort compare = function
  | [] -> []
  | [hd] -> [hd]
  | l ->
    let (left, right) = split l in
    merge compare (merge_sort compare left) (merge_sort compare right);;

Answer 2

Reading the comments, it seems that your Stack_overflow error is hard to reproduce.

Nevertheless, your code is not entirely in CPS or tail-recursive: in merge_sort, the calls to split_list and merge are made in a non-tail-call position.

The question is: by making your CPS transform and generous use of accumulators, what will be the worst stack depth related to recursion? Saving stack depth on the sort calls is in fact not very interesting: as each split the list in two, the worst stack depth would be O(log n) for n the size the input list.

On the contrary, split and merge would have made a linear O(n) usage of the stack if they weren't written in accumulator-passing style, so they are important to make tail-rec. As your implementation of those routines is tail-rec, there should be no need to worry about stack usage, and neither to convert the sort routine itself in CPS form that makes the code harder to read.

(Note that this logarithmic-decrease argument is specific to mergesort. A quicksort can have linear stack usage in worst case, so it could be important to make it tail-rec.)