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

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.

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

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.

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 

erasing that type info.

I don't know why the Sun engineers aren't fixing this. I guess there are 
some political and organizational problems involved. They fear that Java 
is getting too complex so they keep it simple, but slow and unproductive. 
That's not the only problem in JVM. Languages are getting more and more 
functional these days and many enterprise Java projects use ad-hoc single 
method interfaces to emulate lambdas. They're now solving the dynamic 

python/ruby/php/smalltalk/functional language like closures. Soon 99.9% 
of active programming languages have closure support - being able to say 
list.filter(\e => !e.isBadElement) seems to be the next cool thing..

 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.

"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

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

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

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?

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.

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.

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 :-)

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

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

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

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

 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

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?

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.


useless for real programming.

The Haskell folks really need to find a better canonical example.

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

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.

 

 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

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

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.

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.

 Add to that the Erlang folk, too. I'm reading the book on Erlang by
 Armstrong. Here's the Quicksort section and example on page 52:

 "Here's how to write a sort algorithm[footnote] using two list
 comprehensions."

 The footnote says (how the hell did this make it through the editorial
 pass???)

 "This code is shown for its elegance rather than its efficiency. Using
 ++ in this way is not generally considered good programming practice."

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

 I have gathered a fair amount of samples of involuntary humor from that
 book. I wouldn't want to go on about that because it could too easily be
 interpreted as poor taste competitiveness. Let me say I don't think the
 book is well written.

 
 So now that you've finished writing your own book you have nothing else 
 to do but to bash all books written by users of competitive languages. 
 How low..
 

It's his opinion and he, being an author himself, has a better basis for it
than you do.

 I'm 100% sure I can find a suboptimal programming example from some C/C++/
 D book.

That's not what he said though - he said the example is inefficient, and *also*
that he considers the book to be poorly written.

 Just like an operating system implementation book discusses Minix
 or some educational kernel, it's not really a surprise that programming 
 books have naive examples. I'm not really interested to hear how latest 
 win7 or linux 2.6.33 kernel patch solves some SATA2 / btrfs issue when 
 reading about filesystems and buses. You should take those words about 
 relative elegance with a grain of salt. Functional code is usually less 
 verbose, less buggy, a bit less efficient due to many issues etc. These 
 are things most professionals agree with.

The issue is that what this example demonstrates, is that functional code is
apparently _either_ elegant _or_ efficient. This is not a good trade-off to be
forced to make.

 Apparently D users need to
 enhance their e-dick by ranting about everything that's not done in d 
 just to get a tiny bit of publicity.

Nice.

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.

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.

 Add to that the Erlang folk, too. I'm reading the book on Erlang by
 Armstrong. Here's the Quicksort section and example on page 52:

 "Here's how to write a sort algorithm[footnote] using two list
 comprehensions."

 The footnote says (how the hell did this make it through the editorial
 pass???)

 "This code is shown for its elegance rather than its efficiency. Using
 ++ in this way is not generally considered good programming practice."

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

 I have gathered a fair amount of samples of involuntary humor from that
 book. I wouldn't want to go on about that because it could too easily be
 interpreted as poor taste competitiveness. Let me say I don't think the
 book is well written.

 
 So now that you've finished writing your own book you have nothing else 
 to do but to bash all books written by users of competitive languages. 
 How low..

Well I haven't finished, and in fact I'm reading the Erlang book exactly 
to get better insight into handling concurrency via message passing.

Apparently I haven't managed to qualify my statements well enough - I 
tried to make it clear I'm not going for cheap shots, so I'm a bit 
puzzled that you fell exactly for that.

 I'm 100% sure I can find a suboptimal programming example from some C/C++/
 D book.

Yah, but that's not the one that's featured prominently as one of the 
coolest examples there is, and it wouldn't be horrendously bad. 
Virtually all introductions to FP contain this ridiculous qsort. It 
should be dipped in tar and feathers and showed around the town.

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

I think it would grow yours to understand what functional qsort's 
problems are.

