Stack_overflow in processing List using OCaml

Question

So basically I am processing a long list in Ocaml, and I got the Stack_overflow error.

Then I did this experiment, and the error re-occured.

let rec create l =
  match l with
    | 0 -> []
    | _ -> "00"::(create (l-1))

let ll = create 999999;   (*my list can be as long as around 100k*)

I use ocamlbuild to build this code into native, run it and then the code crushed and I got this:

Fatal error: exception Stack_overflow

So my question is that:

1. Can I extend the length of stack and avoid this error?

2. I know that tail recursive could help in this situation classically, but do I have to re-write my code thus enable tail-recursive? That would require a lot of manually modification... Could OCaml's compiler help in this issue?

Answer 1

Tail recursion is achieved by making the recursive call the very last thing your function does. In your case, after the recursive call, there is a list concatenation. The usual workaround is to use an accumulator:

let create l =
  let rec create2 l accu =
    match l with
      | 0 -> accu
      | _ -> create2 (l-1) ("00"::accu)
  in create2 l []

let ll = create 999999;;

print_int (List.length ll) (* outputs 999999 *)

Answer 2

Generally increasing the stack size does not really help you, since soon you will encounter larger examples which eat your enlarged stack. You should change your code. After converting simple handful of non tail-rec functions into tail-rec, then you should feel much easier to write tail-rec functions from scratch.

Another way to convert non tail-rec functionos to tail-rec is using CPS conversion http://en.wikipedia.org/wiki/Continuation-passing_style :

let rec create' k = function
  | 0 -> k []
  | l -> create' (fun xs -> k ("00"::xs)) (l-1)
let create = create (fun x -> x)

When I convert complex recursive functions to non tail-rec, sometimes I personally find it easier than adding accumulators, though the result code may be even harder to read.

Some compilers of functional languages use this CPS conversion to eliminate the non tail calls. Therefore they have no problem of stack overflow due to non tail calls. OCaml is, however, rather stack based so there is no auto CPS conversion: you must convert non tail calls to tail ones by yourself.