[Haskell-cafe] I love purity, but it's killing me.
wren ng thornton
wren at freegeek.org
Tue May 26 20:23:27 EDT 2009
Conal Elliott 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?
> Thanks, - Conal
One common trick that Tom didn't seem to mention in the 2008-02-07T23:33
post is hash cons'ing.
Given a perfect hash function, traverse the term bottom-up storing each
(hash,subterm) pair in a memo table and replacing the subterm by its
hash. Once that's done, equality checks are trivial, and the memotable
can be converted to SSA rather easily.
This works best if you amortize the memoization by doing it with smart
constructors, so that you don't need to worry about the exponential
duplication of work for expressions with DAGy structure sharing in the
Haskell. Since it's stateful, that means the smart constructors may need
to be in an appropriate monad/applicative for passing the memo table
around (some hash functions may not need to store the table explicitly).
Maybe this is the too-slow too-complex solution you're using already?
More information about the Haskell-Cafe