Andrei

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.

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

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!

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

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

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.

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?

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

 I disagree. We don't want to educate people to write patently
 inefficient code and in poor programming practice.

 When I was doing Windows programming, I noticed that many example in the
 documentation were written in terrible style. I also noticed that much
 of the production code I was working with was often stitched from
 documentation examples.

 There are very many examples in programming text books that may not be
 efficient, but do show the solution to a problem elegantly.

 Yeah, exponential-time Fibonacci and bubble sort come to mind.

 In my mind "elegant" and "at a polynomial blowup in complexity" can't be
 reconciled anywhere outside a Turing machine introduction where
 everything is equivalent within a polynomial difference in time and
 space.

 E.g. consider list reversal in a recursive function or predicate. It is
 easy to see that to reverse a list, you append the head to the reversed
 tail. E.g.:

 reverse([],[]).
 reverse([H|T],R) :-
  reverse(T,RT),
  append(RT,[H],R).

 Of course, this is very inefficient, since the program is doing (slow)
 appends all the time, and is not tail-recursive. You can do it a lot
 faster with an accumulator, but it makes the solution also less
 understandable, and not something you'd want to present
 students/readers immediately:

 reverse(List,Reverse) :-
  reverse_aux(List,Reverse,[]).

 reverse_aux([],List,List).
 reverse_aux([H|T],List,List0) :-
  reverse_aux(T,List,[H|List0]).

 Yah, I understand. But what you're really saying is that reverse offers
 either a simple implementation or an efficient implementation, but not
 both. That's hardly furthering my belief that FP has a crushing
 advantage over pretty much anything else.

 In another thread, "retard" wrote in response to the comparison of the
 real quicksort in C and Haskell:

 "What is so brilliant? Referential transparency is broken unless single-
 threadedness is forced through monadic computation or by some other
 means (uniqueness types comes to mind)."

 I think that's a roundabout way of saying that functional programming is
 unable to express certain algorithms easily or at all.

 
 I think one of the things that make good programming languages good is 
 that they allow hiding the complexity behind abstractions. This is 
 something I remember from the SICP lectures. This is the ideology behind 
 pure functional and pure object oriented programming. Reliability is 
 transitive - if the building blocks are good, you can't screw /those/ 
 things on higher level. Things like referential transparency also give 
 you truly modular isolation in this way. You can always find a loop hole 
 in languages like D.

That all sounds nice and I agree with it, but friction is also 
transitive. Inefficiencies add when you build higher-level abstractions, 
and may force you at some point to choose between good abstraction and 
working program.

The beauty of D is that it has low or often zero friction in the way of 
creating abstractions. That is very difficult to achieve.

As far as loop holes go, D's answer is SafeD. We managed to pull it in 
an extremely short time, and it's in some ways a gambit, but I am 
confident we have made the right decision. Until somebody provides a 
soundness proof a la Featherweight Java, there is no ultimate proof that 
SafeD is in fact safe, but I have reasons to believe there are no 
principle reasons we can't, and if you do find loopholes please let us 
know. Java has had for years safety holes, and naysayers enjoyed 
claiming it will always have. Now it's common knowledge that Java is safe.

 I think I've already read what you think about abstractions. After all, 
 it's not really surprising why in "systems programming languages" like D 
 one can more or less easily convert any high level expression into 
 machine code in their head. On relatively low level it's benefical to 
 always think in terms of machine code instructions, stack layouts, 
 pointers etc.
 
 But on higher level, performance is in many domains only a secondary 
 goal. Reliability is the main goal. If there's an abstract data type such 
 as a queue or a stack, you simply can't produce traditional stack 
 overflows because the abstraction protects against that. The container 
 code can be really ugly spaghetti internally - the abstraction works as a 
 public interface.

I fail to see how in D you'd be hard pressed to think in terms of lower 
level abstractions.


Andrei

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?

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

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.

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!

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.

 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.

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.

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

=?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= <jeberger free.fr> writes:

Andrei Alexandrescu wrote:
 retard wrote:
 I use the Okasaki book as my bible when talking about purely=20
 functional data structures.

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

,=20
 as opposed to others (*cough*) that patronize the reader by artificiall=

y=20
 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=

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

=3D=20
 X + 1".
=20

	AIUI most compilers are able to do this themselves automatically=20
and they use it for optimisation (SSA form). That being the case,=20
it's ridiculous to force the programmer to take notice...

		Jerome
--=20
mailto:jeberger free.fr
http://jeberger.free.fr
Jabber: jeberger jabber.fr

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 * 2
     x = x - 5
   = x

vs

T foo(T)(T x) {
  x = x + 1;
  x = x * 2;
  x = x - 5;
  return x;
}

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.

 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 * 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

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

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

Philippe Sigaud <philippe.sigaud gmail.com> writes:

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

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

ing
 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

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

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.

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.

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

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

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

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!

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!

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? 

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.

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.

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

=?UTF-8?B?IkrDqXLDtG1lIE0uIEJlcmdlciI=?= <jeberger free.fr> writes:

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=


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

	No, he's right, it should be part of any introductory programming=20
