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

[Sittampalam, Ganesh]

Yes, though we don't bother with weak pointers as we only keep the
stable names map around for the duration of CSE so there's no ongoing
memory leak issue.
 
________________________________

From: haskell-cafe-bounces at haskell.org
[mailto:haskell-cafe-bounces at haskell.org] On Behalf Of Conal Elliott
Sent: 27 May 2009 16:14
To: Sittampalam, Ganesh
Cc: Haskell Cafe
Subject: Re: [Haskell-cafe] I love purity, but it's killing me.



	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
	
========================================================================
=======
	
	



=============================================================================== 
 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/1f262b19/attachment.html