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 <w...@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 >> > > > 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 > > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe