RE: [Caml-list] Generation of streams is slow

["Dave Berry" <Dave@kal.com>]

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" <avv@quasar.ipa.nw.ru>

> Sorry :-), an example in Prolog is:
> 
> f([],[]) :- !.
> f([H1|T1], [H2|T2]) :-
> 	g(H1,H2),
> 	f(T1,T2).
> 
> 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:
> 
>     h::(make_tail arg1 argN),
> 
> that is
> 	CALL make_tail
> 	CONS
> 
> and change them to
>  
> 	PREPARE_CONS
> 	CALL make_tail
> 
> 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