From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 5A5D3BB9A for ; Mon, 3 Oct 2005 16:57:21 +0200 (CEST) Received: from ash25e.internode.on.net (ash25e.internode.on.net [203.16.214.182]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j93EvJdd011980 for ; Mon, 3 Oct 2005 16:57:20 +0200 Received: from rosella (ppp2-148.lns1.syd7.internode.on.net [59.167.2.148]) by ash25e.internode.on.net (8.12.9/8.12.6) with ESMTP id j93Ev7pG006125; Tue, 4 Oct 2005 00:27:08 +0930 (CST) (envelope-from skaller@users.sourceforge.net) Subject: Re: Ant: Re: Ant: Re: [Caml-list] Avoiding shared data From: skaller To: Thomas Fischbacher Cc: Martin Chabr , Pal-Kristian Engstad , caml-list@yquem.inria.fr In-Reply-To: References: <20051001210520.64728.qmail@web26809.mail.ukl.yahoo.com> <1128300118.10449.136.camel@rosella> Content-Type: text/plain Date: Tue, 04 Oct 2005 00:57:07 +1000 Message-Id: <1128351427.7573.61.camel@rosella> Mime-Version: 1.0 X-Mailer: Evolution 2.2.1.1 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 434146CF.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 avoiding:01 compilers:01 transforming:01 recursion:01 recursive:01 iterator:01 iterator:01 nodes:01 2005,:98 wrote:01 wrote:01 sourceforge:01 tail:01 data:02 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 On Mon, 2005-10-03 at 15:09 +0200, Thomas Fischbacher wrote: > On Mon, 3 Oct 2005, skaller wrote: > > > > I hope that one day functional language compilers will > > > do that optimization for you - convert a > > > non-tail-recursive code into a tail-recursive one. Do > > > you know of some progress in that direction? > > > > Isn't that just CPS? > > He presumably wanted to see a different thing, e.g. > automatically transforming I know. But his comment 'that's different' is inadequate. CPS transforms code so there are no function calls at all, (procedural form), or, in functional form, every function contains exactly one call which is always in tail position. So it certainly does what is required. Therefore the question is nonsense. The real question is more like asking if it is possible to transform a routine using O(n^k) store into one using O(n^j) store, where j < k. It is always possible to eliminate recursion: for example, a recursive descent of a simple tree can always be replaced by a using an iterator .. of course the iterator will have to retain a list of parent nodes to allow the traversal, so eliminating the 'recursion' does not save any storage. -- John Skaller Felix, successor to C++: http://felix.sf.net