Re: Go rant
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: > >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? 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.
Re: Go rant
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
Re: Go rant
bearophile Wrote: > 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 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.
Re: Go rant
Mon, 14 Dec 2009 19:51:10 -0500, Sean Kelly wrote: > 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: >> >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? > > 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. 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 in other areas). C# implementations also manage to solve this by not 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 language support in Java 7, but JVM probably isn't getting c++0x/d/c#/ 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.. > 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.
Re: Go rant
retard wrote in news:hg8ppr$107...@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
Re: Go rant
Thu, 17 Dec 2009 12:24:50 +, Peter C. Chapin wrote: > retard wrote in > news:hg8ppr$107...@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. 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..
Re: Go rant
On 2009-12-17 13:58:44 +0100, retard 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
Re: Go rant
Fri, 18 Dec 2009 16:43:35 +0100, Daniel de Kok wrote: > On 2009-12-17 13:58:44 +0100, retard 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. 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?
Re: Go rant
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.
Re: Go rant
== Quote from Walter Bright (newshou...@digitalmars.com)'s article > 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. > 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.
Re: Go rant
dsimcha wrote: == Quote from Walter Bright (newshou...@digitalmars.com)'s article 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. I'm very doubtful it can be optimized out in theory. I'll bet it isn't done 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. Then it's not looking so simple and elegant anymore :-)
Re: Go rant
dsimcha wrote: == Quote from Walter Bright (newshou...@digitalmars.com)'s article 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. 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. Median 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 Andrei
Re: Go rant
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 (and F# and a bit less Scala) are using more and more 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. Please ask if you have missed my two points, because they must be understood if you want to design a modern language. Bye, bearophile
Re: Go rant
bearophile wrote: 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. It's a piece of crap. A crappy example is a crappy example is a crappy example. It consistently does more harm than good. 2) The second point you are missing is even bigger. Today languages as Clojure (and F# and a bit less Scala) are using more and more 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
Re: Go rant
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. In other words, the #1 example of how great Haskell is sucks and is useless for real programming. The Haskell folks really need to find a better canonical example.
Re: Go rant
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
Re: Go rant
Fri, 18 Dec 2009 16:42:27 -0800, Walter Bright wrote:
> 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.
>
> In other words, the #1 example of how great Haskell is sucks and is
> useless for real programming.
>
> The Haskell folks really need to find a better canonical example.
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 c
Re: Go rant
Andrei Alexandrescu wrote: bearophile wrote: 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. It's a piece of crap. A crappy example is a crappy example is a crappy example. It consistently does more harm than good. What's that argument?
Re: Go rant
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
Re: Go rant
Sat, 19 Dec 2009 14:04:32 -0600, Andrei Alexandrescu wrote: > 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. 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.
Re: Go rant
retard wrote: > Sat, 19 Dec 2009 14:04:32 -0600, Andrei Alexandrescu wrote: > >> 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. > > 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.. > It's his opinion and he, being an author himself, has a better basis for it than you do. > 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.
Re: Go rant
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.
Re: Go rant
== Quote from Andrei Alexandrescu (seewebsiteforem...@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.
Re: Go rant
dsimcha wrote: == Quote from Andrei Alexandrescu (seewebsiteforem...@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. That 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
Re: Go rant
retard wrote: Sat, 19 Dec 2009 14:04:32 -0600, Andrei Alexandrescu wrote: 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. 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.. 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. 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
Re: Go rant
Sat, 19 Dec 2009 21:29:45 -0600, Andrei Alexandrescu wrote: > dsimcha wrote: >> == Quote from Andrei Alexandrescu (seewebsiteforem...@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. > > That 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? 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!
Re: Go rant
On 2009-12-18 18:02:28 +0100, retard 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
Re: Go rant
On 2009-12-18 20:39:08 +0100, Walter Bright 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
Re: Go rant
On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu 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
Re: Go rant
Daniel de Kok wrote: On 2009-12-18 20:39:08 +0100, Walter Bright 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). 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.) Andrei
Re: Go rant
Daniel de Kok wrote: On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu 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. 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. 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 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. 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. Andrei
Re: Go rant
Mon, 21 Dec 2009 18:54:19 +0100, Daniel de Kok wrote: > On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu > 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. I have several imperative language programming books and instead of qsort they introduce the reader to the wonderful world of bubble sort!
Re: Go rant
Mon, 21 Dec 2009 18:01:29 +0100, Daniel de Kok wrote:
> On 2009-12-18 18:02:28 +0100, retard 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?
>
> 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.
This is an unfortunate implementation issue. There's probably a
workaround - some conversion classes such as
scala.collection.JavaConversions._ - one could imagine.
> - 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
Re: Go rant
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!
Re: Go rant
retard wrote: > Mon, 21 Dec 2009 18:54:19 +0100, Daniel de Kok wrote: > >> On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu >> 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. > > I have several imperative language programming books and instead of qsort > they introduce the reader to the wonderful world of bubble sort! And do you think that is good and elegant or stupid and ugly?
Re: Go rant
Mon, 21 Dec 2009 12:13:48 -0600, Andrei Alexandrescu wrote: > Daniel de Kok wrote: >> On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu >> 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. > > 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. > >> 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 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.
Re: Go rant
Mon, 21 Dec 2009 20:04:05 +0100, Lutger wrote: > retard wrote: > >> Mon, 21 Dec 2009 18:54:19 +0100, Daniel de Kok wrote: >> >>> On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu >>> 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. >> >> I have several imperative language programming books and instead of >> qsort they introduce the reader to the wonderful world of bubble sort! > > And do you think that is good and elegant or stupid and ugly? I'll let the official authority decide that. I have no opinion.
Re: Go rant
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.
Re: Go rant
Walter Bright wrote: 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. 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/ Andrei
Re: Go rant
retard wrote: Mon, 21 Dec 2009 12:13:48 -0600, Andrei Alexandrescu wrote: Daniel de Kok wrote: On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu 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. 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. 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 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. 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. 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
Re: Go rant
== Quote from Andrei Alexandrescu (seewebsiteforem...@erdani.org)'s > I fail to see how in D you'd be hard pressed to think in terms of lower > level abstractions. > Andrei Devil's advocate since I mostly agree: Conservative GC?
Re: Go rant
Andrei Alexandrescu wrote: Walter Bright wrote: 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. 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/ 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 -- mailto:jeber...@free.fr http://jeberger.free.fr Jabber: jeber...@jabber.fr signature.asc Description: OpenPGP digital signature
Re: Go rant
On Tue, 22 Dec 2009 00:10:44 +0300, Jérôme M. Berger wrote: Andrei Alexandrescu wrote: Walter Bright wrote: 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. 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/ 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 Bubble sort is not that bad (e.g. a sequence with one element out of place), it's just niche algorithm.
Re: Go rant
Walter Bright Wrote: > dsimcha wrote: > > == Quote from Walter Bright (newshou...@digitalmars.com)'s article > >> 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. > > I'm very doubtful it can be optimized out in theory. I'll bet it isn't > done in practice. 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. > >> 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. > > Then it's not looking so simple and elegant anymore :-)
Re: Go rant
"Andrei Alexandrescu" wrote in message news:4b2fcf53.9050...@erdani.org... > Walter Bright wrote: >> 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. > > 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/ > 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...).
Re: Go rant
On Mon, 21 Dec 2009 14:01:23 -0500, Walter Bright wrote: 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! 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.
Re: Go rant
On 2009-12-21 19:13:48 +0100, Andrei Alexandrescu 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
Re: Go rant
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.
Re: Go rant
Tue, 22 Dec 2009 01:43:17 -0800, Walter Bright wrote: > 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. 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. > > 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!
Re: Go rant
Tue, 22 Dec 2009 01:43:17 -0800, Walter Bright wrote: > 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 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.
Re: Go rant
Andrei Alexandrescu Wrote: > retard wrote: > > Sat, 19 Dec 2009 14:04:32 -0600, Andrei Alexandrescu wrote: > > > >> Walter Bright wrote: > >>> 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? > >> > > 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.. > > 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. > > > 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. 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? > > 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. 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 Johansson
Re: Go rant
Daniel de Kok wrote: On 2009-12-21 19:13:48 +0100, Andrei Alexandrescu 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. My point is that there is no "concept" being explained. The concept of quicksort is not what the FP classic explains. 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 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. 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. 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. So then I guess I can be given a break about FP ueber alles. Andrei
Re: Go rant
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
Re: Go rant
On 2009-12-22 10:43:17 +0100, Walter Bright 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
Re: Go rant
On 2009-12-22 14:24:41 +0100, Andrei Alexandrescu said: Daniel de Kok wrote: ...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. 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
Re: Go rant
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. 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! 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.
Re: Go rant
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.
Re: Go rant
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!
Re: Go rant
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). >> 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. I use the Okasaki book as my bible when talking about purely functional data structures.
Re: Go rant
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 ? The answer is easy. Invent a new variable whose name hasn't been used before (say X1), and write X1 = X + 1". Andrei
Re: Go rant
Andrei Alexandrescu 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. 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 ? The answer is easy. Invent a new variable whose name hasn't been used before (say X1), and write X1 = X + 1". AIUI most compilers are able to do this themselves automatically and they use it for optimisation (SSA form). That being the case, it's ridiculous to force the programmer to take notice... Jerome -- mailto:jeber...@free.fr http://jeberger.free.fr Jabber: jeber...@jabber.fr signature.asc Description: OpenPGP digital signature
Re: Go rant
Tue, 22 Dec 2009 14:51:55 -0600, Andrei Alexandrescu 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.
>
> 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
> ? The answer is easy. Invent a
> new variable whose name hasn't been used before (say X1), and write X1 =
> X + 1".
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 + 1
x = x * 2
x = x - 5
= x
vs
T foo(T)(T x) {
x = x + 1;
x = x * 2;
x = x - 5;
return x;
}
Re: Go rant
retard wrote:
Tue, 22 Dec 2009 14:51:55 -0600, Andrei Alexandrescu 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.
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
? The answer is easy. Invent a
new variable whose name hasn't been used before (say X1), and write X1 =
X + 1".
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 + 1
x = x * 2
x = x - 5
= x
vs
T foo(T)(T x) {
x = x + 1;
x = x * 2;
x = x - 5;
return x;
}
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."
Andrei
Re: Go rant
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 - rain...@eldwood.com
Re: Go rant
Rainer Deyke wrote: 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. 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). Andrei
Re: Go rant
On Tue, Dec 22, 2009 at 21:51, Andrei Alexandrescu < seewebsiteforem...@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...) Philippe
Re: Go rant
Philippe Sigaud wrote: On Tue, Dec 22, 2009 at 21:51, Andrei Alexandrescu mailto:seewebsiteforem...@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
Re: Go rant
Denis Koroskin wrote: > On Tue, 22 Dec 2009 00:10:44 +0300, Jérôme M. Berger > wrote: > >> Andrei Alexandrescu wrote: >>> Walter Bright wrote: 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. >>> >>> 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/ >>> >> 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 > > Bubble sort is not that bad (e.g. a sequence with one element out of > place), it's just niche algorithm. I 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.
Re: Go rant
Sat, 26 Dec 2009 09:21:55 -0800, Charles Hixson wrote: > Denis Koroskin wrote: > >> On Tue, 22 Dec 2009 00:10:44 +0300, Jérôme M. Berger > >> wrote: >> >>> Andrei Alexandrescu wrote: Walter Bright wrote: > 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. 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/ >>> 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 >> >> Bubble sort is not that bad (e.g. a sequence with one element out of >> place), it's just niche algorithm. > > I 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. 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.
Re: Go rant
retard wrote: Sat, 26 Dec 2009 09:21:55 -0800, Charles Hixson wrote: Denis Koroskin wrote: On Tue, 22 Dec 2009 00:10:44 +0300, Jérôme M. Berger wrote: Andrei Alexandrescu wrote: Walter Bright wrote: 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. 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/ 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 Bubble sort is not that bad (e.g. a sequence with one element out of place), it's just niche algorithm. I 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. 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. 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.
Re: Go rant
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!
Re: Go rant
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
Re: Go rant
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
Re: Go rant
== Quote from Don (nos...@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.
Re: Go rant
== Quote from Walter Bright (newshou...@digitalmars.com)'s article > 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! 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.
Re: Go rant
== Quote from Kevin Bealer (kevinbea...@gmail.com)'s article > (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. You mean a bucket sort? http://en.wikipedia.org/wiki/Bucket_sort
Re: Go rant
Walter Bright Wrote: > 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! 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.
Re: Go rant
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 - rain...@eldwood.com
Re: Go rant
Sean Kelly wrote: Walter Bright Wrote: 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. 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.
Re: Go rant
dsimcha wrote: == Quote from Don (nos...@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. I 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?
Re: Go rant
dsimcha Wrote: > == Quote from Kevin Bealer (kevinbea...@gmail.com)'s article > > (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. > > You mean a bucket sort? http://en.wikipedia.org/wiki/Bucket_sort More 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
Re: Go rant
Rainer Deyke Wrote: > 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 - rain...@eldwood.com 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. Kevin
Re: Go rant
Kevin Bealer 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
Re: Go rant
Simen kjaeraas Wrote: > Kevin Bealer 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 Some information about dual pivot quicksort: http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
Re: Go rant
Nekuromento Wrote: > Simen kjaeraas Wrote: > > > Kevin Bealer 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 > > Some information about dual pivot quicksort: > > http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf > > http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628 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?
Re: Go rant
On Tue, 29 Dec 2009 21:36:25 +0300, justme wrote: Nekuromento Wrote: Simen kjaeraas Wrote: > Kevin Bealer 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 Some information about dual pivot quicksort: http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628 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? http://www.dsource.org/projects/druntime/browser/trunk/src/rt/qsort.d
Re: Go rant
Denis Koroskin Wrote: > On Tue, 29 Dec 2009 21:36:25 +0300, justme wrote: > > > Nekuromento Wrote: > > > >> Simen kjaeraas Wrote: > >> > >> > Kevin Bealer 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 > >> > >> Some information about dual pivot quicksort: > >> > >> http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf > >> > >> http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628 > > > > 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? > > http://www.dsource.org/projects/druntime/browser/trunk/src/rt/qsort.d 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-Craftsmanship/dp/0132350882). To me it looks like it uses insertion sort for small arrays (< 8 elements) and single-pivot quicksort for larger ones.
Re: Go rant
Denis Koroskin wrote: On Tue, 29 Dec 2009 21:36:25 +0300, justme wrote: Nekuromento Wrote: Simen kjaeraas Wrote: > Kevin Bealer 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 Some information about dual pivot quicksort: http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628 Looks awesome? But the proof is too academical for my taste. Why can't D implement a three-pivot quicksort and beat Java? 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.
Re: Go rant
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
Re: Go rant
Wed, 30 Dec 2009 02:58:14 -0500, bearophile wrote: > 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. 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.
Re: Go rant
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
Re: Go rant
bearophile wrote: 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 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.
Re: Go rant
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
Re: Go rant
Don wrote: > dsimcha wrote: >> == Quote from Don (nos...@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. > > I 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? 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.
