The way to write the book, I think, would be to take something referred to as "real world problems" - problems a large proportion of programmers deals with and gets paid for, and then show how to solve these problems in Haskell (preferrably quicker and easier than with "conventional" solutions). I would divide the book into two parts. The first part would introduce Haskell via traditional small examples. Quick sort, towers of Hanoi, etc. The second part would have two or three large examples - something that people would relate to. I'd take a web application, tetris, and perhaps a chat server. Thanks, - Slava. On 12/11/06, Kirsten Chevalier wrote:

On 12/11/06, Patrick Mulder wrote:

...

In my opinion it would be important to increase the understanding about "semantics" and "processes". And it would be good to introduce the concepts in a similar way as Profokiev introduces the sound of classical music in "Peter and the Wolf". If my suspicion is correct, functional programming would be very close to composing classical music (or concurrent algorithms and processes). Has anyone of you similar thoughts on music and programming ? What are the basic ingredients for making abstractions (like in music rythm, keys, tempo, ...) ? It would be useful to express different ways of expression by explaining first "semantics" of processes and abstractions.

I love the analogy, though it's been at least eleven years since I tried to compose any music. (Coincidentally, eleven years ago was when I learned to program...)

I've often thought that reading code (if it's well-written code) is a little like reading a poem, which of course is also a little like listening to classical music. There's certainly a sense of rhythm involved in how you choose variable names: that's why nobody likes variable names like theHashTableThatStoresMappingsBetweenNamesAndEmails.

I'm not sure what the analogy with keys would be. Maybe writing in a point-free versus a pointed style is sort of like transposing a melody into another key.

For the potential book, I definitely think a Peter-and-the-Wolf-like idea is good. (The wolf would be unsafePerformIO, obviously.) Probably any metaphors that assume any knowledge of music should be left for a different piece of writing that assumes a different audience, but pursuing it would be fun. I've been thinking a lot lately about how to present computer science (and programming languages) to a popular audience, too. I don't remember who originally posed the question of "who's going to be the Carl Sagan of computer science?", but it's a question somebody should try to answer. (The answer isn't "Douglas Hofstadter", because obviously somebody needs to be out there explaining why languages with static type systems are cool, too.)

Cheers, Kirsten

-- Kirsten Chevalier* chevalier@alum.wellesley.edu *Often in error, never in doubt "Are you aware that rushing toward a goal is a sublimated death wish? It's no coincidence we call them 'deadlines'." -- Tom Robbins _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

[...] I think the concept of computer is better to see as sort of telescope or translator. Computers allow to look at processes (and complexity) which would otherwise not conceivable to our limited minds. The idea of computers as telescopes is from Daniel Dennett though.

"Computer Science is no more about computers than astronomy is about telescopes." :p More relevantly: again Dijkstra, but now on (programming as) composing music: "There are many different styles of composition. I characterize them always as Mozart versus Beethoven. When Mozart began to write at that time he had the composition ready in his mind. He wrote the manuscript and it was 'aus einem Guss' (casted as one). And it was also written very beautiful. Beethoven was an indecisive and a tinkerer and wrote down before he had the composition ready and plastered parts over to change them. There was a certain place where he plastered over nine times and one did remove that carefully to see what happened and it turned out the last version was the same as the first one."

Not sure whether this is the right place to discuss computers and programming in general: But Dijkstra's metaphor is suggesting, that while Beethoven learned by experiment and debugging compositions, Mozart did not have a need for reflection while writing down music ? The observation above sounds to me more as a difference between youthful enthousiasm (= allows few time for reflection but a lot for action) and old wisdom (= no risk taking but few action for the young). Also this difference has already been documented in Aristotele's Rethorics. It is of course difficult to transmit the characteristics of old age to young age, or vice versa. Furthermore about Dijkstra's quote on computers and telescopes which I like more. Telescopes are indeed not saying anything at all about the laws of the universe, as computers themselves don't say anything at all about complexity. But I wonder if we would have concepts as gravity or general relativity if we would have never had observed the movement of planets and light with telescopes. Equally, what can parallelity in computers teach us about the concept of monad ? I also find the approach of the designers of telescopes (= computer architects) interesting to understand parallel processes: http://view.eecs.berkeley.edu/wiki/Main_Page I think they use the name "dwarfs" for monads. PS I like the idea of a book "Hakell for Hackers" ___________________________________________________________ Telefonate ohne weitere Kosten vom PC zum PC: http://messenger.yahoo.de

You're implying that there's a *more* appropriate forum somewhere for discussing analogies between music composition and programming languages? If so, I'd like to know what it is!

Yes, music and programming languages are ultimately phenomena of our human brains/minds. Therefore, the expression of music or algorithms touch as much mathematics as they touch the field of philosophy (and here the philosophy of the mind). Sometimes there are interesting posts in comp.ai.philosophy and attempts to discuss the semantics in Mozart or Beethoven's style: http://groups.google.de/groups/search?hl=de&q=beethoven+mozart+comparison

I've been thinking about this. Are there really any programmers who are like Mozart in the way you describe?

No, and I think Dijkstra perception is a bit flawed with respect to Mozart's compositions. Certainly, there are very strong rewarding mechanisms in the brain which can be activated by special circumstances and allow to develop special capabilities (Feynman spoke about falling in love with an idea). But it is not highly desirable for a society to have every member to develop radical new idea's or skills. A species would quickly stop to reproduce if everyone would be sitting in a room thinking about a certain abstract subject.

Whereas it's conceivable to imagine somebody writing a piece of music that way, or a poem.

