验证一个OCaml函数是否为尾递归

Question

我怎么知道OCaml是否将特定函数识别为尾递归？特别地，我想找出OCaml编译器是否识别短路运算符和尾递归。

---

感谢Jeffrey在下面的答案，我使用了这个简单函数进行测试

let rec check_all l =
    match l with
    | [] -> true
    | hd :: tl ->
        hd && check_all tl

实际上，它确实进行了优化，结果为：

camlTest__check_all_1008:
        .cfi_startproc
.L102:
        cmpl    $1, %eax
        je      .L100
        movl    (%eax), %ebx
        cmpl    $1, %ebx
        je      .L101
        movl    4(%eax), %eax
        jmp     .L102
        .align  16
.L101:
        movl    $1, %eax
        ret

- dspyz

Answer 1

从OCaml 4.03开始，尽管在Changes文件中存在拼写错误，您仍然可以在函数应用中使用@tailcall，并且编译器会在不是尾调用的情况下发出警告。

(f [@tailcall]) x y会在f x y不是尾调用时发出警告

例如：

$ cat tailrec.ml
let rec f a x = if x <= 1 then a else (f [@tailcall]) (a * x) (x - 1)

let rec g x = if x <= 1 then 1 else x * (g [@tailcall]) (x - 1)

$ ocaml tailrec.ml

File "tailrec.ml", line 3, characters 40-63:
Warning 51: expected tailcall

- anol

Answer 2

对于OCaml内部，许多人比我聪明，但对于简单的函数来说，很容易在ocamlopt生成的汇编代码中看到尾递归：

$ cat tailrec.ml
let rec f a x = if x <= 1 then a else f (a * x) (x - 1)

let rec g x = if x <= 1 then 1 else x * g (x - 1)
$ ocamlopt -c -S tailrec.ml

如果你忽略了很多额外的输出，你会看到以下关于f的内容：

_camlTailrec__f_1008:
        .cfi_startproc
.L101:
        cmpq    $3, %rbx
        jg      .L100
        ret
        .align  2
.L100:
        movq    %rbx, %rdi
        addq    $-2, %rdi
        sarq    $1, %rbx
        decq    %rax
        imulq   %rbx, %rax
        incq    %rax
        movq    %rdi, %rbx
        jmp     .L101
        .cfi_endproc

编译器已将递归调用转换为循环（即函数是尾递归的）。

下面是对于`g`的输出结果：

        .cfi_startproc
        subq    $8, %rsp
        .cfi_adjust_cfa_offset  8
.L103:
        cmpq    $3, %rax
        jg      .L102
        movq    $3, %rax
        addq    $8, %rsp
        .cfi_adjust_cfa_offset  -8
        ret
        .cfi_adjust_cfa_offset  8
        .align  2
.L102:
        movq    %rax, 0(%rsp)
        addq    $-2, %rax
        call    _camlTailrec__g_1011
.L104:
        movq    %rax, %rbx
        sarq    $1, %rbx
        movq    0(%rsp), %rax
        decq    %rax
        imulq   %rbx, %rax
        incq    %rax
        addq    $8, %rsp
        .cfi_adjust_cfa_offset  -8
        ret
        .cfi_adjust_cfa_offset  8
        .cfi_endproc

这个递归是通过实际的递归调用处理的（而不是尾递归）。

正如我所说，如果您对OCaml中间形式的理解比我更好，可能有更好的方法来解决这个问题。

- Jeffrey Scofield

---

好答案（+1）。准确地说，一个人应该谈论尾调用和尾调用优化。问题实际上是关于OCaml是否优化尾调用，而不是它是否识别它们（无论这意味着什么）。 - Giorgio

随着事情变得更加复杂，编译器的-annot选项输出中也提供了更多信息。一种展示类型注释的工具可以用来在文件中添加尾调用信息。ocamlopt[.opt]的-dlinear选项也会在修改后的源代码输出中包含带有尾调用的注释。 - nlucaroni

Answer 3

我想知道为什么没有人提到尊敬的-annot选项，它将转储所有调用的注释。虽然使用汇编是最可靠的方法，但并不是每个人都擅长阅读汇编语言。但是使用annot非常容易，甚至可以自动化。例如，假设您的代码位于test.ml文件中，我们可以使用以下一行命令自动检查所有调用是否处于尾部位置：

 ocamlc -annot test.ml && if grep -A1 call test.annot | grep stack; then echo "non tailrecursive"; exit 1; fi

使用ocaml -annot test.ml编译文件会生成一个test.annot文件，其中包含每个表达式的注释。使用grep -A1 call test.annot提取所有调用注释并查看其内容。如果存在至少一个堆栈调用，则使用grep stack将返回true。

实际上，甚至有一个emacs补充程序，可以在the ocaml库中找到，它可以从annot文件中提取此信息。例如，有一个caml-types-show-call函数，将显示指定点处函数的一种调用方式。但是，该函数目前存在错误（似乎不再受支持），要修复它，您需要对其应用以下补丁：

--- a/emacs/caml-types.el
+++ b/emacs/caml-types.el
@@ -221,7 +221,7 @@ See `caml-types-location-re' for annotation file format."
               (right (caml-types-get-pos target-buf (elt node 1)))
               (kind (cdr (assoc "call" (elt node 2)))))
           (move-overlay caml-types-expr-ovl left right target-buf)
-          (caml-types-feedback kind)))))
+          (caml-types-feedback "call: %s" kind)))))
     (if (and (= arg 4)
              (not (window-live-p (get-buffer-window caml-types-buffer))))
         (display-buffer caml-types-buffer))

- ivg

---

也许你应该提交一个 PR？ - HappyFace

可能，但我不想给OCaml开发人员增加太多负担，因为这是一个如此微小的PR（有很多未决的PR），更好的想法是将此代码提取到单独的存储库中。此外，我相信我在ocaml/merlin中看到了类似的东西。 - ivg