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 CAA09823; Thu, 30 Jan 2003 02:44:30 +0100 (MET) 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 CAA11429 for ; Thu, 30 Jan 2003 02:44:29 +0100 (MET) Received: from grace.speakeasy.org (grace.speakeasy.org [216.254.0.2]) by nez-perce.inria.fr (8.11.1/8.11.1) with SMTP id h0U1iRv03249 for ; Thu, 30 Jan 2003 02:44:28 +0100 (MET) Received: (qmail 29474 invoked by uid 36130); 30 Jan 2003 01:44:21 -0000 Received: from localhost (sendmail-bs@127.0.0.1) by localhost with SMTP; 30 Jan 2003 01:44:21 -0000 Date: Wed, 29 Jan 2003 17:44:21 -0800 (PST) From: brogoff@speakeasy.net To: Andrew Kennedy cc: Brian Hurt , Ocaml Mailing List Subject: RE: [Caml-list] @, List.append, and tail recursion In-Reply-To: <92FC642DD24AC94AA356906BD9FCD2D8D8422F@tvp-msg-03.europe.corp.microsoft.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Thanks for the reference. I get nailed by this a couple of times a year, and I usually just blame myself for being sloppy and recode all of my maps, appends, and filters to remove it. I think it would be great if those three functions (at least) could be tail recursive, either by having the compiler do it or by providing these "hole abstractions" in the language. I wonder, like the other Brian, if there are existing ML compilers which implement this optimization, and if there is any chance we'll see this in OCaml? On Fri, 24 Jan 2003, Andrew Kennedy wrote: > Brian, > > The optimization you describe is sometimes known as > "tail modulo cons", and is an example of "destination-passing > style". In other words, the place to put the result (in > this case, the address of the tail of a just-constructed > cons cell) is passed on in a tail-recursive call. > > See "A Functional Representation of Data Structures with a Hole" > by Minamide in POPL'98. > > http://www.score.is.tsukuba.ac.jp/~minamide/index.html > > Although Minimide formalizes the problem in the context of > a typed intermediate language, it's probably quite easy to > spot special cases quite far down the compiler pipeline. > - Andrew. > > > -----Original Message----- [...snip...] ------------------- 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