I think in general it is underestimated how rare such moments of divine inspiration are in reality. There is this nice speech by Wislawa Szymborska about the difficulties of inspiration in poetry (http://nobelprize.org/nobel_prizes/literature/laureates/1996/index.html).... and also the late Beethoven explains this in his music: Have a listening to the 3rd movement of his op.106. In my view, he explains about the suffering of a lonely genius, and then starts laughing about it because our own nature changes all the time, and that there is almost no way to control these changes, nor on time that passed away or predicting times to come, neither a judgement whether he is happy or not with this fact of life- I find it a very powerful observation on how learning works. ___________________________________________________________ Telefonate ohne weitere Kosten vom PC zum PC: http://messenger.yahoo.de

2006/12/12, Kirsten Chevalier :

[snip] I've been thinking about this. Are there really any programmers who are like Mozart in the way you describe? Donald Knuth might be one, or at least, he wrote that he wrote and debugged all of TeX on paper before entering it into a computer and "only found 13 more bugs" (or something like that), once he did. I don't remember if it was 13 exactly, but "13 more bugs" might be the closest that any programmer gets to Mozart, or at least any programmer in the 20th or early 21st century.

But, can you imagine waking up in the middle of the night, sitting down, and writing a compiler from start to finish? Well, of course, easily, undergrads do it all the time during finals period. But, one that works, and that contains original ideas? I know some awesome programmers, but I don't think any of them are quite that awesome. Whereas it's conceivable to imagine somebody writing a piece of music that way, or a poem. Does that just mean that computer science has a long way to go in maturation? Or does it mean something else?

Maybe you forget one fact : we're talking about people who have exprerience, not undergrad. Moreover, if we talk about experience in one area (for example computer languages, ore opera/classic music (not electro, pop, rock, jazz and so on), I'm sure there're people who have enough experience in compiler to try out a new idea in a short amount of time. Or in other discipline. I think I've read John Carmack wrote *several* 3d engines for each of their titles that throw them away. Another difference with music that strikes me is the level of abstraction : a note is a note. A line of code (especially in a imperative setting) is much more than a line of code. Ok, one can argue that notes interact together but, imo, not in the same way line of code can do. Programming is complex, you have to layer code on codeon code. Music is quite 'direct', you hear it without thinking. Bye, minh thu

If I remember my EWD's[1] right, whether or not composing music is similar to writing programs was not Dijkstra's point. I paraphrase (possibly from another EWD, can't be bothered to look it up): Computers, in their capacity as a tool, are highly overrated. Dijkstra was referring to the fact (as also pointed out earlier in this thread) that, due to the volatility of things written on a computer (be it text, code or whatever), someone who writes things on a computer is inclined, even encouraged, to write in a very iterative fashion. Aka you just blabber on until you read the whole thing, press shift-pageup delete, and more or less start over (times 20). Dijkstra argued that this leads to bad thinking habits, and maintained a (in those and these days) very special writing style, typically by hand or with a typewriter. It forces you to actually think about a sentence before you put it down. It is a habit I have been trying to cultivate myself, and I must say no one here will be able to convince me that he or she can more quickly outweigh different sentences or paragraph options on screen than I can in my head. Whenever I want to write something down, and I just can't seem to get it "right", I just take an empty piece of paper and write it. By hand. With a pen. I'm just old enough that I can remember writing papers in the earlier years of high school, by hand. I used to write them exactly twice: one time to get the text right, one time on the special school paper that I didn't like to waste. I've been re-training myself to be able to do that again. I've actually looked into some fairly old research, concerning the use of word processor and various so called tools in offices (not available online afaik, you'll have to search the library). If I remember correctly, some experiment was set up where professionial writers (journalists,...) were asked to write a number of words, some by hand, some with computers (as they preferred, ie as there habits dictated). It turns out that the writers who write by hand wrote much faster. Other studies typically show a decrease in offcice productivity after the installation of computer supported tools. Even on a recent ICSE (2005 I think), I saw a presentation of a sociologist or psychologist who measered the number of correct diagnosis of breast cancer using mammography, both with and without computer support. The outcome was not spectacularly in favour of the computer-supported case. It makes people lazy, and feel less responsible. Typically the harder to spot cases are better found by doctors without any computer support. I highly recommend reading some EWD's. They have changed my view on computing, programming, writing, basically about everything I do in my daily life. Kurt [1] Over a thousand manuscripts written by Edsger W. Dijkstra over his carreer, all available online. http://www.cs.utexas.edu/users/EWD/

On Tue, 12 Dec 2006 12:07:37 +0100, Kirsten Chevalier wrote:

On 12/12/06, Patrick Mulder wrote:

...

Not sure whether this is the right place to discuss computers and programming in general:

You're implying that there's a *more* appropriate forum somewhere for discussing analogies between music composition and programming languages? If so, I'd like to know what it is!

Maybe the UseNet newsgroup comp.music? -- Met vriendelijke groet, Henk-Jan van Tuyl -- http://Van.Tuyl.eu/ -- Using Opera's revolutionary e-mail client: https://secure.bmtmicro.com/opera/buy-opera.html?AID=789433

On 12/14/06, Benjamin Franksen wrote:

Kirsten Chevalier wrote:

...

(Since, of course, one should never apply the term "hacker" to oneself.)

Who told you that?

The Jargon File. But yes, I can anticipate more or less all of the possible responses to *that*, and, point taken.

Calling oneself 'hacker' is a sign of healthy self-respect; to the contrary, I don't know anyone who would call themselves wannabe-hacker.

Well, I hope so, since I contradict my own advice and call myself a hacker anyway :-)

Being a hacker is a matter of attitude and self-definition more than knowledge and experience. A hacker, even if young and lacking experience, reads books for hackers (if at all) not 'how do I become a hacker' books. The attitude is 'gimme the knowledge so i can go ahead and start doing real stuff', not 'oh, there is so much to learn, maybe after 10 years of study and hard work people will finally call me a hacker'.

Very reasonable. Very sane. Speaking of the term "hacker" and of various subcultures, the way in which Haskell and the open-source community seem to have met each other this year just makes me melt with joy. I know it wasn't like that six years ago; the Haskell community was small, and there wasn't exactly such a thing as the "open-source community" (and please let's not have a "free software" vs. "open source" debate, because I've heard that all before, too). I don't know exactly what happened in the meantime, besides the miracle of this vast series of tubes that we cann the Internet, but someone should really be writing a sociology paper about it. Cheers, Kirsten -- Kirsten Chevalier* chevalier@alum.wellesley.edu *Often in error, never in doubt "The geeks shall inherit the earth." -- Karl Lehenbauer

On Thu, Dec 14, 2006 at 17:45:45 +0100, Benjamin Franksen wrote: [..]

One is that it opens up new possibilities for individuals that were formerly closed to them. The two most prominent projects written in Haskell (darcs and Pugs) have both been started by a single person undertaking a project that would otherwise (i.e. without Haskell) have been just too complex to realize. (David Roundy once said that the C++ version he started with had after a while "amassed a solid number of bugs", so he gave up on it and started a re-implemention in Haskell (which clearly hasn't met the same fate).) With Haskell complex things become manageable for individuals again, and this opens whole new areas in the "noosphere" to conquer.

When reading this[1] I couldn't help thinking that rewriting GPG is an excellent opportunity for using Haskell to have an impact on the world. /M [1]: http://layer-acht.org/blog/debian/#1-58 -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus@therning.org Jabber: magnus.therning@gmail.com http://therning.org/magnus Software is not manufactured, it is something you write and publish. Keep Europe free from software patents, we do not want censorship by patent law on written works. "`How do you feel?' he asked him. `Like a military academy,' said Arthur, `bits of me keep passing out.' -- Arthur after his first ever teleport ride.

Bulat Ziganshin writes: (snip)

Haskell can't provide fast execution speed unless very low-level programming style is used (snip)

Is that an intrinsic feature of the language, or could compilers' optimisation plausibly get clever enough to do well without lots of seq and explicit unboxings and suchlike? -- Mark

G'day all. Quoting Neil Mitchell :

I believe that compilers can get a lot cleverer - my hope is that one day the natural Haskell definition will outperform a C definition.

First off, let's get something straight: Everyone's metric for "performance" is different. When someone makes a claim about the "performance" of some programming language (let alone a particular program built with a particular implementation), always ask how "performance" is measured. In my ad-hoc testing, Haskell has already outperformed most other languages for some of my projects using a particular metric that I care about at the time. For example, for certain types of problem, Haskell minimises the amount of time between the point where I start typing and the point where I have the answer. Similarly, I think today that a decent merge sort in Haskell is likely to outperform most C qsort() implementations TODAY, under reasonable conditions (reasonably large data set, for example), because C's qsort() interface simply cannot support good specialisation. This last point is important, because no matter what language you're writing in, and no matter what your metric for "performance" is, the best thing you can do for the performance of your code is to write your APIs carefully. If you do that, then when you find a performance problem, you can swap out the offending code, swap more in, and everything should work fine. The known performance problems in Haskell with I/O, and binary I/O in particular, are based in this issue, too. The insistance on defining String as [Char] means that your data is inefficiently represented even before it hits hPutStr. This is why I think it's a mistake to blame the performance of executable code. The biggest performance issues in a language tend to come from the part of the language in which you define the APIs. Cheers, Andrew Bromage

Bulat Ziganshin writes:

Hello ajb,

Monday, December 18, 2006, 4:12:01 AM, you wrote:

...

time. For example, for certain types of problem, Haskell minimises the amount of time between the point where I start typing and the point where I have the answer.

of course, we can fool any topic by changing the names. no one will say that Haskell is small productive language, the topic was just about speed of code generated

No. The topic was "A suggestion for the next high profile Haskell project", before that "Mozart vs. Beethoven" and before that "Haskell for Dummies". All of which could be construed to suggest the value of structure and clearness over mere performance.

...

Similarly, I think today that a decent merge sort in Haskell is likely to outperform most C qsort() implementations TODAY, under reasonable conditions (reasonably large data set, for example), because C's qsort() interface simply cannot support good specialisation.

is that really important, having cheap calls? how about comparision between

't'was your topic: speed. :-)

C sorting array of numbers and Haskell sorting *lazy* list of numbers? :)

Sorting lazy lists? I think they would have to be forced ..., wouldn't they? Regards -- Markus

| > Is that an intrinsic feature of the language, or could compilers' | > optimisation plausibly get clever enough to do well without lots of | seq | > and explicit unboxings and suchlike? | | I believe that compilers can get a lot cleverer - my hope is that one | day the natural Haskell definition will outperform a C definition. | | Of course, lazy evaluation makes that hard work, but I think it can be | done eventually. My view is that Haskell's performance is very seldom the limiting factor - often it is simply fast enough - when it isn't, optimising the algorithm often suffices (and that sort of refactoring can be much easier in a functional language) - when it doesn't, using lower-level stuff on small chunks of code often suffices - when none of these are enough, even C is sometimes not fast enough Of course there is a window in which C is fast enough and Haskell isn't. But I think that the window is fairly narrow. Much more significant are libraries, GUIs, database connections, integration with other languages etc. It's great to see so much work on these aspects happening in the Haskell community. All of that said, I agree with Neil that there is plenty of room for further improvement of performance. For example, in our data-parallel Haskell project, we're hoping for highly-competitive performance by doing aggressive fusion that just would not be possible in an imperative setting. (There's a status report on my home page.) Whole-program optimisation is another fertile area (e.g. jhc, mlton). Simon

On 12/18/06, Bulat Ziganshin wrote:

Hello Simon,

Monday, December 18, 2006, 12:08:49 PM, you wrote:

...

My view is that Haskell's performance is very seldom the limiting factor

of course. when someone said about GPG i just mentioned that this project may be hihgly speed-dependent and this case Haskell is definitely not the solution

I highly disagree. Why would you want to write 99% of your code in a tedious and error-prone way to get speed in 1% of your code? Isn't it better to write that 1% of the code in a slightly more tedious way (Haskell imitating C), or even call a foreign function for it? Yes, if you just write naive Haskell code it will probably be slower than C, but why on earth would you do that? There are significant benefits (less bugs, better security) of using Haskell over C, and the only benefit of C (speed) can be achieved where it matters by writing low-level imperative style Haskell, or calling C directly. I happen to think Haskell would be very well suited for this since the current project seems to be plagued by problems typical for C, and higly atypical for Haskell (book-keeping bugs, sometimes also leading to security issues). -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862

On Tue, Dec 19, 2006 at 01:55:55AM +0300, Bulat Ziganshin wrote:

no. it seems that you never tried to write such code and believe someone else who's said that such code may be written. try to write something very simple, like summing bytes in memory buffer, before you will do any conclusions

Are you claiming that every (even slightly) non-trivial problem (or algorithm) results in a mess of IO code in Haskell? Come on, admit that you like to program in imperative style, and that's why you end up with such mess ;-) Best regards Tomasz

why you (and Donald) don't want to understand me. i say that imperative Haskell code is more efficient than pure (and especially lazy) one and that even such code in ghc is slower than C equivalent.

I think the concern about execution speed of algorithms is a fairly recent topic. At least, the reason why compilers were developped at all was to save expensive memory capacity. Imagine to pay $3500 for 2kB memory! (http://www-03.ibm.com/ibm/history/exhibits/system7/system7_tpress.html) It would pay off to invest thinking in how to make programs short in terms of memory space usage. The counting of instruction cycles in speed context came only later when personal computers became mainstream. And nowadays, they use is an interesting idea of measuring performance in multimedia: "Quality of Experience". I don't know exactly which parameters play a role, but it is interesting to relate speed to human perception. At least, speed is relative after all (with respect to the timebase we use: eons to femtoseconds). Patrick ___________________________________________________________ Telefonate ohne weitere Kosten vom PC zum PC: http://messenger.yahoo.de

Hello Tomasz, Tuesday, December 19, 2006, 3:19:52 PM, you wrote:

...

why you (and Donald) don't want to understand me. i say that imperative Haskell code is more efficient

Your statement is too general to deserve answering.

can you provide couter-examples, or just believe? i mean maximum-optimized code in both cases -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Hello ls-haskell-developer-2006, Tuesday, December 19, 2006, 9:32:13 PM, you wrote:

...

...

...

why you (and Donald) don't want to understand me. i say that imperative Haskell code is more efficient

Second: Bulat, I think your generalization is, that performance matters so much and all the time

i don't say so. please don't make me a root of all evil :) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

On 12/18/06, Bulat Ziganshin wrote:

Hello Sebastian,

Monday, December 18, 2006, 10:58:52 PM, you wrote:

...

Yes, if you just write naive Haskell code it will probably be slower than C, but why on earth would you do that? There are significant benefits (less bugs, better security) of using Haskell over C, and the only benefit of C (speed) can be achieved where it matters by writing low-level imperative style Haskell, or calling C directly.

no. it seems that you never tried to write such code and believe someone else who's said that such code may be written. try to write something very simple, like summing bytes in memory buffer, before you will do any conclusions

Clearly non-trivial libraries such as Data.Bytestring and various of your own libraries coped just fine with low level programming in Haskell. As I said, you may write the imortant bits in C, or resort to using Ptr's etc (or slightly better, the ST monad if possible). in Haskell. The fact that you, for performance reasons, are forced to use a tedious and error prone style in a small part of the code is no reason to willingly choose to use it everywhere. And a small amount of syntactic convenience for this style of programming is certainly not a very good reason to use C. Now, there are a few apps that don't really have any hot spots, but GPG seems like a poster-child case for hot-spot optimization. Use a high level language to get it RIGHT first, then optimize the hot spots. And as I said, the problems with the current project seems to be that they have issues with correctness, not performance. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862

On Mon, Dec 18, 2006 at 11:57:59PM +0100, ls-haskell-developer-2006@m-e-leypold.de wrote:

... but I wonder: GPG, AFAIK undertakes some special measures to ensure that neither clear text nor private keys are paged out to the disk (since it might be recovered from there by "the enemy"). How would you lock data in memory in Haskell? Would that be possible?

It seems to me that all participants in this thread have missed this point so far.

You could just mlock() everything allocated by the RTS... Best regards Tomasz

On Tue, Dec 19, 2006 at 12:26:29AM +0100, ls-haskell-developer-2006@m-e-leypold.de wrote:

...

You could just mlock() everything allocated by the RTS...

Brute force. :-)

