On Tuesday 06 December 2005 04:00 pm, haskell-cafe.mail.zooloo@xoxy.net wrote:

From: "Shae Matijs Erisson - shae@ScannedInAvian.com" Sent: Tuesday, December 06, 2005 6:16 PM

...

haskell-cafe.mail.zooloo@xoxy.net writes:

...

being occupied with learning both languages, I'm getting curious if Haskell couldn't achieve most of the performance gains resulting from uniqueness typing in Clean by *automatically* determining the reference count of arguments wherever possible and subsequently allowing them to be physically replaced immediately by (the corresponding part of) the function's result. Are there any principal obstacles, or *could* this be done, or *is* this even done already, e. g. in ghc?

Maybe you're describing speculative evaluation?

Optimistic Evaluation: An Adaptive Evaluation Strategy for Non-Strict Programs http://citeseer.ist.psu.edu/ennals03optimistic.html --

Thanks for the pointer - I have heard a little about optimistic evaluation already, but don't know much of the details (yet). Anyway, from what I know, I think it's a different thing.

In Clean, you can (and often are required to) assign uniqueness attributes to some parts of a function's type signature. The extended type checker ensures that none of those parts is referred to more than once during a single run of the program. Based on this guarantee, a function does not have to allocate new memory at all to store a unique result but can overwrite the unique arguments in place.

Apparently, the uniqueness assignments have to comply with very tight laws - getting a program through the Clean type checker can be tough, once it reports an uniqueness coercion error. I suppose, no explicit uniqueness attributing is going to be implemented in Haskell, anyway.

My question is - and this might better suit to Haskell -, can't uniqueness be inferred (and exploited) automatically in many cases?

Yes, probably. There is a technique called sharing analysis that attempts to determine when a datastructure is only referenced once (ie, NOT shared). If you can prove a datastructure node is not shared then you can reuse it destructively. Here is a paper on the technique. It's written for lisp cons cells, but one might be able to generalize the technique to ADT. I don't know where to find a free copy. http://portal.acm.org/citation.cfm?id=99375 There has also been some similar work done along these lines for Mercury (a logic programming language). http://www.cs.mu.oz.au/research/mercury/information/papers.html Search for papers with the word "reuse" in the title. I'm not very familiar with this work, so I don't know how applicable this might be.

On Wed, Dec 07, 2005 at 04:38:19PM +0300, Bulat Ziganshin wrote:

may be, John Meacham can say something about it? his JHC compiler uses region analysis to avoid garbage collection - may be these techniques has something in common?

By the time jhc makes any decisions regarding memory management, the code has already been transformed into a first order, strict, imperative language (but with stronger types than normal and in a monad) so I am not sure how much they would have in common. But there definitely are higher level optimizations that achieve similar things, update avoidance being a particular one as it collects pretty much exactly the info we want, when a node will only be referenced once. GHC has some very advanced algorithms for this sort of thing and I believe from first glance they will do a better job than the clean system. The update analysis info in jhc is not propegated all the way to the back end, the grin compiler does do a separate analysis to recapture this type of info after various transformations. I found it somewhat tricky to maintain the annotations all the way through various optimizations so I recalculate it (and perhaps get better results on the simpler program). However figuring out a way to propagate that info would be vital if we wanted user supplied region annotations, which several papers have said can be very beneficial. It is not clear at all what they would look like in a lazy language though since your run-time stack does not follow your program structure. (I'm open to ideas...) John -- John Meacham - ⑆repetae.net⑆john⑈

haskell-cafe.mail.zooloo@xoxy.net wrote:

It might be possible to get extremely fast code out of ghc, but as an overall impression, it's not easy, whilst Clean sort of gives it for granted (well, struggeling with wrongly assigned uniqueness attributes aside).

<snip>

programs generated by ghc generally need multiples of time and space of the Clean version, even though the latter is, in many cases, a nearly literal translation from Haskell.

Maybe you'd be interested in Hacle? http://www-users.cs.york.ac.uk/~mfn/hacle/ " The aim was to develop a translator which is capable of reading in any given Haskell'98 program and writing out a semantically equivalent Clean one. Why? To investigate the suitability of the Clean compiler for compiling Haskell programs, i.e. Can the Clean compiler, in combination with this tool, produce faster executables than existing Haskell compilers? " Greg Buchholz

----- Original Message ----- From: "Sebastian Sylvan - sebastian.sylvan@gmail.com" Sent: Wednesday, December 07, 2005 8:36 PM

...

Maybe you'd be interested in Hacle?

http://www-users.cs.york.ac.uk/~mfn/hacle/

Yep, I am. :) I've discovered it a while ago.

...

