www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Go rant

reply bearophile <bearophileHUGS lycos.com> writes:
This is a mostly boring rant against the Go language:
http://monoc.mo.funpic.de/go-rant/

Near the end it contains an interesting bit:
Too, why this divide, again, with reference types and value types? Did they not
learn from the problems this caused in Java? While Java slowly struggles its
way free of that tarpit, the Go designers leap in headfirst.<

Can someone here explain me this problem better? Bye, bearophile
Dec 14 2009
parent reply Sean Kelly <sean invisibleduck.org> writes:
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.
Dec 14 2009
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
There are things that I read often around in blogs and papers (and sometimes
even in books), but sometimes I keep not understanding them.

Sean Kelly:
 If I had to guess I'd say that he's referring to that fact that value types in
Java are second-class citizens.  The standard containers can only hold objects,
so boxing is necessary,<

Reading that page I have thought he wants all data to be managed by reference.
I have absolutely no idea how all this applies to Go, however.<

Currently Go has no generics or templates, and it has both refence-based data and value data. Thank you for your answer, bye, bearophile
Dec 14 2009
parent Mike Farnsworth <mike.farnsworth gmail.com> writes:
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.
Dec 14 2009
prev sibling next sibling parent reply retard <re tard.com.invalid> writes:
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.
Dec 15 2009
parent reply "Peter C. Chapin" <pcc482719 gmail.com> writes:
retard <re tard.com.invalid> wrote in
news:hg8ppr$107b$4 digitalmars.com: 

 That's not the only problem in JVM. Languages are
 getting more and more functional these days and many enterprise Java
 projects use ad-hoc single method interfaces to emulate lambdas.

I've been using Scala (http://www.scala-lang.org/) a fair about recently. It's a function/OO hybrid language on the JVM that supports closures, etc. It's actually quite nice in a number of respects, I have no idea what kind of hoops the Scala implementors had to jump through to get it to work, though. I do know that compiling a typical Scala file generates a bunch of .class files with weirdo names so they are definitely creating quite a few auxillary classes behind the scenes to get things done. Peter
Dec 17 2009
parent reply Daniel de Kok <me danieldk.eu> writes:
On 2009-12-17 13:58:44 +0100, retard <re tard.com.invalid> said:
 Most likely they have will have to wrap lambdas inside some kind of
 Function objects. I've read that even Scala would benefit from a more
 functional friendly VM. But Sun's focus is on JavaFX and dynamic
 languages now..

One of the first necessities for good functional programming on the JVM would be support for tail call optimization. I believe the Scala 2.7.x compiler performs this optimization only in the self-recursive case. From my first experiences with Scala for number crunching (machine learning), is that it is very slow for non-trivial programs. Besides that, it is the beauty of functional languages mixed with the mess of Java and generics. And it ain't pretty. -- Daniel
Dec 18 2009
next sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
retard wrote:
 I've only seen how Scala solves problems elegantly. These are from some 
 biased blog posts etc. Can you show one example that looks uglier in 
 Scala, but looks decent in D or some other language?

