I got a Stack_overflow error in my OCaml program lately. If I turn on backtracing, I see the exception is raised by a "primitive operation" "pervasives.ml", line 270. I went into the OCaml source code and saw that line 270 defines the function @ (i.e. list append). I don't get any other information from the backtrace, not even where the exception gets thrown in my program. I switched to bytecode and tried ocamldebug, and it doesn't help (no backtrace generated).
I thought this is an extremely weird situation. The only places in my program where I used a list is (a) building a list containing integers 1 to 1000000, (b) in-order traversing a RBT and putting the result into a list, and (c) printing a list of integers containing ostensibly 1000000 numbers. I've tested all functions and none of them contain could an infinite loop, and I thought 1000000 isn't even a huge number. Moreover, I've tried the equivalent of my program in Haskell (GHC), Scala and SML (MLton), and all of those versions worked perfectly and in a reasonably short amount of time. So, the question is, what could be going on? Can I debug it?
The @ operator is not tail-recursive in the OCaml standard library,
let rec ( @ ) l1 l2 =
match l1 with
[] -> l2
| hd :: tl -> hd :: (tl @ l2)
Thus calling it with large lists (as the left argument) will overflow your stack.
It could be possible, that you're building your list by appending a new element to the end of the already generated list, e.g.,
let rec init n x = if n > 0 then init (n-1) x @ [x] else []
This has time complexity n^2 and will consume n slots in the stack space.
Concerning the general question - how to debug such stack overflows, my usual recipe is to reduce the stack size, so that the problem is triggered as soon as possible before the trace is bloated, e.g.,
OCAMLRUNPARAM=b,l=1024 ocaml ./test.ml
If you're compiling your OCaml code to the native code, then you need to pass the -g option to the compiler, so that it can produce backtraces. Also, in the native execution, the size of the stack is controlled by the operating system and should be set using the corresponding mechanism of your OS, for example with ulimit in GNU/Linux, e.g., ulimit -s 1024.
As a bonus track, the following init function is tail recursive and will have O(N) time complexity and will take O(1) stack space:
let init n x =
let rec loop n xs =
if n = 0 then xs else loop (n-1) (x :: xs) in
loop n []
The idea is to use an accumulator list and build the list in the heap space.
If you don't like thinking about tail-recursiveness then you can use Janestreet Base library (or Core), or Batteries library. They both provide tail-recursive versions of the init function, as well as guarantees that all other functions are tail-recursive.