Verify that an OCaml function is tail-recursive

Question

How can I tell if OCaml recognizes a particular function as tail-recursive? In particular, I want to find out if the OCaml compiler recognizes Short-circuited operators and tail recursion

---

Thanks to Jeffrey's answer below, I tried this with the simple function

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

and indeed, it does optimize to:

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

Watch

Answer 1

Starting from OCaml 4.03, and despite the typo in the Changes file, you can use @tailcall in a function application and the compiler will warn if it is not the case.

(f [@tailcall]) x y warns if f x y is not a tail-call

Example:

$ 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

Attenweiler

Answer 2

Many others are wiser than I am about OCaml internals, but for simple functions it's pretty easy to see tail recursion in the generated assembly code of 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

If you ignore a lot of extra output you see this for 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

The compiler has changed the recursive call into a loop (i.e., the function is tail recursive).

Here's what you get for 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

The recursion is handled by an actual recursive call (not tail recursive).

As I say, there may be better ways to figure this out if you understand the OCaml intermediate forms better than I do.

Alkalinity

Good answer (+1). To be precise, shouldn't one speak about tail-call and tail-call optimization? What the question really is about if whether OCaml optimizes tail calls, not whether it recognizes them (whatever that means). – Clipboard

As things get more complicated, the information is also provided in the output of the -annot option to the compilers, a tool to show the type annotations could decorate the file with tail-call information. The -dlinear option of ocamlopt[.opt] will also have annotatoins in the modified source output with tail-calls. – Toffee

Answer 3

I wonder, why nobody told about the venerable -annot option, that will dump annotations for all calls. Although using assembly is the most sure method, not everyone is good at reading the assembly. But with annot it is so easy, that you can even automate it. For example, given that your code is in test.ml file, we can automatically check that all calls are in a tail position with the following one-liner:

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

The ocaml -annot test.ml will compile a file an create test.annot file, that will contain an annotation for each expression. The grep -A1 call test.annot will extract all call annotations, and look at their contents. The grep stack will return true, if there is at least one stack call.

There is actually even a emacs complement, that you can find in the ocaml repository, that will extract this information from the annot file. For example, there is a caml-types-show-call function, that will show a kind of call of a function, specified at the point. However, this function currently has a bug (it looks like it is no longer supported), to fix it you need to apply the following patch to it:

--- 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))

Abad

Perhaps you should submit a PR? – Triune

probably, but I don't want to overburden OCaml developers with so minor PR (that have lots of pending PRs), much better idea would be to extract this code into a separate repo. Also, I believe, that I saw a similar in ocaml/merlin. – Abad