Common subexpression elemination (CSE)

[Bulat Ziganshin]

Hello Dinko,

Wednesday, November 29, 2006, 11:56:49 AM, you wrote:
>> How exactly can CSE cause space leaks, and what does this have to do
>> with strictness?

standard example is

x = [1..9] ++ [1..9]

comparing to

x = a++a where a=[1..9]

first version runs (without CSE transformation) in fixed space, but
computes [1..9] twice. second version computes its only once but needs
more memory to hold results for second consumption. so, it's a
classical space/time trade-off and lack of CSE transformation in such
circumstances allow program to explicitly select whether he need
better speed or space usage

in the absence of laziness, entire a++a expression should be evaluated
before return, so first version is no more able to tun in fixed space
and second one definitely is winner

so, in lazy environment, sometimes it's better to keep data in
unevaluated form and compute it on each use, while in strict
environment, CSE always win


-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com