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

[wren ng thornton]

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?

-- 
Live well,
~wren