Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
RE: [Caml-list] Generation of streams is slow
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Dave Berry <Dave@k...>
Subject: RE: [Caml-list] Generation of streams is slow
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.


-----Original Message-----
From: Jacques Garrigue []
Sent: 17 July 2001 03:37
Subject: Re: [Caml-list] Generation of streams is slow

From: "Alexander V. Voinov" <>

> 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
> the garbage collection, whose launch strategy may be based more on
> heuristics than on a theory. In OCaml, if it were possible to handle
> special case of the _two_ last calls of the form:
>     h::(make_tail arg1 argN),
> that is
> 	CALL make_tail
> and change them to
> 	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

Bug reports:  FAQ:
To unsubscribe, mail  Archives:
Bug reports:  FAQ:
To unsubscribe, mail  Archives: