<blockquote style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;" class="gmail_quote">In my experience [1], observable sharing using GHC's stable names is a pretty effective solution to this problem.</blockquote>
<div><br>Plus unsafePerformIO and weak references as in <i><a href="http://citeseer.ist.psu.edu/peytonjones99stretching.html">Stretching the storage
manager: weak pointers and stable names in Haskell</a></i>?<br><br>Lacking a more elegant alternative, that's what I'll probably do again, as in Pan, Vertigo, and Pajama.<br><br> - Conal<br></div><br><div class="gmail_quote">
On Wed, May 27, 2009 at 3:51 AM, Sittampalam, Ganesh <span dir="ltr"><<a href="mailto:ganesh.sittampalam@credit-suisse.com">ganesh.sittampalam@credit-suisse.com</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><div></div><div class="h5">Sebastiaan Visser wrote:<br>
> On May 27, 2009, at 1:49 AM, Conal Elliott wrote:<br>
>> Hi Tom,<br>
>><br>
>> I've been working on another code-generating graphics compiler,<br>
>> generating GPU code. As always, I run into the problem of efficient<br>
>> common subexpression elimination. In Pan, Vertigo & Pajama, I used<br>
>> lazy memoization, using stable pointers and weak references, to avoid<br>
>> the worst-case-exponential behavior you mention below. I'm now using<br>
>> a bottom-up CSE method that's slower and more complicated than I'm<br>
>> going for.<br>
><br>
> What do you mean with `exponential behavior'? Exponential related to<br>
> what?<br>
><br>
> For my FRP EDSL to JavaScript (toy) compiler[1] I've been<br>
> implementing CSE as well. I traverses the expression tree recursively<br>
> and creates an small intermediate language containing id's (pointers)<br>
> to expressions instead of real sub-expressions.<br>
><br>
> Maybe (probably) I am very naive, but I think this trick takes time<br>
> linear to the amount of sub-expressions in my script. When using a<br>
> trie instead of a binary tree for the comparisons there should be no<br>
> more character (or atomic expression) comparisons that the amount of<br>
> characters in the script.<br>
><br>
> So the problem seems not to be CSE algorithm, but the fact that EDSL<br>
> itself tends to blow up because it is hosted in Haskell. Like Tom's<br>
> example:<br>
><br>
> > let d = Add c c<br>
> > e = Add d d -- "e" now as 16 leaf nodes.<br>
><br>
> But again, I might be missing some important point here.<br>
<br>
</div></div>That's exactly right. But it's pretty inconvenient to have your<br>
expression tree to blow up exponentially in relation to the code the<br>
user actually wrote! You can indeed construct an intermediate language<br>
that collapses this blowup, but the pass to create it must take<br>
exponential time if written completely purely, since it has to visit<br>
everything at least once.<br>
<br>
In my experience [1], observable sharing using GHC's stable names is a<br>
pretty effective solution to this problem.<br>
<br>
Ganesh<br>
<br>
[1] <a href="http://www.earth.li/%7Eganesh/research/paradise-icfp08/" target="_blank">http://www.earth.li/~ganesh/research/paradise-icfp08/</a><br>
<br>
===============================================================================<br>
Please access the attached hyperlink for an important electronic communications disclaimer:<br>
<a href="http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html" target="_blank">http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html</a><br>
===============================================================================<br>
<br>
</blockquote></div><br>