OCaml and tail recursion

OCaml and tail recursion

[Norman Ramsey]

Dear Camllists,

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.  I made some progress
by using ocamlopt, but I miss being able to use the debugger.
Do experienced Camllists have any suggestions?


Norman

Re: OCaml and tail recursion

[Xavier Leroy]

> 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!

I'd like to see the code, since ocamlc performs tail calls, of course.
(ocamlopt too, although on some platforms the tail-call optimization
doesn't apply to calls with many arguments, e.g. 8 or more.  But
ocamlc has no such limitation.)

- Xavier Leroy

Re: OCaml and tail recursion

[Alain Frisch]

On Mon, 13 Dec 1999, Norman Ramsey wrote:

> [snip]
> Apparently ocamlc doesn't optimize tail calls.

Yes it does. It is difficult to help if you don't give the code or its
structure. If you build a list with the characters you parse, consider
rewriting a code like :

let rec map f = function
 | h::t -> (f h)::(m f t)
 | _ -> []

(which is not tail recursive)

into something like:

let rec map f l =
 let rec aux accu = function
 | h::t -> aux ((f h)::accu) t
 | _ -> []
 in
 List.rev (aux [] l)

(List.rev is tail recursive)


Alain

Re: OCaml and tail recursion

[Jerome Vouillon]

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

Re: OCaml and tail recursion

[Jean-Francois Monin]

Since it is not always immediate to see if a function is
tail-recursive, a kind of compile time "assert" could be useful to
check this. E.g. some memory leaks could be prevented in this way.

  Jean-Francois