[Haskell-cafe] I love purity, but it's killing me.

[Tom Hawkins]

On Tue, May 26, 2009 at 6:49 PM, Conal Elliott <conal at conal.net> wrote:
> Hi Tom,
>
> I've been working on another code-generating graphics compiler, generating
> GPU code.  As always, I run into the problem of efficient common
> subexpression elimination.  In Pan, Vertigo & Pajama, I used lazy
> memoization, using stable pointers and weak references, to avoid the
> worst-case-exponential behavior you mention below.  I'm now using a
> bottom-up CSE method that's slower and more complicated than I'm going for.
>
> What's your latest wisdom about CSE in DSELs?

I wasn't able to find a solution that offered both performance and
elegance, so I changed the fundamental operation of the DSL (in this
case, atom).  When atom was still a hardware description language, the
compiler would combine several user defined expressions together
resulting in very wide and deep expression trees, resulting in the
same problem you are observing.  But when I switch the target of atom
from HDL to C, the compiler no longer needed to perform the same
expression expansion.  And since the user defined expressions are
generally shallow -- at least in the case of my applications -- atom
is able to get away with exhaustive equality comparison (deriving Eq).

Sorry I can't be of more help.

-Tom