6

我在课堂上被告知，以下函数不是尾递归，因为布尔运算符在递归调用之后被评估：

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 编译器能够在像这样的简单情况下优化布尔运算以利用尾递归。但我注意到，如果我像这样切换操作数的顺序

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

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

4

3 回答 3

12

告诉你这件事的人是错误的。

实际上，||并不是马上翻译成 if/then/else，而是通过编译器的中间语言保留了一点，以便轻松实现两种不同的转换：

  1. 正如你所说，a || b在表达位置被翻译成if a then true else b
  2. 但是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用于原生编译（(1)，(2) ]），以及bytecomp/bytegen.ml用于字节码编译（两个方面同时处理，通过生成使用结果的字节码的指令）。

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

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

于 2012-07-08T07:07:59.093 回答
9

如果有人写道：

let rec add_result p = function
  [] -> 0
| a::l -> p a + add_result p l

这不会是尾递归，因为在递归调用之后，函数必须添加两个结果。

But||不是普通运算符，A || B严格等价于if A then true else B，所以当你写

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

并且函数是尾递归的。

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

相当于

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

这不是尾递归。

于 2012-07-08T06:33:08.063 回答
2

雷米的回答是完全正确的。请注意，某些类型系统与 OCaml 不同的语言会自动将某些非布尔值强制转换为布尔值。这些语言可以选择使用 (||) 之类的运算符：要么不尝试将 rhs 的结果强制转换为布尔值，而是返回给定的任何内容，或者进行强制转换，但在 rhs 之后你还有一些工作要做被评估，所以你放弃了 (||) 的尾递归。你不能两者兼得。也许您的线人是按照这些思路思考的，这就是为什么他们错误地说他们对 OCaml 做了什么。鉴于 OCaml 对类型的严格处理，您不能true || succ 5一开始就这么说。

于 2012-07-08T07:17:46.693 回答