course, along with a good explanation of why it is so bad. They say=20
that "for every problem there is a solution which is simple,=20
elegant, and wrong", and bubble sort is as good a way as any to make=20
that point.

	However, it is essential that the teacher actually *make* that=20
point and not leave the students believing that bubble sort is a=20
good algorithm.

		Jerome
--=20
mailto:jeberger free.fr
http://jeberger.free.fr
Jabber: jeberger jabber.fr

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




rt!
 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=



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



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


 typo. Let me fix that for you.

 s/should be/should not be/

 	No, he's right, it should be part of any introductory programming
 course, along with a good explanation of why it is so bad. They say
 that "for every problem there is a solution which is simple,
 elegant, and wrong", and bubble sort is as good a way as any to make
 that point.

 	However, it is essential that the teacher actually *make* that
 point and not leave the students believing that bubble sort is a
 good algorithm.

 		Jerome

Bubble sort is not that bad (e.g. a sequence with one element out of  =

place), it's just niche algorithm.

Charles Hixson <charleshixsn earthlink.net> writes:

Denis Koroskin wrote:

 On Tue, 22 Dec 2009 00:10:44 +0300, Jérôme 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 





sort!
 Bubble sort should be part of an introductory programming course, 




if
 only because:

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




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




a
 lot in production code

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

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


 I've run into bubble sort reimplementations in production code 




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




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



slight
 typo. Let me fix that for you.

 s/should be/should not be/

 No, he's right, it should be part of any introductory programming
 course, along with a good explanation of why it is so bad. They say
 that "for every problem there is a solution which is simple,
 elegant, and wrong", and bubble sort is as good a way as any to 


make
 that point.

 However, it is essential that the teacher actually *make* that
 point and not leave the students believing that bubble sort is a
 good algorithm.

 Jerome

 
 Bubble sort is not that bad (e.g. a sequence with one element out of
 place), it's just niche algorithm.

I believe that I was taught that a bubble sort was optimal for lists 
of fewer than about 25 elements.  I.e., where n is very small, the 
overhead for the other sorts wasn't worth it.

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

 <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





 sort!
 Bubble sort should be part of an introductory programming course,




 if
 only because:

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




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




 a
 lot in production code

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

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


 I've run into bubble sort reimplementations in production code




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




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



 slight
 typo. Let me fix that for you.

 s/should be/should not be/

 No, he's right, it should be part of any introductory programming
 course, along with a good explanation of why it is so bad. They say
 that "for every problem there is a solution which is simple, elegant,
 and wrong", and bubble sort is as good a way as any to


 make
 that point.

 However, it is essential that the teacher actually *make* that point
 and not leave the students believing that bubble sort is a good
 algorithm.

 Jerome

 
 Bubble sort is not that bad (e.g. a sequence with one element out of
 place), it's just niche algorithm.

 
 I believe that I was taught that a bubble sort was optimal for lists of
 fewer than about 25 elements.  I.e., where n is very small, the overhead
 for the other sorts wasn't worth it.

Nope, that's big time bs. http://en.wikipedia.org/wiki/
Bubble_sort#In_practice -- I wasn't even taught bubble sort in school 
because insertion sort performs much better and is about as easy to 
comprehend.

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

 <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





 sort!
 Bubble sort should be part of an introductory programming course,




 if
 only because:

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




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




 a
 lot in production code

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

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


 I've run into bubble sort reimplementations in production code




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




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



 slight
 typo. Let me fix that for you.

 s/should be/should not be/

 No, he's right, it should be part of any introductory programming
 course, along with a good explanation of why it is so bad. They say
 that "for every problem there is a solution which is simple, elegant,
 and wrong", and bubble sort is as good a way as any to


 make
 that point.

 However, it is essential that the teacher actually *make* that point
 and not leave the students believing that bubble sort is a good
 algorithm.

 Jerome

 Bubble sort is not that bad (e.g. a sequence with one element out of
 place), it's just niche algorithm.

 I believe that I was taught that a bubble sort was optimal for lists of
 fewer than about 25 elements.  I.e., where n is very small, the overhead
 for the other sorts wasn't worth it.

 
 Nope, that's big time bs. http://en.wikipedia.org/wiki/
 Bubble_sort#In_practice -- I wasn't even taught bubble sort in school 
 because insertion sort performs much better and is about as easy to 
 comprehend.

I'd say it's easier. If you watch someone sorting some cards, they'll 
use either insertion sort or selection sort. Nobody should have ever 
heard of bubble sort, I'm pleased to hear some schools aren't mentioning 
it. Such a foolish algorithm.

