7

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?

1
  • @Pascal Cuoq: You should post that as answer, so I can accept it ;-)
    – user350814
    Feb 4, 2011 at 9:33

3 Answers 3

15

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.

2
  • 8
    And to think of it another way: since recursion is the standard looping construct in functional languages, a recursion limit in OCaml would be equivalent to a limit on how many times a loop can run in C or Python. Feb 4, 2011 at 20:00
  • 1
    Only if the function is tail recursive, otherwise it will stackoverflow in the exception of a loop
    – 0xFF
    Feb 5, 2011 at 20:46
4

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

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.