" The aim was to develop a translator which is capable of reading in any given Haskell'98 program and writing out a semantically equivalent Clean one. Why? To investigate the suitability of the Clean compiler for compiling Haskell programs, i.e. Can the Clean compiler, in combination with this tool, produce faster executables than existing Haskell compilers? "

That looks interesting. I wonder what the results mean =)

It could be that Clean and Haskell are roughly equivalent in speed (modulo som variance), or it could mean that GHC is great at optimizing Haskell code, but in certain cases uniqueness typing (among other things?) gives so much benifits that it outweights GHC's optimization.

Just a side note (please, correct me if I'm wrong): Hacle does not even make use of uniqueness typing (apart from *World and *File), so any benefits are due to other differences, like, inferred strictness. Regards, zooloo -- No virus found in this outgoing message. Checked by AVG Free Edition. Version: 7.1.371 / Virus Database: 267.13.12/192 - Release Date: 05.12.2005

----- Original Message ----- From: "Tomasz Zielonka - tomasz.zielonka@gmail.com" Sent: Wednesday, December 07, 2005 8:53 PM

...

Clean-like _explicit_ uniqueness typing is not what I'm asking for in Haskell.

So you want implicit, automatically inferred uniqueness typing - something that would be even more fragile and sensitive then current Haskell's space problems arising from laziness? ;-)

Maybe it's just my lacking insight, but why should uniqueness inferring be all that fragile? A uniqueness checker can be rather robust, as is demonstrated by the Clean one, so all we'd have to worry about is how to find a good set of supposedly unique node candidates to suggest to the checker. (It certainly would not work well the dumb way, like, trying every single combination out of n^2 possibilities, where n is the total node count.) Whatever suggestion gets through the uniqueness checker, the resulting code can't be consuming more space, slower, or otherwise worse than the one without reusing unique nodes, can it? On the other hand, performance gains thereby seem likely to me.

...

It might be possible to get extremely fast code out of ghc, but as an overall impression, it's not easy, whilst Clean sort of gives it for granted (well, struggeling with wrongly assigned uniqueness attributes aside).

Well, C sort of gives it for granted too, because it is very difficult to write inefficient, simple, specification-like code. I want to be able to write simple and elegant code, even if it is inefficient!

errr..., could you give me some clue how you'd expect automatically uniqueness detection to deteriorate your coding style? I, for one, don't define elegance in terms of not running too fast. ;) I don't feel very comfortable either with the impact _explicit_ uniqueness attributing has on the ease of coding. Anyway, I am not arguing pro Clean but pro compile time sharing analysis here. To be honest, your reply feels like a counterpart to the likewise questionable monad avoidance in Clean. Regards, zooloo p. s.: Anyone knows what makes your cited mail appear in the list archive as beeing sent from my address? The copy I got to my mailbox is ok. -- No virus found in this outgoing message. Checked by AVG Free Edition. Version: 7.1.371 / Virus Database: 267.13.12/192 - Release Date: 05.12.2005

----- Original Message ----- From: "Tomasz Zielonka - tomasz.zielonka@gmail.com" Sent: Wednesday, December 07, 2005 8:53 PM

...

Clean-like _explicit_ uniqueness typing is not what I'm asking for in Haskell.

So you want implicit, automatically inferred uniqueness typing - something that would be even more fragile and sensitive then current Haskell's space problems arising from laziness? ;-)

Why should inferring uniqueness be all that fragile? A uniqueness checker can be rather robust, as is demonstrated by the Clean one. Maybe I'm lacking insight, but to me it seems that all we'd have to worry about is how to find a good set of supposedly unique node candidates to suggest to the checker. (It certainly would not work well the dumb way, like, trying every single combination out of n^2 possibilities, where n is the total node count.) Whatever suggestion gets through the uniqueness checker, the resulting code can't be consuming more space, slower, or otherwise worse than the one without reusing unique nodes, can it? On the other hand, performance gains thereby seem likely to me.

...

It might be possible to get extremely fast code out of ghc, but as an overall impression, it's not easy, whilst Clean sort of gives it for granted (well, struggeling with wrongly assigned uniqueness attributes aside).

Well, C sort of gives it for granted too, because it is very difficult to write inefficient, simple, specification-like code. I want to be able to write simple and elegant code, even if it is inefficient!

errr..., could you give me some clue how you'd expect automatically uniqueness detection to deteriorate your coding style? I, for one, don't define elegance in terms of "not running too fast". ;) I don't feel very comfortable either with the impact _explicit_ uniqueness attributing has on the ease of coding. Anyway, I am not arguing pro Clean but pro compile time sharing analysis here. To be honest, your reply feels like a counterpart to the likewise questionable monad avoidance in Clean. Regards, zooloo p.s.: Anyone knows what makes your (Tomasz's) cited mail appear in the list archive as beeing sent from my address? The copy I got to my mailbox correctly shows you as the sender. p.p.s.: I've sent this mail a second time because the first one got lost somehow - hopefully, it doesn't show up again. -- No virus found in this outgoing message. Checked by AVG Free Edition. Version: 7.1.371 / Virus Database: 267.13.12/192 - Release Date: 05.12.2005

