OCaml:pervasives.ml中的Stack_overflow异常

Question

我有一个Stack_overflow在我的OCaml程序错误最近.如果我打开回溯,我看到异常是由"原始操作""pervasives.ml"引发的,第270行.我进入了OCaml源代码,看到第270行定义了函数@(即列表追加).我没有从回溯中获得任何其他信息,即使在我的程序中抛出异常也没有.我切换到字节码并尝试ocamldebug,它没有帮助(没有产生回溯).

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

Answer 1

该@运营商是不是尾递归在OCaml的标准库,

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堆栈空间中的槽.

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

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

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

作为奖励跟踪,以下init函数是尾递归的,并且将具有O(N)时间复杂性并且将占用O(1)堆栈空间:

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

我们的想法是使用累加器列表并在堆空间中构建列表.

如果您不喜欢考虑尾递归,那么您可以使用Janestreet Base库(或Core)或Batteries库.它们都提供init函数的尾递归版本,并保证所有其他函数都是尾递归的.