确保OCAML功能是尾部回复

Question

我如何判断Ocaml是否将特定功能识别为尾部回复？ 特别是，我想找出OCAML编译器是否识别了圈的操作员和尾部递归

---

thanks to 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

其他其他人比我对OCAML内部设备更明智，但是对于简单的功能，在Ocamlopt生成的装配法规中看到尾巴递归非常容易：

$ 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

$ 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

递归是由实际的递归调用（不是尾部递归）处理的。

我说，如果您比我更好地了解OCAML中级形式，可能会有更好的方法来弄清楚这一点。

我想知道，为什么没有人告诉这个尊敬的选择，这会丢弃所有电话的注释。尽管使用组装是最确定的方法，但并不是每个人都擅长阅读组件。但是有了Annot，它是如此简单，您甚至可以自动化它。例如，鉴于您的代码位于

        .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

文件中，我们可以自动检查所有调用都处于尾部位置，并具有以下单线：

-annot

test.ml

Answer 3

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

将提取所有呼叫注释，并查看其内容。如果至少有一个堆栈呼叫，则

ocaml -annot test.ml

将返回true。

实际上，您甚至可以在Ocaml

存储库中找到它，它将从

test.annot

文件中提取此信息。例如，有一个

grep -A1 call test.annot

函数，它将显示在该点指定的函数的一种呼叫。但是，此功能当前具有一个错误（看起来不再支持它），要修复它，您需要对其应用以下补丁：

grep stack