Many languages offer "show" examples that look elegant. A classic example is the one line Haskell quick sort: qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs) prominently featured in Haskell's official introduction page: http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell Ain't that cool? But look closer. The advantage of quicksort is that it is an *in-place* sort. The Haskell one creates new arrays for every state in the sort. The other fundamental problem with the Haskell version is that it selects the first array element as the "pivot". This is the worst choice, since arrays to be sorted tend to already be mostly sorted, and quicksort gives quadratic performance to sort an already sorted array with the first element as the pivot. Ironically, the quicksort example shows a serious weakness of functional programming, not an elegant strength.
Dec 18 2009
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Walter Bright (newshound1 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.
Dec 18 2009
next sibling parent Walter Bright <newshound1 digitalmars.com> writes:
dsimcha wrote:
 == Quote from Walter Bright (newshound1 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 :-)
Dec 18 2009
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
dsimcha wrote:
 == Quote from Walter Bright (newshound1 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
Dec 18 2009
prev sibling next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
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
Dec 18 2009
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Dec 18 2009
parent Ary Borenszweig <ary esperanto.org.ar> writes:
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?
Dec 18 2009
prev sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
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.
Dec 18 2009
next sibling parent Walter Bright <newshound1 digitalmars.com> writes:
Walter Bright wrote:
 There is no
 mention in the text of any of the egregious shortcomings of the example.

I take that back, later on it does mention the memory consumption problem: http://www.haskell.org/haskellwiki/Introduction#When_C_is_better
Dec 18 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Walter Bright wrote:
 The Haskell folks really need to find a better canonical example.

Add to that the Erlang folk, too. I'm reading the book on Erlang by Armstrong. Here's the Quicksort section and example on page 52: "Here's how to write a sort algorithm[footnote] using two list comprehensions." The footnote says (how the hell did this make it through the editorial pass???) "This code is shown for its elegance rather than its efficiency. Using ++ in this way is not generally considered good programming practice." So if the code is inefficient and in poor programming practice, how in this blessed world could it count as elegant? I have gathered a fair amount of samples of involuntary humor from that book. I wouldn't want to go on about that because it could too easily be interpreted as poor taste competitiveness. Let me say I don't think the book is well written. Andrei
Dec 19 2009
next sibling parent downs <default_357-line yahoo.de> writes:
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.

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.
Dec 19 2009
prev sibling next sibling parent Walter Bright <newshound1 digitalmars.com> writes:
retard wrote:
 I'm 100% sure I can find a suboptimal programming example from some C/C++/
 D book.

Andrei's book draft is out for review. If you wish to review it and make suggestions for improvement, I'm sure Andrei can arrange that. Now's the time to do that!
 Just like an operating system implementation book discusses Minix 
 or some educational kernel, it's not really a surprise that programming 
 books have naive examples. I'm not really interested to hear how latest 
 win7 or linux 2.6.33 kernel patch solves some SATA2 / btrfs issue when 
 reading about filesystems and buses. You should take those words about 
 relative elegance with a grain of salt. Functional code is usually less 
 verbose, less buggy, a bit less efficient due to many issues etc. These 
 are things most professionals agree with. Apparently D users need to 
 enhance their e-dick by ranting about everything that's not done in d 
 just to get a tiny bit of publicity.

I've read many books about programming languages. One stands out - K&R's The C Programming Language. The code examples in it are marvelous in conciseness and utility. It is possible to write a programming language book that way, and there's a good reason why K&R is an enduring classic of the genre. I know it's hard to come up with examples that are illustrative, educational, elegant, and concise, but it is worth the author's best efforts in trying to do so.
Dec 19 2009
prev sibling next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s
 "This code is shown for its elegance rather than its efficiency. Using
 ++ in this way is not generally considered good programming practice."
 So if the code is inefficient and in poor programming practice, how in
 this blessed world could it count as elegant?

Because most functional programming purists (or, to avoid singling out functional programming, purists of any single paradigm) are theory weenies. These people usually don't know an L2 cache from a floating point unit. They wouldn't grok things like implementation efficiency (as opposed to algorithmic/asymptotic efficiency) or close to the metal concepts if they were hit smack in the head with them. Thus, they live in paradigm land and work with theoretical models instead of real-world code.
Dec 19 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
dsimcha wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s
 "This code is shown for its elegance rather than its efficiency. Using
 ++ in this way is not generally considered good programming practice."
 So if the code is inefficient and in poor programming practice, how in
 this blessed world could it count as elegant?

Because most functional programming purists (or, to avoid singling out functional programming, purists of any single paradigm) are theory weenies. These people usually don't know an L2 cache from a floating point unit. They wouldn't grok things like implementation efficiency (as opposed to algorithmic/asymptotic efficiency) or close to the metal concepts if they were hit smack in the head with them. Thus, they live in paradigm land and work with theoretical models instead of real-world code.

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
Dec 19 2009
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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.

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
Dec 19 2009
prev sibling next sibling parent reply Daniel de Kok <me danieldk.eu> writes:
On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:
 "This code is shown for its elegance rather than its efficiency. Using 
 ++ in this way is not generally considered good programming practice."
 
 So if the code is inefficient and in poor programming practice, how in 
 this blessed world could it count as elegant?

Well, it is elegant in that it is very readable, and as such provides educational value. There are very many examples in programming text books that may not be efficient, but do show the solution to a problem elegantly. E.g. consider list reversal in a recursive function or predicate. It is easy to see that to reverse a list, you append the head to the reversed tail. E.g.: reverse([],[]). reverse([H|T],R) :- reverse(T,RT), append(RT,[H],R). Of course, this is very inefficient, since the program is doing (slow) appends all the time, and is not tail-recursive. You can do it a lot faster with an accumulator, but it makes the solution also less understandable, and not something you'd want to present students/readers immediately: reverse(List,Reverse) :- reverse_aux(List,Reverse,[]). reverse_aux([],List,List). reverse_aux([H|T],List,List0) :- reverse_aux(T,List,[H|List0]).
 I have gathered a fair amount of samples of involuntary humor from that 
 book. I wouldn't want to go on about that because it could too easily 
 be interpreted as poor taste competitiveness. Let me say I don't think 
 the book is well written.

It seems that currently the time to market is much more important than to provide good material, although I cannot comment on that particular book. -- Daniel
Dec 21 2009
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Daniel de Kok wrote:
 On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu 
 <SeeWebsiteForEmail erdani.org> said:
 "This code is shown for its elegance rather than its efficiency. Using 
 ++ in this way is not generally considered good programming practice."

 So if the code is inefficient and in poor programming practice, how in 
 this blessed world could it count as elegant?

Well, it is elegant in that it is very readable, and as such provides educational value.

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
Dec 21 2009
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
 <SeeWebsiteForEmail erdani.org> said:
 "This code is shown for its elegance rather than its efficiency. Using
 ++ in this way is not generally considered good programming practice."

 So if the code is inefficient and in poor programming practice, how in
 this blessed world could it count as elegant?

educational value.

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.

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]).

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
Dec 21 2009
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail 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?
Dec 21 2009
prev sibling parent reply Daniel de Kok <me nowhere.nospam> writes:
On 2009-12-21 19:13:48 +0100, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> said:
 I disagree. We don't want to educate people to write patently 
 inefficient code and in poor programming practice.

