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 TAA17334; Mon, 12 Jul 2004 19:07:40 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA17701 for ; Mon, 12 Jul 2004 19:07:39 +0200 (MET DST) Received: from yquem.inria.fr (yquem.inria.fr [128.93.8.37]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i6CH7cEV013203; Mon, 12 Jul 2004 19:07:38 +0200 Received: by yquem.inria.fr (Postfix, from userid 18180) id 3D928BBD8; Mon, 12 Jul 2004 19:07:38 +0200 (CEST) Date: Mon, 12 Jul 2004 19:07:38 +0200 From: Xavier Leroy To: brogoff Cc: caml-list@inria.fr Subject: Re: Tail calls (Was Re: [Caml-list] Does Caml have slow arithmetics ?) Message-ID: <20040712170738.GA3699@yquem.inria.fr> References: <20040707091308.GA26172@bourg.inria.fr> <20040707145803.GB27498@yquem.inria.fr> <1089227778.29648.81.camel@pelican.wigram> <20040708034455.GB29942@davidb.org> <40ED190E.3080005@ps.uni-sb.de> <20040708140408.GA2386@davidb.org> <20040708163653.A1260@beaune.inria.fr> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.3.28i X-Miltered: at nez-perce with ID 40F2C55A.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 arithmetics:01 tail-call:01 tail-call:01 ocamlc:01 recursion:01 passing:01 implemented:01 ocamlopt:01 callee:01 ocaml:01 ocaml:01 caml:01 feasible:01 bytecode:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk > 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