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

Conal Elliott wrote: Hi Wren, I considered the idea of hashing, but not *perfect* hashing. I don't know how to hash perfectly with something like expressions, which have infinitely many values. An imperfect hash can work. You'll need a memo table with a source of unique symbols (e.g. storing

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

f 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

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

I just remembered: Andy Gill has a new paper "Type Directed Observable Sharing" (http://www.ittc.ku.edu/~andygill/paper.php?label=DSLExtract09) that looks very relevant. Abstract: Haskell is a great language for writing and supporting embedded Domain > Specific Languages (DSLs). Some form of obse

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

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

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

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

Hi Wren, I considered the idea of hashing, but not *perfect* hashing. I don't know how to hash perfectly with something like expressions, which have infinitely many values. Since it's stateful, that means the smart constructors may need to be in an > appropriate monad/applicative for passing the

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

On May 27, 2009, at 12:51 PM, Sittampalam, Ganesh wrote: Sebastiaan Visser wrote: ... 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 wro

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

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 us

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

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

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

On Tue, May 26, 2009 at 6:49 PM, 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

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

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 av

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

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

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

Hi Tom, > So is the general strategy with observable sharing to use > unsafePerformIO with Data.Unique to label expressions at > construction? something like that, yes. Basically, you just need: {-# NOINLINE ref #-} ref x = unsafePerformIO (newIORef x) and you can write expressions like

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

Hi Matt, On Feb 9, 2008 1:07 PM, Matthew Naylor <[EMAIL PROTECTED]> wrote: > If you go the real compiler route, would it not make sense to take the > DSL as the source language rather than Haskell? Or are the DSL and > Haskell quite similar? The two are nearly identical. In fact the only signif

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

On Fri, 8 Feb 2008, Matthew Naylor wrote: > Now recall that referential transparency lets you replace equals with > equals without changing the *value produced* by a program. Note that > it says nothing about preserving *runtime behaviour*. Sharing, for > example, may be lost. So if you do equ

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

On Feb 9, 2008 12:28 AM, Tom Hawkins <[EMAIL PROTECTED]> wrote: > 5) Forget embedding the DSL, and write a direct compiler. > > In addition to the sharing problem, another shortcoming of Haskell > DSLs is they can not fully exploit the benefits of algebraic > datatypes. Specifically, pattern match

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

On Fri, 8 Feb 2008, Tom Hawkins wrote: > 5) Forget embedding the DSL, and write a direct compiler. > > In addition to the sharing problem, another shortcoming of Haskell > DSLs is they can not fully exploit the benefits of algebraic > datatypes. Specifically, pattern matching ADTs can only be us

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

Hi Tom, > In addition to the sharing problem, another shortcoming of Haskell > DSLs is they can not fully exploit the benefits of algebraic > datatypes. Specifically, pattern matching ADTs can only be used to > control the compile-time configuration of the target, it can't be used > to describe t

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

Matthew Naylor wrote: (snip) > Now, there remains the concern that Haskell's semantics does not > enforce sharing. A Haskell compiler is free to change the sharing a > program at a whim, unknowingly to the programmer who may be relying on > it in for an efficient program. However, to my knowledge

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

On Feb 9, 2008 12:34 PM, Bertram Felgenhauer <[EMAIL PROTECTED]> wrote: > ghc actually provides a primop for this: > > reallyUnsafePtrEquality# :: a -> a -> Int# > > Use at your own risk. Why is it more than unsafe? 'unsafePerformIO' seems to me a lot unsafer than 'reallyUnsafePtrEquality#'. Al

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

Matthew Naylor wrote: [snip] > Finally, when I say "observable sharing", I don't necessarily mean it > as defined by Koen Claessen and David Sands. I simply mean the use of > unsafePerformIO to detect sharing, whether or not this is done by an > "eq" predicate on Refs. (I say this because I think

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

tomahawkins: > On 2/8/08, Emil Axelsson <[EMAIL PROTECTED]> wrote: > > I know of a few of ways to express sharing in a pure language: > > > > 1) "Observable sharing", which, in general, is unsafe. > > 2) Using Template Haskell > > 3) Matthew Naylor has done some work on "expressible sharing", which

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

On 2/8/08, Emil Axelsson <[EMAIL PROTECTED]> wrote: > I know of a few of ways to express sharing in a pure language: > > 1) "Observable sharing", which, in general, is unsafe. > 2) Using Template Haskell > 3) Matthew Naylor has done some work on "expressible sharing", which has > 4) Use a monad (bu

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

On 2/8/08, Matthew Naylor <[EMAIL PROTECTED]> wrote: > it in for an efficient program. However, to my knowledge, it is an > unwritten rule of Haskell compilers that sharing *is* preserved, and > that they do perform *graph* reduction. Clean, a similar language to I'm not sure that programmers ou

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

Hi, (Warning: longish message!) There is some concern, and rightly so, that observable sharing is dangerous, and that your Haskell program will explode if you use it, and perhaps even that anyone who uses it is "dirty" and should be sent to matron's for a good scrubbing! However, when used "safe

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

On Fri, 8 Feb 2008, Tom Hawkins wrote: > I've been programming with Haskell for a few years and love it. One > of my favorite applications of Haskell is using for domain specific > languages. However, after designing a handful of DSLs, I continue to > hit what appears to be a fundamental hurdle

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

Hello Tom, Friday, February 8, 2008, 9:33:35 AM, you wrote: > The process of converting an expression tree to a graph uses either Eq > or Ord (either derived or a custom instance) to search and build a set > of unique nodes to be ordered for execution. in similar situation, i've added hash field

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

I know of a few of ways to express sharing in a pure language: 1) "Observable sharing", which, in general, is unsafe. http://www.cs.chalmers.se/~koen/pubs/entry-asian99-lava.html 2) Using Template Haskell http://www.dcs.gla.ac.uk/publications/PAPERS/7524/EmbedHDLinTH.ps 3) Matthew Naylor

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

As I pointed out a few days ago in another thread, you can benefit from using Observable sharing [1] Be warned that Observable sharing is a non-conservative extension of Haskell and it breaks referential transparency. [1] http://www.cs.chalmers.se/~koen/pubs/entry-asian99-lava.html On Feb 8, 200