I would call it simplicity ;-) This way you are also guarding yourself against inadvertenty leaking clues about the key to non mlock'ed memory (cause everything is mlock'ed). Of course, the question is: how much memory will the program use.

Certainly the most simple way to do it. But is that option already here (say in ghc), or would one have to patch the runtime for that?

That's nitpicking :-) Best regards Tomasz

On Mon, Dec 18, 2006 at 20:11:05 -0500, Brandon S. Allbery KF8NH wrote:

On Dec 18, 2006, at 18:26 , ls-haskell-developer-2006@m-e-leypold.de wrote:

...

Tomasz Zielonka writes:

...

On Mon, Dec 18, 2006 at 11:57:59PM +0100, ls-haskell-developer-2006@m-e-leypold.de wrote:

...

... but I wonder: GPG, AFAIK undertakes some special measures to ensure that neither clear text nor private keys are paged out to the disk (since it might be recovered from there by "the enemy"). How would you lock data in memory in Haskell? Would that be possible?

It seems to me that all participants in this thread have missed this point so far.

You could just mlock() everything allocated by the RTS...

Brute force. :-) Certainly the most simple way to do it. But is that option already here (say in ghc), or would one have to patch the runtime for that?

Note also that this requires setuid root (yes, in gpg as well) --- so you are trading one known security issue for an unknown number of others.

Very true. In the end it comes down to what threats one wants to address and personally I don't think that the threat that mlock() addresses rates very highly. Even when taking into account the seemingly rampant misplacing of laptops of late. /M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus@therning.org Jabber: magnus.therning@gmail.com http://therning.org/magnus Software is not manufactured, it is something you write and publish. Keep Europe free from software patents, we do not want censorship by patent law on written works. As we enjoy great advantages from the inventions of others we should be glad of an opportunity to serve others by any invention of ours, and this we should do freely and generously. -- Benjamin Franklin

Hello Mark, Sunday, December 17, 2006, 9:13:08 PM, you wrote:

Is that an intrinsic feature of the language, or could compilers' optimisation plausibly get clever enough to do well without lots of seq and explicit unboxings and suchlike?

of course it is not language feature - if you will compile by hand, you can get any performance :) btw, there is "parallel arrays" project by Manuel Chakravarty et al, which is oriented toward generating of C-level efficent programs from pure array computations. but anyway this don't solves all efficiency problems 15 years ago i preferred asm because C compilers was not smart enough. may be 15 years later Haskell compilers will also generate asm-quality code. who knows?.. :) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Magnus Therning schrieb:

There is of course the possibility that Haskell would bring a whole slew of yet-to-be-determined security issues. I doubt it will be worse than C though.

Haskell might be prone to denial-of-service attacks. E.g. sending it data that cause it to evaluate an infinite data structure. Of course, any algorithm might run into an endless loop :-) Still, I'd want to have the results of a strictness analysis attached to Haskell software. That said, Haskell should be a *lot* more safe than C. Denial-of-service is something that one should take active precautions against, but it's still a far cry from the code injection vulnerabilities that come with most C software... Then again, avoiding global state and using a language with garbage collection, a strong type discipline and checked pointer dereferencing (say: Java, Ruby, Python, whatever) would probably go a far way towards safer software, even if it's not an FPL. Regards, Jo

Tomasz Zielonka schrieb:

On Mon, Dec 18, 2006 at 12:14:36AM +0100, Joachim Durchholz wrote:

...

Magnus Therning schrieb:

...

There is of course the possibility that Haskell would bring a whole slew of yet-to-be-determined security issues. I doubt it will be worse than C though. Haskell might be prone to denial-of-service attacks. E.g. sending it data that cause it to evaluate an infinite data structure.

That would be a bug in the implementation of an algorithm, not an inherent Haskell problem.

In the same way one could argue that running over the end of an array in C is a bug in the implementation of an algorithm, not an inherent C problem. IOW it's the same kind of problem: a kind of bug that the language, by its very nature, allows. The Haskell designers decided that the advantages (more flexibility in code reuse) outweighs the disadvantages (having bottom in every domain, potential for driving Haskell programs into nontermination by feeding them cleverly constructed inputs). I'm not sure that this problem really exists. It's just a potential problem that's difficult to diagnose. In other words, this kind of problem won't get much notice until people start attacking Haskell code in earnest. That's the reason why I'd like to see this kind of problem addressed before Haskell systems become both large and widely-used.

