生成列表导致堆栈溢出

Question

我正在生成运行dom 号码列表：

let gen n =
    let rec pom l n =
        match n with
        | 0 -> l
        | _ ->
            let el = Random.int 20000000
            in pom (el::l) (n-1)
    in
        pom [] n

let lo = gen 1000000

我得到的是

Fatal error: exception Stack_overflow

为什么？我正在使用尾递归（和累加器）

编辑:

你是对的，两种类型的堆栈都溢出了。

但是如果我的代码有无数行，用这种方式调试它会很痛苦。我想在这里使用ocamldebug，只是作为学习经验。我运行 ocamldebug 是这样的：

(ocd) r
Loading program... done.
Time: 88089944
Program end.
Uncaught exception: Stack_overflow
(ocd) b
Time: 88089943 - pc: 52 - module Pervasives
214   | hd :: tl -> <|b|>hd :: (tl @ l2)
(ocd) bt
#0  Pc: 52  Pervasives char 7700
#1  Pc: 64  Pervasives char 7715
#2  Pc: 64  Pervasives char 7715
#3  Pc: 64  Pervasives char 7715
#4  Pc: 64  Pervasives char 7715
#5  Pc: 64  Pervasives char 7715
#6  Pc: 64  Pervasives char 7715
// and so it goes on forever

这并没有说明我的程序崩溃的原因。我如何使用 ocamldebug 调试它？

（元：我应该post一个单独的线程还是应该留在这里）

Answer 1

我运行你的代码在我的 Mac Pro 上，没有出现堆栈溢出。正如您所说，您的代码看起来非常好。

可能的解释：

您运行处于内存有限的环境中。
您的部分代码有一些旧定义。也许在新的 OCaml 顶层尝试重新运行。

更新

我认为@antron 说得很好。如果您是运行编译代码，您很可能不知道问题出在哪里。添加一些跟踪，您很可能会发现堆栈溢出在其他地方。

Answer 2

由于错误发生在不同的函数中，以下是您以后如何更快地调试此类问题的方法。

您可以打开回溯。要么在程序开头调用 Printexc.record_backtrace true，要么在运行中将环境变量 OCAMLRUNPARAM 设置为 b，如 OCAMLRUNPARAM=b ./a.out。这应该会告诉您错误发生的位置，尽管有时它会跳过您希望成为调用堆栈的部分——我相信这是由于内联等优化所致。不过，它通常很有用。为此，程序必须使用标志 -g.
您仍然可以找到异常的来源，即使是在您的程序中的一堆函数调用中，通过进行二分查找。首先将一半的函数调用包装在处理程序中。如果异常发生在那里，解开它们，然后再次将其中一半包装在处理程序中，依此类推，直到您深入了解源代码。它仍然有些劳动密集型，但你可以在 O(log n) 时间内以这种方式进行调试，并且 zillion 的日志并没有那么多:)

Answer 3

打印Stack_overflow异常的回溯通常有些无用，因为导致溢出的调用次数超过了回溯缓冲区的大小。例如，如果您采用以下程序 (backtrace.ml)：

let init n =
  let rec loop xs x =
    if x >= 0 then loop (x::xs) (x-1) else xs in
  loop [] (n-1)

let sum = function
  | [] -> 0
  | x :: xs -> List.fold_right (+) xs x

let () =
  let xs = init 10000000 in
  let y = sum xs in
  print_int y

并用

执行

 OCAMLRUNPARAM=b ocamlbuild backtrace.d.byte --

你会得到一个无用的表单回溯：

Fatal error: exception Stack_overflow
Raised by primitive operation at file "list.ml", line 89, characters 16-37
Called from file "list.ml", line 89, characters 16-37
Called from file "list.ml", line 89, characters 16-37
...

我们无法增加内部回溯缓冲区，但我们可以减小堆栈大小，从而限制回溯的大小，使其适合缓冲区。因此，如果我们运行程序在有限的堆栈内，我们将获得更好的回溯：

OCAMLRUNPARAM="b,l=100" ocamlbuild backtrace.d.byte --
Fatal error: exception Stack_overflow
Raised by primitive operation at file "list.ml", line 89, characters 16-37
Called from file "list.ml", line 89, characters 16-37
Called from file "list.ml", line 89, characters 16-37
...
Called from file "backtrace.ml", line 18, characters 10-16

宾果游戏。问题的根源被精确定位到调用站点。

注意：OCAMLRUNPARAM的l选项只有字节码运行时才能理解。为了对本机代码重复相同的技巧，应该使用操作系统提供的机制来限制堆栈。对于 unices 它通常是 ulimit -s shell 原始的。

生成列表导致堆栈溢出

Generating a list causes a stack overflow

ocaml

stack-overflow

tail-recursion