[Caml-list] strange tail recursion behavior by caml compiler

["S. Ted Sandler" <tsandler@seas.upenn.edu>]

Here's a question to those who are "in the know"
about when the caml compiler eliminates tail-calls.

I wrote the following tail-recursive function
"listbest", which is supposed to return the "best"
element of a list (where "best" is determined by the 
behavior of the "compare_fn" that is passed as an
argument).

Just for background, know that the "compare_fn"
should return +1 if arg1 is better than arg2, -1 if
arg2 is better than arg1, or 0 if they are equally
good.

So here's the problem.  When I write listbest like
this, it's not tail recursive.  I get stack overflow
exceptions on long lists:

  let listbest = fun compare_fn lst ->
    let rec listbest_rec = fun best lst_ ->
      match lst_ with
        | [] -> best
        | head :: tail ->
            let cmp = compare_fn head best in
              if cmp > 0
              then listbest_rec head tail
              else listbest_rec best tail
    in
      match lst with
        | [] -> raise
           (Invalid_argument "error: list is empty")
        | head :: tail ->
           listbest_rec head tail



BUT when I write "listbest" like this, it is:

  let listbest = fun compare_fn lst ->
    let rec listbest_rec = fun cmp_fn best lst_ ->
      match lst_ with
        | [] -> best
        | head :: tail ->
            let cmp = cmp_fn head best in
              if cmp > 0
              then listbest_rec cmp_fn head tail
              else listbest_rec cmp_fn best tail
    in
      match lst with
       | [] -> raise
          (Invalid_argument "error: list is empty")
       | head :: tail ->
          listbest_rec compare_fn head tail



The difference btwn these 2 defns doesn't seem like
one that should affect whether they are tail recursive,
does it?  Thanks in advance for shedding light on this.

-ted


PS I am using the ocaml-3.08 ocamlopt compiler.

PPS btw, "List.map", as defined in the ocaml stdlib,
is not tail recursive either.  Someone might want to
change that.

 let rec map f = function
     [] -> []
   | a ::l -> let r = f a in r :: map f l

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