...

Still, I'd want to have the results of a strictness analysis attached to Haskell software.

Why? In case the strictness analyzer was buggy?

I'd be perfectly happy if that analysis were just a note saying "run ghc with such-and-these options and inspect the intermediate code for function foo to see that the strictness analyzer determined it will always terminate". I'm after checkability, not after making life miserable for programmers :-)

...

Then again, avoiding global state and using a language with garbage collection, a strong type discipline and checked pointer dereferencing (say: Java, Ruby, Python, whatever) would probably go a far way towards safer software, even if it's not an FPL.

But implementing deeply mathematical concepts in a mathematically oriented language (like Haskell) seems to be a better idea, if only to make the implementation closer to specification.

The equational properties of Haskell expressions make programming easier. I wouldn't expect them to help particularly for expressing mathematical concepts: for once, the bulk of GPG code is still about moving around and transforming data, not about mathematics; second, I'd expect that non-mathematical concepts benefit from equational reasoning just as much. Regards, Jo

Hi Joachim,

...

...

Why? In case the strictness analyzer was buggy?

I'd be perfectly happy if that analysis were just a note saying "run ghc with such-and-these options and inspect the intermediate code for function foo to see that the strictness analyzer determined it will always terminate".

I think you are asking too much from the strictness analyzer.

Why would you want strict code? Haskell's lazy semantics makes it much more amenable to equational reasoning. If you keep this laziness you can do all manner of proofs on the code. If what you want is real-time guarantees then something like the Hume project might be what you are after. Shoving a strictness analyser over a piece of code only returns info about the WHNF, nothing deeper. If you take it as anything more than an optimisation hint, it will come back and bite you... If what you do want is termination proofs, then you want this: http://www-i2.informatik.rwth-aachen.de/giesl/papers/RTA06-distribute.ps Thanks Neil

Hi minh thu,

Lazy semantics -> equational reasoning ? I thought that : lack of mutable state -> equational reasoning. For instance, I think to data flow variable in Oz (whcih I really don't know much / never used) : if a (Oz managed) thread attemps to read the value of an unbound (data flow) variable, it waits until another thread binds it. But the equational reasoning (referential transparency) remains (and the evaluation is eager by default).

Lack of mutable state, referentially transparent and laziness all help with equational reasoning. Inlining is much easier in a lazy language - and inlining is really handy for equational reasoning. Imagine: not_term = non_term f x = 12 Now evaluating: main = f non_term In a lazy language the value is always 12, in a strict language its always _|_. Now let's inline f: main = 12 In a lazy language the value is still 12, in a strict language the value has changed. Note how in a strict language inlining is not as safe as it once was... Thanks Neil

Hi

I don't know if any actual language does this,

What, that is strict and would like to inline things for performance? There is a reason they can't do this.

but your inlining problem can be solved by letting _|_ = arbitrary behaivor.

So would you allow folding? (inlining = unfolding) i.e. replacing defined behaviour with _|_? And how many equational reasoning steps do you have to go, before your program is totally different? Equational reasoning is easier in a lazy language. Thanks Neil

2006/12/19, Neil Mitchell :

Hi minh thu,

...

Lazy semantics -> equational reasoning ? I thought that : lack of mutable state -> equational reasoning. For instance, I think to data flow variable in Oz (whcih I really don't know much / never used) : if a (Oz managed) thread attemps to read the value of an unbound (data flow) variable, it waits until another thread binds it. But the equational reasoning (referential transparency) remains (and the evaluation is eager by default).

Lack of mutable state, referentially transparent and laziness all help with equational reasoning. Inlining is much easier in a lazy language - and inlining is really handy for equational reasoning.

Imagine:

not_term = non_term f x = 12

Now evaluating:

main = f non_term

In a lazy language the value is always 12, in a strict language its always _|_. Now let's inline f:

main = 12

In a lazy language the value is still 12, in a strict language the value has changed. Sorry, I don't see how it has changed. Isn't it still _|_ ? i.e.

main = _|_ Thanks minh thu

2006/12/19, Brandon S. Allbery KF8NH :

On Dec 19, 2006, at 16:03 , minh thu wrote:

...

2006/12/19, Neil Mitchell :

...

not_term = non_term f x = 12

Now evaluating:

main = f non_term

In a lazy language the value is always 12, in a strict language its always _|_. Now let's inline f:

main = 12

In a lazy language the value is still 12, in a strict language the value has changed. Sorry, I don't see how it has changed. Isn't it still _|_ ? i.e.

No, because inlining f results in the inlined value being 12, where it used to be _|_. Depending on the optimizer, it may well drop the call to non_term entirely because it's not being used (thus changing program semantics), or it may continue to call it (final result will remain _|_ because the inlined value is never reached).

Thank you, I see now. mt

Tomasz Zielonka schrieb:

On Tue, Dec 19, 2006 at 12:52:17PM +0100, Joachim Durchholz wrote:

...

Tomasz Zielonka schrieb:

...

On Mon, Dec 18, 2006 at 12:14:36AM +0100, Joachim Durchholz wrote:

...

Haskell might be prone to denial-of-service attacks. E.g. sending it data that cause it to evaluate an infinite data structure. That would be a bug in the implementation of an algorithm, not an inherent Haskell problem. In the same way one could argue that running over the end of an array in C is a bug in the implementation of an algorithm, not an inherent C problem.

But the C bug can cause vastly more unexpected things, and can often be used by an attacker to run arbitrary code in your program.

I was purposefully saying "denial-of-service bugs". By their nature, bugs of this type are far less dangerous than code injection bugs. (They are also much more visible, of course.)

...

IOW it's the same kind of problem: a kind of bug that the language, by its very nature, allows.

Trying to fully evaluate an infinite data structure will result in looping or memory exhaustion, and you have that possibilities in almost all languages.

Yes, but I suspect that Haskell makes it easier to make that kind of bug. Worse, it's easy to introduce this kind of bug: just pass a list returned from function a to function b, not being aware that a may return an infinite list and that b may do something with it that requires that it's evaluated. In other words, this kind of bug can come into existence during code integration... and the type system doesn't warn you when you do it.

...

potential for driving Haskell programs into nontermination by feeding them cleverly constructed inputs

But you agree that not all Haskell programs have this caveat? For correct programs you would have to actually feed them an infinitely big input to get nontermination.

No, not at all. You just need to construct an input that makes the first function return an infinite list and makes the second function force its evaluation. It may be more difficult to construct such inputs. Or code that has this kind of problem may be rare. So this may be irrelevant, or highly relevant, depending on how often this happens in practice. However, to find out how relevant this is, it's probably best to get some qualified feedback. E.g. by doing termination analysis on a reasonable sample of Haskell software and seeing how many of these return "will always terminate", "may not always terminate", "will not always terminate".

Some propose a variant of Haskell built on a strongly normalising calculus to reduce the risk of inadvertent nontermination.

I don't know how restrictive that would be. If it introduces restrictions, it may be more helpful to have code annotations (assertions in the form of preconditions and postconditions).

...

I'm not sure that this problem really exists. It's just a potential problem that's difficult to diagnose. In other words, this kind of problem won't get much notice until people start attacking Haskell code in earnest.

I think it's a similar kind of problem as the possibility of making an imperative program enter an infinite loop.

Well, an infinite loop is usually a local thing. Nontermination from laziness can be introduced by nonlocal interaction, and that's far more difficult to diagnose. (Note that this is not an imperative-vs-functional issue, but a strict-vs-lazy issue.)

...

...

...

Still, I'd want to have the results of a strictness analysis attached to Haskell software. Why? In case the strictness analyzer was buggy? I'd be perfectly happy if that analysis were just a note saying "run ghc with such-and-these options and inspect the intermediate code for function foo to see that the strictness analyzer determined it will always terminate".

I think you are asking too much from the strictness analyzer.

Actually I was typing too quickly there - it would have to be a termination checker. I know these things aren't easy. I'd like to have all sorts of properties checked for code - I'm hopelessly infected by my experience with preconditions and postconditions during my Eiffel years. They are an invaluable documentation tool, and they could be an invaluable verification tool. Regards, Jo

Seth Gordon schrieb:

Joachim Durchholz wrote:

...

...

Trying to fully evaluate an infinite data structure will result in looping or memory exhaustion, and you have that possibilities in almost all languages. Yes, but I suspect that Haskell makes it easier to make that kind of bug. Worse, it's easy to introduce this kind of bug: just pass a list returned from function a to function b, not being aware that a may return an infinite list and that b may do something with it that requires that it's evaluated. In other words, this kind of bug can come into existence during code integration... and the type system doesn't warn you when you do it.

If you're worrying about some unexpected input causing a function never to terminate, don't you also have to worry about some unexpected input causing a function to become so glacially slow that from the user's perspective, it *might as well* never terminate?

I'm not really talking about bad algorithms. I'd talking about integrating two innocent functions and getting a result that doesn't terminate. That's a problem that doesn't exist in strict languages: feeding the output of one function into another function won't turn terminating functions into nonterminating ones. However, you're right that composing functions might drastically change their performance - simply because the inner function may return data structures that are expensive to evaluate, and the outer function insists on evaluating them. So, for a lazy language, nontermination is just one side of the coin, the other is unexpected performance effects. OT3H this kind of problem may occur whenever you're passing around executable stuff, whether it's in the form of unevaluated lazy thunks, strict-language streams, or (to add the perspective from a non-FPL camp) passing around polymorphic objects that carry functions of unknown space and time complexity. It's probably a question of how idiomatic code behaves. OT4H I know how to annotate code with space and time complexities in a strict language. I.e. a Sort typeclass should impose an O(N log N) complexity on the sort function, slower sorts don't really do what the programmer expects - and that's then a guarantee that callers of the sort function can build upon. And while I have an in-principle approach for strict languages, I don't have one for lazy languages. Is there any literature on the subject? Regards, Jo

Quoting Bulat Ziganshin :

...

Haskell can't provide fast execution speed unless very low-level programming style is used (which is much harder to do in Haskell than in C, see one of my last messages for example) AND jhc compiler is used

I have to dispute this Bulat's characterisation here. We can solve lots of nice problems and have high performance *right now*. Particularly concurrency problems, and ones involving streams of bytestrings. No need to leave the safety of GHC either, nor resort to low level evil code. This obsession with mutable-variable, imperative code is unhealthy, Bulat ;)

ajb: The PGP format is heavily character stream-based. We know how horrible the performance of character streams are in Haskell. On one hand, this would be an excellent test case. On the other hand, performance would indeed suck now.

Unless you used a stream of lazy bytestrings! As Duncan did for his pure gzip and bzip2 bindings: compress, decompress :: ByteString -> ByteString http://haskell.org/~duncan/zlib/docs http://haskell.org/~duncan/bzlib/docs With underlying stream fusion, you keep the nice high level code. And no imperative gunk required! I see no reason a PGP tool couldn't be implemented similarly. -- Don P.S. The comments on this thread makes me think that the state of the art high perf programming in Haskell isn't widely known. Bulat-style imperative Haskell is rarely (ever?) needed in the GHC 6.6 Haskell code I'm writing in these days. Solving large data problems is feasible *right now* using bytestrings. Trying to write code using an imperative style is likely to do more harm than good, and certainly not something to suggest to beginners on the mailing list ;)

Hello Henning, Monday, December 18, 2006, 4:46:16 PM, you wrote:

Very true. I really like to know some more clean tricks for speedup.

use C. seriously :) you can look into sources of FPS and Streams libs, speed-optimized parts are written in the imperative way and all that you can do in Haskell is just emulate C imperative code, and even in this case speed (with ghc) will be 3-10 times worser than with gcc -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Hello Donald, Monday, December 18, 2006, 3:51:48 AM, you wrote:

...

...

Haskell can't provide fast execution speed unless very low-level programming style is used (which is much harder to do in Haskell than in C, see one of my last messages for example) AND jhc compiler is used

I have to dispute this Bulat's characterisation here. We can solve lots of nice problems and have high performance *right now*. Particularly concurrency problems, and ones involving streams of bytestrings. No need to leave the safety of GHC either, nor resort to low level evil code.

let's go further in this long-term discussion. i've read Shootout problems and concluded that there are only 2 tasks which speed is dependent on code-generation abilities of compiler, all other tasks are dependent on speed of used libraries. just for example - in one test TCL was fastest language. why? because this test contained almost nothing but 1000 calls to the regex engine with very large strings and TCL regex engine was fastest the same applies to the two above-mentioned areas - GHC wins in concurrency tests just because only built-in libraries considered, and GHC has a lightweight threads library built-in while C compilers don't with ByteString library, i know at least one example, where you have added function - readInt - to the library only to win in Shootout test

This obsession with mutable-variable, imperative code is unhealthy, Bulat ;)

