[Haskell-cafe] I love purity, but it's killing me.
conal at conal.net
Wed May 27 10:59:21 EDT 2009
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
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
On Tue, May 26, 2009 at 5:23 PM, wren ng thornton <wren at 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
>> 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,
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe