CODEWITHSUNDEEP
ocamltail-recursion
kamituel
kamituel

Reputation: 35960

Why is compiler considering this function non tail recursive?

I'm solving problems posted in one of the OCaml tutorials. One of them is to write a function that will calculate the length of the list. It should be tail-recursive.

The naive, non tail-recursive solution is:

let rec length_naive xs  = (** Not tail recursive *)
  match xs with
  | [] -> 0
  | _ :: xs -> 1 + length_naive xs;;

(length_naive [@tailcall]) [1, 2, 3, 4];;

let one_hundred_million = 100000000;;
let non_tail_result = length_naive(List.init one_hundred_million (Fun.id));;
print_endline("Non-tail-recursive result: " ^ string_of_int(non_tail_result));;

Compiling and running this works exactly as expected. The warning (due to @tailcall) is printed, and the execution fails due to the stack getting overfown:

$ ocamlc lib/so.ml
File "lib/so.ml", line 14, characters 0-39:
14 | (length_naive [@tailcall]) [1, 2, 3, 4];;
     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 51 [wrong-tailcall-expectation]: expected tailcall

$ ./a.out
Fatal error: exception Stack_overflow

Now time for my attempt at writing a tail recursive version:

let length xs =
  let rec f xs len =
    match xs with
    | [] -> len
    | _ :: xs -> f xs (len + 1)
  in
  f xs 0;;

(length [@tailcall]) [1, 2, 3, 4];;

let one_hundred_million = 100000000;;
let tail_result = length(List.init one_hundred_million (Fun.id));;
print_endline("Tail recursive result: " ^ string_of_int(tail_result));;

Compiling and running it:

$ ocamlc lib/so.ml
File "lib/so.ml", line 15, characters 0-33:
15 | (length [@tailcall]) [1, 2, 3, 4];;
     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 51 [wrong-tailcall-expectation]: expected tailcall

$ ./a.out
Tail recursive result: 100000000

So it works, stack overflow exception didn't get thrown. However, compiler warns about the function not being tail recursive. My questions are:

I'm using OCaml compiler v 4.14.0.

Upvotes: 2

Views: 136

Answers (1)

octachron
octachron

Reputation: 18892

A tail-recursive function and a tailcall optimizable (function) call are two different notions. Being tail-call is a property of function calls, whereas being tail-recursive is a property of functions.

In your example

length []

is a not tail-call optimizable call to a tail-recursive function.

It is the function calls inside the definition of length that are tail-call optimizable:

  let rec f xs len =
    match xs with
    | [] -> len
    | _ :: xs -> (f[@tailcall]) xs (len + 1)

More explicitly,

  • A function call is tail-call optimizable when it is possible to reuse the current stack frame and thus avoid allocating a new stack frame. In particular, calls to recursive function inside the definition of the recursive function might reuse the parent call stack if it is possible to shortcut the return address.

  • A function is tail-recursive when all calls to the function f in its body are tail-call optimizable.

Upvotes: 5

Related Questions