so why your readInt routine is written in imperative way? ;)

...

ajb: The PGP format is heavily character stream-based. We know how horrible the performance of character streams are in Haskell. On one hand, this would be an excellent test case. On the other hand, performance would indeed suck now.

Unless you used a stream of lazy bytestrings! As Duncan did for his pure gzip and bzip2 bindings:

these are binding to existing C libs. if you try to convince us that to get fast FPS routines one need to write them in C and then provide Haskell binding, i will 100% agree otherwise, please explain me why your own function, readInt, don't use these fascinating stream fusion capabilities? ;)

P.S. The comments on this thread makes me think that the state of the art high perf programming in Haskell isn't widely known. Bulat-style imperative Haskell is rarely (ever?) needed in the GHC 6.6 Haskell code I'm writing in these days. Solving large data problems is feasible *right now* using bytestrings.

may be it's me who wrote FPS library? :) let's agree that high-performance code can be written in C and then called from Haskell. and when *you* want to have real performance, you write something very far from your optimistic words: readInt :: ByteString -> Maybe (Int, ByteString) readInt as | null as = Nothing | otherwise = case unsafeHead as of '-' -> loop True 0 0 (unsafeTail as) '+' -> loop False 0 0 (unsafeTail as) _ -> loop False 0 0 as where loop :: Bool -> Int -> Int -> ByteString -> Maybe (Int, ByteString) STRICT4(loop) loop neg i n ps | null ps = end neg i n ps | otherwise = case B.unsafeHead ps of w | w >= 0x30 && w <= 0x39 -> loop neg (i+1) (n * 10 + (fromIntegral w - 0x30)) (unsafeTail ps) | otherwise -> end neg i n ps end _ 0 _ _ = Nothing end True _ n ps = Just (negate n, ps) end _ _ n ps = Just (n, ps)

Trying to write code using an imperative style is likely to do more harm than good, and certainly not something to suggest to beginners on the mailing list ;)

of course, if you want to fool beginners, you can continue to sing these songs :D -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Hello Neil, Monday, December 18, 2006, 11:04:59 PM, you wrote:

...

let's go further in this long-term discussion. i've read Shootout problems It's more than 2 tasks that are dependant on the code generated by the compiler.

can you give me their names, please? :)

And in my opinion, generally the Clean solution was the nicest in terms of speed/performance. There is absolutely no reason Haskell can't be as fast as Clean. Clean doesn't seem to go to the imperative style in most of the benchmarks.

of course. i've written in Feb detailed analysis why ghc generates slower code than jhc/clean/ocaml. it's just not #1 priority and not so easy to fix

I think Bulat has a point, currently the speed of idiomatic Haskell lags behind that of idiomatic C. But the two responses to that have to be "currently", but not "forever". And idiomatic C is like pulling out your own teeth with a pair of pliers - sometimes necessary, but never fun.

saying about idiomatic Haskell, it is 100-1000 times slower :) look for example at http://www.cse.unsw.edu.au/~chak/papers/afp-arrays.ps.gz -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Hello Andy, Tuesday, December 19, 2006, 12:35:28 AM, you wrote:

...

and concluded that there are only 2 tasks which speed is dependent on

Maybe it would not be a bad idea to check the number of cache misses, branch mispredictions etc. per instruction executed for the shootout apps, in different languages, and of course, in haskell, on the platforms ghc targets. Do you think it might potentially be interesting to the GHC developing community to have such an overview? It might show potential bottlenecks, I think.

i was skipped one thing that is entirely obvious for me - all these fast libs are written in C :) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Hi,

The GHC head can currently build against PAPI[1], a library for gathering CPU statistics.

I did not know that. I know PAPI, though I prefer using perfctr directly, at least for what I'm doing (stuff in a JVM) [1], [2], [3].

At the moment you can only gather such statistics for AMD Opteron but it shouldn't be difficult to port it to other CPUs after a bit of browsing around the PAPI docs. Installing PAPI requires installing a linux kernel driver though, so it is not for the faint hearted.

Well, AFAIK, PAPI abstracts away the platform dependencies quite well, so I guess your code can be run straightforward on all IA-32 platforms (depending on the events you wish to measure, which may or may not be present on all platforms). PowerPC, Itanium, Mips, Alpha should work as well, IIRC. If the GHC backend can generate code there, that is.

We have used this library to find bottlenecks in the current code generation and we have implemented ways of correcting them, so expect some good news about this in the future.

Have you published anything about that?

