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

[Conal Elliott]

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 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
>> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090527/3a32cf46/attachment.html