I do not mind it, it's ok for explaining a concept clearly. Of course, inadequacies should also be discussed. I'd argue that these are also the thinking steps normally involved in designing a solution to a problem: first try to solve it in the obvious way to understand the problem. Then, make a more performant implementation. Of course, performant also depends on the context. I have written a lot of C++ code that tries to squeeze the last bit of performance out of the machine in a single-core world, but it is also difficult to parallelize. In a parallel world, the 'slower' solution is sometimes better.
 In my mind "elegant" and "at a polynomial blowup in complexity" can't 
 be reconciled anywhere outside a Turing machine introduction where 
 everything is equivalent within a polynomial difference in time and 
 space.

Elegant in the sense of being able to describe a concept briefly. The in-place quicksort does not do this.
 I think that's a roundabout way of saying that functional programming 
 is unable to express certain algorithms easily or at all.

...in pure FP. Of course, another problem is that some algorithms are inherently imperative. For instance, I find calculating the edit distance in a performant manner ugly in functional languages. -- Daniel
Dec 22 2009
next sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Daniel de Kok wrote:
 I do not mind it, it's ok for explaining a concept clearly. Of course, 
 inadequacies should also be discussed. I'd argue that these are also the 
 thinking steps normally involved in designing a solution to a problem: 
 first try to solve it in the obvious way to understand the problem. 
 Then, make a more performant implementation. Of course, performant also 
 depends on the context. I have written a lot of C++ code that tries to 
 squeeze the last bit of performance out of the machine in a single-core 
 world, but it is also difficult to parallelize. In a parallel world, the 
 'slower' solution is sometimes better.

One of the big problems with the presentations of the functional qsort is that it is presented as a shining success of FP, when it is anything but. There may be later a footnote or comment that it is not suitable, but those appear to be written as afterthoughts and do not clearly lay out what the problems are. Furthermore, an introductory FP programming text should be about how to write useful programs in FP, not about how sorting algorithms work.
Dec 22 2009
next sibling parent Daniel de Kok <me nowhere.nospam> writes:
On 2009-12-22 10:43:17 +0100, Walter Bright <newshound1 digitalmars.com> said:
 One of the big problems with the presentations of the functional qsort 
 is that it is presented as a shining success of FP, when it is anything 
 but.

There are better examples of 'shining succes' in FP. For example, consider the very clear and terse examples of balancing binary search trees or heaps in the Okasaki book. DSLs are also another good example where FP works very well. However, these examples are probably too long to catch attention from a casual reader browsing the haskell.org, or as an introductary example of functional languages.
 Furthermore, an introductory FP programming text should be about how to 
 write useful programs in FP, not about how sorting algorithms work.

'ML for the working programmer' is certainly one of the better FP programming texts I have seen, and it discusses various sorting algorithms and how they work (with the head as a pivot in quicksorting :p). But how is that problematic? Some of good programming books will end up being used in CS curricula, and then it's useful to learn something along the way, rather than have a dry treaty about yet another language. -- Daniel
Dec 22 2009
prev sibling next sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
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.

bad? That only means that there's market for good FPL books, then!

Any FP programming text that puts the one line qsort front and center as an example of how great FP is is a book that has room for improvement, you bet.
Dec 22 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
retard wrote:
 I use the Okasaki book as my bible when talking about purely functional 
 data structures.