I should get around to start a wiki page about using PAPI these days, but meanwhile feel free to contact me if you need further information or help.

I've been toying with this idea for a while [4], but never had the time to do something with it. If you have some cool stuff, let us know. I'm very interested. -- Andy [1] Eeckhout, L.; Georges, A.; De Bosschere, K. How Java Programs Interact with Virtual Machines at the Microarchitectural Level. Proceedings of the 18th Annual ACM SIGPLAN Conference on Object- Oriented Programming, Systems, Languages and Applications (OOPSLA 2003). ACM. 2003. pp. 169-186 [2] Georges, A.; Buytaert, D.; Eeckhout, L.; De Bosschere, K. Method- Level Phase Behavior in Java Workloads. Proceedings of the 19th ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages and Applications. ACM Press. 2004. pp. 270-287 [3] Georges, A.; Eeckhout, L.; De Bosschere, K. Comparing Low-Level Behavior of SPEC CPU and Java Workloads. Proceedings of the Advances in Computer Systems Architecture: 10th Asia-Pacific Conference, ACSAC 2005. Springer-Verlag GmbH. Lecture Notes in Computer Science. Vol. 3740. 2005. pp. 669-679 [4] http://sequence.complete.org/node/68

Alexey,

...

Well, AFAIK, PAPI abstracts away the platform dependencies quite well, so I guess your code can be run straightforward on all IA-32 platforms (depending on the events you wish to measure, which may or may not be present on all platforms). PowerPC, Itanium, Mips, Alpha should work as well, IIRC. If the GHC backend can generate code there, that is.

As the code stands now, data cache misses can be measured in a platform independent way. For branch mispredictions, I am using Opteron specific counters for reasons I no longer remember. Maybe I couldn't find platform independent counters in PAPI for branch misprediction.

Hmm, I think they should be there, IIRC. Anyway, it seems quite cool that you're doing that.

...

Have you published anything about that?

We are on the process of writing such a paper right now. My wish is to have the related code submitted to the head as soon as possible :). But at the moment we still have to tweak and clean up our optimisations a bit more.

Nice. Would you mind letting me know when you submitted something ... I'm quite interested.

...

...

I should get around to start a wiki page about using PAPI these days, but meanwhile feel free to contact me if you need further information or help.

I've been toying with this idea for a while [4], but never had the time to do something with it. If you have some cool stuff, let us know. I'm very interested.

The code in the head will allow you to get numbers for the Mutator and the GC separately. Also, I have hacked nofib-analyse so you can compare CPU statistics among different runs of the nofib suite. This is not committed yet, I guess it will make its way to the PAPI wiki page once it's up. I will let you know when I bring the page up.

Great, thanks! -- Andy

I'm allergic to hex constants. Surely, they are not necessary. -- Lennart On Dec 18, 2006, at 18:14 , Chris Kuklewicz wrote:

Hi all (and Don!),

I have some rewritten versions of readInt below...

Bulat Ziganshin wrote:

...

Hello Donald,

Monday, December 18, 2006, 3:51:48 AM, you wrote:

...

...

...

Haskell can't provide fast execution speed unless very low-level programming style is used (which is much harder to do in Haskell than in C, see one of my last messages for example) AND jhc compiler is used

...

I have to dispute this Bulat's characterisation here. We can solve lots of nice problems and have high performance *right now*. Particularly concurrency problems, and ones involving streams of bytestrings. No need to leave the safety of GHC either, nor resort to low level evil code.

let's go further in this long-term discussion. i've read Shootout problems and concluded that there are only 2 tasks which speed is dependent on code-generation abilities of compiler, all other tasks are dependent on speed of used libraries. just for example - in one test TCL was fastest language. why? because this test contained almost nothing but 1000 calls to the regex engine with very large strings and TCL regex engine was fastest

the same applies to the two above-mentioned areas - GHC wins in concurrency tests just because only built-in libraries considered, and GHC has a lightweight threads library built-in while C compilers don't

with ByteString library, i know at least one example, where you have added function - readInt - to the library only to win in Shootout test

...

This obsession with mutable-variable, imperative code is unhealthy, Bulat ;)

so why your readInt routine is written in imperative way? ;)

...

...

ajb: The PGP format is heavily character stream-based. We know how horrible the performance of character streams are in Haskell. On one hand, this would be an excellent test case. On the other hand, performance would indeed suck now.

...

Unless you used a stream of lazy bytestrings! As Duncan did for his pure gzip and bzip2 bindings:

these are binding to existing C libs. if you try to convince us that to get fast FPS routines one need to write them in C and then provide Haskell binding, i will 100% agree

otherwise, please explain me why your own function, readInt, don't use these fascinating stream fusion capabilities? ;)

...

P.S. The comments on this thread makes me think that the state of the art high perf programming in Haskell isn't widely known. Bulat-style imperative Haskell is rarely (ever?) needed in the GHC 6.6 Haskell code I'm writing in these days. Solving large data problems is feasible *right now* using bytestrings.

may be it's me who wrote FPS library? :) let's agree that high- performance code can be written in C and then called from Haskell. and when *you* want to have real performance, you write something very far from your optimistic words:

readInt :: ByteString -> Maybe (Int, ByteString) readInt as | null as = Nothing | otherwise = case unsafeHead as of '-' -> loop True 0 0 (unsafeTail as) '+' -> loop False 0 0 (unsafeTail as) _ -> loop False 0 0 as

where loop :: Bool -> Int -> Int -> ByteString -> Maybe (Int, ByteString) STRICT4(loop) loop neg i n ps | null ps = end neg i n ps | otherwise = case B.unsafeHead ps of w | w >= 0x30 && w <= 0x39 -> loop neg (i+1) (n * 10 + (fromIntegral w - 0x30)) (unsafeTail ps) | otherwise -> end neg i n ps

end _ 0 _ _ = Nothing end True _ n ps = Just (negate n, ps) end _ _ n ps = Just (n, ps)

...

Trying to write code using an imperative style is likely to do more harm than good, and certainly not something to suggest to beginners on the mailing list ;)

of course, if you want to fool beginners, you can continue to sing these songs :D

That code for readInt has no mutable state or IO, and it may be imperative style, it is not much like c-code.

I liked my readInt1 version below, which actually benchmarks faster than the GHC 6.6 Data.ByteString.Char8.readInt (on the little "test r" below). What a pleasant surprise.

The readInt2 version below is even more functional, but takes about 1.7 times as long to run "test r". (gaged from running "time ./ReadInt.2" on Mac OS X on a G4 cpu). The latest fusion in darcs fps might be better...

...

module Main(main) where

