验证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

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

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中间形式,可能有更好的方法来解决这个问题.