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 "safely", it is not a hack, nor even dirty, but a nice, simple solution to an otherwise nasty problem. Below I define what I mean by "safely". First consider the circumstances under which obserevable sharing is useful. Typically we have some Haskell function "f" that produces a symbolic representation of an expression. For whatever reason, we'd like to *generate a program* that computes the value of this expression, rather that computing it in Haskell. For example, in Lava, we want to generate a VHDL program so that the expression can be computed on, say, an FPGA. In Tom's case, he wants to generate a C program to compute the expression. All perfectly reasonable, and in my opinion, a very powerfull way to use Haskell. 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 equational reasoning on function "f" (above), and loose some sharing, then you can only expect that the same sharing will also be also lost in the generated program. As long as the generated program computes the same result as it did before, referential transparency will be, overall, preserved; it would only be lost intermediately. This is what I mean by "safe". 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, it is an unwritten rule of Haskell compilers that sharing *is* preserved, and that they do perform *graph* reduction. Clean, a similar language to Haskell, indeed has a semantics based on graphs. So I don't believe Haskell being non-strict (not necessarily lazy) is a good reason for not using observable sharing. Though I do feel better when I compile without -O. :-) 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 are simpler ways to detect sharing, though these will probably not have the nice semantic properties of observable sharing.) Sorry for the somewhat long exposition. :-) Matt.

On 2/8/08, Matthew Naylor 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 to be relying on this rule. Sure, all Haskell compilers I know of preserve sharing and do graph reduction. But conventional wisdom is not the same thing as an unwritten rule. Someday, someone might come along and write a Haskell compiler that isn't based on graph reduction and doesn't preserve sharing at the implementation level (while still preserving the informal semantics of Haskell). A programmer who had written code that failed to compile correctly under this hypothetical compiler would be a very naughty Haskell programmer indeed.

Haskell, indeed has a semantics based on graphs. So I don't believe

Haskell doesn't have a semantics, graph-based or not... or at least not a formal one, and if not a formal one, I don't know what you mean :-) Cheers, Tim -- Tim Chevalier * http://cs.pdx.edu/~tjc * Often in error, never in doubt "There are no sexist decisions to be made. There are antisexist decisions to be made. And they require tremendous energy and self-scrutiny, as well as moral stamina..." -- Samuel R. Delany

On Feb 9, 2008 12:34 PM, Bertram Felgenhauer 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 anybody using 'reallyUnsafePtrEquality#' on a working project? Cheers, -- Felipe.

On 2/8/08, Emil Axelsson 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 this is what you're trying to avoid).

Or... 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 to control the compile-time configuration of the target, it can't be used to describe the target's behavior -- at least for DSLs that generate code that executes outside of Haskell's runtime. Writing a real compiler would solve both of these problems. Is there any Haskell implementation that has a clean cut-point, from which I can start from a fully type-checked, type-annotated intermediate representation? And thanks for the link to John's paper describing Hydra's use of Template Haskell. I will definiately consider TH. -Tom

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 to control the compile-time configuration of the target, it can't be used to describe the target's behavior -- at least for DSLs that generate code that executes outside of Haskell's runtime.

Also in a pure Haskell library you will try to avoid direct access to constructors, because the internal data structures might change. Better are functions that access the internal data of a type, like 'maybe' and 'either' for 'Maybe' and 'Either', respectively.

Hi Matt, On Feb 9, 2008 1:07 PM, Matthew Naylor 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 significant difference between the languages is the semantics of top level monad; it wouldn't be IO, but something else. With the syntax the same, it could leverage much of Haskell's standard library.

Or perhaps you are thinking of a two language system, where some code is evaluated at compile time by Haskell, and some is compiled to the target language?

Not necessarily in the same compilation flow, but I can think of several scenarios where it would be advantageous for code written in this other language to be pulled into a conventional Haskell program.

Taking options 2 or 5 just to solve the sharing problem sounds to me like a lot of hard work for little reward. But don't worry, I won't repeat my observable sharing speech. :-)

So is the general strategy with observable sharing to use unsafePerformIO with Data.Unique to label expressions at construction? Ahh...clever! I did not think of this. Of course, now that you have me reading up on Yhc.Core, option #5 is looking considerably more fun. -Tom

On Feb 9, 2008 12:28 AM, 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 to control the compile-time configuration of the target, it can't be used to describe the target's behavior -- at least for DSLs that generate code that executes outside of Haskell's runtime.

