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 QAA23608; Thu, 8 Jul 2004 16:07:28 +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 QAA23970 for ; Thu, 8 Jul 2004 16:07:27 +0200 (MET DST) Received: from mail.davidb.org (adsl-64-172-240-129.dsl.sndg02.pacbell.net [64.172.240.129]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i68E7PSH029728 for ; Thu, 8 Jul 2004 16:07:26 +0200 Received: from davidb by mail.davidb.org with local (Exim 3.36 #1 (Debian)) id 1BiZVR-0000dn-00; Thu, 08 Jul 2004 07:04:09 -0700 Date: Thu, 8 Jul 2004 07:04:09 -0700 From: David Brown To: Andreas Rossberg Cc: caml-list Subject: Re: [Caml-list] Does Caml have slow arithmetics ? Message-ID: <20040708140408.GA2386@davidb.org> 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> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <40ED190E.3080005@ps.uni-sb.de> User-Agent: Mutt/1.5.4i X-Miltered: at concorde with ID 40ED551D.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 caml-list:01 arithmetics:01 2004:99 rossberg:01 recursion:01 implemented:01 gcc:01 recursion:01 gcc:01 pointers:01 tail-call:01 tail-call:01 compiler:01 semantics:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Thu, Jul 08, 2004 at 11:51:10AM +0200, Andreas Rossberg wrote: > David Brown wrote: > > > >In some functional languages (Scheme, specifically), tail recursion is > >required to be implemented iteratively. It is a common enough idiom, > >and easy enough to implement, that it is generally done in functional > >languages. In fact, gcc does it in C, with enough optimization. > > The latter is, to a certain extent, a myth. > First, you have to distinguish between simple tail *recursion*, and the > much more general concept of tail *call*. I believe Scheme requires to > fully optimize the latter, and so it is done by all decent FPL > implementations. GCC does not do that, already falling short of mutually > recursive functions, IIRC. I just tested it, and gcc did tail call of two, (simple) mutually recursive functions. If they aren't simple enough, it doesn't. > Second, a C compiler can only optimize tail recursion under limited > circumstances, because generally the C language semantics prevent it > (once more due to pointers, particularly C allowing - and its libraries > relying on - taking the address of local variables). Last time I heard > of it, it was said that GCC is having a hard time doing anything > practically usefull at all. C is certainly going to limit the cases where tail-call elimination can be done. It also isn't very obvious where it can, so it isn't useful to depend on. Many ocaml programs depend on tail-call elimination, although I don't believe anything in the docs requires it to be done. Dave ------------------- 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