"the bubble sort seems to have nothing to recommend it, except a catchy 
name " - Knuth.

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!

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

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.

 I suppose I'm alone in thinking that engineering school should also
 cover designs that don't work and explain why!

Yes, the same way programmers discuss anti-patterns.  If it's a bad idea **but
occurs frequently in the real world** then it should be pointed out for
explaining
to people why it's a bad idea, because obviously there are plenty of people that
aren't getting it.

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.

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.

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.

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?

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 



catchy
 name " - Knuth.

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


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


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


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

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

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

not
 forgotten with the rest?

Because it's SIMPLE.  And because for the small sample sizes used in 
most classes (still?) scaling with n^2 isn't all that bad.  Someone 
said that the insertion sort is better even for small sample sizes, 
but if you don't have an array type that implements insertion, then 
that means writing an extra loop to move things down.  I might have 
suggested that the exchange sort was a good choice.  But with small 
sample sizes and limited memory (no longer a significant problem for 
cases where this is even vaguely reasonable) the bubble sort isn't 
that bad.  In fact it's difficult to measure the difference as n tends 
towards 3.  For n == 2 there's no other even vaguely reasonable 
choice.

The problem with bubble sorts is the factor of n^2.  My teacher might 
well have been wrong when he put n as high as 25 for where the bubble 
sort was optimal, but it's clearly optimal when n is less than 4.  
It's just that those cases don't matter in the real world.  (And 
actually, they'd probably be handled with a case statement, or a 
nested if.)  But if you have code that needs to handle sorting array 
sizes between 3 and 25 (varying in the calls, and tending towards the 
low end), then there's no reason to go for anything more complicated.  
Of course, a better choice yet is often to use a library function.  
Even if the low end calls have excess overhead, it won't matter much, 
and you don't need to worry about coding errors.

(Yeah, I believe that Knuth said there was no reason for the bubble 
sort existing.  And without knowing the exact context in which he said 
it, I'm not going to call him wrong.  The times to use it are not only 
extremely limited, there's also a tendency to use it at the wrong 
times, just because you have the code handy, and it's easy.)

P.S.:  If you have an Array class, and the array class has an insert 
method, then the insertion sort is clearly better for building a 
sorted list.  It's less clear if you're sorting a list that you 
already have, and you're trying to avoid allocating new memory.  
Especially if it's not stored a container class with an insert method.

N.B.:  If the bubble sort weren't taught, it would be continually re-
invented.  And as it's so rarely the proper choice, it needs to be 
warned against.  Preferably by having someone write something that, 
sorts things interactively, and then having them start adding things 
to be sorted.  But processors may be fast enough to defeat this 
experiential learning unless you add things in a way that doubles the 
collection size each time you make an addition.

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

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

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

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

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 

comprise of. Scala doesn't look especially Java like. Keywords like 

Pascal, Haskell etc.

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!

"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.

Kevin Bealer <kevinbealer gmail.com> writes:

Walter Bright Wrote:

 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.

Ironically, I think you could write a nearly identical approach in D.  By using
array
slicing, you could get something like Haskell's elegant syntax but still be
sorting
the array in-place.

 The other fundamental problem with the Haskell
 version is that it selects the first array element as the "pivot". This
 is the worst choice, since arrays to be sorted tend to already be mostly
 sorted, and quicksort gives quadratic performance to sort an already
 sorted array with the first element as the pivot.

 
 True.  All you'd need to remedy this, though, is a median of 3 function.

 
 Then it's not looking so simple and elegant anymore :-)

Justin Johansson <no spam.com> writes:

Andrei Alexandrescu Wrote:

 retard wrote:
 Sat, 19 Dec 2009 14:04:32 -0600, Andrei Alexandrescu wrote:
 
 Walter Bright wrote:
 The Haskell folks really need to find a better canonical example.

 The footnote says (how the hell did this make it through the editorial
 pass???)

 "This code is shown for its elegance rather than its efficiency. Using
 ++ in this way is not generally considered good programming practice."

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

 So now that you've finished writing your own book you have nothing else 
 to do but to bash all books written by users of competitive languages. 
 How low..

 
 Apparently I haven't managed to qualify my statements well enough - I 
 tried to make it clear I'm not going for cheap shots, so I'm a bit 
 puzzled that you fell exactly for that.
 
 I'm 100% sure I can find a suboptimal programming example from some C/C++/
 D book.

 
 Yah, but that's not the one that's featured prominently as one of the 
 coolest examples there is, and it wouldn't be horrendously bad. 
 Virtually all introductions to FP contain this ridiculous qsort. It 
 should be dipped in tar and feathers and showed around the town.
 
 Just like an operating system implementation book discusses Minix 
 or some educational kernel, it's not really a surprise that programming 
 books have naive examples.  I'm not really interested to hear how latest
 win7 or linux 2.6.33 kernel patch solves some SATA2 / btrfs issue when 
 reading about filesystems and buses. You should take those words about 
 relative elegance with a grain of salt. Functional code is usually less 
 verbose, less buggy, a bit less efficient due to many issues etc. These 
 are things most professionals agree with. Apparently D users need to 
 enhance their e-dick by ranting about everything that's not done in d 
 just to get a tiny bit of publicity.

 
 I think it would grow yours to understand what functional qsort's 
 problems are.

Don't have much time to read D NG these days but I saw this and felt it fair to
reply.

"Elegant" FP qsorts are the aquintessential, useless big O, examples of
academic FP (as opposed to real-world, practical FP).

Gotta give Andrei due for his command of the English language.  Sometimes he
sounds like a modern day Shakespeare.

"... introductions to FP contain this ridiculous qsort. It should be dipped in
tar and feathers and showed around the town"

Disagree though; having watched The Scarlet Pimpernel last night, I'd rather
suggest the guillotine?

 Apparently D users need to 
 enhance their e-dick by ranting about everything that's not done in d 
 just to get a tiny bit of publicity.


Currently I wouldn't classify myself as a D user but think that very unfair
statement is well deserving of Andrei's curt reply:

"... it would grow yours to understand what functional qsort's problems are."

Justin Johansson

Justin Johansson <no spam.com> writes:

Nick Sabalausky Wrote:

 It should be "should be", for the same reason and in the same way that the 
 "waterfall" development model *should be* taught: Presenting it up front as 
 conceptually-easy-but-generally-a-bad-thing-to-do will help people identify 
 it and therefore avoid it. Not teaching about it increases the chances that 
 they'll either rediscover it or come across a usage of it without actually 
 noticing that there's a problem. It would be like selling sodium without 
 including a warning that it explodes upon contact with water (Or something 
 like that, anyway, I never actually took chemistry...).

Pity, Nick; chemistry was really good fun.

Citing potassium would be even better.  An accident with pot (K) actually
happened to someone I knew at high school and the result was rather ugly.

Better still would be to cite rubidium -> caesium -> francium.  These elements,
all in the the alkali metals group, have an extreme affinity for oxidation i.e.
explosion when in contact with, well, oxidants :-)

