Re: Tail calls (Was Re: [Caml-list] Does Caml have slow arithmetics ?)

[Xavier Leroy <Xavier.Leroy@inria.fr>]

> Many ocaml programs depend on tail-call elimination, although I don't
> believe anything in the docs requires it to be done.

Just for the record, here is the exact situation regarding tail-call
elimination in OCaml.  It is performed in any of the following
situations:

1- Compilation to bytecode (with ocamlc).
2- When the function being tail-called is the current function
   (tail recursion).
3- When the function being tail-called has no more than N arguments,
   keeping in mind that a function with free variables has one extra
   hidden argument representing its environment.

Here, N is a constant that depend on the target processor: it's 6 for
the Intel x86, and 10 or more for the other supported processors.
This constant is the number of processor registers used for parameter
passing.  The tail-call issue appears when extra parameters need to be
passed on stack.

In other words, the only case where tail-call elimination isn't
performed is: native-code compilation, more than N arguments, and the
function being tail-called is not the current function.

Before case 2 (tail call to self) was implemented, we often received
problem reports from x86 users.  Since the addition of case 2, we
haven't received any.  This makes me suspect that the lack of
tail-call elimination in the situation described above isn't that much
of a problem in practice.

Proper elimination of tail calls in ocamlopt in all cases is feasible
but requires a bit of work.  In particular, the current code
generation convention "caller deallocates stack-allocated arguments"
must be changed to "callee deallocates stack-allocated arguments".
Also, some stack manipulations are needed that would make tail-calls
slightly more expensive (in time) than regular calls.

- Xavier Leroy

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners