From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id VAA06715; Wed, 25 Aug 2004 21:57:08 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id VAA05148 for ; Wed, 25 Aug 2004 21:57:07 +0200 (MET DST) Received: from stag.seas.upenn.edu (stag.seas.upenn.edu [158.130.70.79]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id i7PJv5WQ014552 (version=TLSv1/SSLv3 cipher=EDH-RSA-DES-CBC3-SHA bits=168 verify=NO) for ; Wed, 25 Aug 2004 21:57:06 +0200 Received: from red.seas.upenn.edu (RED.seas.upenn.edu [158.130.64.176]) by stag.seas.upenn.edu (8.12.10/8.12.10) with ESMTP id i7PJv5lG017007 (version=TLSv1/SSLv3 cipher=EDH-RSA-DES-CBC3-SHA bits=168 verify=NOT) for ; Wed, 25 Aug 2004 15:57:05 -0400 Received: from red.seas.upenn.edu (localhost [127.0.0.1]) by red.seas.upenn.edu (8.12.10/8.12.9) with ESMTP id i7PJv40S014354 for ; Wed, 25 Aug 2004 15:57:04 -0400 (EDT) Received: (from tsandler@localhost) by red.seas.upenn.edu (8.12.10/8.12.9/Submit) id i7PJv43m014351 for caml-list@inria.fr; Wed, 25 Aug 2004 15:57:04 -0400 (EDT) Date: Wed, 25 Aug 2004 15:57:04 -0400 From: "S. Ted Sandler" To: caml-list@inria.fr Subject: [Caml-list] strange tail recursion behavior by caml compiler Message-ID: <20040825195704.GA11359@red.seas.upenn.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.4.2.1i X-Miltered: at concorde with ID 412CEF11.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; ted:99 recursion:01 ocamlopt:01 stdlib:01 compiler:01 compiler:01 ocaml:01 caml:01 caml:01 ocaml-:01 rec:01 rec:01 overflow:02 match:02 match:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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