为什么 OCaml 中没有函数头？

Question

在某些编程语言中，尤其是在 C 语言中，存在带有函数声明的头文件。这些函数 "headers" 出现在代码之前，并且在相互递归的情况下是必需的。当函数头放在头文件中时，它们还有助于链接多个 C 文件一起编译的情况。

我对 C 文件中的函数头文件的理解是它们有助于编译，因为如果在定义函数之前调用函数，它们会定义函数的类型。如果这是错误的，我很乐意接受纠正并更好地了解情况，但这是我的理解。

所以我不明白的是，为什么其他语言——在本例中我挑出 OCaml——没有函数头。在 OCaml 中，存在带有签名的模块，但是签名不允许您的函数实例化相互递归，即使给出了类型。为了在 OCaml 中实现相互递归，您需要使用 "and" 关键字，或者在另一个函数中本地定义一个函数（据我所知）。

(* version 1 *)
let rec firstfun = function
  | 0 -> 1
  | x -> secondfun (x - 1)
and secondfun = function
  | 0 -> 1
  | x -> firstfun x

(* version 2 *)
let rec firstfun = function
  | 0 -> 1
  | x -> 
       let rec secondfun = function
         |0 -> 1
         | x -> firstfun x in
       secondfun (x - 1)

那么为什么会这样呢？跟多态有关吗？有没有我没有考虑的编译瓶颈？

Answer 1

首先，您似乎暗示C头文件的主要目的是相互递归。我不同意这一点。相反，我将 C 头文件视为 interface/implementation 分离的尝试。从这个意义上说，与 C 相比，OCaml 并不缺少任何东西。

现在是相互递归本身：它不支持跨不同的编译单元。（同一编译单元中的不同模块之间支持它。）但它可以使用高阶函数以某种方式模拟。在我开始之前，您的示例是不正确的 OCaml 语法。更正后的版本是：

(* version 1 *)
let rec firstfun = function 0 -> 1
  | x -> secondfun (x - 1)
and secondfun = function 0 -> 1
  | x -> firstfun x

现在，如何将其传播到可能位于不同编译单元中的不同模块中（附带条件，在这种情况下 First_module 必须首先编译）：

module First_module = struct
  let rec firstfun secondfun = function 0 -> 1
    | x -> secondfun (x - 1)
end

module Second_module = struct
  let rec secondfun = function 0 -> 1
    | x -> First_module.firstfun secondfun x
end

请注意 First_module.firstfun 的类型不是您示例中的 int -> int，而是 (int -> int) -> int -> int。也就是说，该函数需要一个额外的参数，即尚未定义的secondfun。所以我们用参数传递（发生在运行时（尽管足够优化的编译器可能会通过再次链接来代替它。））代替链接（发生在编译时）。

（旁注：firstfun 定义中的 rec 不再需要。为了与您的代码相似，我将其留在那里。）

编辑：

在评论中你扩展了你的问题：

That being said, I am wondering why OCaml requires let-and notation within a module, as opposed to having predeclared function headers at the top of the module definition.

抛开实用性不谈，实际上可以用递归模块模拟（警告：从 4.02 开始，该功能被标记为实验性的。）如下：

module rec All : sig
  val firstfun : int -> int
  val secondfun : int -> int
end = struct

  let firstfun = function 0 -> 1
    | x -> All.secondfun (x - 1)

  let secondfun = function 0 -> 1
    | x -> All.firstfun x

end

include All

您问题的总体答案可能是：C 和 OCaml 是不同的语言。他们以不同的方式做事。

Answer 2

Ocaml 有模块接口文件 .mli，其作用等同于 C 和 C++ 中的 header 文件 .h。阅读 §2.5 Modules and Separate Compilation chapter of the Ocaml documentation. Actually what is important is the .cmi compiled form of these module interface files. (In C with GCC precompiled headers are very limited).

顺便说一句，C++ header 文件是一场噩梦。大多数标准 C++ headers（例如 <map>）实际上拉动了数千行。在我的 GCC6 Linux 系统上，一个仅包含 #include <vector> 的简单文件被扩展到一万多行（这也是编译 C++ 代码可能非常慢的原因之一）。

C++标准化团队已经讨论了将模块纳入标准的问题，但目前还没有被接受。顺便说一句，这表明模块比 header 文件更有用且更干净。阅读 Clang's Modules 文档。

^{最新的编程语言都有某种编译模块或包（Ada、Go、D、...）}

C header 文件不那么混乱（但 C 没有通用性）并且实际上比 C++ 文件小。

Ocaml 实现文件可以（并且经常有）相当长的 let rec top-level 定义，如

let rec 
 foo x y = 
 (* many lines *)
 .....
and 
 bar z t = 
 (* many lines *)
 ....
and 
 freezbee u v w = 
 (* many lines *)
 ....

(**** the above let rec definition can span many thousand lines *)

如果您需要在多个 Ocaml 模块中定义相互递归函数，您可以将递归模块用作 answered by kne 或者您可以定义初始化为存根函数的引用异常：

let refoo = ref (fun (x : int) -> failwith "refun unitialized");;

在同一模块的其他部分，您将调用 !refoo y（而不是例如调用 foo y...）并且您需要一些代码来填充 refoo 具有有意义的功能。 IIRC 这个技巧在 Ocaml 编译器本身中使用了几次。

Answer 3

事实上，这与 headers 无关，因为它们只是一些代码，使用预处理器 copy-pasted 到文件中。你的问题的根源是为什么我们需要一个外部值的完整定义，以便编译一个单元。例如，在 C 中，您可以自由使用任何外部函数，前提是您提供了原型，而在旧版本的 C 中，您甚至不需要原型。

它起作用的原因是因为由 C 编译器生成的编译单元将包含未解析的符号（例如，在其他地方定义的函数或数据值），连接这些符号是链接器的工作到他们各自的实现。

OCaml，在引擎盖下，使用 C-like 编译单元格式，实际上依赖于系统 C 链接器来生成可执行文件。因此，到目前为止没有实际或理论上的限制。

那么问题是什么？只要你能提供一个外部符号的类型，你就可以很容易地使用它。这是主要问题——如果两个编译单元（即文件）之间存在相互依赖（在类型级别），则 OCaml 类型检查器无法推断类型。此限制主要是技术性的，因为类型检查器在编译单元级别上工作。这种限制的原因主要是历史原因，因为在编写 OCaml 编译器的时候，分离编译很流行，因此决定在每个文件的基础上应用类型检查器。

总而言之，如果您能够提供 OCaml 类型检查器将接受的类型，那么您可以轻松地在编译单元之间引入相互递归。要移动类型检查器，您可以使用不同的机制，例如 Obj 模块或 external 定义。当然，在那种情况下，您要对类型定义的健全性承担全部责任。基本上和C语言一样。

由于您始终可以从支持单独编译的编译器生成 whole-program 编译系统，只需将所有模块连接到一个大模块中，替代解决方案是使用某种预处理器这将收集所有定义，并将它们复制到一个文件中（即一个编译单元），然后将编译器应用于它。

为什么 OCaml 中没有函数头？

Why aren't there function headers in OCaml?

c

ocaml

programming-languages

mutual-recursion