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

[Conal Elliott]

>
> In my experience [1], observable sharing using GHC's stable names is a
> pretty effective solution to this problem.


Plus unsafePerformIO and weak references as in *Stretching the storage
manager: weak pointers and stable names in
Haskell<http://citeseer.ist.psu.edu/peytonjones99stretching.html>
*?

Lacking a more elegant alternative, that's what I'll probably do again, as
in Pan, Vertigo, and Pajama.

  - Conal

On Wed, May 27, 2009 at 3:51 AM, Sittampalam, Ganesh <
ganesh.sittampalam at credit-suisse.com> wrote:

> Sebastiaan Visser 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.
>
> That's exactly right. But it's pretty inconvenient to have your
> expression tree to blow up exponentially in relation to the code the
> user actually wrote! You can indeed construct an intermediate language
> that collapses this blowup, but the pass to create it must take
> exponential time if written completely purely, since it has to visit
> everything at least once.
>
> In my experience [1], observable sharing using GHC's stable names is a
> pretty effective solution to this problem.
>
> Ganesh
>
> [1] http://www.earth.li/~ganesh/research/paradise-icfp08/<http://www.earth.li/%7Eganesh/research/paradise-icfp08/>
>
>
> ===============================================================================
>  Please access the attached hyperlink for an important electronic
> communications disclaimer:
>  http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html
>
>  ===============================================================================
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090527/7c50547b/attachment.html