CODEWITHSUNDEEP
functional-programmingocamltail-recursion
user350814
user350814

Reputation:

Doesn't OCaml have any recursion checks?

I've been playing with OCaml recently, and promptly did my favourite thing to check how well developed a VM/Compiler really is, and wrote a recursive Program:

let rec f i =
    Printf.eprintf "i = %d\n" i;
    f(i+1);;

let () =
    f 0;;

The program runs as expected, however, the recursion NEVER breaks, infact, I had this program running for some times (roughly 30 minutes), redirected stderr to a File, to avoid clogging up my terminal. After checking the file, I was astounished when I noticed that the file was around 7*GB* big!

How can this be? Doesn't OCaml have any recursion limits?

Upvotes: 7

Views: 1191

Answers (3)

Steve Rowe
Steve Rowe

Reputation: 19413

Pascal is correct, but I think more explanation is in order because there are limits.

OCaml implements tail call recursion. If the return value of a function is wholly the result of a function call, then the call can be optimized. Consider these two pieces of code:

let rec foo i = 
  i * foo(i-1)

and

let rec bar i j = 
  bar(i - 1, j * i)

These both calculate the the same thing (and neither terminates). However, the first will cause a stack overflow and the 2nd will not. Why? Because foo does a calculation with the result of the function call. This means the value i need to be kept on the stack until foo (i - 1) returns. On the other hand, the result of bar is the result of the call bar (i - 1, j * i) with no modification. There is nothing that has to be kept on the stack.

Visualize it this way. Let's say we start with i = 3 (and j = 1). Foo would look like this:

foo(3)
  3 * foo (2)
    2 * foo (1)

and bar would look like this:

bar (3, 1)
bar (2, 3)
bar (1, 6)

Upvotes: 4

Pascal Cuoq
Pascal Cuoq

Reputation: 80355

You should look for information about tail-call optimization.

To answer your question, there is a stack limit, which would have been reached by your program if the stack was growing.

You shouldn't expect to reach it with your program any more than you would expect a division by zero in a useless expression in a C program to always produce a division by zero once compiled: the compiler might remove the useless division. In your example, the compiler removed the useless stack overflow.

Actually, it goes a bit further than that. As explained on the Wikipedia page, OCaml and most functional languages guarantee that the tail-call transformation is done, so that you can rely on it when using recursion.

Upvotes: 15

rlibby
rlibby

Reputation: 6021

Caveat, I don't know OCaml, but this is typical of a compiler or VM that implements tail call optimization. In the case of your function above, even the more limited optimization on tail recursion applies.

Upvotes: 0

Related Questions