Re: OCaml and tail recursion

[Jerome Vouillon <Jerome.Vouillon@inria.fr>]

Hello,

> I have just completed my first nontrival Caml program (an implementation
> of the rsync algorithm) and I am distressed about the treatment of
> tail calls.  My code has to go through files one character at a time,
> and as an SML programmer from way back, I wrote the code using three
> mutually recursive functions that make tail calls to each other.
> Imagine my surprise when I started getting errors with stack overflow!
> Apparently ocamlc doesn't optimize tail calls.

[Benjamin Pierce sent me your code]

You have written some functions such as this one:
  let string s = 
    let rec next k sum =
      try next (k+1) (append sum (String.get s k))
      with Invalid_argument _ -> sum in
    next 0 0
This function is not tail-recursive.  Indeed, an exception handler
need to be pushed on the stack at each invocation of the function
"next" and must remain until the recursive call terminates. It may be
possible here to only keep the last handler on the stack, but this
optimization cannot be done in the general case.

By the way, this kind of function does not use constant space under
SML/NJ either: the following function will happily eat all available
memory:
   fun f x = f x handle _ => 1;

-- Jérôme