Only partly true. Probably you are not aware of them (I myself learned about its existence a few days ago) but pattern quasiquoting (available in GHC's HEAD) can be used for that. http://www.haskell.org/ghc/dist/current/docs/users_guide/template-haskell.ht...

Writing a real compiler would solve both of these problems. Is there any Haskell implementation that has a clean cut-point, from which I can start from a fully type-checked, type-annotated intermediate representation?

If you have to write a compiler why not define a language which fits better with the semantics of the embedded language instead of using plain Haskell? The approach you propose has the disadvantages of both the embedded and the standalone languages. On one hand you have to stick with the syntax of the host language which may not fit with your exact semantical requirements and, on the other hand, you cannot take advantage of all the existing machinery around the host language (you have to code your own compiler). Furthermore, the first citizen status of functions make it impossible (or really difficult at least) to compile EDSL descriptions avoiding runtime and simply applying a static analysis approach (using Core or plain Haskell as input).

And thanks for the link to John's paper describing Hydra's use of Template Haskell. I will definiately consider TH.

Well, TH would be one of those static analysis approaches. Actually, O'Donell's implementation (which uses an outdated version of Template Haskell) only works with a small Haskell subset. So using TH you'd probably be changing the host language anyhow. Furthermore, the TH approach consists in adding node labels by preprocessing the EDSL description, making sharing observable. That makes the original EDSL description inpure. The only difference is that side effects are added by preprocessing instead of using runtime unsafe functions. ---- Some pointers covering the topic: [1] and [2] summarize what are the alternatives to observe sharing in Haskell whereas [3] compares the embedded approach vs standalone approach and advocates the last one. 1) http://www.imit.kth.se/~ingo/MasterThesis/ThesisAlfonsoAcosta2007.pdf (section 2.4.1 and 3.1) 2) http://www.cs.um.edu.mt/svrg/Papers/csaw2006-01.pdf (section 3) 3) http://web.cecs.pdx.edu/~sheard/papers/secondLook.ps

Let-expression in the EDSL indeed solves the sharing problem, but only partially. Recursion appears when you have a leaf node pointing back to the root node or another branch and forming a cyclic graph in the data structure. It is often desirable to recover cyclic sharing when showing/reading/interpretating EDSL programs. One possible solution is to further introduce a fixed point data constructor, a Rec or even LetRec to explicitly capture cycles. But then you still incur much overheads interpreting them, and syntax wise it just gets more and more complicated to the point that turning the EDSL into a DSL (or even a preprocessor with your own lexer and parser) becomes more attractive. Another alternative is to express the EDSL as Monad/MonadFix, or Arrows/ArrowLoop. There are still interpretive overheads, but at the very least they could help with the syntax. The tagless paper is really nice, but I doubt it offers solutions to the (cyclic) sharing problem. On 2/13/08, Chung-chieh Shan wrote:

Henning Thielemann wrote in article in gmane.comp.lang.haskell.cafe:

...

It seems to become a FAQ. I think all DSLs suffer from the same problems: sharing and recursion. I've used wrappers for CSound, SuperCollider, MetaPost, they all have these problems.

What do you mean by the "recursion" problem?

Sometimes (or perhaps even often), sharing in an EDSL can be expressed in two ways. First, to reuse a -value- in the embedded language, you could introduce a "let" construct in the embedded language.

let_ expr body = body expr

Second, to reuse an -expression- in the embedded language, if your interpreter is compositional (here by "interpreter" I include a compiler, and by "compositional" I mean a fold), then you can represent an embedded expression simply as its interpretation.

add x y = x + y let expr = add x y in add expr expr

Jacques Carette, Oleg Kiselyov, and I have been exploring this "final" representation. http://okmij.org/ftp/Computation/tagless-typed.html

-- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig I am a signature virus. Put me in your signature.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Regards, Paul Liu Yale Haskell Group http://www.haskell.org/yale

On 2009-05-27T03:58:58-0400, Paul L wrote:

One possible solution is to further introduce a fixed point data constructor, a Rec or even LetRec to explicitly capture cycles. But then you still incur much overheads interpreting them,

I don't understand this criticism -- what interpretive overhead do you mean? Certainly the Rec/LetRec encoding is pretty efficient for one object language with cycles, namely the lambda calculus with Rec or LetRec. :) One concrete way for you to explain what interpretive overhead you mean, if it's not too much trouble, might be to compare a Rec/LetRec encoding of a particular object language to another encoding that does not have the interpretive overhead you mean and is therefore more efficient. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig We want our revolution, and we want it now! -- Marat/Sade We want our revolution, and we'll take it at such time as you've gotten around to delivering it -- Haskell programmer

Paul L wrote in article <856033f20906082224s2b7d5391gdc7a4ed913004639@mail.gmail.com> in gmane.comp.lang.haskell.cafe:

The open question is whether there exists such a solution that's both elegant and efficient at maintain proper sharing in the object language.

What is your criterion for "efficient"?

We certainly can get rid of all interpretive overheads by either having a "tagless" interpreter (as in Oleg and Shan's paper), or by direct compilation.

(BTW, the paper is by Jacques Carette, Oleg Kiselyov, and Chung-chieh Shan.)

But so far I don't see how a tagless interpreter could handle sharing when it can't be distinguished in the host language.

Indeed, I would agree with those on this thread who have stated that sharing should be distinguished in the host language. -- Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig We want our revolution, and we want it now! -- Marat/Sade We want our revolution, and we'll take it at such time as you've gotten around to delivering it -- Haskell programmer

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's your latest wisdom about CSE in DSELs?

Thanks, - Conal

One common trick that Tom didn't seem to mention in the 2008-02-07T23:33 post is hash cons'ing. Given a perfect hash function, traverse the term bottom-up storing each (hash,subterm) pair in a memo table and replacing the subterm by its hash. Once that's done, equality checks are trivial, and the memotable can be converted to SSA rather easily. This works best if you amortize the memoization by doing it with smart constructors, so that you don't need to worry about the exponential duplication of work for expressions with DAGy structure sharing in the Haskell. Since it's stateful, that means the smart constructors may need to be in an appropriate monad/applicative for passing the memo table around (some hash functions may not need to store the table explicitly). Maybe this is the too-slow too-complex solution you're using already? -- Live well, ~wren

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 the next unused integer) in order to, effectively, make the "hash" function perfect[1]. If you have a source of unique symbols then you can also use a trie, Data.Map, or similar in lieu of a hash map. In a language with pointers (or stable names), the pointer is often used as the "hash" in conjunction with using the memo table as an intern table for smart constructors. Thus, client code can never observe that structurally equal expressions could have different hashes. [1] hash :: HashState m => Expr -> m Hash hash e = case lookupHS e of Just h -> return h Nothing -> do h <- nextH insertHS e h return h

...

Since it's stateful, that means the smart constructors may need to be in an appropriate monad/applicative for passing the memo table around (some hash functions may not need to store the table explicitly).

Hm -- stateful? Unless I'm misunderstanding, a stateful & monadic/applicative approach would break the simple functional interface I'm going for. Could well be I haven't formed a mental picture that matches yours.

Er, it's only stateful for the versions above that use pointers or a source of unique symbols (since they need to maintain a memo table). If you can come up with a perfect hash function[2], then there's no need to create/store the memo table at all, since it can be reconstructed on the fly. Since perfect hashing often isn't feasible, the stateful approximations to a perfect hash function are generally used. Sorry if I was unclear. If you don't mind unsafePerformIO (or similar hacks) then you can hide the state from the type system by using the same table for the whole program. Generally for hash cons'ing you want your tables to be as large as they can be (to maximize sharing) so this shouldn't be problematic. However, for languages with scoping it can be beneficial to use separate tables to recognize when expressions need to be recomputed; so the global store might want to be something like a stack of memo tables with fall-through lookup. I believe Applicative is powerful enough to capture the sort of state passing needed since the client code can't ever make decisions based on the state. So with smart constructors (to package up the <*> etc) I'd think you should be able to have an EDSL that looks nice, just with a more complicated type. Perhaps the issues are with mixing pure Haskell functions into the EDSL? ... The real trick behind hash cons'ing is everywhere substituting the "hash" in for the sub-expression, effectively flattening all expressions into a single ply. Thus, expression constructors "cons the hashes" rather than cons'ing expressions. It's similar in spirit to trie'ing, but from the bottom up in the same way that dynamic programming is done. The reason for wanting to do the hashing in smart constructors, as opposed to at the end, is to maximize the benefit of dynamic programming. If all client-visible expressions are represented by hashes, then any structure sharing in the Haskell layer is sharing the hash representation, thus you don't need to traverse the shared substructure multiple times. (If you hand construct equal expressions without sharing, then you'll have to traverse each expression to prove that they're equal, but you can use that proof (the hashes) thenceforth). For host languages with destructive updates (like Smalltalk's "become"), you can rewrite the subterms as you traverse them, so doing it at the end isn't too bad. If you only expose smart constructors then your Expr type can "recurse" as whatever Hash type. If you do the hashing at the end, then you'll need to define a catamorphism on Expr. ... This is probably similar to what you're doing in Pan, Vertigo, and Pajama (I haven't read it). The general technique is elegant in its simplicity, and it's not uncommon. Though, like most dynamic programming tricks, it seems not to be as widely known as I would assume, so I thought I'd mention it in case you've missed it. [2] Into any domain of terms that can quickly answer (==), namely flat terms like Integer. Using a bounded type like Int can give better performance guarantees, but there's only so many of them. -- Live well, ~wren

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

...

...

-- Sebastiaan Visser (warning: messy code) [1] http://github.com/sebastiaanvisser/frp-js/blob/b4f37d3b564c4932a3019b9b580e6...

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

Thanks, I just pushed your paper on top of my stack. -- Sebastiaan Visser

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@haskell.org [mailto:haskell-cafe-bounces@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 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 ===============================================================================

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

...

...

-- Sebastiaan Visser

(warning: messy code) [1] http://github.com/sebastiaanvisser/frp-js/blob/b4f37d3b564c4932a3019b9b580e6...