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 KAA13144; Fri, 31 Jan 2003 10:34:53 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id KAA13091 for caml-list@pauillac.inria.fr; Fri, 31 Jan 2003 10:34:52 +0100 (MET) 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 KAA19911 for ; Thu, 30 Jan 2003 10:56:31 +0100 (MET) Received: from julie.univ-savoie.fr (univax.univ-savoie.fr [193.48.120.32]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h0U9uVr16597 for ; Thu, 30 Jan 2003 10:56:31 +0100 (MET) Received: from post.bourget.univ-savoie.fr (post.bourget.univ-savoie.fr [193.48.120.73]) by julie.univ-savoie.fr (8.9.3/jtpda-5.3.3) with ESMTP id KAA44488 ; Thu, 30 Jan 2003 10:56:29 +0100 (CET) Received: from univ-savoie.fr (d85.lama.univ-savoie.fr [193.48.123.85]) by post.bourget.univ-savoie.fr (8.12.3/jtpda-5.4) with ESMTP id h0U9uO75006572 ; Thu, 30 Jan 2003 10:56:25 +0100 Message-ID: <3E38F6F6.7000206@univ-savoie.fr> Date: Thu, 30 Jan 2003 10:57:10 +0100 From: Christophe Raffalli User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.1) Gecko/20020826 X-Accept-Language: en-us, en MIME-Version: 1.0 To: brogoff@speakeasy.net CC: Andrew Kennedy , Brian Hurt , Ocaml Mailing List Subject: Re: [Caml-list] @, List.append, and tail recursion References: X-Enigmail-Version: 0.65.2.0 X-Enigmail-Supports: pgp-inline, pgp-mime Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enig12F1EE7E328A3165E76BBE99" Content-Transfer-Encoding: 8bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enig12F1EE7E328A3165E76BBE99 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit brogoff@speakeasy.net wrote: > 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: To compute append l1 l2 in a tail recursive way the only solution I see (in a pure functionnal program) is to traverse l1 twice (to reverse it first), which replaces using memory on the stack by using memory to build an intermediate list (and this use more memory ?). Usually in recursive program, when you limit youself to tail recursive function, you have often to reverse list and lisp languages always provide the rev_append function which is tail recursive and very often what you need (often l1 is an accumulator and is naturaly reversed compared with l2). May be rev_append could be added to the list module (despite the fact it is trivial to write it yoursleft) ? >>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 -- Christophe Raffalli Université de Savoie Batiment Le Chablais, bureau 21 73376 Le Bourget-du-Lac Cedex tél: (33) 4 79 75 81 03 fax: (33) 4 79 75 87 42 mail: Christophe.Raffalli@univ-savoie.fr www: http://www.lama.univ-savoie.fr/~RAFFALLI --------------------------------------------- IMPORTANT: this mail is signed using PGP/MIME At least Enigmail/Mozilla, mutt or evolution can check this signature --------------------------------------------- --------------enig12F1EE7E328A3165E76BBE99 Content-Type: application/pgp-signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.7 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQE+OPb2SQDyWB/+xBwRAmXsAJ9UOAYUCaWQHQgJsKMSyIVnVinArwCggOnR f4KexCRTMgYVci8W3phV5VE= =ymLO -----END PGP SIGNATURE----- --------------enig12F1EE7E328A3165E76BBE99-- ------------------- 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