import Control.Arrow((***)) import Data.Char(chr,ord) import Data.ByteString(ByteString) import qualified Data.ByteString as B(null,foldl',span) import qualified Data.ByteString.Char8 as C (readInt,pack) import qualified Data.ByteString.Base as B(unsafeHead,unsafeTail) import Data.Ix(inRange) import Data.Maybe(fromJust) import Data.Word(Word8)

default ()

{-# INLINE chr8 #-} chr8 :: Word8 -> Char chr8 = chr . fromEnum {-# INLINE ord8 #-} ord8 :: Char -> Word8 ord8 = toEnum . ord

{-# INLINE decompose #-} decompose :: a -> (Word8 -> ByteString -> a) -> ByteString -> a decompose whenNull withHeadTail bs = if B.null bs then whenNull else (withHeadTail $! (B.unsafeHead bs)) $! (B.unsafeTail bs)

-- This does not do any bound checking if the Int overflows readInt1 :: ByteString -> Maybe (Int, ByteString) readInt1 bs = decompose Nothing (\h t -> case h of 0x2d -> fmap (negate *** id) $ first t -- '-' 0x2b -> first t -- '+' _ -> first bs) bs where first :: ByteString -> Maybe (Int, ByteString) first = decompose Nothing (\h t -> if inRange (0x30,0x39) h then Just (loop t $! (fromIntegral h-0x30)) else Nothing) loop :: ByteString -> Int -> (Int, ByteString) loop bs n = decompose (n,bs) (\h t -> if inRange (0x30,0x39) h then loop t $! (n*10+(fromIntegral h-0x30)) else (n,bs)) bs

readInt2 :: ByteString -> Maybe (Int,ByteString) readInt2 bs = decompose Nothing (\h t -> case h of 0x2d -> fmap (negate *** id) $ toInt t -- '-' 0x2b -> toInt t -- '+' _ -> toInt bs) bs where toInt :: ByteString -> Maybe (Int,ByteString) toInt bs = let (digits,rest) = B.span (inRange (0x30,0x39)) bs in if B.null digits then Nothing else Just (convert digits,rest) convert :: ByteString -> Int convert = B.foldl' (\n h -> n*10 + (fromIntegral h - 0x30)) 0

test r = let a = take 1000000 $ cycle [C.pack "13247897",C.pack "-13247896"] in (sum . map (fst . fromJust . r) $ a , take 4 a , map r $ take 4 a)

main = print $ test $ (readInt2)

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

Hello Tomasz, Tuesday, December 19, 2006, 2:35:35 AM, you wrote:

...

Haskell can't provide fast execution speed unless very low-level programming style is used (which is much harder to do in Haskell than in C, see one of my last messages for example) AND jhc compiler is used

I have experienced the opposite quite a number of times.

In some cases, Haskell's features (polymorphism, monads) allowed me to optimize code in a modular way, that is by adding a small amount of code (a new monad), rather than by rewriting lots of code. The resulting program had similar speed to C++ program.

it was because C++ program was not optimized at maximum, yes? :) we are saying about PGP, are you believe that its code isn't yet optimized? -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Hello Tomasz, Tuesday, December 19, 2006, 12:33:54 PM, you wrote:

...

it was because C++ program was not optimized at maximum, yes? :) we are saying about PGP, are you believe that its code isn't yet optimized?

We are talking about _useful_ programs. A program doesn't have to be blindingly fast to be useful.

in previous message you wrote that your Haskell program was not slower than C++ one. now you says that you don't need fast program. seems that you don't sure what you want to say -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

On Tue, Dec 19, 2006 at 01:24:36PM +0100, Tomasz Zielonka wrote:

I see a lack of will to understand on your part (the same thing you see in me :-). My statements are not contradictory: Some of the programs I was talking about were throw-away programs, for one use, and I would be satisfied even if they ran 10x-100x slower than they did, as long as they could finish the task. But it is nice to see that they are fast, even if they don't have to be, at least because it makes me more confident with using Haskell in more performance sensitive areas.

I didn't explain why I did optimize the program. It was not because of speed, but because of memory usage. Better speed was a welcome, but not neccesary side effect. Anyway, don't concentrate on this particular example. All I say is that: - sometimes I get efficient programs in Haskell right away (I my case quite often, but YMMV) - sometimes efficiency doesn't matter I don't think it is contradictory, especially because the two "sometimes" can have a non-empty symmetric difference. Best regards Tomasz

Hi

Obviously when

Cost(Upgrade) > Cost(Optimisation)

for the customer. Those costs are

Cost(Upgrade) = Price of more memory or new PC which is fast enough.

Cost(Optimisation) = Hours_spent * Fee_per_Hour / N

You are talking closed source commercial software for the masses. I don't know anyone who distributes software like this written in Haskell (although I'm sure there might be one or two) Now imagine working for a single company, or for small volume software. You ask them to upgrade, they turn around and say "bye bye". Now imagine you are working for a company, and have to convince people to throw away C and move to Haskell. Haskell is too slow will often be an initial argument, if its in any way right, that will be enough. Now imagine you are writing an open source project. People will turn around and use a Haskell compiler written in C (Hugs) instead of one written in Haskell (GHC) because its 100 times faster to load the program. Imagine you are writing a version control client, people will complain because certain operations take 100's of years on their big Haskell repo. [I use Hugs, and complain that darcs on the Yhc repo sometimes goes into virtual non-termination - although I love both GHC and darcs at the same time] Speed is sometimes important. Let's not forget that and wheel out cost of hardware arguments. Thanks Neil

On 12/19/06, ls-haskell-developer-2006@m-e-leypold.de wrote:

Tomasz Zielonka writes:

...

Anyway, don't concentrate on this particular example. All I say is that: - sometimes I get efficient programs in Haskell right away (I my case quite often, but YMMV) - sometimes efficiency doesn't matter I don't think it is contradictory, especially because the two "sometimes" can have a non-empty symmetric difference.

I'd like to add, that speed/efficiency is rather less important in "real world programming" than most people realize. Assume I write program for some clients with a total install base of N machines.

Assume I don't optimize.

If the program runs fast enough but could run faster, I'm wasting my time to optimize. I'd have to charge more money to the licensees / clients without actually delivering a better experience.

Assume now the unoptimized program doesn't run fast enough -- it's slow enough to seriously affect the user experience and the clients start grumbling.

Now, something has to be done: Either the customers have to upgrade their machines (I call that the MS experience ;-) or I have to optimize. The latter also incurs cost which finally has to be factored in the licensing / service fees for the program (if not I'd not be getting revenue from the program and had to close my shop :-).

Now let's ask: When is it better to optimize instead of urging the customer to upgrade?

Obviously when

Cost(Upgrade) > Cost(Optimisation)

for the customer. Those costs are

Cost(Upgrade) = Price of more memory or new PC which is fast enough.

Cost(Optimisation) = Hours_spent * Fee_per_Hour / N

(remember: N was the number of licensed Nodes).

So finally for optimisation to be the better decision, we must have:

Price_New_PC > Hours_spent * Fee_per_Hour / N

With hardware prices being as cheap as they are, hourly rates being not cheap (thanks to that :-), only optimizations pay that are either easy (done fast) or if you have a large number of customers / clients.

There are of course other real world scenarios. For example you may have competitors. I currently write C++ for my day job because in my industry (games) speed is a major "bullet point" on which you get judged. I do think that the trends are conspiring so that Haskell will outrun C/C++ "any day now". Probably not in "fair" comparisons, but easily in the "real world". E.g. when consoles have 40 cores your C++ engine may be faster in single threaded mode, but if the multithreaded version crashes too often to be useful or simply isn't good enough at utilizing the available hardware, the Haskell version (which doesn't crash, and uses all available cores) will win, even if it is multiple times slower in a "fair" benchmark. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862

Hello,

PS: Talking about smart programs: Is there a library anywhere that could be used to implement expert systems in Haskell or to evaluate Horn clauses in Prolog style?

Here is one possible starting point is the backtracking monad transformer by Oleg et al: http://okmij.org/ftp/Computation/monads.html#LogicT --Jeff --- This e-mail may contain confidential and/or privileged information. If you are not the intended recipient (or have received this e-mail in error) please notify the sender immediately and destroy this e-mail. Any unauthorized copying, disclosure or distribution of the material in this e-mail is strictly forbidden.

G'day all. Quoting Tomasz Zielonka :

I think it's high time to remind the very true Hoare's words: "Premature optimization is the root of all evil in programming" It's strange nobody mentioned it earlier.

You have yeard it said in the past that the three rules of optimisation are: Rule 1. Don't do it. Rule 2. (For experts only) Don't do it yet. Rule 3. (For real experts only) When you've found a performance issue, profile first, find where the bottlenecks are, and then optimise. For if you guess, you'll guess wrong. Truly I say unto you that there is a fourth rule: Rule 4. (For serious guru experts only) Sometimes, performance matters. When it matters, it REALLY matters. If you find yourself in this situation, then the performance that you need must be designed in; it can't be added later. So go ahead and spend ten minutes optimising your code on the back of an envelope before writing anything. It's fair to say that this conversation is mostly being conducted by experts, so we're way past rule 1. Which of rules 2, 3 or 4 apply to the hypothetical OpenPGP project can only be determined by someone trying it. Cheers, Andrew Bromage

Hello Tomasz, Tuesday, December 19, 2006, 3:24:36 PM, you wrote:

in me :-). My statements are not contradictory: Some of the programs I was talking about were throw-away programs, for one use, and I would be satisfied even if they ran 10x-100x slower than they did, as long as

you was 101st one who wrote this obvious thing -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Arie Peterson schrieb:

He wrote the manuscript and it was 'aus einem Guss' (casted as one).

The literal meaning of "aus einem Guss" is "cast all at once". This has overtones of "it is seamless, has no internal structural bounds which may cause the final product to fracture under stress". This is one of the highest praises that you can sing for software in German, so it's not an uncommon idiom in the field over here. Regards, Jo