On Thu, Dec 08, 2005 at 06:38:53PM +0100, haskell-cafe.mail.zooloo@xoxy.net wrote:

----- Original Message ----- From: "Tomasz Zielonka - tomasz.zielonka@gmail.com" Sent: Wednesday, December 07, 2005 8:53 PM

...

...

Clean-like _explicit_ uniqueness typing is not what I'm asking for in Haskell.

So you want implicit, automatically inferred uniqueness typing - something that would be even more fragile and sensitive then current Haskell's space problems arising from laziness? ;-)

Why should inferring uniqueness be all that fragile?

It's just that I automatically thought about how uniqueness typing is used in Clean, expecially as a way to achieve O(1) array update. It would be nice if Haskell could infer that an *immutable* array given as parameter to an update operation (like. //) can be reused to create the result effectively. But if you wrote code with such an optimisation in mind, you could be very disappointed with performance if the compiler didn't perform the optimisation. I think that in the case of arrays I would still prefer to use mutable arrays to be sure that my program has the desired asymptotic complexity. Maybe you didn't intend to propose it for arrays? It would be fine to use your idea for "smaller", constant-size things, like records, etc, just to reduce the constant factor.

A uniqueness checker can be rather robust, as is demonstrated by the Clean one.

In Clean there is no surprise, because this optimisation is part of the type system, it's part of the language definition.

Whatever suggestion gets through the uniqueness checker, the resulting code can't be consuming more space, slower, or otherwise worse than the one without reusing unique nodes, can it?

It can be slower than the programmer expects, in terms of asymptotic complexity. So this feature could be difficult to use to create reliable, efficient code. Of course, unpredictabile efficiency of Haskell programs is not a new problem.

...

...

It might be possible to get extremely fast code out of ghc, but as an overall impression, it's not easy, whilst Clean sort of gives it for granted (well, struggeling with wrongly assigned uniqueness attributes aside).

Well, C sort of gives it for granted too, because it is very difficult to write inefficient, simple, specification-like code. I want to be able to write simple and elegant code, even if it is inefficient!

errr..., could you give me some clue how you'd expect automatically uniqueness detection to deteriorate your coding style? I, for one, don't define elegance in terms of "not running too fast". ;)

I was referring to UT as in Clean, not to automatic UT you propose. You said "Clean sort of gives it for granted", with it = "extremely fast code". I don't yet know a language which _grants_ extremely fast code without being more low-level. OK, I am nitpicking ;-)

To be honest, your reply feels like a counterpart to the likewise questionable monad avoidance in Clean.

My english understanding skills failed me here. Could you expand this sentence using simpler words? Best regards Tomasz -- I am searching for a programmer who is good at least in some of [Haskell, ML, C++, Linux, FreeBSD, math] for work in Warsaw, Poland

On Thu, Dec 08, 2005 at 11:29:44AM -0800, Jeremy Shaw wrote:

...

Why should inferring uniqueness be all that fragile? A uniqueness checker can be rather robust, as is demonstrated by the Clean one.

Fragile could refer to the fact that a relatively small looking change to your code could have a enormous impact on the runtime of the code because you unknowningly changed a value from being used uniquely to being used non-uniquely.

In clean, the annotations allow you to enforce the uniqueness, so this change would be caught by the type-checker. But, if the uniqueness is *only* inferred, then the user has to be very careful about ensuring uniqueness if they want performance gains associated with it -- and they have to do it without the help of the type-checker.

Having written a bit of clean code, I can say that it is very easy to accidently un-uniquify things.

That's exactly my point, but I probably didn't express it as clearly as you did. Thanks! Best regards Tomasz -- I am searching for a programmer who is good at least in some of [Haskell, ML, C++, Linux, FreeBSD, math] for work in Warsaw, Poland

On Thu, 8 Dec 2005, Duncan Coutts wrote:

For example it's not currently convenient to find out the strictness that ghc infers for functions (though it is possible). Ideally an IDE or something would be able to present this sort of information along with the inferred type etc.

It'd be nice if we had better strictness annotations available more generally, too.

So if it were easy to find out the uniqueness that the compiler was inferring then it might actually be useful to people that it did such an inference.

'twould be nice for type checking in general, although it's more the typing than just the types that's useful. -- flippa@flippac.org "My religion says so" explains your beliefs. But it doesn't explain why I should hold them as well, let alone be restricted by them.

