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
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
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
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
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
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
Haskellhttp://citeseer.ist.psu.edu/peytonjones99stretching.html
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
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
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.
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
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
On Tue, May 26, 2009 at 6:49 PM, Conal Elliott co...@conal.net 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
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
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 there
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#'.
Also, is
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,
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 the
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 used
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 matching
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
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
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
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 --
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
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 (but I'm sure
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 ought
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 has
4) Use a
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,
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 -- or at least I have yet
to find an adequate
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
30 matches
Mail list logo