Francium is rather rare though and a the skull-and-crossbone radioactive
warning would be more apt for selling this particular alkai metal.

Cheers, Justin

Kevin Bealer <kevinbealer gmail.com> writes:

Don Wrote:
 retard wrote:

...
 
 I'd say it's easier. If you watch someone sorting some cards, they'll 
 use either insertion sort or selection sort. Nobody should have ever 
 heard of bubble sort, I'm pleased to hear some schools aren't mentioning 
 it. Such a foolish algorithm.
 
 "the bubble sort seems to have nothing to recommend it, except a catchy 
 name " - Knuth.

(Non-software) people doing routine tasks often come up with better algorithms
intuitively than my intuition expects them to.

I think a lot of people would do even better than insertion with a deck of
poker cards -- they might group cards by either suit or rank (or rank groups)
(e.g. "Hmm, I'll make three piles of 1-5, 6-10, and J-A"), then order the
"buckets", then stick these ordered sets back together.  If you think about it,
this is a lot like a radix sort or a multi-pivot cousin of the quick sort.

I think when you ask people to do a computer version of how they would sort,
they do worse than this.  It's so hard to communicate anything complicated to a
computer that they instinctively "dumb it down" and do insertion or bubble. 
Insertion is what you would manually use when dealing with adding a few new
elements to a short stack, whereas something like a bubble might be what you
would use manually when it's hard to jump around among the elements of the
sequence (e.g. if you have a bunch of "see also" references embedded in
dictionary entries and you need to sort within the see-also 'chain').  That
approach (kind of) matches the claims often given by computer programmers that
bubble sort is good for linked lists and/or "only fixing a few things that are
out of place in a mostly sorted list".

When you have a pupil that is as hard to talk to and unmotivated to learn as a
computer, the first attempt is to try to teach it anything at all and call that
a success if it works.  A more eager human pupil tries to meet you half way, so
you naturally respond and take pleasure in teaching them more and more advanced
stuff.  If you're really hard headed and immune to tedium, you keep trying with
even a super-dumb pupil like a CPU.  You keep going in for the hard case so
many times that you and eventually major in CompSci out of habit.