On Thu, Dec 08, 2005 at 09:59:25PM +0100, haskell-cafe.mail.zooloo@xoxy.net wrote:

p.s.: Strangely, Tomasz's reply again appears as being sent from my address in the archive. Anyone knows why?

Maybe mailman is somehow confused by this weird address: "xoxy >>= haskell-cafe" <+haskell-cafe+zooloo+4067028ec0.haskell-cafe#haskell.org@spamgourmet.com> ? Best regards Tomasz -- I am searching for a programmer who is good at least in some of [Haskell, ML, C++, Linux, FreeBSD, math] for work in Warsaw, Poland

Sent: Friday, December 09, 2005 3:59 PM On Fri, Dec 09, 2005 at 05:49:15AM +0100, haskell-cafe.mail.zooloo@xoxy.net wrote:

On Thu, Dec 08, 2005 at 09:59:25PM +0100, haskell-cafe.mail.zooloo@xoxy.net wrote:

...

p.s.: Strangely, Tomasz's reply again appears as being sent from my address in the archive. Anyone knows why?

Maybe mailman is somehow confused by this weird address: "xoxy >>= haskell-cafe" <+haskell-cafe+zooloo+4067028ec0.haskell-cafe#haskell.org@spamgourmet.com> ? Relevant headers of this message: [...]

Looks like gourmet.spamgourmet.com resends to haskell-cafe@haskell.org messages addressed to +haskell-cafe+zooloo+4067028ec0.haskell-cafe#haskell.org@spamgourmet.com as if they were send from haskell-cafe.mail.zooloo@xoxy.net.

That is right. Apparently, there is something going wrong with carbon copies at the forwarding service. I couldn't reach the provider yet, so for the time being, I won't use the Cc field here anymore. To avoid further confusion, please, refrain from using the forwarding address (i. e. the lengthy one, containing many funny signs and numbers) as destination of your posts, be it in the "To" or in the "Cc" field. My address to reply or send a Cc to is just haskell-cafe.mail.zooloo@xoxy.net . Thanks, zooloo -- No virus found in this outgoing message. Checked by AVG Free Edition. Version: 7.1.371 / Virus Database: 267.13.12/192 - Release Date: 05.12.2005

Check section 6.2 of the ghc user's guide, under "How do I find out a function's strictness" :) It's in the .hi files. joelr1:

Duncan,

How do you find out the strictness that ghc infers for functions?

Thanks, Joel

On Dec 8, 2005, at 8:09 PM, Duncan Coutts wrote:

...

For example it's not currently convenient to find out the strictness that ghc infers for functions (though it is possible). Ideally an IDE or something would be able to present this sort of information along with the inferred type etc.

-- http://wagerlabs.com/

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

On Wed, Dec 07, 2005 at 08:21:42AM -0500, Jan-Willem Maessen wrote:

Yes, this could be done. The principle obstacles are the same as for any reference counting scheme: It imposes more run-time overhead than GC does, unless the data structures involved are large. Let me repeat that: accurate up-to-the-moment reference counting is dramatically slower than GC. Techniques exist to make ref counting fast, but they all require the equivalent of a full stack walk in order to get an accurate count.

For strict functions, does ghc do optimizations like this automatically? i.e. can it statically count references and avoid allocation of intermediates? -- David Roundy http://www.darcs.net

----- Original Message ----- From: "Jan-Willem Maessen - jmaessen@alum.mit.edu" Sent: Wednesday, December 07, 2005 2:21 PM

Wearing my "Fortress language designer" hat, we've given serious thought to these techniques for very large arrays. Copying such structures is terribly expensive, or even impossible (imagine copying a 1PB array).

That's slightly beyond the size of arrays I am currently dealing with. ;) I can see that in-place updating is of utmost importance in such cases. However, I was actually thinking of something the Clean people call "garbage collection at compile time", which, as far as I can see, involves no runtime overhead at all (Clean Language Report 2.1, section 9.1. - ftp://ftp.cs.kun.nl/pub/Clean/Clean20/doc/CleanLangRep.2.1.pdf). I don't quite see why it should be necessary to specify uniqueness attributes explicitely (as it mostly is in Clean), if the type checker knows the coercion laws better than me, anyway. Hence, my question about automatically deriving uniqueness properties of tokens, to the greatest extent safely feasible at compile time. (Sorry, if this is all trivial and already implemented in ghc. As indicated, I am merely learning Haskell, and I haven't spent any mentionable time yet to understand compiler intestines.) Regards, zooloo -- No virus found in this outgoing message. Checked by AVG Free Edition. Version: 7.1.371 / Virus Database: 267.13.12/192 - Release Date: 05.12.2005