<blockquote style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;" class="gmail_quote">What do you mean with `exponential behavior&#39;? Exponential related to what?</blockquote><div>

<br>I mean that the size of the observable tree can be exponential in the size of the unobservable dag representation.<br></div><br><blockquote style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;" class="gmail_quote">

So the problem seems not to be CSE algorithm, but the fact that EDSL itself tends to blow up because it is hosted in Haskell.</blockquote><div><br>In other words, the tree size blows up, and hosting in pure Haskell doesn&#39;t allow us to examine the compact dag.<br>

<br>Are we on the same track now?<br><br>  - Conal<br></div><br><div class="gmail_quote">On Wed, May 27, 2009 at 3:15 AM, Sebastiaan Visser <span dir="ltr">&lt;<a href="mailto:sfvisser@cs.uu.nl">sfvisser@cs.uu.nl</a>&gt;</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">On May 27, 2009, at 1:49 AM, 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&#39;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 &amp; Pajama, I used lazy memoization, using stable pointers and weak references, to avoid the worst-case-exponential behavior you mention below.  I&#39;m now using a bottom-up CSE method that&#39;s slower and more complicated than I&#39;m going for.<br>


</blockquote>
<br></div>
What do you mean with `exponential behavior&#39;? Exponential related to what?<br>
<br>
For my FRP EDSL to JavaScript (toy) compiler[1] I&#39;ve been implementing CSE as well. I traverses the expression tree recursively and creates an small intermediate language containing id&#39;s (pointers) to expressions instead of real sub-expressions.<br>


<br>
Maybe (probably) I am very naive, but I think this trick takes time linear to the amount of sub-expressions in my script. When using a trie instead of a binary tree for the comparisons there should be no more character (or atomic expression) comparisons that the amount of characters in the script.<br>


<br>
So the problem seems not to be CSE algorithm, but the fact that EDSL itself tends to blow up because it is hosted in Haskell. Like Tom&#39;s example:<div class="im"><br>
<br>
&gt; let d = Add c c<br>
&gt;     e = Add d d    -- &quot;e&quot; now as 16 leaf nodes.<br>
<br></div>
But again, I might be missing some important point here.<br>
<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">
What&#39;s your latest wisdom about CSE in DSELs?<br>
<br>
Thanks,  - Conal<br>
<br>
On Thu, Feb 7, 2008 at 11:33 PM, Tom Hawkins &lt;<a href="mailto:tomahawkins@gmail.com" target="_blank">tomahawkins@gmail.com</a>&gt; wrote:<br>
</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
...<br>
</blockquote></blockquote>
<br>
--<br>
Sebastiaan Visser<br>
<br>
(warning: messy code)<br>
[1] <a href="http://github.com/sebastiaanvisser/frp-js/blob/b4f37d3b564c4932a3019b9b580e6da9449768a8/src/Core/Compiler.hs" target="_blank">http://github.com/sebastiaanvisser/frp-js/blob/b4f37d3b564c4932a3019b9b580e6da9449768a8/src/Core/Compiler.hs</a><br>


</blockquote></div><br>