It's an awesome book. It's also very frank and tells things as they are, as opposed to others (*cough*) that patronize the reader by artificially making it seem so easy, it's amazing how Stoopid People missed the point. Un-incidentally, Okasaki does not dabble in qsort. He does describe mergesort - a perfectly sound and advantageous sorting methods for lists. Ok, I'm itching to share another gem. "At this point you might be wondering how it's possible to program without variables. How can you express something like X = X + 1 in <language erased to protect the guilty>? The answer is easy. Invent a new variable whose name hasn't been used before (say X1), and write X1 = X + 1". Andrei
Dec 22 2009
next sibling parent =?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= <jeberger free.fr> writes:
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: quoted-printable

Andrei Alexandrescu wrote:
 retard wrote:
 I use the Okasaki book as my bible when talking about purely=20
 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 artificiall=

 making it seem so easy, it's amazing how Stoopid People missed the=20
 point. Un-incidentally, Okasaki does not dabble in qsort. He does=20
 describe mergesort - a perfectly sound and advantageous sorting methods=

 for lists.
=20
 Ok, I'm itching to share another gem.
=20
 "At this point you might be wondering how it's possible to program=20
 without variables. How can you express something like X =3D X + 1 in=20
 <language erased to protect the guilty>? The answer is easy. Invent a=20
 new variable whose name hasn't been used before (say X1), and write X1 =

 X + 1".
=20

and they use it for optimisation (SSA form). That being the case,=20 it's ridiculous to force the programmer to take notice... Jerome --=20 mailto:jeberger free.fr http://jeberger.free.fr Jabber: jeberger jabber.fr
Dec 22 2009
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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.

as opposed to others (*cough*) that patronize the reader by artificially making it seem so easy, it's amazing how Stoopid People missed the point. Un-incidentally, Okasaki does not dabble in qsort. He does describe mergesort - a perfectly sound and advantageous sorting methods for lists. Ok, I'm itching to share another gem. "At this point you might be wondering how it's possible to program without variables. How can you express something like X = X + 1 in <language erased to protect the guilty>? The answer is easy. Invent a new variable whose name hasn't been used before (say X1), and write X1 = X + 1".

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
Dec 22 2009
parent reply Rainer Deyke <rainerd eldwood.com> writes:
Andrei Alexandrescu wrote:
 Hm, I guess I should have been more explicit. The problem isn't defining
 a few more names, but that the explanation completely neglects any
 control flow issues (e.g. conditionals and loops). You can't define a
 new name for each instance of a loop, so everything is recursion etc. I
 mean the consequences are earth-shattering.

The implications of single assignment on control structures seem both insignificant and obvious to me. Much more troubling is that it doesn't work for fields and array elements at all. -- Rainer Deyke - rainerd eldwood.com
Dec 22 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Dec 22 2009
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Philippe Sigaud wrote:
 
 
 On Tue, Dec 22, 2009 at 21:51, Andrei Alexandrescu 
 <SeeWebsiteForEmail erdani.org <mailto:SeeWebsiteForEmail erdani.org>> 
 wrote:
 
     retard wrote:
 
         I use the Okasaki book as my bible when talking about purely
         functional data structures.
 
 
     It's an awesome book. It's also very frank and tells things as they
     are, as opposed to others (*cough*) that patronize the reader by
     artificially making it seem so easy, it's amazing how Stoopid People
     missed the point. Un-incidentally, Okasaki does not dabble in qsort.
     He does describe mergesort - a perfectly sound and advantageous
     sorting methods for lists.
 
  
 I've only read his PhD a few months ago. Lots of mind-expanding ideas in 
 there.
 Someone told me the book is even better. Is it worth the 25-30  I see 
 on Amazon? (gosh, why I'm asking this when I'll spend thrice as much in 
 food just for tonight's dinner...)

If you could ingest his thesis, you'll like the book, which is an expansion of the ideas therein. Andrei
Dec 23 2009
prev sibling parent Walter Bright <newshound1 digitalmars.com> writes:
retard wrote:
 Simon Peyton Jones had in his slides a nice graph of the reliability vs 
 performance issues. Functional languages were originally very slow, but 
 had the safety aspect. Imperative languages have always been fast, and 
 only gradually improved on the reliability front. Pure functional 
 languages have never given up the reliability aspect, so it's a bit 
 surprising how small amount of people here know what's their biggest 
 advantage.

I don't need convincing of that. I agree it is a great advantage to FP. I argue this point repeatedly when people question the point of immutability.
Dec 22 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Daniel de Kok wrote:
 On 2009-12-21 19:13:48 +0100, Andrei Alexandrescu 
 <SeeWebsiteForEmail erdani.org> said:
 I disagree. We don't want to educate people to write patently 
 inefficient code and in poor programming practice.

I do not mind it, it's ok for explaining a concept clearly.

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
Dec 22 2009
parent reply Daniel de Kok <me nowhere.nospam> writes:
On 2009-12-22 14:24:41 +0100, Andrei Alexandrescu 
<SeeWebsiteForEmail erdani.org> 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
Dec 22 2009
parent Walter Bright <newshound1 digitalmars.com> writes:
Daniel de Kok wrote:
 Of course, there are good counter-examples where purity helps. But it's 
 not a black-white world. Not that I really have to say that on a D list 
 ;-).