I think this might be a good time to step back and make some general comments of my own. I learned Haskell in the summer of 2000. I see that that's exactly when SOE was published. I didn't have a copy. (I did acquire a copy of SOE about two years later, when I didn't need it anymore :-) I did have another book whose name I won't mention that I didn't find entirely helpful (I won't mention its name since I don't remember entirely for sure which book it was). I remember sitting in a windowless office trying to figure out why I couldn't seem to find any function that had the type IO a -> a. I'm thinking about that now because I hope to be able to not forget what it was like to be in that frame of mind. I'm sure SOE answers that question early on. But newbies on #haskell still ask it pretty often anyway. Obviously, there will always be people who don't know how to pick up a book, but on the other hand, I don't think that the problem of how to explain Haskell to beginners is solved yet. So the book that I want to write, hopefully with help from a few other people (maybe some of the people who've been contributing to the discussion so far, maybe others) would be aimed at a beginner (not a beginning programmer, but someone who's starting *perhaps* because they want to contribute to an open-source project that's written in Haskell, because there are such projects now that aren't Haskell compilers) who wants to get to the point where they can get real work done. And I'm not thinking of it as a textbook. Maybe this is way too ambitious. But I know that I managed to get from wondering where the IO a -> a function was to writing my own monad transformers, mostly by fumbling around in the dark, and I can't help thinking that there might be a possible book that would -- if not make it that much *easier* for somebody else to do the same -- at least allow *more* people to do the same. Cheers, Kirsten -- Kirsten Chevalier* chevalier@alum.wellesley.edu *Often in error, never in doubt "and the things I'm working on are invisible to everyone"--Meg Hutchinson

Hi,

I wonder if a similar "theme" is apropriate for proposed book. Graphics and sounds give a very direct feedback to the programmer, and I expect that helps with the motivation. Perhaps a single largish application could be the "end product" of the book. Like a game or something. You'd start off with some examples early on, and then as quickly as possible start working on the low level utility functions for the game, moving on to more and more complex things as the book progresses. You'd inevitably have to deal with things like performance and other "real world" tasks. It might be difficult to find something which would work well, though.

Maybe this idea (ok, isJust) comes to mind because I'm looking around at cakephp, which is a rails like framework for PHP, but a real-life example could be something like rails. It need not be as extensive or fully fledged, but enough such that people can get the hang of things and take it from there. That would include DB interaction, web interaction, logging, XML and what have you. It might just require enough of the more exotic Haskell stuff to get newbies up to speed. Details can be tackled either when they arise or deferred to an appendix, if they bloat the actual issues that is being explained. Just my €.02 -- Andy PS. I still belong somewhat to the latter category of the subject.

Paul Hudak wrote:

Maybe some of you can do better, but it's really tough to show someone how an /advanced/ Haskell programmer would solve /advanced /problems that arise in the real world. As a simple example, I love this recent quote by Garrett Morris:

"I'm personally fond of framing most non-trivial Haskell problems as defining domain specific languages; as a result, everything over about 200 lines that I've written in the past 3 years has used the mtl [Monad Transformer Library] in some form or fashion. It's great."

So how do we teach Garrett's way of programming (which I like very much) to the masses? I don't know either, but I would really like to have that book.

I started out with Haskell using resources like SOE, Thomson's "Craft of", and the "Gentle Introduction". Apart from reading the "Structure and Interpretation of Computer Programs", this was my first exposure to functional programming. Some things took a bit of effort to wrap my head around, but it generally wasn't too hard to get to a level where I could write useful programs. Now there is a plethora of introductions, tutorials and guides, and I wonder if we really need yet another 'for dummies' resource? The challenge for me is to learn more advanced practices. This is much harder to do - at least for me - for several reasons: * there is less material describing the advanced stuff * a lot of the existing material is in the form of research papers or similar communications between the cognoscenti. This (often) implies - it is hard to understand for us laymen - it isn't tied to practical problems * I'm already productive with what I know, so I don't have the direct motivation I generally manage to absorb just enough to get by, but I think there is a niche for a book (coupled to practical problems and complete with excercises etc) that is waiting to be filled. -k

Ketil Malde schrieb:

I generally manage to absorb just enough to get by, but I think there is a niche for a book (coupled to practical problems and complete with excercises etc) that is waiting to be filled.

Agreed. Something along the lines of "The Art of Functional Programming". HSoE is great as a starting textbook. However, it just scratches the surfaces - and after that, trying to grok monads keeps you occupied for a year or longer, keeping you distracted from developing other skills (such as writing and reading point-free code, or developing an intuition for curried code, or digging into a combinator library). Regards, Jo

On Wed, 13 Dec 2006 17:18:31 +0100, Justin Bailey wrote:

On 12/12/06, Joachim Durchholz wrote:

...

Agreed. Something along the lines of "The Art of Functional Programming".

+1 . I would love to read something that is the equivalent of 'design patterns', but for functional languages. I thought Osasaki's book "Purely Functional Data Structures" would have that, but it was little too focused on proving properties of algorithms. As someone in industry, that wasn't so important to me. I want to learn how to "think" functionally.

Seconded! The thing I appreciate about e.g. OO is that it is very clearly articulated what the principles are to make good design choices. Having e.g. some experience with grading fairly large OO projects from masters students, such a number of general rules of thumb are invaluable. It allows you to transform "good design" much more directly than through the typically Haskell way (it seems) of "code examples". OO also has a clear goal: to improve reuse and simplify evolution. More or less all design problems can be illustrated by saying: "but what happens if I want to add functionality y? You'll have to modify code in 200 places!" It seems that most (all?) Haskell introduction focus on features (functions, pattern matching, type classes, monads,...), who seem somewhat interchangeable for any given problem (at least to my newbie eyes). Also, most idioms on the wiki and answers on questions here are based on very specific examples, from which I find it hard to generalise. Usually the argument goes along this way: "Oh, I see you're using feature x (e.g. type classes). I prefer to use feature y (e.g. higher order functions) here, _because it's much more elegant_, and I rewrote your code as follows:" Instead of that emphasised part, I'd like to see a more particular explanation, that starts from properties of the _problem_ (not of the solution). Along the lines of: "Oh, I see you're having a typical representation problem where you need to decouple a data types structure from its content. Generally, this can be handled by using features x and y as follows. This will make it easy for you to change the type's content later with minimum changes, but will affect performance negatively if you' re not careful when using feature z." (ok, that didn't actually make sense, but you get the picture) Design patterns are a good way to make such knowledge explicit. At the moment, while learning haskell, my most important difficulty is how to translate a given problem to an elegant solution. What is elegant? What are my benchmarks to weigh different solutions against each other? Kurt

...

+1 . I would love to read something that is the equivalent of 'design patterns', but for functional languages.. I want to learn how to "think" functionally.

If you want to learn how to "think" functionally, forget you ever heard the words "design pattern". There shouldn't be patterns in your programs. If there are, that means that either your language isn't providing you with enough abstractions or that you aren't using the abstractions that are available (or possibly both).

while that is perhaps the ideal, we often hit intermediate stages, where it is useful to express the pattern of what we are trying to program, before attempting to extend the language so that we can capture that pattern more easily. and even if the pattern then becomes as trivial as "use MonadPlus for multiple solutions" or "use combinators and language recursion to capture grammars for parsers", it may still be useful to list them, because that makes it easier to communicate them to others (and would give newcomers a way in to making better use of the abstractions that are available). what is perhaps different in Haskell is that instead of managing growing databases of complex patterns with arbitrary names, the language evolves and generalizes existing features to make the common patterns easy to capture. once that happens, the pattern description becomes short enough and the language features become general enough to make invented names superfluous, and listings of design patterns less necessary. for many instances of that, and generally for nice-to-read Haskell, I recommend browsing through Mark Jones' papers: http://web.cecs.pdx.edu/~mpj/pubs.html for starters, try the Springschool paper or the one on monad transformers. Claus

G'day all. Quoting Donn Cave :

Well, maybe not Patterns, but wouldn't there be important skills relating to patterns in a more general sense? Like "fold", for example, seems to be a pattern, with several standard implementations and no doubt countless others to suit particular applications.

This is actually an excellent illustration of what patterns actually are. Patterns are a form of engineering experience. When we see the same form of code or data turning up multiple times, we abstract it and give it a name so we can reason about it independently of any application that we find it in. This is exactly the same as category theory. The point of category theory is to spot patterns in mathematical structures, and then abstract them away from those structures, and give them names so we can reason about them independently. The only real problem with patterns (apart from the hype) is that some people have the mistaken impression that Design Patterns == Gang of Four Book. The patterns that GoF documented were not meant to be an exhaustive list, nor were they meant to apply to non-OO languages. (The plethora of "modern C++"-style headers which encapsulate a lot of the GoF patterns are good examples.) Some patterns have different names in other languages. What GoF calls "factory method", for example, a Haskell programmer would call "smart constructor". What they call "flyweight" we call "memoing" or "hash consing". And some patterns are trivial in some languages but hard in others. In Haskell, forward iteration is trivial (we call it a "lazy list"), but it has to be manually added in Java. In C, global mutable state is trivial, but has to be manually simulated in Haskell. Cheers, Andrew Bromage

Those are some great resources, thanks everyone! Justin

Hello John, Tuesday, December 19, 2006, 7:16:48 PM, you wrote:

...

It's not as if this is the first time that this has been suggested, but some people have suggested that a practical book about Haskell would be a good idea. I agree. Some people have also suggested that the right moment for this hasn't arrived yet, and I see that as a challenge.

I know this is a late reply, but some of us tried to get something like this off the ground a little while back.

Haskell book? it can't be too late, it's invaluable thing! -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com