Убедитесь, что функция OCaml является хвостовой рекурсивной

Как я могу сказать, распознает ли OCaml определенную функцию как хвостовую рекурсивную? В частности, я хочу выяснить, распознает ли компилятор OCaml короткозамкнутые операторы и хвостовую рекурсию

Благодаря ответу Джеффри ниже, я попытался сделать это с помощью простой функции

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
3 6
compiler-construction short-circuiting tail-recursion ocaml

3 ответа:

Начиная с 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
6

Многие другие более мудры, чем я, в отношении внутренних функций 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 лучше, чем я.
7

Я удивляюсь, почему никто не сказал о почтенной опции -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, которое вы можете найти в репозитории 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))
1