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

[Sebastiaan Visser]

On May 27, 2009, at 1:49 AM, 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 do you mean with `exponential behavior'? Exponential related to  
what?

For my FRP EDSL to JavaScript (toy) compiler[1] I've been implementing  
CSE as well. I traverses the expression tree recursively and creates  
an small intermediate language containing id's (pointers) to  
expressions instead of real sub-expressions.

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.

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's  
example:

 > let d = Add c c
 >     e = Add d d    -- "e" now as 16 leaf nodes.

But again, I might be missing some important point here.

> What's your latest wisdom about CSE in DSELs?
>
> Thanks,  - Conal
>
> On Thu, Feb 7, 2008 at 11:33 PM, Tom Hawkins <tomahawkins at gmail.com>  
> wrote:
>> ...

--
Sebastiaan Visser

(warning: messy code)
[1] http://github.com/sebastiaanvisser/frp-js/blob/b4f37d3b564c4932a3019b9b580e6da9449768a8/src/Core/Compiler.hs