OCaml：Stack_overflow pervasives.ml 中的异常

Question

最近我的 OCaml 程序出现 Stack_overflow 错误。如果我打开回溯，我会看到第 270 行 "primitive operation" "pervasives.ml" 引发了异常。我进入 OCaml 源代码并看到第 270 行定义了函数 @（即列表追加）。我没有从回溯中获得任何其他信息，甚至在我的程序中抛出异常的地方也没有。我切换到字节码并尝试 ocamldebug，但它没有帮助（没有生成回溯）。

我认为这是一个非常奇怪的情况。在我的程序中，我唯一使用列表的地方是 (a) 构建一个包含 1 到 1000000 整数的列表，(b) 按顺序遍历 RBT 并将结果放入列表，以及 (c) 打印一个整数列表表面上包含 1000000 个数字。我已经测试了所有函数，其中 none 个可能包含无限循环，我认为 1000000 甚至不是一个很大的数字。此外，我已经在 Haskell (GHC)、Scala 和 SML (MLton) 中尝试了与我的程序等效的程序，所有这些版本都在相当短的时间内完美运行。所以，问题是，会发生什么？我可以调试吗？

Answer 1

标准库中的列表函数针对小列表进行了优化，不一定tail-recursive；部分理由是列表不是存储大量数据的有效数据结构（请注意 Haskell 列表是惰性的，因此与 OCaml 热切列表完全不同）。

特别是，如果您在使用 @ 时遇到计算器溢出错误，您很可能正在实施具有二次 time-complexity 的算法，因为 @ 的复杂度是与其左参数的大小成线性关系。

对于您的问题，它们可能是比列表更好的数据结构，例如，如果您想要迭代，序列库或任何其他形式的迭代器会更有效。

考虑到前面提到的所有警告，重新定义 tail-recursive 但标准库函数的低效版本相对简单，例如:

 let (@!) x y = List.rev_append (List.rev x) y

另一种选择是使用 containers 库或任何扩展标准库（本质上是电池或基础）：所有这些库都重新实现 tail-recursive 版本的列表函数。

Answer 2

OCaml标准库中@运算符不是tail-recursive，

let rec ( @ ) l1 l2 =
  match l1 with
    [] -> l2
  | hd :: tl -> hd :: (tl @ l2)

因此用大列表调用它（作为左边的参数）会使你的堆栈溢出。

您可以通过将新元素附加到已生成列表的末尾来构建列表，例如，

let rec init n x = if n > 0 then init (n-1) x @ [x] else []

这具有时间复杂度 n^2，并且会占用堆栈中的 n 个槽位 space。

关于一般问题 - 如何调试此类堆栈溢出，我通常的方法是减小堆栈大小，以便在跟踪膨胀之前尽快触发问题，例如，

OCAMLRUNPARAM=b,l=1024 ocaml ./test.ml

如果您将 OCaml 代码编译为本机代码，则需要将 -g 选项传递给编译器，以便它可以生成回溯。此外，在本机执行中，堆栈的大小由操作系统控制，应使用 OS 的相应机制进行设置，例如 GNU/Linux 中的 ulimit，例如, ulimit -s 1024.

作为奖励曲目，以下 init 函数是尾递归函数，具有 O(N) 时间复杂度，需要 O(1) 个堆栈 space:

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

想法是使用累加器列表并在堆中构建列表 space。

如果您不喜欢考虑 tail-recursiveness，那么您可以使用 Janestreet Base 库（或 Core）或 Batteries 库。它们都提供 tail-recursive 版本的 init 函数，并保证所有其他函数都是 tail-recursive。

OCaml：Stack_overflow pervasives.ml 中的异常

OCaml: Stack_overflow exception in pervasives.ml

stack-overflow

debugging

ocaml