ocaml - OCaml 中的尾调用转换

Question

我在类里面被告知，由于在递归调用后评估了 bool 运算符，因此以下函数不是尾递归的:

let rec exists p = function
    [] -> false
  | a::l -> p a || exists p l

但这并没有把堆栈吹上千万大小的列表，更重要的是，它是标准库中的实现。如果它不是尾递归，就没有理由使用这种形式而不是看似等效且明显的尾递归

let rec exists p = function
    [] -> false
  | a::l -> if p a then true else exists p l

所以看起来 OCaml 编译器能够在像这样的简单情况下优化 bool 操作，以利用尾递归。但我注意到如果我像这样切换操作数的顺序

let rec exists p = function
    [] -> false
  | a::l -> exists p l || p a

那么堆栈确实在 10m 元素上被炸毁。所以看起来 OCaml 只能在递归调用出现在右侧时利用这一点，这让我怀疑编译器所做的只是用等效的 if 替换 bool 运算表达。有人可以证实或反驳吗？

Answer 1

告诉你这件事的人错了。

事实上，||不会立即转换为 if/then/else，而是通过编译器的中间语言保留一点，以便轻松启用两种不同的转换:

正如你所说，a || b in 表达位置被翻译成 if a then true else b

但是 a || b在测试位置，即 if a || b then c else d被翻译成不同的形式，比如 if a then goto c else if b then goto c else d , 当 goto c跳转到 c 的计算(只是翻译成 if a then c else if b then c 会复制 c 的代码)。这种优化更加神秘，用户无需意识到它就可以推断其程序的性能。

您可以在编译器的源代码中亲自查看。 ||原语表示为 Psequor ，感兴趣的文件是 asmcomp/cmmgen.ml对于 native 编译( (1) 、 (2) ])和 bytecomp/bytegen.ml用于字节码编译(两个方面同时处理，通过生成的字节码指令使用结果)。

一个小问题:您似乎说 OCaml 能够“在右侧”优化尾调用，因为这种情况“足够简单”，但不能在“左侧”进行优化，因为编译器不够聪明。如果调用出现在左边，则不是尾调用，所以一定不要优化。这不是一个“简单”的尾调用与否的问题。

最后，如果你想检查尾部是否是尾调用，你可以使用 OCaml 工具:用 -annot 编译选项将生成一个注释文件 foo.annot (如果您的来源是 foo.ml )，其中包含有关程序表达式类型的信息，以及有关函数调用是否是尾调用的信息。与 caml-mode例如，在 Emacs 中，命令 M-x caml-types-show-call指点一下exists后 ||将向我确认这是一个“尾调用”，而当被调用时 p x它返回“堆栈调用”。