Bart Demoen wrote:
>
> Simon wrote:
>
> > CSE can also make space consumption asymptotically worse.
>
> I can understand this when garbage collection is around and because of
> CSE, some data structures don't get cleaned up; but is it also true
> without gc ?
If you don't use a rule like
e'[e,e] --> let x = e in e'[x,x]
for CSE, but limit yourself to rules like
let x = e in e'[e] --> let x = e in e'[x]
then you are right that the transformed program will not allocate more closures
than the old (in fact less in most cases).
However, the liveness of heap cells will (often) increase and hence they cannot
be collected by garbage collection as early as in the original program.
Just the elimination of a few common subexpressions can increase heap residency
of a program considerably.
If want to know more about why I think that CSE is unfortunately not suitable
for lazy functional languages have a look at my paper `Common Subexpressions are
Uncommon in Lazy Functional Languages' at
http://www-i2.informatik.rwth-aachen.de/~chitil/PUBLICATIONS/comSubsAreUncom.html
Olaf
--
OLAF CHITIL, Lehrstuhl fuer Informatik II, RWTH Aachen, 52056 Aachen, Germany
Tel: (+49/0)241/80-21212; Fax: (+49/0)241/8888-217
URL: http://www-i2.informatik.rwth-aachen.de/~chitil/
