Hi Wren,<br><br>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.<br><br><blockquote style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;" class="gmail_quote">
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).</blockquote><div><br>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.<br>
<br> - Conal<br></div><br><div class="gmail_quote">On Tue, May 26, 2009 at 5:23 PM, wren ng thornton <span dir="ltr"><<a href="mailto:wren@freegeek.org">wren@freegeek.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="im">Conal Elliott wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hi Tom,<br>
<br>
I've been working on another code-generating graphics compiler, generating<br>
GPU code. As always, I run into the problem of efficient common<br>
subexpression elimination. In Pan, Vertigo & Pajama, I used lazy<br>
memoization, using stable pointers and weak references, to avoid the<br>
worst-case-exponential behavior you mention below. I'm now using a<br>
bottom-up CSE method that's slower and more complicated than I'm going for.<br>
<br>
What's your latest wisdom about CSE in DSELs?<br>
<br>
Thanks, - Conal<br>
</blockquote>
<br>
<br></div>
One common trick that Tom didn't seem to mention in the 2008-02-07T23:33 post is hash cons'ing.<br>
<br>
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.<br>
<br>
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).<br>
<br>
Maybe this is the too-slow too-complex solution you're using already?<br>
<br>
-- <br>
Live well,<br><font color="#888888">
~wren</font><div><div></div><div class="h5"><br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</div></div></blockquote></div><br>