Hi Wren,
I considered the idea of hashing, but not *perfect* hashing. I don't know how to hash perfectly with something like expressions, which have infinitely many values.
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).
Hm -- stateful? Unless I'm misunderstanding, a stateful & monadic/applicative approach would break the simple functional interface I'm going for. Could well be I haven't formed a mental picture that matches yours.
- Conal
On Tue, May 26, 2009 at 5:23 PM, wren ng thornton
<wren@freegeek.org> wrote:
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
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