ocaml - 为什么编译器认为这个函数是非尾递归的？

Question

我正在解决 one of the OCaml tutorials 中发布的问题。其中之一是编写一个函数来计算列表的长度。它应该是尾递归的。

简单的非尾递归解决方案是:

let rec length_naive xs  = (** Not tail recursive *)
  match xs with
  | [] -> 0
  | _ :: xs -> 1 + length_naive xs;;

(length_naive [@tailcall]) [1, 2, 3, 4];;

let one_hundred_million = 100000000;;
let non_tail_result = length_naive(List.init one_hundred_million (Fun.id));;
print_endline("Non-tail-recursive result: " ^ string_of_int(non_tail_result));;

编译并运行它完全符合预期。打印警告(由于 @tailcall)，并且由于堆栈溢出而执行失败:

$ ocamlc lib/so.ml
File "lib/so.ml", line 14, characters 0-39:
14 | (length_naive [@tailcall]) [1, 2, 3, 4];;
     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 51 [wrong-tailcall-expectation]: expected tailcall

$ ./a.out
Fatal error: exception Stack_overflow

现在是我尝试编写尾递归版本的时候了:

let length xs =
  let rec f xs len =
    match xs with
    | [] -> len
    | _ :: xs -> f xs (len + 1)
  in
  f xs 0;;

(length [@tailcall]) [1, 2, 3, 4];;

let one_hundred_million = 100000000;;
let tail_result = length(List.init one_hundred_million (Fun.id));;
print_endline("Tail recursive result: " ^ string_of_int(tail_result));;

编译并运行:

$ ocamlc lib/so.ml
File "lib/so.ml", line 15, characters 0-33:
15 | (length [@tailcall]) [1, 2, 3, 4];;
     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 51 [wrong-tailcall-expectation]: expected tailcall

$ ./a.out
Tail recursive result: 100000000

所以它有效，堆栈溢出异常没有被抛出。但是，编译器会警告该函数不是尾递归的。我的问题是:

• 如果这个函数是尾递归的，为什么编译器会打印警告？
• 如果这个函数不是尾递归，为什么会这样？

我使用的是 OCaml 编译器 v 4.14.0。

Answer 1

尾递归函数和尾调用可优化(函数)调用是两个不同的概念。 tail-call 是函数调用的属性，而 tail-recursive 是函数的属性。

在你的例子中

length []

是对尾递归函数的非尾调用优化调用。

length 定义内的函数调用是尾部调用可优化的:

  let rec f xs len =
    match xs with
    | [] -> len
    | _ :: xs -> (f[@tailcall]) xs (len + 1)

更明确地说，

• 当可以重用当前堆栈帧从而避免分配新的堆栈帧时，函数调用是尾部调用可优化的。特别是，如果可以快捷返回地址，则在递归函数定义内调用递归函数可能会重用父调用堆栈。

• 当函数体内对函数 f 的所有调用都是尾调用可优化时，该函数就是尾递归的。