CODEWITHSUNDEEP
ocaml
Jackson Tale
Jackson Tale

Reputation: 25842

Will OCaml compiler deal with boolean operators to make recursion tail-recursive?

Let's have a look at the following function is_prime:

let is_prime n =
  let rec div_check i = i * i > n || (n mod i <> 0 && div_check (i+1))
  in
  n >= 2 && div_check 2

So if n mod i <> 0 is false, then it will stop.

But if n mod i <> 0 is true, then it will recursively continue.

My question is if it continues, has OCaml optimised the compiler so only return div_check(i+1) directly, i.e., tail-recursive? Or will it still hold the true && part and wait for div_check to return?

ps the function is taken from http://www.cs.cornell.edu/Courses/cs3110/2014sp/lectures/2/lec02.html

Upvotes: 4

Views: 382

Answers (1)

ivg
ivg

Reputation: 35280

The answer is yes. I've simplified your example, to make the compiler output more understandable:

let rec is_prime n =
  let rec div_check i =
    i * i > n || (i + i < n && div_check (i+1)) in
  div_check n

Given this input, compiler will emit the following assembly (I've added some annotations):

camlIs_prime__div_check_1010:
.L102:
    movq    16(%rbx), %rdi
    movq    %rax, %rsi
    sarq    $1, %rsi
    movq    %rax, %rdx
    decq    %rdx
    imulq   %rsi, %rdx           ; i * i
    incq    %rdx
    cmpq    %rdi, %rdx           ; if i * i <= n then return
    jle .L101
    movq    $3, %rax
    ret
.L101:
    movq    16(%rbx), %rdi
    leaq    -1(%rax, %rax), %rsi ; i + i
    cmpq    %rdi, %rsi           ; i + i ? n
    jge .L100                    ; if i + i >= n then return
    addq    $2, %rax             ; else i := i + 1
    jmp .L102                    ;      div_check i
.L100:
    movq    $1, %rax
    ret

But be cautious, this will work only for vanilla OCaml's short-circuit operators. Even such harmless change as, let (&&) = (&&) will break it, and jmp .L102, will be substituted with call camlIs_prime__div_check_....

Also, this will only work if the call is to the right of the short-circuit operator. Left expression is marked as non tail-recursive. I've tested it and, indeed, putting div_check to the left of the && operator will emit non tail-recursive code.

If you're in doubt whether the call is tail or not, you can always add -annot flag to the compiler, and look at the corresponding *.annot file, for call (tail) annotations. There is some tooling support in merlin for that, but I've not figured out on how to use it properly. And keep in mind, that the final judge is still the assembly output.

Upvotes: 4

Related Questions