Right, D is not a language implementing a religion!
Dec 22 2009
prev sibling next sibling parent Lutger <lutger.blijdestijn gmail.com> writes:
retard wrote:

 Mon, 21 Dec 2009 18:54:19 +0100, Daniel de Kok wrote:
 
 On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> said:
 "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?
Dec 21 2009
prev sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
retard wrote:
 I have several imperative language programming books and instead of qsort 
 they introduce the reader to the wonderful world of bubble sort!

Bubble sort should be part of an introductory programming course, if only because: 1. it's an algorithm that gets reinvented if one is not aware of it 2. one needs to be able to recognize it, as one will encounter it a lot in production code 3. it's a great way to introduce concepts like big O 4. it's a great stepping stone to introducing better sorts I've run into bubble sort reimplementations in production code written by famous programmers who should know better. It happens all the time.
Dec 21 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Dec 21 2009
next sibling parent reply =?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= <jeberger free.fr> writes:
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: quoted-printable

Andrei Alexandrescu wrote:
 Walter Bright wrote:
 retard wrote:
 I have several imperative language programming books and instead of=20
 qsort they introduce the reader to the wonderful world of bubble sort=



 Bubble sort should be part of an introductory programming course, if=20
 only because:

 1. it's an algorithm that gets reinvented if one is not aware of it

 2. one needs to be able to recognize it, as one will encounter it a=20
 lot in production code

 3. it's a great way to introduce concepts like big O

 4. it's a great stepping stone to introducing better sorts


 I've run into bubble sort reimplementations in production code written=


 by famous programmers who should know better. It happens all the time.=


=20
 Fro your arguments 1-4 and your conclusion, I infer you made a slight=20
 typo. Let me fix that for you.
=20
 s/should be/should not be/
=20

course, along with a good explanation of why it is so bad. They say=20 that "for every problem there is a solution which is simple,=20 elegant, and wrong", and bubble sort is as good a way as any to make=20 that point. However, it is essential that the teacher actually *make* that=20 point and not leave the students believing that bubble sort is a=20 good algorithm. Jerome --=20 mailto:jeberger free.fr http://jeberger.free.fr Jabber: jeberger jabber.fr
Dec 21 2009
parent reply Charles Hixson <charleshixsn earthlink.net> writes:
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 





 qsort they introduce the reader to the wonderful world of bubble 





 Bubble sort should be part of an introductory programming course, 




 only because:

 1. it's an algorithm that gets reinvented if one is not aware of 




 2. one needs to be able to recognize it, as one will encounter it 




 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 




 by famous programmers who should know better. It happens all the 




 Fro your arguments 1-4 and your conclusion, I infer you made a 



 typo. Let me fix that for you.

 s/should be/should not be/

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


 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.
Dec 26 2009
parent reply Don <nospam nospam.com> writes:
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





 qsort they introduce the reader to the wonderful world of bubble





 Bubble sort should be part of an introductory programming course,




 only because:

 1. it's an algorithm that gets reinvented if one is not aware of




 2. one needs to be able to recognize it, as one will encounter it




 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




 by famous programmers who should know better. It happens all the




 Fro your arguments 1-4 and your conclusion, I infer you made a



 typo. Let me fix that for you.

 s/should be/should not be/

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


 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

place), it's just niche algorithm.

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.
Dec 26 2009
next sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Don wrote:
 I'd say it's easier. If you watch someone sorting some cards, they'll 
 use either insertion sort or selection sort. Nobody should have ever 
 heard of bubble sort, I'm pleased to hear some schools aren't mentioning 
 it. Such a foolish algorithm.

I suppose I'm alone in thinking that engineering school should also cover designs that don't work and explain why!
Dec 26 2009
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Walter Bright:
 I suppose I'm alone in thinking that engineering school should also 
 cover designs that don't work and explain why!

