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

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

[S. Ted Sandler]

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

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

[Damien Doligez]

On Aug 25, 2004, at 21:57, S. Ted Sandler wrote:

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

[... 2 different versions of listbest ...]

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

I've just tried both versions of listbest on a list
of 50 million elements, and got no stack overflow, either
in bytecode or in native code.

So I guess it's architecture-dependent and it's a variant
of the old "not enough registers on a Pentium" problem.
But how exactly, I don't know.

-- Damien

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

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

[Xavier Leroy]

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

Your two versions of listbest are both tail-recursive, even on a
register-starved x86 processor, as shown by a quick look at the asm
generated by ocamlopt. Either you've simplified your code a
little too much before posting, or the stack overflow comes from
elsewhere in your code.

- 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