Kevin

dsimcha <dsimcha yahoo.com> writes:

== Quote from Kevin Bealer (kevinbealer gmail.com)'s article
 (Non-software) people doing routine tasks often come up with better algorithms

intuitively than my intuition expects them to.
 I think a lot of people would do even better than insertion with a deck of
poker

cards -- they might group cards by either suit or rank (or rank groups) (e.g.
"Hmm, I'll make three piles of 1-5, 6-10, and J-A"), then order the "buckets",
then stick these ordered sets back together.  If you think about it, this is a
lot
like a radix sort or a multi-pivot cousin of the quick sort.

You mean a bucket sort?  http://en.wikipedia.org/wiki/Bucket_sort

Kevin Bealer <kevinbealer gmail.com> writes:

dsimcha Wrote:

 == Quote from Kevin Bealer (kevinbealer gmail.com)'s article
 (Non-software) people doing routine tasks often come up with better algorithms

 intuitively than my intuition expects them to.
 I think a lot of people would do even better than insertion with a deck of
poker

 cards -- they might group cards by either suit or rank (or rank groups) (e.g.
 "Hmm, I'll make three piles of 1-5, 6-10, and J-A"), then order the "buckets",
 then stick these ordered sets back together.  If you think about it, this is a
lot
 like a radix sort or a multi-pivot cousin of the quick sort.
 
 You mean a bucket sort?  http://en.wikipedia.org/wiki/Bucket_sort

More or less, though I think human beings use algorithms in a more artistic way
than sticking to any one algorithm.

I'm curious if the multi-pivot quicksort (I think everyone gets what I mean by
this?  Divide by more than one pivot on each pass?  I can give details if you
like ...) has been tried out much.  It seems like it must have been, but it
also seems like something that would have cache-awareness advantages that would
not show up in the simplified comparison-counting way of thinking about
efficiency.

Kevin

"Simen kjaeraas" <simen.kjaras gmail.com> writes:

Kevin Bealer <kevinbealer gmail.com> wrote:

 I'm curious if the multi-pivot quicksort (I think everyone gets what I  
 mean by this?  Divide by more than one pivot on each pass?  I can give  
 details if you like ...) has been tried out much.  It seems like it must  
 have been, but it also seems like something that would have  
 cache-awareness advantages that would not show up in the simplified  
 comparison-counting way of thinking about efficiency.

I've heard of two-pivot quicksort, but can't remember where.

-- 
Simen

Nekuromento <necroment gmail.com> writes:

Simen kjaeraas Wrote:

 Kevin Bealer <kevinbealer gmail.com> wrote:
 
 I'm curious if the multi-pivot quicksort (I think everyone gets what I  
 mean by this?  Divide by more than one pivot on each pass?  I can give  
 details if you like ...) has been tried out much.  It seems like it must  
 have been, but it also seems like something that would have  
 cache-awareness advantages that would not show up in the simplified  
 comparison-counting way of thinking about efficiency.

 
 I've heard of two-pivot quicksort, but can't remember where.
 
 -- 
 Simen

Some information about dual pivot quicksort:

http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf

http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

justme <justme somewhere.net> writes:

Nekuromento Wrote:

 Simen kjaeraas Wrote:
 
 Kevin Bealer <kevinbealer gmail.com> wrote:
 
 I'm curious if the multi-pivot quicksort (I think everyone gets what I  
 mean by this?  Divide by more than one pivot on each pass?  I can give  
 details if you like ...) has been tried out much.  It seems like it must  
 have been, but it also seems like something that would have  
 cache-awareness advantages that would not show up in the simplified  
 comparison-counting way of thinking about efficiency.

 
 I've heard of two-pivot quicksort, but can't remember where.
 
 -- 
 Simen

 
 Some information about dual pivot quicksort:
 
 http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf
 
 http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

Looks awesome? But the proof is too academical for my taste. Why can't D
implement a three-pivot quicksort and beat Java? What does myarray.sort in D
use now?

"Denis Koroskin" <2korden gmail.com> writes:

On Tue, 29 Dec 2009 21:36:25 +0300, justme <justme somewhere.net> wrote:

 Nekuromento Wrote:

 Simen kjaeraas Wrote:

 Kevin Bealer <kevinbealer gmail.com> wrote:

 I'm curious if the multi-pivot quicksort (I think everyone gets  


 what I
 mean by this?  Divide by more than one pivot on each pass?  I can  


 give
 details if you like ...) has been tried out much.  It seems like it  


 must
 have been, but it also seems like something that would have
 cache-awareness advantages that would not show up in the simplified
 comparison-counting way of thinking about efficiency.

 I've heard of two-pivot quicksort, but can't remember where.

 --
 Simen

 Some information about dual pivot quicksort:

 http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf

 http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

 Looks awesome? But the proof is too academical for my taste. Why can't D  
 implement a three-pivot quicksort and beat Java? What does myarray.sort  
 in D use now?

