1

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?

Improve this question

2 Answers 2

Reset to default
2

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 *)
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Hi Zoyd, Thank you for your answer! Yes, I know I can do this way, but the problem is that, I am working on a quite big project, and if I go this way, probably I have to change all the recursive call related to this long list..
Why is that ? What does it change ?
Then I am wondering if there is any way I can just enlarge the size of the stack?
You should use tail-functions as Zoyd says, but to change the size of the stack you can set the environment variable OCAMLRUNPARAM to "l=N" where N is the stack size, and the other character is a lowercase L. This may be limited by other runtime factors (like the operating system). I've used this to decrease the size of the stack to check if something is in need of a tail-call rewrite.
According to the manual, the l param is ignored when compiling to native code, which the OP is doing.
|
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.

Improve this answer

3 Comments

Is CPS usually slower than "accum trick" (e.g. allocation of additional closures) or CPS can be optimized to imperative for loop?
I believe CPS is heavier than "accum" in OCaml since it involves closure creations.
Yes, I just measured this tiny example and CPS solution is twice slower and eats twice more memory. If I correctly understand, it is the same recursive function: first we create a sequence of closures and then run it. So, we just move this recursion from stack to heap. Does CPS work better in Haskell?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.