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 SAA17035; Tue, 17 Jul 2001 18:05:05 +0200 (MET DST) 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 SAA17009 for ; Tue, 17 Jul 2001 18:05:04 +0200 (MET DST) Received: from mrwall.kal.com (mrwall.kal.com [194.193.14.236]) by nez-perce.inria.fr (8.11.1/8.10.0) with SMTP id f6HG53H02656 for ; Tue, 17 Jul 2001 18:05:03 +0200 (MET DST) Received: from mrwall.kal.com [194.193.14.236] (HELO localhost) by mrwall.kal.com (AltaVista Mail V2.0J/2.0J BL25J listener) id 0000_0050_3b54_62e8_8bc3; Tue, 17 Jul 2001 17:08:08 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: RE: [Caml-list] Generation of streams is slow Content-Transfer-Encoding: quoted-printable content-class: urn:content-classes:message X-MimeOLE: Produced By Microsoft Exchange V6.0.4417.0 Date: Tue, 17 Jul 2001 17:01:29 +0100 Message-ID: <8E31D6933A2FE64F8AE3CC1381EEDCE7092752@NT.kal.com> Thread-Topic: [Caml-list] Generation of streams is slow Thread-Index: AcEOaQbze2bwX2ljTEul3zY62Lmd0QAcRSbQ From: "Dave Berry" To: "Jacques Garrigue" , Cc: Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Two people at CMU implemented this a couple of years ago. They called it "destination-passing style", because the implementation passes an uninitialised "destination" that is filled in later. There are some subtle interactions with the garbage collector, which they investigated. I don't know why they didn't publish this work -- perhaps they found some problems with it that I never heard about. There have also been papers on automatically discovering source-to-source transformations for this sort of optimisation. And there is a very old paper called "tail-recursion modulo Cons" for doing this particular case in Lisp. Dave. -----Original Message----- From: Jacques Garrigue [mailto:garrigue@kurims.kyoto-u.ac.jp] Sent: 17 July 2001 03:37 To: avv@quasar.ipa.nw.ru Cc: caml-list@inria.fr Subject: Re: [Caml-list] Generation of streams is slow From: "Alexander V. Voinov" > Sorry :-), an example in Prolog is: >=20 > f([],[]) :- !. > f([H1|T1], [H2|T2]) :- > g(H1,H2), > f(T1,T2). >=20 > Last call in this case deals with the final locations of the tails of > the lists. Though chains of indirection may be long, they are handled by > the garbage collection, whose launch strategy may be based more on > heuristics than on a theory. In OCaml, if it were possible to handle the > special case of the _two_ last calls of the form: >=20 > h::(make_tail arg1 argN), >=20 > that is > CALL make_tail > CONS >=20 > and change them to > =20 > PREPARE_CONS > CALL make_tail >=20 > the scope of tail recursion optimization would increase. But it's > unlikely that this idea didn't come to developers. Which may mean that > this [being not that simple] is impossible. You can see: Yasuhiko Minamide, "A functional representation of data-structures with a hole", POPL'98. It does exactly that, using linear types to make sur the hole is initialized later. I don't know of any published compiler implementing it, but this may exist. Jacques ------------------- Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ 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/ To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr