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 QAA26464; Thu, 8 Jul 2004 16:54:55 +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 QAA26409 for ; Thu, 8 Jul 2004 16:54:54 +0200 (MET DST) Received: from herd.plethora.net (herd.plethora.net [205.166.146.1]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i68EsqSH003475 for ; Thu, 8 Jul 2004 16:54:53 +0200 Received: from bhurt.plethora.net (bhurt.plethora.net [205.166.146.49]) by herd.plethora.net (8.11.6/8.10.1) with ESMTP id i68ErNi00673; Thu, 8 Jul 2004 09:53:23 -0500 (CDT) Date: Thu, 8 Jul 2004 10:00:09 -0500 (CDT) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: Andreas Rossberg cc: caml-list Subject: Re: [Caml-list] Does Caml have slow arithmetics ? In-Reply-To: <40ED190E.3080005@ps.uni-sb.de> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at concorde with ID 40ED603C.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 rossberg:01 recursion:01 implemented:01 gcc:01 recursion:01 gcc:01 pushl:01 movl:01 movl:01 pushl:01 cmpl:01 $1,:01 decl:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Thu, 8 Jul 2004, 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. GCC has started optimizing tail calls in 3.x. I compiled: int fib(int a, int b, int n) { if (n <= 1) { return b; } else { return fib(b, a+b, n-1); } } with gcc 3.2.2 -O2, and got: .globl fib .type fib,@function fib: pushl %ebp movl %esp, %ebp movl 12(%ebp), %ecx pushl %ebx movl 16(%ebp), %edx movl 8(%ebp), %ebx .p2align 2,,3 .L4: cmpl $1, %edx jle .L5 leal (%ecx,%ebx), %eax decl %edx movl %ecx, %ebx movl %eax, %ecx jmp .L4 .L5: movl %ecx, %eax popl %ebx leave ret Notice that it's turned the tail call recursion into a loop. I don't recall it doing this back in 2.95 or 2.96, so it's a pretty recent improvement, but it does now exist. What it's limits are, I haven't determined, but it does exist. -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian ------------------- 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