Knuth doesn't say it's uselsss to teach Bubble sort. Knowing bad algorithms is useful if they are both obvious and slow, to know the basics and to avoid them. And learning what Bubble Sort is, is useful to learn other things, like the Kendal Tau distance, for example: http://en.wikipedia.org/wiki/Kendall_tau_distance Bye, bearophile
Dec 27 2009
prev sibling next sibling parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Walter Bright (newshound1 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.

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.
Dec 27 2009
prev sibling parent reply Sean Kelly <sean invisibleduck.org> writes:
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.
Dec 27 2009
parent Walter Bright <newshound1 digitalmars.com> writes:
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.
Dec 27 2009
prev sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Don (nospam nospam.com)'s article
 "the bubble sort seems to have nothing to recommend it, except a catchy
 name " - Knuth.

Well, the bubble sort distance is a pretty good metric of how similarly ordered two lists are. It's useful, for example, in statistics such as Kendall's Tau. One of the easiest ways to calculate it is...with a bubble sort.
Dec 27 2009
parent reply Don <nospam nospam.com> writes:
dsimcha wrote:
 == Quote from Don (nospam nospam.com)'s article
 "the bubble sort seems to have nothing to recommend it, except a catchy
 name " - Knuth.

Well, the bubble sort distance is a pretty good metric of how similarly ordered two lists are. It's useful, for example, in statistics such as Kendall's Tau. One of the easiest ways to calculate it is...with a bubble sort.

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?
Dec 27 2009
parent Charles Hixson <charleshixsn earthlink.net> writes:
Don wrote:

 dsimcha wrote:
 == Quote from Don (nospam nospam.com)'s article
 "the bubble sort seems to have nothing to recommend it, except a 



 name " - Knuth.

Well, the bubble sort distance is a pretty good metric of how


 ordered
 two lists are.  It's useful, for example, in statistics such as 


 Tau. One of the easiest ways to calculate it is...with a bubble 


 
 I don't think that's a coincidence. It seems to be defined in terms 

 bubble sort!
 
 The whole bubble sort phenonemon seems to be self-perpetuating. 

 were loads of really crap algorithms in the 1950's. Why was this one 

 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.
Jan 13 2010
prev sibling parent "Nick Sabalausky" <a a.a> writes:
"Andrei Alexandrescu" <SeeWebsiteForEmail erdani.org> wrote in message 
news:4B2FCF53.9050608 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...).
Dec 21 2009
prev sibling parent Philippe Sigaud <philippe.sigaud gmail.com> writes:
--0016e6d7e6813ef8e0047b65b6fc
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: quoted-printable

On Tue, Dec 22, 2009 at 21:51, Andrei Alexandrescu <
SeeWebsiteForEmail erdani.org> wrote:

 retard wrote:

 I use the Okasaki book as my bible when talking about purely functional
 data structures.

