OCaml中的尾调用转换

Question

我在课堂上被告知,由于在递归调用之后计算了布尔运算符,因此以下函数不是尾递归的:

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

但是这并没有将堆栈放在1000万大小的列表中,更重要的是,它是标准库中的实现.如果它不是尾递归,则没有理由使用这种形式而不是看似等效且明确的尾递归

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

然后堆栈确实在10米元素上爆炸.因此,当递归调用出现在右侧时,OCaml似乎只能利用这一点,这让我怀疑所有编译器都会用等效if表达式替换boolean op .有人可以确认或反驳这个吗？

Answer 1

告诉你这个人是错的.

实际上,||不会立即转换为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-modein Emacs为例,该命令M-x caml-types-show-call指向exists后面||将确认这是一个"尾调用",而当调用p x它时返回"堆栈调用".

Answer 2

如果有人写道:

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

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

但是||不是一个普通的操作符,而且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

这不是尾递归.