http://www.dsource.org/projects/druntime/browser/trunk/src/rt/qsort.d

Don <nospam nospam.com> writes:

Denis Koroskin wrote:
 On Tue, 29 Dec 2009 21:36:25 +0300, justme <justme somewhere.net> wrote:
 
 Nekuromento Wrote:

 Simen kjaeraas Wrote:

 Kevin Bealer <kevinbealer gmail.com> wrote:

 I'm curious if the multi-pivot quicksort (I think everyone gets 


 what I
 mean by this?  Divide by more than one pivot on each pass?  I can 


 give
 details if you like ...) has been tried out much.  It seems like 


 it must
 have been, but it also seems like something that would have
 cache-awareness advantages that would not show up in the simplified
 comparison-counting way of thinking about efficiency.

 I've heard of two-pivot quicksort, but can't remember where.

 --
 Simen

 Some information about dual pivot quicksort:

 http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf

 http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

 Looks awesome? But the proof is too academical for my taste. Why can't 
 D implement a three-pivot quicksort and beat Java? 


Yeah, that's the obvious question -- what's the optimum number of 
pivots? It's a bit annoying that that paper doesn't mention it.

bearophile <bearophileHUGS lycos.com> writes:

Don:
 Yeah, that's the obvious question -- what's the optimum number of 
 pivots? It's a bit annoying that that paper doesn't mention it.

Two pivots help avoid a common bad corner case of the QuickSort (when there are
many equal items). Writing a good sorting routine is not easy, there's lot of
software engineering behind it. I have studied this topic some.

Bye,
bearophile

retard <re tard.com.invalid> writes:

Wed, 30 Dec 2009 02:58:14 -0500, bearophile wrote:

 Don:
 Yeah, that's the obvious question -- what's the optimum number of
 pivots? It's a bit annoying that that paper doesn't mention it.

 
 Two pivots help avoid a common bad corner case of the QuickSort (when
 there are many equal items). Writing a good sorting routine is not easy,
 there's lot of software engineering behind it. I have studied this topic
 some.

So can you tell us then what is the optimal number of pivots? Can it be 
proven? They say the two-pivot version is the best improvement over the 
practical version of classic quicksort since sliced bread.

bearophile <bearophileHUGS lycos.com> writes:

retard:
 So can you tell us then what is the optimal number of pivots?<

I can tell you that two pivot, used in the correct way, lead to a good
quicksort, as I've said.


Can it be proven?

I don't know. It can be proven that two pivot are enough to avoid the problem
with the classic QuickSort.

Bye,
bearophile

Don <nospam nospam.com> writes:

bearophile wrote:
 retard:
 So can you tell us then what is the optimal number of pivots?<

 
 I can tell you that two pivot, used in the correct way, lead to a good
quicksort, as I've said.
 
 
 Can it be proven?

 
 I don't know. It can be proven that two pivot are enough to avoid the problem
with the classic QuickSort.
 
 Bye,
 bearophile

 From a cursory glance, it seems that the number of swaps (0.8) 
ultimately comes out of the binomial theorem, so it ought to be 
straightforward to expand the analysis.

I also suspect that it'd be better to switch from two-pivot to one-pivot 
quicksort at some value of n.
It'd be interesting to know how the two-pivot quicksort compares to timsort.

I suspect there's a median-of-five-killer worst case for this quicksort, 
just as there's a median-of-three killer for standard quicksort.

bearophile <bearophileHUGS lycos.com> writes:

Don:
 It'd be interesting to know how the two-pivot quicksort compares to timsort.

Timsort is probably a bit slower, but they can't be compared, because Timsort
is a stable sort, while normal quicksorts aren't.


 I suspect there's a median-of-five-killer worst case for this quicksort, 
 just as there's a median-of-three killer for standard quicksort.

Yes, there is. The purpose of using two pivots is not to avoid the inevitable
worst case (that's made of usually a limited number of permutations, where the
really worst is just one specific permutation), but to avoid a whole class of
worst cases, where items are distributed in few equivalence classes. This case
is much more common, it's not a sharp point in the landscape of the possible
input permutations, it's a plateu, so it deserves to be fixed, and there's a
simple way to fix it.