It's an awesome book. It's also very frank and tells things as they are, =

 opposed to others (*cough*) that patronize the reader by artificially mak=

 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 =80 I see on Amazon? (gosh, why I'm asking this when I'll spend thrice as much in food just for tonight's dinner...) Philippe --0016e6d7e6813ef8e0047b65b6fc Content-Type: text/html; charset=windows-1252 Content-Transfer-Encoding: quoted-printable <br><br> <div class=3D"gmail_quote">On Tue, Dec 22, 2009 at 21:51, Andrei Alexandres= cu <span dir=3D"ltr">&lt;<a href=3D"mailto:SeeWebsiteForEmail erdani.org">S= eeWebsiteForEmail erdani.org</a>&gt;</span> wrote:<br> <blockquote style=3D"BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex= ; PADDING-LEFT: 1ex" class=3D"gmail_quote"> <div class=3D"im">retard wrote:<br> <blockquote style=3D"BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex= ; PADDING-LEFT: 1ex" class=3D"gmail_quote">I use the Okasaki book as my bib= le when talking about purely functional data structures.<br></blockquote><b= r> </div>It&#39;s an awesome book. It&#39;s also very frank and tells things a= s they are, as opposed to others (*cough*) that patronize the reader by art= ificially making it seem so easy, it&#39;s amazing how Stoopid People misse= d the point. Un-incidentally, Okasaki does not dabble in qsort. He does des= cribe mergesort - a perfectly sound and advantageous sorting methods for li= sts.</blockquote> <div>=A0</div> <div>I&#39;ve only read his PhD a few months ago. Lots of mind-expanding id= eas in there. </div> <div>Someone told me the book is even better. Is it=A0worth the 25-30 =80 I= see on Amazon? (gosh, why I&#39;m asking this when I&#39;ll spend thrice a= s much in food just for tonight&#39;s dinner...)</div> <div>=A0</div> <div>=A0 Philippe</div> <div>=A0</div></div> --0016e6d7e6813ef8e0047b65b6fc--
Dec 23 2009
prev sibling parent reply Daniel de Kok <me danieldk.eu> writes:
On 2009-12-18 20:39:08 +0100, Walter Bright <newshound1 digitalmars.com> said:
 Ain't that cool? But look closer. The advantage of quicksort is that it 
 is an *in-place* sort. The Haskell one creates new arrays for every 
 state in the sort.

But it does have one nice property: due to laziness, the n-th elements of the sorted array can be found without sorting the full array (except of course, the largest two n's). -- Daniel
Dec 21 2009
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Daniel de Kok wrote:
 On 2009-12-18 20:39:08 +0100, Walter Bright <newshound1 digitalmars.com> 
 said:
 Ain't that cool? But look closer. The advantage of quicksort is that 
 it is an *in-place* sort. The Haskell one creates new arrays for every 
 state in the sort.

But it does have one nice property: due to laziness, the n-th elements of the sorted array can be found without sorting the full array (except of course, the largest two n's).

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
Dec 21 2009
prev sibling parent reply Daniel de Kok <me danieldk.eu> writes:
On 2009-12-18 18:02:28 +0100, retard <re tard.com.invalid> said:
 I've only seen how Scala solves problems elegantly. These are from some
 biased blog posts etc. Can you show one example that looks uglier in
 Scala, but looks decent in D or some other language?

I can not paste any of this particular code ($WORK). From the top of my head, some random things that I found annoying: - Types of both worlds get mixed. For instance, Scala has 'functional lists', but much of the Java world uses mutable lists (following the List interface). If you use the vast amounts of Java class libraries around (since the Scala library is still fairly minimal), you either have to fall back to Java lists (which do not work with a functional style of programming) or convert list back and forth all the time. - You can do functional programming, but it will end up being slow, because of the lack of proper tail-call recursion optimization. - Documentation for much of the Scala library is non-existant. There's a lot of second-guessing which traits you are expected to use, or which self-calling functions are tail-recursive. Since method signatures are pretty unreadable as well, you are pretty much on your own. - Classes are ugly. Constructor parameters are part of the class definition: class Something(someString: String) While this looks like a somewhat typically functional type declaration in this simple case, once you start building real classes they pollute class declarations, since you have to do non-trivial initialization somewhere. Of course, you could do this in functional style, but most libraries are not written in this manner. - Pattern matching with match...case is not particularly elegant compared to Haskell (where you just have multiple function definitions). - Currying is not trivial: either you have to define multiple parameter lists, or construct a new function that allows for currying (Function.curried). And at the call site, you also need two parameter lists if you call a 'curryable' function without currying. - There's a lot of operator overloading abuse. I like the freeness of overloading for DSLs. But using method names such as /: and \: (which are just folds) sometimes makes things quite unreadable. - Generics are still implemented via type erasure. Scala is to Java what C++ is to C, an old language with new constructs forcefully bolted on top. It is powerful, and people will continuously find fantastic things you can do with it. But it is also overly complex, verbose, and unreadable, and inherits some legacy from Java. If it really catches on, most users will probably restrict themself to a subset of the language. Personally, I like simple languages better: Haskell/ML for functional programming, Prolog for logics programming, and C/Python/D for imperative programming. Now, if it can be stitched together with LLVM, that would be nice ;). Take care, Daniel
Dec 21 2009
parent Walter Bright <newshound1 digitalmars.com> writes:
retard wrote:
 Agreed. Will be fixed later. Keep in mind that D is older language than 
 Scala - now tell me what mystruct.tupleof.stringof does - where's the 
 documentation? From the top of my head I can imagine at least 200 
 different cases where the D/Phobos's documentation sucks.

I would appreciate it if you could list these cases, and put them in a Bugzilla issue or at least email them to me. Thanks!
Dec 21 2009
prev sibling next sibling parent retard <re tard.com.invalid> writes:
Thu, 17 Dec 2009 12:24:50 +0000, Peter C. Chapin wrote:

 retard <re tard.com.invalid> wrote in
 news:hg8ppr$107b$4 digitalmars.com:
 
 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..
Dec 17 2009
prev sibling next sibling parent retard <re tard.com.invalid> writes:
Fri, 18 Dec 2009 16:43:35 +0100, Daniel de Kok wrote:

 On 2009-12-17 13:58:44 +0100, retard <re tard.com.invalid> said:
 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?
Dec 18 2009
prev sibling next sibling parent retard <re tard.com.invalid> writes:
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
Dec 18 2009
prev sibling next sibling parent retard <re tard.com.invalid> writes:
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.
Dec 19 2009
prev sibling next sibling parent retard <re tard.com.invalid> writes:
Sat, 19 Dec 2009 21:29:45 -0600, Andrei Alexandrescu wrote:

 dsimcha wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s
 "This code is shown for its elegance rather than its efficiency. Using
 ++ in this way is not generally considered good programming practice."
 So if the code is inefficient and in poor programming practice, how in
 this blessed world could it count as elegant?

Because most functional programming purists (or, to avoid singling out functional programming, purists of any single paradigm) are theory weenies. These people usually don't know an L2 cache from a floating point unit. They wouldn't grok things like implementation efficiency (as opposed to algorithmic/asymptotic efficiency) or close to the metal concepts if they were hit smack in the head with them. Thus, they live in paradigm land and work with theoretical models instead of real-world code.

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!
Dec 20 2009
prev sibling next sibling parent retard <re tard.com.invalid> writes:
Mon, 21 Dec 2009 18:01:29 +0100, Daniel de Kok wrote:

 On 2009-12-18 18:02:28 +0100, retard <re tard.com.invalid> said:
 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 *more* complex than D. It has a handful of features that D doesn't - but my gut feeling is that D3 will get some of those (for instance implementations in interfaces aka traits). Unreadable? Ok.. Inherits some legacy from Java? Now build an OOP language that runs on JVM and looks less like Java. Java is pretty much the common subset of features most modern mainstream languages (C#, C++, D, Scala, Vala etc.) comprise of. Scala doesn't look especially Java like. Keywords like 'extends' comes to mind, but it also shares many features with C#, Pascal, Haskell etc.
Dec 21 2009
prev sibling next sibling parent retard <re tard.com.invalid> writes:
Mon, 21 Dec 2009 18:54:19 +0100, Daniel de Kok wrote:

 On 2009-12-19 21:04:32 +0100, Andrei Alexandrescu
 <SeeWebsiteForEmail erdani.org> said:
 "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!
Dec 21 2009
prev sibling next sibling parent retard <re tard.com.invalid> writes:
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
 <SeeWebsiteForEmail erdani.org> said:
 "This code is shown for its elegance rather than its efficiency. Using
 ++ in this way is not generally considered good programming practice."

 So if the code is inefficient and in poor programming practice, how in
 this blessed world could it count as elegant?

Well, it is elegant in that it is very readable, and as such provides educational value.

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.
Dec 21 2009
prev sibling next sibling parent retard <re tard.com.invalid> writes:
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
 <SeeWebsiteForEmail erdani.org> said:
 "This code is shown for its elegance rather than its efficiency.
 Using ++ in this way is not generally considered good programming
 practice."
 
 So if the code is inefficient and in poor programming practice, how
 in this blessed world could it count as elegant?

Well, it is elegant in that it is very readable, and as such provides educational value. There are very many examples in programming text books that may not be efficient, but do show the solution to a problem elegantly.

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.
Dec 21 2009
prev sibling next sibling parent "Denis Koroskin" <2korden gmail.com> writes:
On Tue, 22 Dec 2009 00:10:44 +0300, J=C3=A9r=C3=B4me M. Berger <jeberger=
 free.fr>  =

wrote:

 Andrei Alexandrescu wrote:
 Walter Bright wrote:
 retard wrote:
 I have several imperative language programming books and instead of=




 qsort they introduce the reader to the wonderful world of bubble so=




 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 writt=



 by famous programmers who should know better. It happens all the tim=



 Fro your arguments 1-4 and your conclusion, I infer you made a slight=


 typo. Let me fix that for you.

 s/should be/should not be/

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.
Dec 21 2009
prev sibling next sibling parent "Phil Deets" <pjdeets2 gmail.com> writes:
On Mon, 21 Dec 2009 14:01:23 -0500, Walter Bright  
<newshound1 digitalmars.com> 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.
Dec 21 2009
prev sibling next sibling parent retard <re tard.com.invalid> writes:
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!
Dec 22 2009
prev sibling next sibling parent retard <re tard.com.invalid> writes:
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.
Dec 22 2009
prev sibling next sibling parent retard <re tard.com.invalid> writes:
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.
Dec 22 2009
prev sibling next sibling parent retard <re tard.com.invalid> writes:
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 <language erased to protect the guilty>? The answer is easy. Invent a new variable whose name hasn't been used before (say X1), and write X1 = X + 1".

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; }
Dec 22 2009
prev sibling parent retard <re tard.com.invalid> writes:
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





 qsort they introduce the reader to the wonderful world of bubble





 Bubble sort should be part of an introductory programming course,




 only because:

 1. it's an algorithm that gets reinvented if one is not aware of




 2. one needs to be able to recognize it, as one will encounter it




 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




 by famous programmers who should know better. It happens all the




 Fro your arguments 1-4 and your conclusion, I infer you made a



 typo. Let me fix that for you.

 s/should be/should not be/

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


 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.
Dec 26 2009