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

Conal Elliott conal at conal.net
Wed May 27 11:06:19 EDT 2009


>
> What do you mean with `exponential behavior'? Exponential related to what?


I mean that the size of the observable tree can be exponential in the size
of the unobservable dag representation.

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.


In other words, the tree size blows up, and hosting in pure Haskell doesn't
allow us to examine the compact dag.

Are we on the same track now?

  - Conal

On Wed, May 27, 2009 at 3:15 AM, Sebastiaan Visser <sfvisser at cs.uu.nl>wrote:

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


More information about the Haskell-Cafe mailing list