Common subexpression elemination (CSE)

[Bertram Felgenhauer]

Dinko Tenev wrote:
> On 11/27/06, Lennart Augustsson <lennart at augustsson.net> wrote:
> >
> >GHC doesn't normally do CSE.  CSE can cause space leaks, so you can't
> >do it willy-nilly.
> >I'm sure there are some strict contexts where it could be done
> >safely, but I don't think ghc uses that information (yet).
> >
> >        -- Lennart
> 
> My apologies in advance for asking possibly stupid questions, but I don't
> understand this.
> 
> How exactly can CSE cause space leaks, and what does this have to do with
> strictness?

Combining two expressions means that they're represented by the same
memory location. In particular when you start evaluating the first,
the second reference to the value will keep all of it alive even if
parts of it could otherwise be freed. This is especially problematic
for infinite lists.

  http://hackage.haskell.org/trac/ghc/ticket/947

demonstrates this problem, caused by the little CSE that ghc does.
(Note: This is not of the form "let x = term in ... term ...", but
it will be once it's desugared and the simplifier has floated out
the constant expressions from the "primes0" and "primes" functions)

I'm not sure how it relates to strictness. I'd be more worried about
about the size of the data that's being kept alive. Numbers are
more likely to be ok than lists.

Bertram