OCaml 中的大型列表文字编译期间堆栈溢出

Question

我有一个小项目来检查一个数字是否是素数。这个想法是准备（生成）一个达到某个点的素数列表，供库函数使用（为此使用代码生成器）。

虽然代码生成工作正常，但如果列表很大（例如，对于多达一百万的素数列表，即〜75k条目），生成的文件的编译会失败。

沙丘构建的输出：

沙丘构建输出的部分（底部）--verbose:

一些代码：

(* prime_list.mli *)
val long_list : int list

(* THIS FAILS TO COMPILE: prime_list.ml (was generated, found only in _build directory) *)
let long_list = [2;3;5;7;
<a lot more entries, depending on parameter provided in dune file...>]

据我了解，列表文字（当然是

2 :: (3 :: ( 5 :: ... )))

的糖）在编译期间对

::

的嵌套调用太深并且堆栈溢出（可能是解析而不是构造值？我不知道如何不幸的是，编译在 OCaml 中完全有效）。

您有解决这个问题的想法吗？我想要一个只要我愿意的列表，使用尾递归编写每个函数，而编译器让我像这样失望......

回顾一下：我在内存中（在生成器中）有列表，但无法以允许我在主程序中烘焙它的方式将其转储到文件（最好是 .ml），这令人沮丧。

出于绝望，我也尝试生成这样的文件：

(* prime_list.ml, another try *)
let long_list = []
let long_list = 999983 :: long_list
let long_list = 999979 :: long_list
...
let long_list = 3 :: long_list
let long_list = 2 :: long_list

以及

let long_list0 = []
let long_list1 = 999983 :: long_list0
let long_list2 = 999979 :: long_list1
...
let long_list78487 = 3 :: long_list78496
let long_list78498 = 2 :: long_list78497
let long_list = long_list78498

但这两种方法都导致了同样的结果（

Fatal error: exception Stack overflow

）。我是 OCaml 新手，我不明白为什么这不起作用。我对这个问题的答案很感兴趣——可能是一些猜测。当然，除了解决我的问题之外。

也许我可以以某种方式改变堆栈的限制？来自这个角度（编译器设置和标志）的答案将非常感激，但这作为最终答案并不真正令人满意，因为它可能不会无限期地扩展（不过我在这里可能是错的，谁知道呢？） .

为了完整性，以下是 lib/dune 文件内容：

; primes_with_generator/lib/dune
(library
 (name primes_with_generator)
 (libraries commons))

(rule
 (target prime_list.ml)
 (deps    (:gen ../generator/gen.exe))
 (action  (with-stdout-to %{target} (run %{gen} 1000000))))

1_000_000 是这里的一个参数——生成最多 1_000_000 的素数。对于生成最多 100_000 的素数，一切都很好，但我希望素数达到 sqrt(INT MAX) ≈ 2^32 ≈ 10^9...好吧，至少不想因为愚蠢而停在 ~200k原因是这样的。

Commons 可能无关紧要，但这是它的界面供您查看：

(* commons/prime.mli *)

(* given arguments:
 - list of primes up to a point, should be in ascending order, may be empty),
 - a number n >= 2
   returns answer to the question: is number n prime?
*)
val is_prime : int list -> int -> bool

Answer 1

我尝试定义一个包含 75,000 个整数的列表，实际上编译器在编译过程中耗尽了堆栈空间。这很有趣，但我认为程序必须受到一些限制。

我推测您对单独构建的列表的问题是编译器正在尝试进行常量折叠，即在编译时创建相同的大列表。

我能够通过在运行时进行串联来获得 75,000 个整数的列表。

本质上我定义了 75 个列表，每个列表有 1000 个整数。然后我定义了一个

int list list

类型的值，其中包含每个单独的列表。

最后我有：

let long_list = List.concat list_of_lists

主要功能如下：

let main () = Printf.printf (List.length long_list)

let () = main ()

当我运行它时，我看到这个：

$ ./big
75000