In practice the presence of the O(n^2) sharp worst case is worrying enough the
Java devs, so in Java the quicksort is used only for native data. On classes it
uses a safer sorting routine not-quicksort based, so a possible attacker can't
put inside the class some logic to dynamically find the worst case and attack a
Java system.

I think the default system sort of a language like D has to be stable (as in
Python), and the unstable algorithm (a templated introsort based on 2 pivot
quicksort, with 1 recursive call, trimedian of trimedian, with fallback on
heapsort in slow situations) can be used just as optimization when necessary.

I don't know if the safety adopted by Java (to not use quicksort on objects) is
a good idea in D2 too.

Bye,
bearophile

Rainer Deyke <rainerd eldwood.com> writes:

Kevin Bealer wrote:
 I think a lot of people would do even better than insertion with a
 deck of poker cards -- they might group cards by either suit or rank
 (or rank groups) (e.g. "Hmm, I'll make three piles of 1-5, 6-10, and
 J-A"), then order the "buckets", then stick these ordered sets back
 together.  If you think about it, this is a lot like a radix sort or
 a multi-pivot cousin of the quick sort.

When sorting a deck of cards, insertion sort performs in O(n log n), the
same as the best-case performance of a quick sort.  When sorting arrays,
you can find the insertion point in O(log n), but the actual insertion
takes O(n).  With a deck of cards, you can perform the insertion in
O(1).  There is absolutely no point in using quick sort for a deck of
cards.  Only the non-comparison-based sorts (radix sort, bucket sort)
can do better than insertion sort.


-- 
Rainer Deyke - rainerd eldwood.com

Kevin Bealer <kevinbealer gmail.com> writes:

Rainer Deyke Wrote:

 Kevin Bealer wrote:
 I think a lot of people would do even better than insertion with a
 deck of poker cards -- they might group cards by either suit or rank
 (or rank groups) (e.g. "Hmm, I'll make three piles of 1-5, 6-10, and
 J-A"), then order the "buckets", then stick these ordered sets back
 together.  If you think about it, this is a lot like a radix sort or
 a multi-pivot cousin of the quick sort.

 
 When sorting a deck of cards, insertion sort performs in O(n log n), the
 same as the best-case performance of a quick sort.  When sorting arrays,
 you can find the insertion point in O(log n), but the actual insertion
 takes O(n).  With a deck of cards, you can perform the insertion in
 O(1).  There is absolutely no point in using quick sort for a deck of
 cards.  Only the non-comparison-based sorts (radix sort, bucket sort)
 can do better than insertion sort.
 
 
 -- 
 Rainer Deyke - rainerd eldwood.com

Right, if you mean strictly sorting a physical deck of cards by hand. 
Insertion sort isn't efficient in a computer because you need to find the
insertion point quickly and insert quickly to keep the efficiency, but no data
structure can really do both quickly.  For linked lists, insert is quick (O(1))
but find is slow (O(n/2)); for arrays, find is quick (assuming you use binary
search, O(ln n)) but insert is slow (O(n)).  Either choice sticks you with a
slow operation.

Kevin

justme <justme somewhere.net> writes:

Denis Koroskin Wrote:

 On Tue, 29 Dec 2009 21:36:25 +0300, justme <justme somewhere.net> wrote:
 
 Nekuromento Wrote:

 Simen kjaeraas Wrote:

 Kevin Bealer <kevinbealer gmail.com> wrote:

 I'm curious if the multi-pivot quicksort (I think everyone gets  


 what I
 mean by this?  Divide by more than one pivot on each pass?  I can  


 give
 details if you like ...) has been tried out much.  It seems like it  


 must
 have been, but it also seems like something that would have
 cache-awareness advantages that would not show up in the simplified
 comparison-counting way of thinking about efficiency.

 I've heard of two-pivot quicksort, but can't remember where.

 --
 Simen

 Some information about dual pivot quicksort:

 http://iaroslavski.narod.ru/quicksort/DualPivotQuicksort.pdf

 http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

 Looks awesome? But the proof is too academical for my taste. Why can't D  
 implement a three-pivot quicksort and beat Java? What does myarray.sort  
 in D use now?

 
 http://www.dsource.org/projects/druntime/browser/trunk/src/rt/qsort.d

I can't really read that code - apparently the author has not ever read the
Clean code book (http://www.amazon.com/Clean-Code-Handbook-Software-Craftsman
hip/dp/0132350882). To me it looks like it uses insertion sort for small arrays
(< 8 elements) and single-pivot quicksort for larger ones.