digitalmars.D - Go rant
- bearophile (6/7) Dec 14 2009 This is a mostly boring rant against the Go language:
- Sean Kelly (2/9) Dec 14 2009 If I had to guess I'd say that he's referring to that fact that value ty...
- bearophile (7/9) Dec 14 2009 Reading that page I have thought he wants all data to be managed by refe...
- Mike Farnsworth (2/6) Dec 14 2009 I think that's right, although he may have not realized one key thing: ...
- retard (20/42) Dec 15 2009 The fact that boxing is necessary in Java has not so much to do with it
- Peter C. Chapin (10/13) Dec 17 2009 I've been using Scala (http://www.scala-lang.org/) a fair about recently...
- retard (5/20) Dec 17 2009 Most likely they have will have to wrap lambdas inside some kind of
- Daniel de Kok (9/13) Dec 18 2009 One of the first necessities for good functional programming on the JVM
- retard (7/21) Dec 18 2009 I wouldn't be surprised to hear that. I don't think JVM or JVM languages...
- Walter Bright (15/18) Dec 18 2009 Many languages offer "show" examples that look elegant. A classic
- dsimcha (4/15) Dec 18 2009 I think this can be optimized out in theory, though I have no idea how o...
- Walter Bright (4/21) Dec 18 2009 I'm very doubtful it can be optimized out in theory. I'll bet it isn't
- Andrei Alexandrescu (5/23) Dec 18 2009 Median of N on singly-linked lists is highly nontrivial. More detail
- bearophile (8/15) Dec 18 2009 You are missing two big things, Walter:
- Andrei Alexandrescu (7/46) Dec 18 2009 It's a piece of crap. A crappy example is a crappy example is a crappy
- Ary Borenszweig (2/32) Dec 18 2009 What's that argument?
- Walter Bright (16/20) Dec 18 2009 I believe I do get it. After all, look at D's support for functional
- Walter Bright (3/5) Dec 18 2009 I take that back, later on it does mention the memory consumption proble...
- retard (34/61) Dec 18 2009 Let's try some better examples then:
- Andrei Alexandrescu (16/17) Dec 19 2009 Add to that the Erlang folk, too. I'm reading the book on Erlang by
- retard (15/37) Dec 19 2009 So now that you've finished writing your own book you have nothing else
- downs (5/46) Dec 19 2009 That's not what he said though - he said the example is inefficient, and...
- Walter Bright (12/24) Dec 19 2009 Andrei's book draft is out for review. If you wish to review it and make...
- Andrei Alexandrescu (13/52) Dec 19 2009 Well I haven't finished, and in fact I'm reading the Erlang book exactly...
- dsimcha (8/12) Dec 19 2009 Because most functional programming purists (or, to avoid singling out f...
- Andrei Alexandrescu (12/25) Dec 19 2009 That argument doesn't hold because qsort has quadratic complexity (which...
- retard (10/40) Dec 20 2009 How much faster, more elegant, or more reliable a functional programming...
- Daniel de Kok (27/36) Dec 21 2009 Well, it is elegant in that it is very readable, and as such provides
- Andrei Alexandrescu (27/69) Dec 21 2009 I disagree. We don't want to educate people to write patently
- retard (21/87) Dec 21 2009 I think one of the things that make good programming languages good is
- Andrei Alexandrescu (18/104) Dec 21 2009 That all sounds nice and I agree with it, but friction is also
- dsimcha (3/6) Dec 21 2009 Devil's advocate since I mostly agree:
- Daniel de Kok (18/26) Dec 22 2009 I do not mind it, it's ok for explaining a concept clearly. Of course,
- Walter Bright (8/17) Dec 22 2009 One of the big problems with the presentations of the functional qsort
- retard (32/52) Dec 22 2009 Well, in PL research community the terse functional quicksort code isn't...
- Walter Bright (20/29) Dec 22 2009 I disagree that this is what this thread is about. FP has a lot of
- retard (13/25) Dec 22 2009 People have very differents opinions about the matter now. Some think
- Andrei Alexandrescu (14/16) Dec 22 2009 It's an awesome book. It's also very frank and tells things as they are,...
- =?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= (13/32) Dec 22 2009 y=20
- retard (19/37) Dec 22 2009 That's a nasty limitation indeed. From my point of view imperative
- Andrei Alexandrescu (14/55) Dec 22 2009 Hm, I guess I should have been more explicit. The problem isn't defining...
- Rainer Deyke (6/11) Dec 22 2009 The implications of single assignment on control structures seem both
- Andrei Alexandrescu (4/14) Dec 22 2009 Good point - among other things, it explains why FP by and large tries
- Philippe Sigaud (10/19) Dec 23 2009 as
- Andrei Alexandrescu (4/29) Dec 23 2009 If you could ingest his thesis, you'll like the book, which is an
- retard (16/30) Dec 22 2009 I also have to say that the Haskell wiki doesn't exactly reflect the
- Walter Bright (4/11) Dec 22 2009 I don't need convincing of that. I agree it is a great advantage to FP.
- Daniel de Kok (15/20) Dec 22 2009 There are better examples of 'shining succes' in FP. For example,
- Andrei Alexandrescu (11/39) Dec 22 2009 My point is that there is no "concept" being explained. The concept of
- Daniel de Kok (15/21) Dec 22 2009 Hey, it's not me arguing for that. I think every paradigm has its place....
- Walter Bright (2/5) Dec 22 2009 Right, D is not a language implementing a religion!
- retard (3/15) Dec 21 2009 I have several imperative language programming books and instead of qsor...
- Lutger (2/19) Dec 21 2009 And do you think that is good and elegant or stupid and ugly?
- retard (2/24) Dec 21 2009 I'll let the official authority decide that. I have no opinion.
- Walter Bright (10/12) Dec 21 2009 Bubble sort should be part of an introductory programming course, if
- Andrei Alexandrescu (5/24) Dec 21 2009 Fro your arguments 1-4 and your conclusion, I infer you made a slight
- =?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= (16/42) Dec 21 2009 =20
-
Denis Koroskin
(8/44)
Dec 21 2009
On Tue, 22 Dec 2009 00:10:44 +0300, J=C3=A9r=C3=B4me M. Berger
- Charles Hixson (14/58) Dec 26 2009 of
- retard (5/65) Dec 26 2009 Nope, that's big time bs. http://en.wikipedia.org/wiki/
- Don (7/69) Dec 26 2009 I'd say it's easier. If you watch someone sorting some cards, they'll
- Walter Bright (3/7) Dec 26 2009 I suppose I'm alone in thinking that engineering school should also
- bearophile (6/8) Dec 27 2009 Knuth doesn't say it's uselsss to teach Bubble sort. Knowing bad algorit...
- dsimcha (5/12) Dec 27 2009 Yes, the same way programmers discuss anti-patterns. If it's a bad idea...
- Sean Kelly (2/11) Dec 27 2009 I'm sure every US-taught engineer has heard of the Tacoma Narrows Bridge...
- Walter Bright (10/17) Dec 27 2009 I did spend some time at Boeing designing airplane parts, and past
- dsimcha (4/6) Dec 27 2009 Well, the bubble sort distance is a pretty good metric of how similarly ...
- Don (6/13) Dec 27 2009 I don't think that's a coincidence. It seems to be defined in terms of
- Charles Hixson (47/63) Jan 13 2010 similarly
- Nick Sabalausky (10/33) Dec 21 2009 It should be "should be", for the same reason and in the same way that t...
- Daniel de Kok (5/8) Dec 21 2009 But it does have one nice property: due to laziness, the n-th elements
- Andrei Alexandrescu (12/21) Dec 21 2009 According to what I've read while looking into the subject, whether the
- Daniel de Kok (44/47) Dec 21 2009 I can not paste any of this particular code ($WORK). From the top of my
- retard (65/114) Dec 21 2009 This is an unfortunate implementation issue. There's probably a
- Walter Bright (3/7) Dec 21 2009 I would appreciate it if you could list these cases, and put them in a
- Phil Deets (5/12) Dec 21 2009 http://whatwg.org/html5 has a system where people can leave comments
- Kevin Bealer (4/27) Dec 21 2009 Ironically, I think you could write a nearly identical approach in D. B...
- Justin Johansson (9/56) Dec 22 2009 Don't have much time to read D NG these days but I saw this and felt it ...
- Justin Johansson (6/14) Dec 22 2009 Pity, Nick; chemistry was really good fun.
- Kevin Bealer (7/16) Dec 27 2009 (Non-software) people doing routine tasks often come up with better algo...
- dsimcha (7/9) Dec 27 2009 cards -- they might group cards by either suit or rank (or rank groups) ...
- Kevin Bealer (4/14) Dec 27 2009 More or less, though I think human beings use algorithms in a more artis...
- Simen kjaeraas (4/10) Dec 28 2009 I've heard of two-pivot quicksort, but can't remember where.
- Nekuromento (4/17) Dec 29 2009 Some information about dual pivot quicksort:
- justme (2/23) Dec 29 2009 Looks awesome? But the proof is too academical for my taste. Why can't D...
- Denis Koroskin (2/30) Dec 29 2009 http://www.dsource.org/projects/druntime/browser/trunk/src/rt/qsort.d
- Don (3/34) Dec 29 2009 Yeah, that's the obvious question -- what's the optimum number of
- bearophile (4/6) Dec 29 2009 Two pivots help avoid a common bad corner case of the QuickSort (when th...
- retard (4/12) Dec 30 2009 So can you tell us then what is the optimal number of pivots? Can it be
- bearophile (5/7) Dec 30 2009 I don't know. It can be proven that two pivot are enough to avoid the pr...
- Don (9/21) Dec 30 2009 From a cursory glance, it seems that the number of swaps (0.8)
- bearophile (8/11) Dec 30 2009 Yes, there is. The purpose of using two pivots is not to avoid the inevi...
- Rainer Deyke (10/16) Dec 27 2009 When sorting a deck of cards, insertion sort performs in O(n log n), the
- Kevin Bealer (3/22) Dec 27 2009 Right, if you mean strictly sorting a physical deck of cards by hand. I...
- justme (2/36) Dec 29 2009 I can't really read that code - apparently the author has not ever read ...
This is a mostly boring rant against the Go language: http://monoc.mo.funpic.de/go-rant/ Near the end it contains an interesting bit:Too, why this divide, again, with reference types and value types? Did they not learn from the problems this caused in Java? While Java slowly struggles its way free of that tarpit, the Go designers leap in headfirst.<Can someone here explain me this problem better? Bye, bearophile
Dec 14 2009
bearophile Wrote:This is a mostly boring rant against the Go language: http://monoc.mo.funpic.de/go-rant/ Near the end it contains an interesting bit:If I had to guess I'd say that he's referring to that fact that value types in Java are second-class citizens. The standard containers can only hold objects, so boxing is necessary, and that's such a pain in the ass that now boxing is automatic, leading to a lot of hidden allocations. I wouldn't think this applies to D however. D is a systems language and so must provide value types to deal with explicit memory layout of structured data, etc. Also, D uses templates instead of generics, and so doesn't have any of Java's container problems. I have absolutely no idea how all this applies to Go, however.Too, why this divide, again, with reference types and value types? Did they not learn from the problems this caused in Java? While Java slowly struggles its way free of that tarpit, the Go designers leap in headfirst.<Can someone here explain me this problem better?
Dec 14 2009
There are things that I read often around in blogs and papers (and sometimes even in books), but sometimes I keep not understanding them. Sean Kelly:If I had to guess I'd say that he's referring to that fact that value types in Java are second-class citizens. The standard containers can only hold objects, so boxing is necessary,<Reading that page I have thought he wants all data to be managed by reference.I have absolutely no idea how all this applies to Go, however.<Currently Go has no generics or templates, and it has both refence-based data and value data. Thank you for your answer, bye, bearophile
Dec 14 2009
bearophile Wrote:Sean Kelly:I think that's right, although he may have not realized one key thing: value types are value types in Go (and in D) for performance reasons, as they are targeted towards a systems-ish level of application. The nice thing about D is that, while you do have to memorize a few rules about what is default pass-by-value and what is pass-by-reference, D's templates and other language features likely get around most of the limitations and annoyances the author has.If I had to guess I'd say that he's referring to that fact that value types in Java are second-class citizens. The standard containers can only hold objects, so boxing is necessary,<Reading that page I have thought he wants all data to be managed by reference.
Dec 14 2009
Mon, 14 Dec 2009 19:51:10 -0500, Sean Kelly wrote:bearophile Wrote:The fact that boxing is necessary in Java has not so much to do with it not being a systems programming language. The problem is that Java VM doesn't reify the those types on runtime. I could easily write a new VM for Java and avoid all that boxing (although not being nearly as advanced erasing that type info. I don't know why the Sun engineers aren't fixing this. I guess there are some political and organizational problems involved. They fear that Java is getting too complex so they keep it simple, but slow and unproductive. That's not the only problem in JVM. Languages are getting more and more functional these days and many enterprise Java projects use ad-hoc single method interfaces to emulate lambdas. They're now solving the dynamic python/ruby/php/smalltalk/functional language like closures. Soon 99.9% of active programming languages have closure support - being able to say list.filter(\e => !e.isBadElement) seems to be the next cool thing..This is a mostly boring rant against the Go language: http://monoc.mo.funpic.de/go-rant/ Near the end it contains an interesting bit:If I had to guess I'd say that he's referring to that fact that value types in Java are second-class citizens. The standard containers can only hold objects, so boxing is necessary, and that's such a pain in the ass that now boxing is automatic, leading to a lot of hidden allocations. I wouldn't think this applies to D however. D is a systems language and so must provide value types to deal with explicit memory layout of structured data, etc. Also, D uses templates instead of generics, and so doesn't have any of Java's container problems.Too, why this divide, again, with reference types and value types? Did they not learn from the problems this caused in Java? While Java slowly struggles its way free of that tarpit, the Go designers leap in headfirst.<Can someone here explain me this problem better?I have absolutely no idea how all this applies to Go, however.Well, if it doesn't run in a VM (c++/d like template implementation) or global program optimizations are done, this shouldn't become a problem. I might be wrong, though.
Dec 15 2009
retard <re tard.com.invalid> wrote in news:hg8ppr$107b$4 digitalmars.com:That's not the only problem in JVM. Languages are getting more and more functional these days and many enterprise Java projects use ad-hoc single method interfaces to emulate lambdas.I've been using Scala (http://www.scala-lang.org/) a fair about recently. It's a function/OO hybrid language on the JVM that supports closures, etc. It's actually quite nice in a number of respects, I have no idea what kind of hoops the Scala implementors had to jump through to get it to work, though. I do know that compiling a typical Scala file generates a bunch of .class files with weirdo names so they are definitely creating quite a few auxillary classes behind the scenes to get things done. Peter
Dec 17 2009
Thu, 17 Dec 2009 12:24:50 +0000, Peter C. Chapin wrote:retard <re tard.com.invalid> wrote in news:hg8ppr$107b$4 digitalmars.com:Most likely they have will have to wrap lambdas inside some kind of Function objects. I've read that even Scala would benefit from a more functional friendly VM. But Sun's focus is on JavaFX and dynamic languages now..That's not the only problem in JVM. Languages are getting more and more functional these days and many enterprise Java projects use ad-hoc single method interfaces to emulate lambdas.I've been using Scala (http://www.scala-lang.org/) a fair about recently. It's a function/OO hybrid language on the JVM that supports closures, etc. It's actually quite nice in a number of respects, I have no idea what kind of hoops the Scala implementors had to jump through to get it to work, though. I do know that compiling a typical Scala file generates a bunch of .class files with weirdo names so they are definitely creating quite a few auxillary classes behind the scenes to get things done.
Dec 17 2009
On 2009-12-17 13:58:44 +0100, retard <re tard.com.invalid> said:Most likely they have will have to wrap lambdas inside some kind of Function objects. I've read that even Scala would benefit from a more functional friendly VM. But Sun's focus is on JavaFX and dynamic languages now..One of the first necessities for good functional programming on the JVM would be support for tail call optimization. I believe the Scala 2.7.x compiler performs this optimization only in the self-recursive case. From my first experiences with Scala for number crunching (machine learning), is that it is very slow for non-trivial programs. Besides that, it is the beauty of functional languages mixed with the mess of Java and generics. And it ain't pretty. -- Daniel
Dec 18 2009
Fri, 18 Dec 2009 16:43:35 +0100, Daniel de Kok wrote:On 2009-12-17 13:58:44 +0100, retard <re tard.com.invalid> said:I wouldn't be surprised to hear that. I don't think JVM or JVM languages are any good for number crunching. Besides that, the Scala implementation is probably quite immature at this point since it's so young. I've only seen how Scala solves problems elegantly. These are from some biased blog posts etc. Can you show one example that looks uglier in Scala, but looks decent in D or some other language?Most likely they have will have to wrap lambdas inside some kind of Function objects. I've read that even Scala would benefit from a more functional friendly VM. But Sun's focus is on JavaFX and dynamic languages now..One of the first necessities for good functional programming on the JVM would be support for tail call optimization. I believe the Scala 2.7.x compiler performs this optimization only in the self-recursive case. From my first experiences with Scala for number crunching (machine learning), is that it is very slow for non-trivial programs. Besides that, it is the beauty of functional languages mixed with the mess of Java and generics. And it ain't pretty.
Dec 18 2009
retard wrote:I've only seen how Scala solves problems elegantly. These are from some biased blog posts etc. Can you show one example that looks uglier in Scala, but looks decent in D or some other language?Many languages offer "show" examples that look elegant. A classic example is the one line Haskell quick sort: qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) prominently featured in Haskell's official introduction page: http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell Ain't that cool? But look closer. The advantage of quicksort is that it is an *in-place* sort. The Haskell one creates new arrays for every state in the sort. The other fundamental problem with the Haskell version is that it selects the first array element as the "pivot". This is the worst choice, since arrays to be sorted tend to already be mostly sorted, and quicksort gives quadratic performance to sort an already sorted array with the first element as the pivot. Ironically, the quicksort example shows a serious weakness of functional programming, not an elegant strength.
Dec 18 2009
== Quote from Walter Bright (newshound1 digitalmars.com)'s articleqsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) prominently featured in Haskell's official introduction page: http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell Ain't that cool? But look closer. The advantage of quicksort is that it is an *in-place* sort. The Haskell one creates new arrays for every state in the sort.I think this can be optimized out in theory, though I have no idea how often it is in practice.The other fundamental problem with the Haskell version is that it selects the first array element as the "pivot". This is the worst choice, since arrays to be sorted tend to already be mostly sorted, and quicksort gives quadratic performance to sort an already sorted array with the first element as the pivot.True. All you'd need to remedy this, though, is a median of 3 function.
Dec 18 2009
dsimcha wrote:== Quote from Walter Bright (newshound1 digitalmars.com)'s articleI'm very doubtful it can be optimized out in theory. I'll bet it isn't done in practice.qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) prominently featured in Haskell's official introduction page: http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell Ain't that cool? But look closer. The advantage of quicksort is that it is an *in-place* sort. The Haskell one creates new arrays for every state in the sort.I think this can be optimized out in theory, though I have no idea how often it is in practice.Then it's not looking so simple and elegant anymore :-)The other fundamental problem with the Haskell version is that it selects the first array element as the "pivot". This is the worst choice, since arrays to be sorted tend to already be mostly sorted, and quicksort gives quadratic performance to sort an already sorted array with the first element as the pivot.True. All you'd need to remedy this, though, is a median of 3 function.
Dec 18 2009
dsimcha wrote:== Quote from Walter Bright (newshound1 digitalmars.com)'s articleMedian of N on singly-linked lists is highly nontrivial. More detail about the failings of functional qsort: http://www.informit.com/articles/printerfriendly.aspx?p=1407357 Andreiqsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) prominently featured in Haskell's official introduction page: http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell Ain't that cool? But look closer. The advantage of quicksort is that it is an *in-place* sort. The Haskell one creates new arrays for every state in the sort.I think this can be optimized out in theory, though I have no idea how often it is in practice.The other fundamental problem with the Haskell version is that it selects the first array element as the "pivot". This is the worst choice, since arrays to be sorted tend to already be mostly sorted, and quicksort gives quadratic performance to sort an already sorted array with the first element as the pivot.True. All you'd need to remedy this, though, is a median of 3 function.
Dec 18 2009
Walter Bright:Ain't that cool? But look closer. The advantage of quicksort is that it is an *in-place* sort. The Haskell one creates new arrays for every state in the sort. The other fundamental problem with the Haskell version is that it selects the first array element as the "pivot". This is the worst choice, since arrays to be sorted tend to already be mostly sorted, and quicksort gives quadratic performance to sort an already sorted array with the first element as the pivot.You are missing two big things, Walter: 1) The first one is big: that was not an example of a general-purpose sort routine to be used to sort items. If you go look at how normal system sort is done in Haskell you will see a much longer and much more efficient implementation. The point of that example was to show how you can compactly express a computational idea in Haskell, in a safe, very compact and readable enough way. In a normal program a significant percentage of the code doesn't need to be top performance, in both runtime performance and memory used, because it's used rarely and/or on small data sets. So for this code it's not good to write an extremely efficient implementation, it's better to use a safe, very compact and readable implementation. Haskell gives you both safety and compact code. Note that for real sorting purposes you don't use that onliner, you use some kind of system sort. So what I am says applies to new code, absent in the standard library. 2) The second point you are missing is even bigger. Today languages as Clojure They reduce bugs, allow a quite simpler multi-processing (so they are multicore-friendly) and they allow a more functional-style coding (that in the hands of a modern compiler/VM allows gives enough semantic constraints to allow a good compilation. See pure functions). This of course puts more pressure on the garbage collector, but the GC of Haskell is designed for this purpose, and the compile is able to optimize away some of this work. The resulting code is not as efficient as C code on a single CPU but on many CPUs it may lead to efficient code. Please ask if you have missed my two points, because they must be understood if you want to design a modern language. Bye, bearophile
Dec 18 2009
bearophile wrote:Walter Bright:It's a piece of crap. A crappy example is a crappy example is a crappy example. It consistently does more harm than good.Ain't that cool? But look closer. The advantage of quicksort is that it is an *in-place* sort. The Haskell one creates new arrays for every state in the sort. The other fundamental problem with the Haskell version is that it selects the first array element as the "pivot". This is the worst choice, since arrays to be sorted tend to already be mostly sorted, and quicksort gives quadratic performance to sort an already sorted array with the first element as the pivot.You are missing two big things, Walter: 1) The first one is big: that was not an example of a general-purpose sort routine to be used to sort items. If you go look at how normal system sort is done in Haskell you will see a much longer and much more efficient implementation. The point of that example was to show how you can compactly express a computational idea in Haskell, in a safe, very compact and readable enough way. In a normal program a significant percentage of the code doesn't need to be top performance, in both runtime performance and memory used, because it's used rarely and/or on small data sets. So for this code it's not good to write an extremely efficient implementation, it's better to use a safe, very compact and readable implementation. Haskell gives you both safety and compact code. Note that for real sorting purposes you don't use that onliner, you use some kind of system sort. So what I am says applies to new code, absent in the standard library.2) The second point you are missing is even bigger. Today languages immutabe data structures. They reduce bugs, allow a quite simpler multi-processing (so they are multicore-friendly) and they allow a more functional-style coding (that in the hands of a modern compiler/VM allows gives enough semantic constraints to allow a good compilation. See pure functions). This of course puts more pressure on the garbage collector, but the GC of Haskell is designed for this purpose, and the compile is able to optimize away some of this work. The resulting code is not as efficient as C code on a single CPU but on many CPUs it may lead to efficient code.Quicksort is parallellizable although it uses mutation so you chose the wrong example to make an otherwise generally valid point.Please ask if you have missed my two points, because they must be understood if you want to design a modern language.I'd say that's a tad assuming :o). Andrei
Dec 18 2009
Andrei Alexandrescu wrote:bearophile wrote:What's that argument?Walter Bright:It's a piece of crap. A crappy example is a crappy example is a crappy example. It consistently does more harm than good.Ain't that cool? But look closer. The advantage of quicksort is that it is an *in-place* sort. The Haskell one creates new arrays for every state in the sort. The other fundamental problem with the Haskell version is that it selects the first array element as the "pivot". This is the worst choice, since arrays to be sorted tend to already be mostly sorted, and quicksort gives quadratic performance to sort an already sorted array with the first element as the pivot.You are missing two big things, Walter: 1) The first one is big: that was not an example of a general-purpose sort routine to be used to sort items. If you go look at how normal system sort is done in Haskell you will see a much longer and much more efficient implementation. The point of that example was to show how you can compactly express a computational idea in Haskell, in a safe, very compact and readable enough way. In a normal program a significant percentage of the code doesn't need to be top performance, in both runtime performance and memory used, because it's used rarely and/or on small data sets. So for this code it's not good to write an extremely efficient implementation, it's better to use a safe, very compact and readable implementation. Haskell gives you both safety and compact code. Note that for real sorting purposes you don't use that onliner, you use some kind of system sort. So what I am says applies to new code, absent in the standard library.
Dec 18 2009
bearophile wrote:Please ask if you have missed my two points, because they must be understood if you want to design a modern language.I believe I do get it. After all, look at D's support for functional programming (immutable and pure). I wrote the post in reply to "Can you show one example that looks uglier in Scala, but looks decent in D or some other language?" Whatever the advantages of FP, and there are many, to keep trotting out the qsort example front and center is a huge mistake. The Haskell qsort example is horrible in that it purports to show how elegant and simple FP is, but instead shows a misguided and essentially useless implementation. The Haskell qsort example is not only the VERY FIRST example given for the language on the INTRODUCTORY PAGE of the Haskell wiki, and is under the heading "What's good about functional programming?". There is no mention in the text of any of the egregious shortcomings of the example.Note that for real sorting purposes you don't use that onliner, you use some kind of system sort.useless for real programming. The Haskell folks really need to find a better canonical example.
Dec 18 2009
Walter Bright wrote:There is no mention in the text of any of the egregious shortcomings of the example.I take that back, later on it does mention the memory consumption problem: http://www.haskell.org/haskellwiki/Introduction#When_C_is_better
Dec 18 2009
Fri, 18 Dec 2009 16:42:27 -0800, Walter Bright wrote:bearophile wrote:Let's try some better examples then: **) function composition [haskell] (.) :: (b->c) -> (a->b) -> (a->c) f . g = \ x -> f (g x) (note how the syntax is readable unlike the ass-backwards function type syntax in C/D) **) custom control structures [scala] (new Object) synchronized { ... } 1 to 42 foreach println react {}, loop {}, receive {} etc. in actors lib **) consistent return values from control constructs a = if predicate then foo else bar val a = if (predicate) foo else bar b = case foo of A -> 1 ... Z -> 27 val b = foo match { case A => 1 ... case Z => 27 **) serious pattern matching [scala] foo match { case Nil => println("Empty list, it seems") case 1 :: 2 :: _ => println("Got 1,2,… list") case 9 :: 8 :: 7 :: _ => println("Got 9,8,7,… list") case _ => } **) lazy evaluation myIf a b c = if a then b else c def myIf[A <: C,B <: C,C](a: Boolean, b: => A, c: => B) = if (a) b else cPlease ask if you have missed my two points, because they must be understood if you want to design a modern language.I believe I do get it. After all, look at D's support for functional programming (immutable and pure). I wrote the post in reply to "Can you show one example that looks uglier in Scala, but looks decent in D or some other language?" Whatever the advantages of FP, and there are many, to keep trotting out the qsort example front and center is a huge mistake. The Haskell qsort example is horrible in that it purports to show how elegant and simple FP is, but instead shows a misguided and essentially useless implementation. The Haskell qsort example is not only the VERY FIRST example given for the language on the INTRODUCTORY PAGE of the Haskell wiki, and is under the heading "What's good about functional programming?". There is no mention in the text of any of the egregious shortcomings of the example.Note that for real sorting purposes you don't use that onliner, you use some kind of system sort.useless for real programming. The Haskell folks really need to find a better canonical example.
Dec 18 2009
Walter Bright wrote:The Haskell folks really need to find a better canonical example.Add to that the Erlang folk, too. I'm reading the book on Erlang by Armstrong. Here's the Quicksort section and example on page 52: "Here's how to write a sort algorithm[footnote] using two list comprehensions." The footnote says (how the hell did this make it through the editorial pass???) "This code is shown for its elegance rather than its efficiency. Using ++ in this way is not generally considered good programming practice." So if the code is inefficient and in poor programming practice, how in this blessed world could it count as elegant? I have gathered a fair amount of samples of involuntary humor from that book. I wouldn't want to go on about that because it could too easily be interpreted as poor taste competitiveness. Let me say I don't think the book is well written. Andrei
Dec 19 2009
Sat, 19 Dec 2009 14:04:32 -0600, Andrei Alexandrescu wrote:Walter Bright wrote:So now that you've finished writing your own book you have nothing else to do but to bash all books written by users of competitive languages. How low.. I'm 100% sure I can find a suboptimal programming example from some C/C++/ D book. Just like an operating system implementation book discusses Minix or some educational kernel, it's not really a surprise that programming books have naive examples. I'm not really interested to hear how latest win7 or linux 2.6.33 kernel patch solves some SATA2 / btrfs issue when reading about filesystems and buses. You should take those words about relative elegance with a grain of salt. Functional code is usually less verbose, less buggy, a bit less efficient due to many issues etc. These are things most professionals agree with. Apparently D users need to enhance their e-dick by ranting about everything that's not done in d just to get a tiny bit of publicity.The Haskell folks really need to find a better canonical example.Add to that the Erlang folk, too. I'm reading the book on Erlang by Armstrong. Here's the Quicksort section and example on page 52: "Here's how to write a sort algorithm[footnote] using two list comprehensions." The footnote says (how the hell did this make it through the editorial pass???) "This code is shown for its elegance rather than its efficiency. Using ++ in this way is not generally considered good programming practice." So if the code is inefficient and in poor programming practice, how in this blessed world could it count as elegant? I have gathered a fair amount of samples of involuntary humor from that book. I wouldn't want to go on about that because it could too easily be interpreted as poor taste competitiveness. Let me say I don't think the book is well written.
Dec 19 2009
retard wrote:Sat, 19 Dec 2009 14:04:32 -0600, Andrei Alexandrescu wrote:It's his opinion and he, being an author himself, has a better basis for it than you do.Walter Bright wrote:So now that you've finished writing your own book you have nothing else to do but to bash all books written by users of competitive languages. How low..The Haskell folks really need to find a better canonical example.Add to that the Erlang folk, too. I'm reading the book on Erlang by Armstrong. Here's the Quicksort section and example on page 52: "Here's how to write a sort algorithm[footnote] using two list comprehensions." The footnote says (how the hell did this make it through the editorial pass???) "This code is shown for its elegance rather than its efficiency. Using ++ in this way is not generally considered good programming practice." So if the code is inefficient and in poor programming practice, how in this blessed world could it count as elegant? I have gathered a fair amount of samples of involuntary humor from that book. I wouldn't want to go on about that because it could too easily be interpreted as poor taste competitiveness. Let me say I don't think the book is well written.I'm 100% sure I can find a suboptimal programming example from some C/C++/ D book.That's not what he said though - he said the example is inefficient, and *also* that he considers the book to be poorly written.Just like an operating system implementation book discusses Minix or some educational kernel, it's not really a surprise that programming books have naive examples. I'm not really interested to hear how latest win7 or linux 2.6.33 kernel patch solves some SATA2 / btrfs issue when reading about filesystems and buses. You should take those words about relative elegance with a grain of salt. Functional code is usually less verbose, less buggy, a bit less efficient due to many issues etc. These are things most professionals agree with.The issue is that what this example demonstrates, is that functional code is apparently _either_ elegant _or_ efficient. This is not a good trade-off to be forced to make.Apparently D users need to enhance their e-dick by ranting about everything that's not done in d just to get a tiny bit of publicity.Nice.
Dec 19 2009
retard wrote:I'm 100% sure I can find a suboptimal programming example from some C/C++/ D book.Andrei's book draft is out for review. If you wish to review it and make suggestions for improvement, I'm sure Andrei can arrange that. Now's the time to do that!Just like an operating system implementation book discusses Minix or some educational kernel, it's not really a surprise that programming books have naive examples. I'm not really interested to hear how latest win7 or linux 2.6.33 kernel patch solves some SATA2 / btrfs issue when reading about filesystems and buses. You should take those words about relative elegance with a grain of salt. Functional code is usually less verbose, less buggy, a bit less efficient due to many issues etc. These are things most professionals agree with. Apparently D users need to enhance their e-dick by ranting about everything that's not done in d just to get a tiny bit of publicity.I've read many books about programming languages. One stands out - K&R's The C Programming Language. The code examples in it are marvelous in conciseness and utility. It is possible to write a programming language book that way, and there's a good reason why K&R is an enduring classic of the genre. I know it's hard to come up with examples that are illustrative, educational, elegant, and concise, but it is worth the author's best efforts in trying to do so.
Dec 19 2009
retard wrote:Sat, 19 Dec 2009 14:04:32 -0600, Andrei Alexandrescu wrote:Well I haven't finished, and in fact I'm reading the Erlang book exactly to get better insight into handling concurrency via message passing. Apparently I haven't managed to qualify my statements well enough - I tried to make it clear I'm not going for cheap shots, so I'm a bit puzzled that you fell exactly for that.Walter Bright wrote:So now that you've finished writing your own book you have nothing else to do but to bash all books written by users of competitive languages. How low..The Haskell folks really need to find a better canonical example.Add to that the Erlang folk, too. I'm reading the book on Erlang by Armstrong. Here's the Quicksort section and example on page 52: "Here's how to write a sort algorithm[footnote] using two list comprehensions." The footnote says (how the hell did this make it through the editorial pass???) "This code is shown for its elegance rather than its efficiency. Using ++ in this way is not generally considered good programming practice." So if the code is inefficient and in poor programming practice, how in this blessed world could it count as elegant? I have gathered a fair amount of samples of involuntary humor from that book. I wouldn't want to go on about that because it could too easily be interpreted as poor taste competitiveness. Let me say I don't think the book is well written.I'm 100% sure I can find a suboptimal programming example from some C/C++/ D book.Yah, but that's not the one that's featured prominently as one of the coolest examples there is, and it wouldn't be horrendously bad. Virtually all introductions to FP contain this ridiculous qsort. It should be dipped in tar and feathers and showed around the town.Just like an operating system implementation book discusses Minix or some educational kernel, it's not really a surprise that programming books have naive examples. I'm not really interested to hear how latest win7 or linux 2.6.33 kernel patch solves some SATA2 / btrfs issue when reading about filesystems and buses. You should take those words about relative elegance with a grain of salt. Functional code is usually less verbose, less buggy, a bit less efficient due to many issues etc. These are things most professionals agree with. Apparently D users need to enhance their e-dick by ranting about everything that's not done in d just to get a tiny bit of publicity.I think it would grow yours to understand what functional qsort's problems are. Andrei
Dec 19 2009
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s"This code is shown for its elegance rather than its efficiency. Using ++ in this way is not generally considered good programming practice." So if the code is inefficient and in poor programming practice, how in this blessed world could it count as elegant?Because most functional programming purists (or, to avoid singling out functional programming, purists of any single paradigm) are theory weenies. These people usually don't know an L2 cache from a floating point unit. They wouldn't grok things like implementation efficiency (as opposed to algorithmic/asymptotic efficiency) or close to the metal concepts if they were hit smack in the head with them. Thus, they live in paradigm land and work with theoretical models instead of real-world code.
Dec 19 2009
dsimcha wrote:== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'sThat argument doesn't hold because qsort has quadratic complexity (which is a theoretical thing) for a large category of inputs. Theory also has demonstrated that the correct choice is to randomize the pivot. So I don't buy it that qsort has any merit, theoretical or practical. I think the qsort example does a lot of damage to the FP community. It's just lousy every way you look at it, and consider this: 1. FP has a crushing superiority compared to all other paradigms. 2. An FP expert could choose ANY example to illustrate said crushing superiority. 3. Is qsort it? Andrei"This code is shown for its elegance rather than its efficiency. Using ++ in this way is not generally considered good programming practice." So if the code is inefficient and in poor programming practice, how in this blessed world could it count as elegant?Because most functional programming purists (or, to avoid singling out functional programming, purists of any single paradigm) are theory weenies. These people usually don't know an L2 cache from a floating point unit. They wouldn't grok things like implementation efficiency (as opposed to algorithmic/asymptotic efficiency) or close to the metal concepts if they were hit smack in the head with them. Thus, they live in paradigm land and work with theoretical models instead of real-world code.
Dec 19 2009
Sat, 19 Dec 2009 21:29:45 -0600, Andrei Alexandrescu wrote:dsimcha wrote:How much faster, more elegant, or more reliable a functional programming needs to be in order to make joe coder use it? My impression is that joe often chooses the worst possible language for the task just because some authority tells him to. I've worked with people who favor php4 over everything else because php4 is the most concise, orthogonal, cost- effective, easy to use language available to them in this world. They would even write their 3d engines in php if they only knew how to fill a triangle without leaving holes due to rounding errors or if someone told them how to find out if x0 is smaller than x1!== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'sThat argument doesn't hold because qsort has quadratic complexity (which is a theoretical thing) for a large category of inputs. Theory also has demonstrated that the correct choice is to randomize the pivot. So I don't buy it that qsort has any merit, theoretical or practical. I think the qsort example does a lot of damage to the FP community. It's just lousy every way you look at it, and consider this: 1. FP has a crushing superiority compared to all other paradigms. 2. An FP expert could choose ANY example to illustrate said crushing superiority. 3. Is qsort it?"This code is shown for its elegance rather than its efficiency. Using ++ in this way is not generally considered good programming practice." So if the code is inefficient and in poor programming practice, how in this blessed world could it count as elegant?Because most functional programming purists (or, to avoid singling out functional programming, purists of any single paradigm) are theory weenies. These people usually don't know an L2 cache from a floating point unit. They wouldn't grok things like implementation efficiency (as opposed to algorithmic/asymptotic efficiency) or close to the metal concepts if they were hit smack in the head with them. Thus, they live in paradigm land and work with theoretical models instead of real-world code.
Dec 20 2009
On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> said:"This code is shown for its elegance rather than its efficiency. Using ++ in this way is not generally considered good programming practice." So if the code is inefficient and in poor programming practice, how in this blessed world could it count as elegant?Well, it is elegant in that it is very readable, and as such provides educational value. There are very many examples in programming text books that may not be efficient, but do show the solution to a problem elegantly. E.g. consider list reversal in a recursive function or predicate. It is easy to see that to reverse a list, you append the head to the reversed tail. E.g.: reverse([],[]). reverse([H|T],R) :- reverse(T,RT), append(RT,[H],R). Of course, this is very inefficient, since the program is doing (slow) appends all the time, and is not tail-recursive. You can do it a lot faster with an accumulator, but it makes the solution also less understandable, and not something you'd want to present students/readers immediately: reverse(List,Reverse) :- reverse_aux(List,Reverse,[]). reverse_aux([],List,List). reverse_aux([H|T],List,List0) :- reverse_aux(T,List,[H|List0]).I have gathered a fair amount of samples of involuntary humor from that book. I wouldn't want to go on about that because it could too easily be interpreted as poor taste competitiveness. Let me say I don't think the book is well written.It seems that currently the time to market is much more important than to provide good material, although I cannot comment on that particular book. -- Daniel
Dec 21 2009
Daniel de Kok wrote:On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> said:I disagree. We don't want to educate people to write patently inefficient code and in poor programming practice. When I was doing Windows programming, I noticed that many example in the documentation were written in terrible style. I also noticed that much of the production code I was working with was often stitched from documentation examples."This code is shown for its elegance rather than its efficiency. Using ++ in this way is not generally considered good programming practice." So if the code is inefficient and in poor programming practice, how in this blessed world could it count as elegant?Well, it is elegant in that it is very readable, and as such provides educational value.There are very many examples in programming text books that may not be efficient, but do show the solution to a problem elegantly.Yeah, exponential-time Fibonacci and bubble sort come to mind. In my mind "elegant" and "at a polynomial blowup in complexity" can't be reconciled anywhere outside a Turing machine introduction where everything is equivalent within a polynomial difference in time and space.E.g. consider list reversal in a recursive function or predicate. It is easy to see that to reverse a list, you append the head to the reversed tail. E.g.: reverse([],[]). reverse([H|T],R) :- reverse(T,RT), append(RT,[H],R). Of course, this is very inefficient, since the program is doing (slow) appends all the time, and is not tail-recursive. You can do it a lot faster with an accumulator, but it makes the solution also less understandable, and not something you'd want to present students/readers immediately: reverse(List,Reverse) :- reverse_aux(List,Reverse,[]). reverse_aux([],List,List). reverse_aux([H|T],List,List0) :- reverse_aux(T,List,[H|List0]).Yah, I understand. But what you're really saying is that reverse offers either a simple implementation or an efficient implementation, but not both. That's hardly furthering my belief that FP has a crushing advantage over pretty much anything else. In another thread, "retard" wrote in response to the comparison of the real quicksort in C and Haskell: "What is so brilliant? Referential transparency is broken unless single- threadedness is forced through monadic computation or by some other means (uniqueness types comes to mind)." I think that's a roundabout way of saying that functional programming is unable to express certain algorithms easily or at all.I agree, and I already know of many places in which TDPL has cut quality corners to make it on time, but I hope it never transgressed into intellectual dishonesty. You are supposed to make it look easy, but you can't afford expending the truth in the process. AndreiI have gathered a fair amount of samples of involuntary humor from that book. I wouldn't want to go on about that because it could too easily be interpreted as poor taste competitiveness. Let me say I don't think the book is well written.It seems that currently the time to market is much more important than to provide good material, although I cannot comment on that particular book.
Dec 21 2009
Mon, 21 Dec 2009 12:13:48 -0600, Andrei Alexandrescu wrote:Daniel de Kok wrote:I think one of the things that make good programming languages good is that they allow hiding the complexity behind abstractions. This is something I remember from the SICP lectures. This is the ideology behind pure functional and pure object oriented programming. Reliability is transitive - if the building blocks are good, you can't screw /those/ things on higher level. Things like referential transparency also give you truly modular isolation in this way. You can always find a loop hole in languages like D. I think I've already read what you think about abstractions. After all, it's not really surprising why in "systems programming languages" like D one can more or less easily convert any high level expression into machine code in their head. On relatively low level it's benefical to always think in terms of machine code instructions, stack layouts, pointers etc. But on higher level, performance is in many domains only a secondary goal. Reliability is the main goal. If there's an abstract data type such as a queue or a stack, you simply can't produce traditional stack overflows because the abstraction protects against that. The container code can be really ugly spaghetti internally - the abstraction works as a public interface.On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> said:I disagree. We don't want to educate people to write patently inefficient code and in poor programming practice. When I was doing Windows programming, I noticed that many example in the documentation were written in terrible style. I also noticed that much of the production code I was working with was often stitched from documentation examples."This code is shown for its elegance rather than its efficiency. Using ++ in this way is not generally considered good programming practice." So if the code is inefficient and in poor programming practice, how in this blessed world could it count as elegant?Well, it is elegant in that it is very readable, and as such provides educational value.There are very many examples in programming text books that may not be efficient, but do show the solution to a problem elegantly.Yeah, exponential-time Fibonacci and bubble sort come to mind. In my mind "elegant" and "at a polynomial blowup in complexity" can't be reconciled anywhere outside a Turing machine introduction where everything is equivalent within a polynomial difference in time and space.E.g. consider list reversal in a recursive function or predicate. It is easy to see that to reverse a list, you append the head to the reversed tail. E.g.: reverse([],[]). reverse([H|T],R) :- reverse(T,RT), append(RT,[H],R). Of course, this is very inefficient, since the program is doing (slow) appends all the time, and is not tail-recursive. You can do it a lot faster with an accumulator, but it makes the solution also less understandable, and not something you'd want to present students/readers immediately: reverse(List,Reverse) :- reverse_aux(List,Reverse,[]). reverse_aux([],List,List). reverse_aux([H|T],List,List0) :- reverse_aux(T,List,[H|List0]).Yah, I understand. But what you're really saying is that reverse offers either a simple implementation or an efficient implementation, but not both. That's hardly furthering my belief that FP has a crushing advantage over pretty much anything else. In another thread, "retard" wrote in response to the comparison of the real quicksort in C and Haskell: "What is so brilliant? Referential transparency is broken unless single- threadedness is forced through monadic computation or by some other means (uniqueness types comes to mind)." I think that's a roundabout way of saying that functional programming is unable to express certain algorithms easily or at all.
Dec 21 2009
retard wrote:Mon, 21 Dec 2009 12:13:48 -0600, Andrei Alexandrescu wrote:That all sounds nice and I agree with it, but friction is also transitive. Inefficiencies add when you build higher-level abstractions, and may force you at some point to choose between good abstraction and working program. The beauty of D is that it has low or often zero friction in the way of creating abstractions. That is very difficult to achieve. As far as loop holes go, D's answer is SafeD. We managed to pull it in an extremely short time, and it's in some ways a gambit, but I am confident we have made the right decision. Until somebody provides a soundness proof a la Featherweight Java, there is no ultimate proof that SafeD is in fact safe, but I have reasons to believe there are no principle reasons we can't, and if you do find loopholes please let us know. Java has had for years safety holes, and naysayers enjoyed claiming it will always have. Now it's common knowledge that Java is safe.Daniel de Kok wrote:I think one of the things that make good programming languages good is that they allow hiding the complexity behind abstractions. This is something I remember from the SICP lectures. This is the ideology behind pure functional and pure object oriented programming. Reliability is transitive - if the building blocks are good, you can't screw /those/ things on higher level. Things like referential transparency also give you truly modular isolation in this way. You can always find a loop hole in languages like D.On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> said:I disagree. We don't want to educate people to write patently inefficient code and in poor programming practice. When I was doing Windows programming, I noticed that many example in the documentation were written in terrible style. I also noticed that much of the production code I was working with was often stitched from documentation examples."This code is shown for its elegance rather than its efficiency. Using ++ in this way is not generally considered good programming practice." So if the code is inefficient and in poor programming practice, how in this blessed world could it count as elegant?Well, it is elegant in that it is very readable, and as such provides educational value.There are very many examples in programming text books that may not be efficient, but do show the solution to a problem elegantly.Yeah, exponential-time Fibonacci and bubble sort come to mind. In my mind "elegant" and "at a polynomial blowup in complexity" can't be reconciled anywhere outside a Turing machine introduction where everything is equivalent within a polynomial difference in time and space.E.g. consider list reversal in a recursive function or predicate. It is easy to see that to reverse a list, you append the head to the reversed tail. E.g.: reverse([],[]). reverse([H|T],R) :- reverse(T,RT), append(RT,[H],R). Of course, this is very inefficient, since the program is doing (slow) appends all the time, and is not tail-recursive. You can do it a lot faster with an accumulator, but it makes the solution also less understandable, and not something you'd want to present students/readers immediately: reverse(List,Reverse) :- reverse_aux(List,Reverse,[]). reverse_aux([],List,List). reverse_aux([H|T],List,List0) :- reverse_aux(T,List,[H|List0]).Yah, I understand. But what you're really saying is that reverse offers either a simple implementation or an efficient implementation, but not both. That's hardly furthering my belief that FP has a crushing advantage over pretty much anything else. In another thread, "retard" wrote in response to the comparison of the real quicksort in C and Haskell: "What is so brilliant? Referential transparency is broken unless single- threadedness is forced through monadic computation or by some other means (uniqueness types comes to mind)." I think that's a roundabout way of saying that functional programming is unable to express certain algorithms easily or at all.I think I've already read what you think about abstractions. After all, it's not really surprising why in "systems programming languages" like D one can more or less easily convert any high level expression into machine code in their head. On relatively low level it's benefical to always think in terms of machine code instructions, stack layouts, pointers etc. But on higher level, performance is in many domains only a secondary goal. Reliability is the main goal. If there's an abstract data type such as a queue or a stack, you simply can't produce traditional stack overflows because the abstraction protects against that. The container code can be really ugly spaghetti internally - the abstraction works as a public interface.I fail to see how in D you'd be hard pressed to think in terms of lower level abstractions. Andrei
Dec 21 2009
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'sI fail to see how in D you'd be hard pressed to think in terms of lower level abstractions. AndreiDevil's advocate since I mostly agree: Conservative GC?
Dec 21 2009
On 2009-12-21 19:13:48 +0100, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> said:I disagree. We don't want to educate people to write patently inefficient code and in poor programming practice.I do not mind it, it's ok for explaining a concept clearly. Of course, inadequacies should also be discussed. I'd argue that these are also the thinking steps normally involved in designing a solution to a problem: first try to solve it in the obvious way to understand the problem. Then, make a more performant implementation. Of course, performant also depends on the context. I have written a lot of C++ code that tries to squeeze the last bit of performance out of the machine in a single-core world, but it is also difficult to parallelize. In a parallel world, the 'slower' solution is sometimes better.In my mind "elegant" and "at a polynomial blowup in complexity" can't be reconciled anywhere outside a Turing machine introduction where everything is equivalent within a polynomial difference in time and space.Elegant in the sense of being able to describe a concept briefly. The in-place quicksort does not do this.I think that's a roundabout way of saying that functional programming is unable to express certain algorithms easily or at all....in pure FP. Of course, another problem is that some algorithms are inherently imperative. For instance, I find calculating the edit distance in a performant manner ugly in functional languages. -- Daniel
Dec 22 2009
Daniel de Kok wrote:I do not mind it, it's ok for explaining a concept clearly. Of course, inadequacies should also be discussed. I'd argue that these are also the thinking steps normally involved in designing a solution to a problem: first try to solve it in the obvious way to understand the problem. Then, make a more performant implementation. Of course, performant also depends on the context. I have written a lot of C++ code that tries to squeeze the last bit of performance out of the machine in a single-core world, but it is also difficult to parallelize. In a parallel world, the 'slower' solution is sometimes better.One of the big problems with the presentations of the functional qsort is that it is presented as a shining success of FP, when it is anything but. There may be later a footnote or comment that it is not suitable, but those appear to be written as afterthoughts and do not clearly lay out what the problems are. Furthermore, an introductory FP programming text should be about how to write useful programs in FP, not about how sorting algorithms work.
Dec 22 2009
Tue, 22 Dec 2009 01:43:17 -0800, Walter Bright wrote:Daniel de Kok wrote:Well, in PL research community the terse functional quicksort code isn't considered that important. The focus is on completely different kinds of systems. I recommend forgetting the whole example for now. The badly performing one liner doesn't mean that all functional programming and all functional programming languages are toys when solving real world problems. There's more diversity in functional languages than in mainstream OOP hybrid languages. You can port the same badly performing code to D and get - surprise, surprise - badly performing qsort in D! The discussion here mostly touts imperative languages with the same old centuries old arguments like "omg functional languages can't do in-place algorithms". "so you need hacks to implement in-place algorithms. that must mean that the elegance of fpl is in fact something that cannot be achieved in real world". I've already repeated this many times: abstractions. Let's assume you have world class in-place implementation of sort in module stdlib.productionquality.collections and a shitty novice implementation of buggy bubble sort in stdlib.crappycrap.collections. Now the only difference on use site is: import sort from stdlib.productionquality.collections sort mycollection vs import sort from stdlib.crappycrap.collections sort mycollection Now how does this prove in any way that functional programming is ugly and broken. With a decent FFI implementation you can even import a C/C++/ D version of the sort function and use that in your functional code. This all works thanks to the universal C ABI. If that C/C++/D code doesn't break referential transparency, it means that the functional code also retains its reliability even if it calls imperative code.I do not mind it, it's ok for explaining a concept clearly. Of course, inadequacies should also be discussed. I'd argue that these are also the thinking steps normally involved in designing a solution to a problem: first try to solve it in the obvious way to understand the problem. Then, make a more performant implementation. Of course, performant also depends on the context. I have written a lot of C++ code that tries to squeeze the last bit of performance out of the machine in a single-core world, but it is also difficult to parallelize. In a parallel world, the 'slower' solution is sometimes better.One of the big problems with the presentations of the functional qsort is that it is presented as a shining success of FP, when it is anything but. There may be later a footnote or comment that it is not suitable, but those appear to be written as afterthoughts and do not clearly lay out what the problems are.Furthermore, an introductory FP programming text should be about how to write useful programs in FP, not about how sorting algorithms work.So all the Haskell/Erlang/ML/Scheme books you've read have been really bad? That only means that there's market for good FPL books, then!
Dec 22 2009
retard wrote:The discussion here mostly touts imperative languages with the same old centuries old arguments like "omg functional languages can't do in-place algorithms". "so you need hacks to implement in-place algorithms. that must mean that the elegance of fpl is in fact something that cannot be achieved in real world".I disagree that this is what this thread is about. FP has a lot of insight and great ideas to offer programming. The thread is about *bad examples*, and the FP qsort is a *bad example* of FP programming. Every paradigm has problems it is ill suited to solve, and FP is ill suited to implementing qsort. For another example, around 1990 the programming world decided that OOP was the solution to all programming problems. One of the results of that thinking is Java. We've now suffered through the inevitable backlash, and a more reasoned consensus these days is that OOP is very well suited to solving some problems, and for other problems one should use a different paradigm. As I mentioned to grauzone, D has adopted some essential characteristics of FP programming (immutability and purity). So, when you're faced with a programming problem that is ideally suited to an FP solution, you can do one in D. But you're not forced to use FP for everything, like qsort and I/O.Any FP programming text that puts the one line qsort front and center as an example of how great FP is is a book that has room for improvement, you bet.Furthermore, an introductory FP programming text should be about how to write useful programs in FP, not about how sorting algorithms work.So all the Haskell/Erlang/ML/Scheme books you've read have been really bad? That only means that there's market for good FPL books, then!
Dec 22 2009
Tue, 22 Dec 2009 10:27:39 -0800, Walter Bright wrote:For another example, around 1990 the programming world decided that OOP was the solution to all programming problems. One of the results of that thinking is Java. We've now suffered through the inevitable backlash, and a more reasoned consensus these days is that OOP is very well suited to solving some problems, and for other problems one should use a different paradigm.People have very differents opinions about the matter now. Some think that the "bloatness" of Java style OOP can be eliminated with extremely slow scripting languages that don't even do syntactic checks. People have started to hate type systems so much that modern languages don't do almost any kind of type checking (PHP!) or defer it as much as possible. Others think that we should express more things in the holy XML format. And the third camp things that everything would work just fine if we used Web 2.0 languages such as Flash, Javascript, (X)HTML, CSS, and some dynamic server side language such as Python (and RESTful protocols with as much XML as possible).I use the Okasaki book as my bible when talking about purely functional data structures.So all the Haskell/Erlang/ML/Scheme books you've read have been really bad? That only means that there's market for good FPL books, then!Any FP programming text that puts the one line qsort front and center as an example of how great FP is is a book that has room for improvement, you bet.
Dec 22 2009
retard wrote:I use the Okasaki book as my bible when talking about purely functional data structures.It's an awesome book. It's also very frank and tells things as they are, as opposed to others (*cough*) that patronize the reader by artificially making it seem so easy, it's amazing how Stoopid People missed the point. Un-incidentally, Okasaki does not dabble in qsort. He does describe mergesort - a perfectly sound and advantageous sorting methods for lists. Ok, I'm itching to share another gem. "At this point you might be wondering how it's possible to program without variables. How can you express something like X = X + 1 in <language erased to protect the guilty>? The answer is easy. Invent a new variable whose name hasn't been used before (say X1), and write X1 = X + 1". Andrei
Dec 22 2009
Andrei Alexandrescu wrote:retard wrote:,=20I use the Okasaki book as my bible when talking about purely=20 functional data structures.=20 It's an awesome book. It's also very frank and tells things as they are=as opposed to others (*cough*) that patronize the reader by artificiall=y=20making it seem so easy, it's amazing how Stoopid People missed the=20 point. Un-incidentally, Okasaki does not dabble in qsort. He does=20 describe mergesort - a perfectly sound and advantageous sorting methods==20for lists. =20 Ok, I'm itching to share another gem. =20 "At this point you might be wondering how it's possible to program=20 without variables. How can you express something like X =3D X + 1 in=20 <language erased to protect the guilty>? The answer is easy. Invent a=20 new variable whose name hasn't been used before (say X1), and write X1 ==3D=20X + 1". =20AIUI most compilers are able to do this themselves automatically=20 and they use it for optimisation (SSA form). That being the case,=20 it's ridiculous to force the programmer to take notice... Jerome --=20 mailto:jeberger free.fr http://jeberger.free.fr Jabber: jeberger jabber.fr
Dec 22 2009
Tue, 22 Dec 2009 14:51:55 -0600, Andrei Alexandrescu wrote:retard wrote:That's a nasty limitation indeed. From my point of view imperative languages just pass around the global state with the value of the computation, and the assignment (X=X+1) shadows the previous value of X. In some cases this allows optimizing compilers to perform the assignment in-place! :o) In fact, this is exactly what happens in another pure functional language (name erased to protect the awesomeness): foo x x = x * 2 x = x - 5 = x vs T foo(T)(T x) { x = x + 1; x = x * 2; x = x - 5; return x; }I use the Okasaki book as my bible when talking about purely functional data structures.It's an awesome book. It's also very frank and tells things as they are, as opposed to others (*cough*) that patronize the reader by artificially making it seem so easy, it's amazing how Stoopid People missed the point. Un-incidentally, Okasaki does not dabble in qsort. He does describe mergesort - a perfectly sound and advantageous sorting methods for lists. Ok, I'm itching to share another gem. "At this point you might be wondering how it's possible to program without variables. How can you express something like X = X + 1 in <language erased to protect the guilty>? The answer is easy. Invent a new variable whose name hasn't been used before (say X1), and write X1 = X + 1".
Dec 22 2009
retard wrote:Tue, 22 Dec 2009 14:51:55 -0600, Andrei Alexandrescu wrote:Hm, I guess I should have been more explicit. The problem isn't defining a few more names, but that the explanation completely neglects any control flow issues (e.g. conditionals and loops). You can't define a new name for each instance of a loop, so everything is recursion etc. I mean the consequences are earth-shattering. There is absolutely no doubt the author is aware of the fact that single assignment is a lot more than just defining a few names, so I find it very questionable that he chose to put things that way. And the book has much more allegations like that one! Imagine you'd find this in a book for learning French: "Translating from English to French is very easy - just replace English words with the corresponding French words." Andreiretard wrote:That's a nasty limitation indeed. From my point of view imperative languages just pass around the global state with the value of the computation, and the assignment (X=X+1) shadows the previous value of X. In some cases this allows optimizing compilers to perform the assignment in-place! :o) In fact, this is exactly what happens in another pure functional language (name erased to protect the awesomeness): foo x x = x * 2 x = x - 5 = x vs T foo(T)(T x) { x = x + 1; x = x * 2; x = x - 5; return x; }I use the Okasaki book as my bible when talking about purely functional data structures.It's an awesome book. It's also very frank and tells things as they are, as opposed to others (*cough*) that patronize the reader by artificially making it seem so easy, it's amazing how Stoopid People missed the point. Un-incidentally, Okasaki does not dabble in qsort. He does describe mergesort - a perfectly sound and advantageous sorting methods for lists. Ok, I'm itching to share another gem. "At this point you might be wondering how it's possible to program without variables. How can you express something like X = X + 1 in <language erased to protect the guilty>? The answer is easy. Invent a new variable whose name hasn't been used before (say X1), and write X1 = X + 1".
Dec 22 2009
Andrei Alexandrescu wrote:Hm, I guess I should have been more explicit. The problem isn't defining a few more names, but that the explanation completely neglects any control flow issues (e.g. conditionals and loops). You can't define a new name for each instance of a loop, so everything is recursion etc. I mean the consequences are earth-shattering.The implications of single assignment on control structures seem both insignificant and obvious to me. Much more troubling is that it doesn't work for fields and array elements at all. -- Rainer Deyke - rainerd eldwood.com
Dec 22 2009
Rainer Deyke wrote:Andrei Alexandrescu wrote:Good point - among other things, it explains why FP by and large tries to convince all who want to listen that arrays are no good :o). AndreiHm, I guess I should have been more explicit. The problem isn't defining a few more names, but that the explanation completely neglects any control flow issues (e.g. conditionals and loops). You can't define a new name for each instance of a loop, so everything is recursion etc. I mean the consequences are earth-shattering.The implications of single assignment on control structures seem both insignificant and obvious to me. Much more troubling is that it doesn't work for fields and array elements at all.
Dec 22 2009
On Tue, Dec 22, 2009 at 21:51, Andrei Alexandrescu < SeeWebsiteForEmail erdani.org> wrote:retard wrote:asI use the Okasaki book as my bible when talking about purely functional data structures.It's an awesome book. It's also very frank and tells things as they are, =opposed to others (*cough*) that patronize the reader by artificially mak=ingit seem so easy, it's amazing how Stoopid People missed the point. Un-incidentally, Okasaki does not dabble in qsort. He does describe mergesort - a perfectly sound and advantageous sorting methods for lists.I've only read his PhD a few months ago. Lots of mind-expanding ideas in there. Someone told me the book is even better. Is it worth the 25-30 =80 I see on Amazon? (gosh, why I'm asking this when I'll spend thrice as much in food just for tonight's dinner...) Philippe
Dec 23 2009
Philippe Sigaud wrote:On Tue, Dec 22, 2009 at 21:51, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org <mailto:SeeWebsiteForEmail erdani.org>> wrote: retard wrote: I use the Okasaki book as my bible when talking about purely functional data structures. It's an awesome book. It's also very frank and tells things as they are, as opposed to others (*cough*) that patronize the reader by artificially making it seem so easy, it's amazing how Stoopid People missed the point. Un-incidentally, Okasaki does not dabble in qsort. He does describe mergesort - a perfectly sound and advantageous sorting methods for lists. I've only read his PhD a few months ago. Lots of mind-expanding ideas in there. Someone told me the book is even better. Is it worth the 25-30 � I see on Amazon? (gosh, why I'm asking this when I'll spend thrice as much in food just for tonight's dinner...)If you could ingest his thesis, you'll like the book, which is an expansion of the ideas therein. Andrei
Dec 23 2009
Tue, 22 Dec 2009 01:43:17 -0800, Walter Bright wrote:Daniel de Kok wrote:I also have to say that the Haskell wiki doesn't exactly reflect the views of the whole FPL community. The target audience is probably novice to moderately experienced programmers coming from other (mainly imperative) languages. There's lot of hype around FPL, and to get a better view of the matter, I recommend studying the history of FPLs, accompanied by references to constructive logic. Simon Peyton Jones had in his slides a nice graph of the reliability vs performance issues. Functional languages were originally very slow, but had the safety aspect. Imperative languages have always been fast, and only gradually improved on the reliability front. Pure functional languages have never given up the reliability aspect, so it's a bit surprising how small amount of people here know what's their biggest advantage. Without syntactic sugar functional languages can be terribly verbose. Try writing functional code in runtime D or worse, with templates, and you'll begin to see just how verbose it really can be.I do not mind it, it's ok for explaining a concept clearly. Of course, inadequacies should also be discussed. I'd argue that these are also the thinking steps normally involved in designing a solution to a problem: first try to solve it in the obvious way to understand the problem. Then, make a more performant implementation. Of course, performant also depends on the context. I have written a lot of C++ code that tries to squeeze the last bit of performance out of the machine in a single-core world, but it is also difficult to parallelize. In a parallel world, the 'slower' solution is sometimes better.One of the big problems with the presentations of the functional qsort is that it is presented as a shining success of FP
Dec 22 2009
retard wrote:Simon Peyton Jones had in his slides a nice graph of the reliability vs performance issues. Functional languages were originally very slow, but had the safety aspect. Imperative languages have always been fast, and only gradually improved on the reliability front. Pure functional languages have never given up the reliability aspect, so it's a bit surprising how small amount of people here know what's their biggest advantage.I don't need convincing of that. I agree it is a great advantage to FP. I argue this point repeatedly when people question the point of immutability.
Dec 22 2009
On 2009-12-22 10:43:17 +0100, Walter Bright <newshound1 digitalmars.com> said:One of the big problems with the presentations of the functional qsort is that it is presented as a shining success of FP, when it is anything but.There are better examples of 'shining succes' in FP. For example, consider the very clear and terse examples of balancing binary search trees or heaps in the Okasaki book. DSLs are also another good example where FP works very well. However, these examples are probably too long to catch attention from a casual reader browsing the haskell.org, or as an introductary example of functional languages.Furthermore, an introductory FP programming text should be about how to write useful programs in FP, not about how sorting algorithms work.'ML for the working programmer' is certainly one of the better FP programming texts I have seen, and it discusses various sorting algorithms and how they work (with the head as a pivot in quicksorting :p). But how is that problematic? Some of good programming books will end up being used in CS curricula, and then it's useful to learn something along the way, rather than have a dry treaty about yet another language. -- Daniel
Dec 22 2009
Daniel de Kok wrote:On 2009-12-21 19:13:48 +0100, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> said:My point is that there is no "concept" being explained. The concept of quicksort is not what the FP classic explains.I disagree. We don't want to educate people to write patently inefficient code and in poor programming practice.I do not mind it, it's ok for explaining a concept clearly.Of course, inadequacies should also be discussed. I'd argue that these are also the thinking steps normally involved in designing a solution to a problem: first try to solve it in the obvious way to understand the problem. Then, make a more performant implementation. Of course, performant also depends on the context. I have written a lot of C++ code that tries to squeeze the last bit of performance out of the machine in a single-core world, but it is also difficult to parallelize. In a parallel world, the 'slower' solution is sometimes better.I'd agree with the above if complexity was not at stake. That's not an optimization.In-place partition is largely what quicksort is about. That concept is sorely missing from FP qsort. The fact that you need random access if you want to avoid quadratic performance is a much more subtle concept that is not only missing from FP qsort - it's hidden.In my mind "elegant" and "at a polynomial blowup in complexity" can't be reconciled anywhere outside a Turing machine introduction where everything is equivalent within a polynomial difference in time and space.Elegant in the sense of being able to describe a concept briefly. The in-place quicksort does not do this.So then I guess I can be given a break about FP ueber alles. AndreiI think that's a roundabout way of saying that functional programming is unable to express certain algorithms easily or at all....in pure FP. Of course, another problem is that some algorithms are inherently imperative. For instance, I find calculating the edit distance in a performant manner ugly in functional languages.
Dec 22 2009
On 2009-12-22 14:24:41 +0100, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> said:Daniel de Kok wrote:Hey, it's not me arguing for that. I think every paradigm has its place... And I am not in for parotting the 'we absolutely need pure FP for a multicore world' stanza. While full purity certainly helps for lock-free programming, it reduces the world to one where there are no embarassingly parallel programs. In natural language parsing we get (nearly) linear speedup without purity, with single-thread processes (just split a corpus in N parts, and run a parser for each part). Or if you do vector/matrix calculations on a GPU it's also a mutable world (with the exception of texture memory). Of course, there are good counter-examples where purity helps. But it's not a black-white world. Not that I really have to say that on a D list ;-). -- Daniel...in pure FP. Of course, another problem is that some algorithms are inherently imperative. For instance, I find calculating the edit distance in a performant manner ugly in functional languages.So then I guess I can be given a break about FP ueber alles.
Dec 22 2009
Daniel de Kok wrote:Of course, there are good counter-examples where purity helps. But it's not a black-white world. Not that I really have to say that on a D list ;-).Right, D is not a language implementing a religion!
Dec 22 2009
Mon, 21 Dec 2009 18:54:19 +0100, Daniel de Kok wrote:On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> said:I have several imperative language programming books and instead of qsort they introduce the reader to the wonderful world of bubble sort!"This code is shown for its elegance rather than its efficiency. Using ++ in this way is not generally considered good programming practice." So if the code is inefficient and in poor programming practice, how in this blessed world could it count as elegant?Well, it is elegant in that it is very readable, and as such provides educational value. There are very many examples in programming text books that may not be efficient, but do show the solution to a problem elegantly.
Dec 21 2009
retard wrote:Mon, 21 Dec 2009 18:54:19 +0100, Daniel de Kok wrote:And do you think that is good and elegant or stupid and ugly?On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> said:I have several imperative language programming books and instead of qsort they introduce the reader to the wonderful world of bubble sort!"This code is shown for its elegance rather than its efficiency. Using ++ in this way is not generally considered good programming practice." So if the code is inefficient and in poor programming practice, how in this blessed world could it count as elegant?Well, it is elegant in that it is very readable, and as such provides educational value. There are very many examples in programming text books that may not be efficient, but do show the solution to a problem elegantly.
Dec 21 2009
Mon, 21 Dec 2009 20:04:05 +0100, Lutger wrote:retard wrote:I'll let the official authority decide that. I have no opinion.Mon, 21 Dec 2009 18:54:19 +0100, Daniel de Kok wrote:And do you think that is good and elegant or stupid and ugly?On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> said:I have several imperative language programming books and instead of qsort they introduce the reader to the wonderful world of bubble sort!"This code is shown for its elegance rather than its efficiency. Using ++ in this way is not generally considered good programming practice." So if the code is inefficient and in poor programming practice, how in this blessed world could it count as elegant?Well, it is elegant in that it is very readable, and as such provides educational value. There are very many examples in programming text books that may not be efficient, but do show the solution to a problem elegantly.
Dec 21 2009
retard wrote:I have several imperative language programming books and instead of qsort they introduce the reader to the wonderful world of bubble sort!Bubble sort should be part of an introductory programming course, if only because: 1. it's an algorithm that gets reinvented if one is not aware of it 2. one needs to be able to recognize it, as one will encounter it a lot in production code 3. it's a great way to introduce concepts like big O 4. it's a great stepping stone to introducing better sorts I've run into bubble sort reimplementations in production code written by famous programmers who should know better. It happens all the time.
Dec 21 2009
Walter Bright wrote:retard wrote:Fro your arguments 1-4 and your conclusion, I infer you made a slight typo. Let me fix that for you. s/should be/should not be/ AndreiI have several imperative language programming books and instead of qsort they introduce the reader to the wonderful world of bubble sort!Bubble sort should be part of an introductory programming course, if only because: 1. it's an algorithm that gets reinvented if one is not aware of it 2. one needs to be able to recognize it, as one will encounter it a lot in production code 3. it's a great way to introduce concepts like big O 4. it's a great stepping stone to introducing better sorts I've run into bubble sort reimplementations in production code written by famous programmers who should know better. It happens all the time.
Dec 21 2009
Andrei Alexandrescu wrote:Walter Bright wrote:!retard wrote:I have several imperative language programming books and instead of=20 qsort they introduce the reader to the wonderful world of bubble sort==20Bubble sort should be part of an introductory programming course, if=20 only because: 1. it's an algorithm that gets reinvented if one is not aware of it 2. one needs to be able to recognize it, as one will encounter it a=20 lot in production code 3. it's a great way to introduce concepts like big O 4. it's a great stepping stone to introducing better sorts I've run into bubble sort reimplementations in production code written=by famous programmers who should know better. It happens all the time.==20 Fro your arguments 1-4 and your conclusion, I infer you made a slight=20 typo. Let me fix that for you. =20 s/should be/should not be/ =20No, he's right, it should be part of any introductory programming=20 course, along with a good explanation of why it is so bad. They say=20 that "for every problem there is a solution which is simple,=20 elegant, and wrong", and bubble sort is as good a way as any to make=20 that point. However, it is essential that the teacher actually *make* that=20 point and not leave the students believing that bubble sort is a=20 good algorithm. Jerome --=20 mailto:jeberger free.fr http://jeberger.free.fr Jabber: jeberger jabber.fr
Dec 21 2009
On Tue, 22 Dec 2009 00:10:44 +0300, J=C3=A9r=C3=B4me M. Berger <jeberger= free.fr> = wrote:Andrei Alexandrescu wrote:Walter Bright wrote:retard wrote:I have several imperative language programming books and instead of=rt!qsort they introduce the reader to the wonderful world of bubble so=Bubble sort should be part of an introductory programming course, if=enonly because: 1. it's an algorithm that gets reinvented if one is not aware of it 2. one needs to be able to recognize it, as one will encounter it a lot in production code 3. it's a great way to introduce concepts like big O 4. it's a great stepping stone to introducing better sorts I've run into bubble sort reimplementations in production code writt=e.by famous programmers who should know better. It happens all the tim=Fro your arguments 1-4 and your conclusion, I infer you made a slight=Bubble sort is not that bad (e.g. a sequence with one element out of = place), it's just niche algorithm.typo. Let me fix that for you. s/should be/should not be/No, he's right, it should be part of any introductory programming course, along with a good explanation of why it is so bad. They say that "for every problem there is a solution which is simple, elegant, and wrong", and bubble sort is as good a way as any to make that point. However, it is essential that the teacher actually *make* that point and not leave the students believing that bubble sort is a good algorithm. Jerome
Dec 21 2009
Denis Koroskin wrote:On Tue, 22 Dec 2009 00:10:44 +0300, Jérôme M. Berger<jeberger free.fr>wrote:ofAndrei Alexandrescu wrote:Walter Bright wrote:retard wrote:I have several imperative language programming books and insteadsort!qsort they introduce the reader to the wonderful world of bubbleifBubble sort should be part of an introductory programming course,itonly because: 1. it's an algorithm that gets reinvented if one is not aware ofa2. one needs to be able to recognize it, as one will encounter itwrittenlot in production code 3. it's a great way to introduce concepts like big O 4. it's a great stepping stone to introducing better sorts I've run into bubble sort reimplementations in production codetime.by famous programmers who should know better. It happens all theslightFro your arguments 1-4 and your conclusion, I infer you made amaketypo. Let me fix that for you. s/should be/should not be/No, he's right, it should be part of any introductory programming course, along with a good explanation of why it is so bad. They say that "for every problem there is a solution which is simple, elegant, and wrong", and bubble sort is as good a way as any toI believe that I was taught that a bubble sort was optimal for lists of fewer than about 25 elements. I.e., where n is very small, the overhead for the other sorts wasn't worth it.that point. However, it is essential that the teacher actually *make* that point and not leave the students believing that bubble sort is a good algorithm. JeromeBubble sort is not that bad (e.g. a sequence with one element out of place), it's just niche algorithm.
Dec 26 2009
Sat, 26 Dec 2009 09:21:55 -0800, Charles Hixson wrote:Denis Koroskin wrote:Nope, that's big time bs. http://en.wikipedia.org/wiki/ Bubble_sort#In_practice -- I wasn't even taught bubble sort in school because insertion sort performs much better and is about as easy to comprehend.On Tue, 22 Dec 2009 00:10:44 +0300, Jérôme M. Berger<jeberger free.fr>wrote:ofAndrei Alexandrescu wrote:Walter Bright wrote:retard wrote:I have several imperative language programming books and insteadsort!qsort they introduce the reader to the wonderful world of bubbleifBubble sort should be part of an introductory programming course,itonly because: 1. it's an algorithm that gets reinvented if one is not aware ofa2. one needs to be able to recognize it, as one will encounter itwrittenlot in production code 3. it's a great way to introduce concepts like big O 4. it's a great stepping stone to introducing better sorts I've run into bubble sort reimplementations in production codetime.by famous programmers who should know better. It happens all theslightFro your arguments 1-4 and your conclusion, I infer you made amaketypo. Let me fix that for you. s/should be/should not be/No, he's right, it should be part of any introductory programming course, along with a good explanation of why it is so bad. They say that "for every problem there is a solution which is simple, elegant, and wrong", and bubble sort is as good a way as any toI believe that I was taught that a bubble sort was optimal for lists of fewer than about 25 elements. I.e., where n is very small, the overhead for the other sorts wasn't worth it.that point. However, it is essential that the teacher actually *make* that point and not leave the students believing that bubble sort is a good algorithm. JeromeBubble sort is not that bad (e.g. a sequence with one element out of place), it's just niche algorithm.
Dec 26 2009
retard wrote:Sat, 26 Dec 2009 09:21:55 -0800, Charles Hixson wrote:I'd say it's easier. If you watch someone sorting some cards, they'll use either insertion sort or selection sort. Nobody should have ever heard of bubble sort, I'm pleased to hear some schools aren't mentioning it. Such a foolish algorithm. "the bubble sort seems to have nothing to recommend it, except a catchy name " - Knuth.Denis Koroskin wrote:Nope, that's big time bs. http://en.wikipedia.org/wiki/ Bubble_sort#In_practice -- I wasn't even taught bubble sort in school because insertion sort performs much better and is about as easy to comprehend.On Tue, 22 Dec 2009 00:10:44 +0300, Jérôme M. Berger<jeberger free.fr>wrote:ofAndrei Alexandrescu wrote:Walter Bright wrote:retard wrote:I have several imperative language programming books and insteadsort!qsort they introduce the reader to the wonderful world of bubbleifBubble sort should be part of an introductory programming course,itonly because: 1. it's an algorithm that gets reinvented if one is not aware ofa2. one needs to be able to recognize it, as one will encounter itwrittenlot in production code 3. it's a great way to introduce concepts like big O 4. it's a great stepping stone to introducing better sorts I've run into bubble sort reimplementations in production codetime.by famous programmers who should know better. It happens all theslightFro your arguments 1-4 and your conclusion, I infer you made amaketypo. Let me fix that for you. s/should be/should not be/No, he's right, it should be part of any introductory programming course, along with a good explanation of why it is so bad. They say that "for every problem there is a solution which is simple, elegant, and wrong", and bubble sort is as good a way as any toI believe that I was taught that a bubble sort was optimal for lists of fewer than about 25 elements. I.e., where n is very small, the overhead for the other sorts wasn't worth it.that point. However, it is essential that the teacher actually *make* that point and not leave the students believing that bubble sort is a good algorithm. JeromeBubble sort is not that bad (e.g. a sequence with one element out of place), it's just niche algorithm.
Dec 26 2009
Don wrote:I'd say it's easier. If you watch someone sorting some cards, they'll use either insertion sort or selection sort. Nobody should have ever heard of bubble sort, I'm pleased to hear some schools aren't mentioning it. Such a foolish algorithm.I suppose I'm alone in thinking that engineering school should also cover designs that don't work and explain why!
Dec 26 2009
Walter Bright:I suppose I'm alone in thinking that engineering school should also cover designs that don't work and explain why!Knuth doesn't say it's uselsss to teach Bubble sort. Knowing bad algorithms is useful if they are both obvious and slow, to know the basics and to avoid them. And learning what Bubble Sort is, is useful to learn other things, like the Kendal Tau distance, for example: http://en.wikipedia.org/wiki/Kendall_tau_distance Bye, bearophile
Dec 27 2009
== Quote from Walter Bright (newshound1 digitalmars.com)'s articleDon wrote:Yes, the same way programmers discuss anti-patterns. If it's a bad idea **but occurs frequently in the real world** then it should be pointed out for explaining to people why it's a bad idea, because obviously there are plenty of people that aren't getting it.I'd say it's easier. If you watch someone sorting some cards, they'll use either insertion sort or selection sort. Nobody should have ever heard of bubble sort, I'm pleased to hear some schools aren't mentioning it. Such a foolish algorithm.I suppose I'm alone in thinking that engineering school should also cover designs that don't work and explain why!
Dec 27 2009
Walter Bright Wrote:Don wrote:I'm sure every US-taught engineer has heard of the Tacoma Narrows Bridge disaster. But it would be nice if there were a bit more time spent on this sort of thing.I'd say it's easier. If you watch someone sorting some cards, they'll use either insertion sort or selection sort. Nobody should have ever heard of bubble sort, I'm pleased to hear some schools aren't mentioning it. Such a foolish algorithm.I suppose I'm alone in thinking that engineering school should also cover designs that don't work and explain why!
Dec 27 2009
Sean Kelly wrote:Walter Bright Wrote:I did spend some time at Boeing designing airplane parts, and past failures were always minutely studied in order to avoid repeating mistakes. But this happened in industry, not in school. From reading the replies to "C's Biggest Mistake", I see a lot of people who are going to relearn the hard way. I get similar responses when I tell kids "If you don't floss your teeth, you'll be sorry! not now, not in 5 years, but you will be sorry." Now get off my lawn! P.S. I'm not joking about the flossing thing.I suppose I'm alone in thinking that engineering school should also cover designs that don't work and explain why!I'm sure every US-taught engineer has heard of the Tacoma Narrows Bridge disaster. But it would be nice if there were a bit more time spent on this sort of thing.
Dec 27 2009
== Quote from Don (nospam nospam.com)'s article"the bubble sort seems to have nothing to recommend it, except a catchy name " - Knuth.Well, the bubble sort distance is a pretty good metric of how similarly ordered two lists are. It's useful, for example, in statistics such as Kendall's Tau. One of the easiest ways to calculate it is...with a bubble sort.
Dec 27 2009
dsimcha wrote:== Quote from Don (nospam nospam.com)'s articleI don't think that's a coincidence. It seems to be defined in terms of bubble sort! The whole bubble sort phenonemon seems to be self-perpetuating. There were loads of really crap algorithms in the 1950's. Why was this one not forgotten with the rest?"the bubble sort seems to have nothing to recommend it, except a catchy name " - Knuth.Well, the bubble sort distance is a pretty good metric of how similarly ordered two lists are. It's useful, for example, in statistics such as Kendall's Tau. One of the easiest ways to calculate it is...with a bubble sort.
Dec 27 2009
Don wrote:dsimcha wrote:catchy== Quote from Don (nospam nospam.com)'s article"the bubble sort seems to have nothing to recommend it, except asimilarlyname " - Knuth.Well, the bubble sort distance is a pretty good metric of howKendall'sordered two lists are. It's useful, for example, in statistics such assort.Tau. One of the easiest ways to calculate it is...with a bubbleI don't think that's a coincidence. It seems to be defined in termsofbubble sort! The whole bubble sort phenonemon seems to be self-perpetuating.Therewere loads of really crap algorithms in the 1950's. Why was this onenotforgotten with the rest?Because it's SIMPLE. And because for the small sample sizes used in most classes (still?) scaling with n^2 isn't all that bad. Someone said that the insertion sort is better even for small sample sizes, but if you don't have an array type that implements insertion, then that means writing an extra loop to move things down. I might have suggested that the exchange sort was a good choice. But with small sample sizes and limited memory (no longer a significant problem for cases where this is even vaguely reasonable) the bubble sort isn't that bad. In fact it's difficult to measure the difference as n tends towards 3. For n == 2 there's no other even vaguely reasonable choice. The problem with bubble sorts is the factor of n^2. My teacher might well have been wrong when he put n as high as 25 for where the bubble sort was optimal, but it's clearly optimal when n is less than 4. It's just that those cases don't matter in the real world. (And actually, they'd probably be handled with a case statement, or a nested if.) But if you have code that needs to handle sorting array sizes between 3 and 25 (varying in the calls, and tending towards the low end), then there's no reason to go for anything more complicated. Of course, a better choice yet is often to use a library function. Even if the low end calls have excess overhead, it won't matter much, and you don't need to worry about coding errors. (Yeah, I believe that Knuth said there was no reason for the bubble sort existing. And without knowing the exact context in which he said it, I'm not going to call him wrong. The times to use it are not only extremely limited, there's also a tendency to use it at the wrong times, just because you have the code handy, and it's easy.) P.S.: If you have an Array class, and the array class has an insert method, then the insertion sort is clearly better for building a sorted list. It's less clear if you're sorting a list that you already have, and you're trying to avoid allocating new memory. Especially if it's not stored a container class with an insert method. N.B.: If the bubble sort weren't taught, it would be continually re- invented. And as it's so rarely the proper choice, it needs to be warned against. Preferably by having someone write something that, sorts things interactively, and then having them start adding things to be sorted. But processors may be fast enough to defeat this experiential learning unless you add things in a way that doubles the collection size each time you make an addition.
Jan 13 2010
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message news:4B2FCF53.9050608 erdani.org...Walter Bright wrote:It should be "should be", for the same reason and in the same way that the "waterfall" development model *should be* taught: Presenting it up front as conceptually-easy-but-generally-a-bad-thing-to-do will help people identify it and therefore avoid it. Not teaching about it increases the chances that they'll either rediscover it or come across a usage of it without actually noticing that there's a problem. It would be like selling sodium without including a warning that it explodes upon contact with water (Or something like that, anyway, I never actually took chemistry...).retard wrote:Fro your arguments 1-4 and your conclusion, I infer you made a slight typo. Let me fix that for you. s/should be/should not be/I have several imperative language programming books and instead of qsort they introduce the reader to the wonderful world of bubble sort!Bubble sort should be part of an introductory programming course, if only because: 1. it's an algorithm that gets reinvented if one is not aware of it 2. one needs to be able to recognize it, as one will encounter it a lot in production code 3. it's a great way to introduce concepts like big O 4. it's a great stepping stone to introducing better sorts I've run into bubble sort reimplementations in production code written by famous programmers who should know better. It happens all the time.
Dec 21 2009
On 2009-12-18 20:39:08 +0100, Walter Bright <newshound1 digitalmars.com> said:Ain't that cool? But look closer. The advantage of quicksort is that it is an *in-place* sort. The Haskell one creates new arrays for every state in the sort.But it does have one nice property: due to laziness, the n-th elements of the sorted array can be found without sorting the full array (except of course, the largest two n's). -- Daniel
Dec 21 2009
Daniel de Kok wrote:On 2009-12-18 20:39:08 +0100, Walter Bright <newshound1 digitalmars.com> said:According to what I've read while looking into the subject, whether the concatenations are lazy or not depends on the language and a number of implementation vagaries. Even assuming perfect, overhead-free laziness and ignoring the cost of all allocations and concatenations, in the worst case (reverse sorted array) just seeing the top 1 smallest element requires O(n*n) work. It's an uphill battle finding anything good about functional qsort. It's bad through and through. (For solving the selection problem there are better methods - all use mutation and are very difficult to express in a functional language.) AndreiAin't that cool? But look closer. The advantage of quicksort is that it is an *in-place* sort. The Haskell one creates new arrays for every state in the sort.But it does have one nice property: due to laziness, the n-th elements of the sorted array can be found without sorting the full array (except of course, the largest two n's).
Dec 21 2009
On 2009-12-18 18:02:28 +0100, retard <re tard.com.invalid> said:I've only seen how Scala solves problems elegantly. These are from some biased blog posts etc. Can you show one example that looks uglier in Scala, but looks decent in D or some other language?I can not paste any of this particular code ($WORK). From the top of my head, some random things that I found annoying: - Types of both worlds get mixed. For instance, Scala has 'functional lists', but much of the Java world uses mutable lists (following the List interface). If you use the vast amounts of Java class libraries around (since the Scala library is still fairly minimal), you either have to fall back to Java lists (which do not work with a functional style of programming) or convert list back and forth all the time. - You can do functional programming, but it will end up being slow, because of the lack of proper tail-call recursion optimization. - Documentation for much of the Scala library is non-existant. There's a lot of second-guessing which traits you are expected to use, or which self-calling functions are tail-recursive. Since method signatures are pretty unreadable as well, you are pretty much on your own. - Classes are ugly. Constructor parameters are part of the class definition: class Something(someString: String) While this looks like a somewhat typically functional type declaration in this simple case, once you start building real classes they pollute class declarations, since you have to do non-trivial initialization somewhere. Of course, you could do this in functional style, but most libraries are not written in this manner. - Pattern matching with match...case is not particularly elegant compared to Haskell (where you just have multiple function definitions). - Currying is not trivial: either you have to define multiple parameter lists, or construct a new function that allows for currying (Function.curried). And at the call site, you also need two parameter lists if you call a 'curryable' function without currying. - There's a lot of operator overloading abuse. I like the freeness of overloading for DSLs. But using method names such as /: and \: (which are just folds) sometimes makes things quite unreadable. - Generics are still implemented via type erasure. Scala is to Java what C++ is to C, an old language with new constructs forcefully bolted on top. It is powerful, and people will continuously find fantastic things you can do with it. But it is also overly complex, verbose, and unreadable, and inherits some legacy from Java. If it really catches on, most users will probably restrict themself to a subset of the language. Personally, I like simple languages better: Haskell/ML for functional programming, Prolog for logics programming, and C/Python/D for imperative programming. Now, if it can be stitched together with LLVM, that would be nice ;). Take care, Daniel
Dec 21 2009
Mon, 21 Dec 2009 18:01:29 +0100, Daniel de Kok wrote:On 2009-12-18 18:02:28 +0100, retard <re tard.com.invalid> said:This is an unfortunate implementation issue. There's probably a workaround - some conversion classes such as scala.collection.JavaConversions._ - one could imagine.I've only seen how Scala solves problems elegantly. These are from some biased blog posts etc. Can you show one example that looks uglier in Scala, but looks decent in D or some other language?some random things that I found annoying: - Types of both worlds get mixed. For instance, Scala has 'functional lists', but much of the Java world uses mutable lists (following the List interface). If you use the vast amounts of Java class libraries around (since the Scala library is still fairly minimal), you either have to fall back to Java lists (which do not work with a functional style of programming) or convert list back and forth all the time.- You can do functional programming, but it will end up being slow, because of the lack of proper tail-call recursion optimization.Again an unfortunate implementation issue. Will probably be fixed later.- Documentation for much of the Scala library is non-existant. There's a lot of second-guessing which traits you are expected to use, or which self-calling functions are tail-recursive. Since method signatures are pretty unreadable as well, you are pretty much on your own.Agreed. Will be fixed later. Keep in mind that D is older language than Scala - now tell me what mystruct.tupleof.stringof does - where's the documentation? From the top of my head I can imagine at least 200 different cases where the D/Phobos's documentation sucks.- Classes are ugly. Constructor parameters are part of the class definition: class Something(someString: String) While this looks like a somewhat typically functional type declaration in this simple case, once you start building real classes they pollute class declarations, since you have to do non-trivial initialization somewhere. Of course, you could do this in functional style, but most libraries are not written in this manner.The idea probably is to make all declarations syntactically uniform: class foo(bar: T) - class def def foo(bar: T) - function def case foo(bar: T) - pattern new foo(bar: T) - class instantiation (new) foo(bar: T) - case class instantiation Did you know you can also use D like explicit constructor functions: class foo { def this(...) { ... } } The constructor on the first line has a special meaning. It can save a lot of typing - no getters and setters anywhere.- Pattern matching with match...case is not particularly elegant compared to Haskell (where you just have multiple function definitions).No, the match-case construct is equivalent to case-of in haskell. You can also pattern match via overloading: abstract class A case class B() extends A case class C() extends A def a(b: B) = 1 def a(b: C) = 2 def b = _ match { case B => 1 case C => 2 } val foo = a(B()) vs data A = B | C a B = 1 a C = 2 a b = case b of B -> 1 C -> 2 foo = a B- Currying is not trivial: either you have to define multiple parameter lists, or construct a new function that allows for currying (Function.curried). And at the call site, you also need two parameter lists if you call a 'curryable' function without currying.This is a larger problem in the language. I'm not sure if anything can be done without causing problems in other use cases.- There's a lot of operator overloading abuse. I like the freeness of overloading for DSLs. But using method names such as /: and \: (which are just folds) sometimes makes things quite unreadable.Those are not operator overloads. Abuse?- Generics are still implemented via type erasure.Implementation issues..Scala is to Java what C++ is to C, an old language with new constructs forcefully bolted on top. It is powerful, and people will continuously find fantastic things you can do with it. But it is also overly complex, verbose, and unreadable, and inherits some legacy from Java. If it really catches on, most users will probably restrict themself to a subset of the language.JVM has its weaknesses. If you write win32 code in D, you get the shitty performance and terrible toolchain when using dmd/dmc or give up exception support (ldc). I wouldn't use D on win32 for anything that requires high performance - c, c++, and java are much better. Other than that I'd call your claims big time utter bullshit. First, scala is less verbose than c++, c, d, or java. You can measure this yourself - come back when you've done your homework. Scala is less complex than C++ or D. Count the number of keywords, the number of constructs, the number of special cases in language grammar or semantics, built-in types, etc. Try to find even one area where Scala is *more* complex than D. It has a handful of features that D doesn't - but my gut feeling is that D3 will get some of those (for instance implementations in interfaces aka traits). Unreadable? Ok.. Inherits some legacy from Java? Now build an OOP language that runs on JVM and looks less like Java. Java is pretty much the common subset of comprise of. Scala doesn't look especially Java like. Keywords like Pascal, Haskell etc.
Dec 21 2009
retard wrote:Agreed. Will be fixed later. Keep in mind that D is older language than Scala - now tell me what mystruct.tupleof.stringof does - where's the documentation? From the top of my head I can imagine at least 200 different cases where the D/Phobos's documentation sucks.I would appreciate it if you could list these cases, and put them in a Bugzilla issue or at least email them to me. Thanks!
Dec 21 2009
On Mon, 21 Dec 2009 14:01:23 -0500, Walter Bright <newshound1 digitalmars.com> wrote:retard wrote:http://whatwg.org/html5 has a system where people can leave comments pointing out issues without even leaving the page. This lowers the bar for submitting documentation bugs. It might work for D's spec too.Agreed. Will be fixed later. Keep in mind that D is older language than Scala - now tell me what mystruct.tupleof.stringof does - where's the documentation? From the top of my head I can imagine at least 200 different cases where the D/Phobos's documentation sucks.I would appreciate it if you could list these cases, and put them in a Bugzilla issue or at least email them to me. Thanks!
Dec 21 2009
Walter Bright Wrote:dsimcha wrote:Ironically, I think you could write a nearly identical approach in D. By using array slicing, you could get something like Haskell's elegant syntax but still be sorting the array in-place.== Quote from Walter Bright (newshound1 digitalmars.com)'s articleI'm very doubtful it can be optimized out in theory. I'll bet it isn't done in practice.qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) prominently featured in Haskell's official introduction page: http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell Ain't that cool? But look closer. The advantage of quicksort is that it is an *in-place* sort. The Haskell one creates new arrays for every state in the sort.I think this can be optimized out in theory, though I have no idea how often it is in practice.Then it's not looking so simple and elegant anymore :-)The other fundamental problem with the Haskell version is that it selects the first array element as the "pivot". This is the worst choice, since arrays to be sorted tend to already be mostly sorted, and quicksort gives quadratic performance to sort an already sorted array with the first element as the pivot.True. All you'd need to remedy this, though, is a median of 3 function.
Dec 21 2009
Andrei Alexandrescu Wrote:retard wrote:Don't have much time to read D NG these days but I saw this and felt it fair to reply. "Elegant" FP qsorts are the aquintessential, useless big O, examples of academic FP (as opposed to real-world, practical FP). Gotta give Andrei due for his command of the English language. Sometimes he sounds like a modern day Shakespeare. "... introductions to FP contain this ridiculous qsort. It should be dipped in tar and feathers and showed around the town" Disagree though; having watched The Scarlet Pimpernel last night, I'd rather suggest the guillotine?Sat, 19 Dec 2009 14:04:32 -0600, Andrei Alexandrescu wrote:Apparently I haven't managed to qualify my statements well enough - I tried to make it clear I'm not going for cheap shots, so I'm a bit puzzled that you fell exactly for that.Walter Bright wrote:So now that you've finished writing your own book you have nothing else to do but to bash all books written by users of competitive languages. How low..The Haskell folks really need to find a better canonical example.The footnote says (how the hell did this make it through the editorial pass???) "This code is shown for its elegance rather than its efficiency. Using ++ in this way is not generally considered good programming practice." So if the code is inefficient and in poor programming practice, how in this blessed world could it count as elegant?I'm 100% sure I can find a suboptimal programming example from some C/C++/ D book.Yah, but that's not the one that's featured prominently as one of the coolest examples there is, and it wouldn't be horrendously bad. Virtually all introductions to FP contain this ridiculous qsort. It should be dipped in tar and feathers and showed around the town.Just like an operating system implementation book discusses Minix or some educational kernel, it's not really a surprise that programming books have naive examples. I'm not really interested to hear how latest win7 or linux 2.6.33 kernel patch solves some SATA2 / btrfs issue when reading about filesystems and buses. You should take those words about relative elegance with a grain of salt. Functional code is usually less verbose, less buggy, a bit less efficient due to many issues etc. These are things most professionals agree with. Apparently D users need to enhance their e-dick by ranting about everything that's not done in d just to get a tiny bit of publicity.I think it would grow yours to understand what functional qsort's problems are.Currently I wouldn't classify myself as a D user but think that very unfair statement is well deserving of Andrei's curt reply: "... it would grow yours to understand what functional qsort's problems are." Justin JohanssonApparently D users need to enhance their e-dick by ranting about everything that's not done in d just to get a tiny bit of publicity.
Dec 22 2009
Nick Sabalausky Wrote:It should be "should be", for the same reason and in the same way that the "waterfall" development model *should be* taught: Presenting it up front as conceptually-easy-but-generally-a-bad-thing-to-do will help people identify it and therefore avoid it. Not teaching about it increases the chances that they'll either rediscover it or come across a usage of it without actually noticing that there's a problem. It would be like selling sodium without including a warning that it explodes upon contact with water (Or something like that, anyway, I never actually took chemistry...).Pity, Nick; chemistry was really good fun. Citing potassium would be even better. An accident with pot (K) actually happened to someone I knew at high school and the result was rather ugly. Better still would be to cite rubidium -> caesium -> francium. These elements, all in the the alkali metals group, have an extreme affinity for oxidation i.e. explosion when in contact with, well, oxidants :-) Francium is rather rare though and a the skull-and-crossbone radioactive warning would be more apt for selling this particular alkai metal. Cheers, Justin
Dec 22 2009
Don Wrote:retard wrote:...I'd say it's easier. If you watch someone sorting some cards, they'll use either insertion sort or selection sort. Nobody should have ever heard of bubble sort, I'm pleased to hear some schools aren't mentioning it. Such a foolish algorithm. "the bubble sort seems to have nothing to recommend it, except a catchy name " - Knuth.(Non-software) people doing routine tasks often come up with better algorithms intuitively than my intuition expects them to. I think a lot of people would do even better than insertion with a deck of poker cards -- they might group cards by either suit or rank (or rank groups) (e.g. "Hmm, I'll make three piles of 1-5, 6-10, and J-A"), then order the "buckets", then stick these ordered sets back together. If you think about it, this is a lot like a radix sort or a multi-pivot cousin of the quick sort. I think when you ask people to do a computer version of how they would sort, they do worse than this. It's so hard to communicate anything complicated to a computer that they instinctively "dumb it down" and do insertion or bubble. Insertion is what you would manually use when dealing with adding a few new elements to a short stack, whereas something like a bubble might be what you would use manually when it's hard to jump around among the elements of the sequence (e.g. if you have a bunch of "see also" references embedded in dictionary entries and you need to sort within the see-also 'chain'). That approach (kind of) matches the claims often given by computer programmers that bubble sort is good for linked lists and/or "only fixing a few things that are out of place in a mostly sorted list". When you have a pupil that is as hard to talk to and unmotivated to learn as a computer, the first attempt is to try to teach it anything at all and call that a success if it works. A more eager human pupil tries to meet you half way, so you naturally respond and take pleasure in teaching them more and more advanced stuff. If you're really hard headed and immune to tedium, you keep trying with even a super-dumb pupil like a CPU. You keep going in for the hard case so many times that you and eventually major in CompSci out of habit. Kevin
Dec 27 2009
== Quote from Kevin Bealer (kevinbealer gmail.com)'s article(Non-software) people doing routine tasks often come up with better algorithmsintuitively than my intuition expects them to.I think a lot of people would do even better than insertion with a deck of pokercards -- they might group cards by either suit or rank (or rank groups) (e.g. "Hmm, I'll make three piles of 1-5, 6-10, and J-A"), then order the "buckets", then stick these ordered sets back together. If you think about it, this is a lot like a radix sort or a multi-pivot cousin of the quick sort. You mean a bucket sort? http://en.wikipedia.org/wiki/Bucket_sort
Dec 27 2009
dsimcha Wrote:== Quote from Kevin Bealer (kevinbealer gmail.com)'s articleMore or less, though I think human beings use algorithms in a more artistic way than sticking to any one algorithm. I'm curious if the multi-pivot quicksort (I think everyone gets what I mean by this? Divide by more than one pivot on each pass? I can give details if you like ...) has been tried out much. It seems like it must have been, but it also seems like something that would have cache-awareness advantages that would not show up in the simplified comparison-counting way of thinking about efficiency. Kevin(Non-software) people doing routine tasks often come up with better algorithmsintuitively than my intuition expects them to.I think a lot of people would do even better than insertion with a deck of pokercards -- they might group cards by either suit or rank (or rank groups) (e.g. "Hmm, I'll make three piles of 1-5, 6-10, and J-A"), then order the "buckets", then stick these ordered sets back together. If you think about it, this is a lot like a radix sort or a multi-pivot cousin of the quick sort. You mean a bucket sort? http://en.wikipedia.org/wiki/Bucket_sort
Dec 27 2009
Kevin Bealer <kevinbealer gmail.com> wrote:I'm curious if the multi-pivot quicksort (I think everyone gets what I mean by this? Divide by more than one pivot on each pass? I can give details if you like ...) has been tried out much. It seems like it must have been, but it also seems like something that would have cache-awareness advantages that would not show up in the simplified comparison-counting way of thinking about efficiency.I've heard of two-pivot quicksort, but can't remember where. -- Simen
Dec 28 2009
Simen kjaeraas Wrote:Kevin Bealer <kevinbealer gmail.com> wrote:Some information about dual pivot quicksort: http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628I'm curious if the multi-pivot quicksort (I think everyone gets what I mean by this? Divide by more than one pivot on each pass? I can give details if you like ...) has been tried out much. It seems like it must have been, but it also seems like something that would have cache-awareness advantages that would not show up in the simplified comparison-counting way of thinking about efficiency.I've heard of two-pivot quicksort, but can't remember where. -- Simen
Dec 29 2009
Nekuromento Wrote:Simen kjaeraas Wrote:Looks awesome? But the proof is too academical for my taste. Why can't D implement a three-pivot quicksort and beat Java? What does myarray.sort in D use now?Kevin Bealer <kevinbealer gmail.com> wrote:Some information about dual pivot quicksort: http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628I'm curious if the multi-pivot quicksort (I think everyone gets what I mean by this? Divide by more than one pivot on each pass? I can give details if you like ...) has been tried out much. It seems like it must have been, but it also seems like something that would have cache-awareness advantages that would not show up in the simplified comparison-counting way of thinking about efficiency.I've heard of two-pivot quicksort, but can't remember where. -- Simen
Dec 29 2009
On Tue, 29 Dec 2009 21:36:25 +0300, justme <justme somewhere.net> wrote:Nekuromento Wrote:http://www.dsource.org/projects/druntime/browser/trunk/src/rt/qsort.dSimen kjaeraas Wrote:Looks awesome? But the proof is too academical for my taste. Why can't D implement a three-pivot quicksort and beat Java? What does myarray.sort in D use now?Kevin Bealer <kevinbealer gmail.com> wrote:what II'm curious if the multi-pivot quicksort (I think everyone getsgivemean by this? Divide by more than one pivot on each pass? I canmustdetails if you like ...) has been tried out much. It seems like itSome information about dual pivot quicksort: http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628have been, but it also seems like something that would have cache-awareness advantages that would not show up in the simplified comparison-counting way of thinking about efficiency.I've heard of two-pivot quicksort, but can't remember where. -- Simen
Dec 29 2009
Denis Koroskin wrote:On Tue, 29 Dec 2009 21:36:25 +0300, justme <justme somewhere.net> wrote:Yeah, that's the obvious question -- what's the optimum number of pivots? It's a bit annoying that that paper doesn't mention it.Nekuromento Wrote:Simen kjaeraas Wrote:Looks awesome? But the proof is too academical for my taste. Why can't D implement a three-pivot quicksort and beat Java?Kevin Bealer <kevinbealer gmail.com> wrote:what II'm curious if the multi-pivot quicksort (I think everyone getsgivemean by this? Divide by more than one pivot on each pass? I canit mustdetails if you like ...) has been tried out much. It seems likeSome information about dual pivot quicksort: http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628have been, but it also seems like something that would have cache-awareness advantages that would not show up in the simplified comparison-counting way of thinking about efficiency.I've heard of two-pivot quicksort, but can't remember where. -- Simen
Dec 29 2009
Don:Yeah, that's the obvious question -- what's the optimum number of pivots? It's a bit annoying that that paper doesn't mention it.Two pivots help avoid a common bad corner case of the QuickSort (when there are many equal items). Writing a good sorting routine is not easy, there's lot of software engineering behind it. I have studied this topic some. Bye, bearophile
Dec 29 2009
Wed, 30 Dec 2009 02:58:14 -0500, bearophile wrote:Don:So can you tell us then what is the optimal number of pivots? Can it be proven? They say the two-pivot version is the best improvement over the practical version of classic quicksort since sliced bread.Yeah, that's the obvious question -- what's the optimum number of pivots? It's a bit annoying that that paper doesn't mention it.Two pivots help avoid a common bad corner case of the QuickSort (when there are many equal items). Writing a good sorting routine is not easy, there's lot of software engineering behind it. I have studied this topic some.
Dec 30 2009
retard:So can you tell us then what is the optimal number of pivots?<I can tell you that two pivot, used in the correct way, lead to a good quicksort, as I've said.Can it be proven?I don't know. It can be proven that two pivot are enough to avoid the problem with the classic QuickSort. Bye, bearophile
Dec 30 2009
bearophile wrote:retard:From a cursory glance, it seems that the number of swaps (0.8) ultimately comes out of the binomial theorem, so it ought to be straightforward to expand the analysis. I also suspect that it'd be better to switch from two-pivot to one-pivot quicksort at some value of n. It'd be interesting to know how the two-pivot quicksort compares to timsort. I suspect there's a median-of-five-killer worst case for this quicksort, just as there's a median-of-three killer for standard quicksort.So can you tell us then what is the optimal number of pivots?<I can tell you that two pivot, used in the correct way, lead to a good quicksort, as I've said.Can it be proven?I don't know. It can be proven that two pivot are enough to avoid the problem with the classic QuickSort. Bye, bearophile
Dec 30 2009
Don:It'd be interesting to know how the two-pivot quicksort compares to timsort.Timsort is probably a bit slower, but they can't be compared, because Timsort is a stable sort, while normal quicksorts aren't.I suspect there's a median-of-five-killer worst case for this quicksort, just as there's a median-of-three killer for standard quicksort.Yes, there is. The purpose of using two pivots is not to avoid the inevitable worst case (that's made of usually a limited number of permutations, where the really worst is just one specific permutation), but to avoid a whole class of worst cases, where items are distributed in few equivalence classes. This case is much more common, it's not a sharp point in the landscape of the possible input permutations, it's a plateu, so it deserves to be fixed, and there's a simple way to fix it. In practice the presence of the O(n^2) sharp worst case is worrying enough the Java devs, so in Java the quicksort is used only for native data. On classes it uses a safer sorting routine not-quicksort based, so a possible attacker can't put inside the class some logic to dynamically find the worst case and attack a Java system. I think the default system sort of a language like D has to be stable (as in Python), and the unstable algorithm (a templated introsort based on 2 pivot quicksort, with 1 recursive call, trimedian of trimedian, with fallback on heapsort in slow situations) can be used just as optimization when necessary. I don't know if the safety adopted by Java (to not use quicksort on objects) is a good idea in D2 too. Bye, bearophile
Dec 30 2009
Kevin Bealer wrote:I think a lot of people would do even better than insertion with a deck of poker cards -- they might group cards by either suit or rank (or rank groups) (e.g. "Hmm, I'll make three piles of 1-5, 6-10, and J-A"), then order the "buckets", then stick these ordered sets back together. If you think about it, this is a lot like a radix sort or a multi-pivot cousin of the quick sort.When sorting a deck of cards, insertion sort performs in O(n log n), the same as the best-case performance of a quick sort. When sorting arrays, you can find the insertion point in O(log n), but the actual insertion takes O(n). With a deck of cards, you can perform the insertion in O(1). There is absolutely no point in using quick sort for a deck of cards. Only the non-comparison-based sorts (radix sort, bucket sort) can do better than insertion sort. -- Rainer Deyke - rainerd eldwood.com
Dec 27 2009
Rainer Deyke Wrote:Kevin Bealer wrote:Right, if you mean strictly sorting a physical deck of cards by hand. Insertion sort isn't efficient in a computer because you need to find the insertion point quickly and insert quickly to keep the efficiency, but no data structure can really do both quickly. For linked lists, insert is quick (O(1)) but find is slow (O(n/2)); for arrays, find is quick (assuming you use binary search, O(ln n)) but insert is slow (O(n)). Either choice sticks you with a slow operation. KevinI think a lot of people would do even better than insertion with a deck of poker cards -- they might group cards by either suit or rank (or rank groups) (e.g. "Hmm, I'll make three piles of 1-5, 6-10, and J-A"), then order the "buckets", then stick these ordered sets back together. If you think about it, this is a lot like a radix sort or a multi-pivot cousin of the quick sort.When sorting a deck of cards, insertion sort performs in O(n log n), the same as the best-case performance of a quick sort. When sorting arrays, you can find the insertion point in O(log n), but the actual insertion takes O(n). With a deck of cards, you can perform the insertion in O(1). There is absolutely no point in using quick sort for a deck of cards. Only the non-comparison-based sorts (radix sort, bucket sort) can do better than insertion sort. -- Rainer Deyke - rainerd eldwood.com
Dec 27 2009
Denis Koroskin Wrote:On Tue, 29 Dec 2009 21:36:25 +0300, justme <justme somewhere.net> wrote:I can't really read that code - apparently the author has not ever read the Clean code book (http://www.amazon.com/Clean-Code-Handbook-Software-Craftsman hip/dp/0132350882). To me it looks like it uses insertion sort for small arrays (< 8 elements) and single-pivot quicksort for larger ones.Nekuromento Wrote:http://www.dsource.org/projects/druntime/browser/trunk/src/rt/qsort.dSimen kjaeraas Wrote:Looks awesome? But the proof is too academical for my taste. Why can't D implement a three-pivot quicksort and beat Java? What does myarray.sort in D use now?Kevin Bealer <kevinbealer gmail.com> wrote:what II'm curious if the multi-pivot quicksort (I think everyone getsgivemean by this? Divide by more than one pivot on each pass? I canmustdetails if you like ...) has been tried out much. It seems like itSome information about dual pivot quicksort: http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628have been, but it also seems like something that would have cache-awareness advantages that would not show up in the simplified comparison-counting way of thinking about efficiency.I've heard of two-pivot quicksort, but can't remember where. -- Simen
Dec 29 2009