I think defining correctness as "producing the desired results is pretty reasonable. Sure correct doesn't mean robust, but they are different things and this discussion has been about correctness.

Yeah, I looked at the code. He replaces the sort says the bug is gone, must be a bug in how the sort is used. Sure seems likely but where is the actual bug. If we are going to spend the time giving a case study of a bug I think showing exactly there the bug is and why it is matters. But I suppose reasonable people can disagree.

The main thing this discussion has shown is the existence of different metrics for program quality, i.e. an error and a bad design, one is wrong the other is undesirable but correct (at least for the current program). Both are bad but in different ways and need to be handled using different techniques.

If that is your opinion. But I should note that IBM, Microsoft, Mozilla, etc. spend a fair bit of money to sponsor and send people to these things. So someone apparently thinks these proceedings count for a fair bit (and companies that care a lot about building robust systems).

I'll leave my part at that.

There are lots of dangerous but technically correct programs. In fact almost every program written is ill specified and most likely has methods that are used in ways that they were not initially intended.

As for my example, I agree in a "good" program one would always use it according to the given specifications. Doing anything else is breaking modularity and invites errors when making later changes. If you fail to understand the difference between modularity/abstraction (using the semantics provided by the contracts) and correctness (producing desired results) then I cannot help you.

No what Rob demonstrated was that replacing the call to sort made the error go away. But several things were changed here as well (most notably the random number generation and initial seeding were probably altered substantially). So, while he is right that calling sort to get a purmutation is a bad idea and he is (probably) right that the sort was the problem, this is never actually shown in the article. He just assumes that the bug went away so it must mean that the sort was the problem (but as I showed above this need not be the case).

As for your concern for me, I doubt if my code has appeared on TheDailyWTF, but I do know that I recently had some of my work in the ACM proceedings of "Verification Model Checking and Abstact Interpetation" on modeling the semantics of programs for later verification applications. So, I do know a bit about program correctness and specification. How about you?

You do realize there is a difference between code that is dangerous (but technically correct) and code that is actually buggy. As per my quicksort example. Dangerous, but correct.

You are getting intent and results confused. Calling my quicksort routine with an invalid compare function clearly violates the intent of the contract abstractions but functionally produces the correct results. The same may happen with your sqrt(-1) example, it is a bad idea from a modularity standpoint but may be functionally correct.

If you want to talk about if that is the case for the browser selection, well, I am glad you agree that determining if the implementation of the JS quicksort routine causes the bug (or if it is something else) would be a good idea. Unfortunately the author of the article was happy to jump to premature (although not unreasonable) conclusions.

And don't worry about me being a programmer. My code is quite reliable and in fact I do a lot of work on software reliability and correctness.

Look, I agree with you on mis-using the sort routine. Using a method to do something unintended does not cause bugs, it makes them more likely and is bad form. But without further analysis it is not certain if and why the sort is the source of the bug.

As for your challenge see the first example of quicksort from wikipedia:

--------
function quicksort(array)
    var list less, greater
    if length(array) 1
        return array
    select and remove a pivot value pivot from array
    for each x in array
        if x pivot then append x to less
        else append x to greater
    return concatenate(quicksort(less), pivot, quicksort(greater))
------

Note that this correctly implements quicksort. By induction on length we show the uniform distribution:

length = 1: trival.
length = 2: a 50/50 comparison has a 50% chance of producing either order.
length = k: Each element has a 50% chance of being in less and a 50% chance of greater. By induction we will get permutations of each of these uniformly. Since we have a uniform chance of putting each element in each of these (and pivot is selected uniformly at random) the combination of the three will produce all purmutations with equal probability.

So if you want to argue the effects of possible implementation details then that is fine but that was my point. These implementation details are key to determining what actaully caused the problem (which as shown above may not be the sort at all). The article never addresses these only says the problem must be there, then after changing multiple things the problem isn't.

Yeah that is exactly what I wanted because the article was about why a particular javascript implementation produced a poor distribution for the browser selection screen in the EU browser ballot. That is a specifc bug in a specific implementation.

I can tell you that failure to do array bounds checking before loads/stores will lead to bugs as well. But that does not explain why a specific bug exists. If you want to discuss poor programming practices that is fine but I did not find this a very enlightening way to do it.

And if you run bubble sort, as described in basic algorithms, it will always terminate (regardless of the comparator) since progress is always made via the loop indexing. In fact termination is often not a function of the loop body behavior. One only needs to show that there is an order (which is not infinitely decending/asscending) on some function of the program state in order to ensure termination. For bubble sort this is just the order on the loop index counter (i).

No there is no guarantee and the article does not specify which sorting algorithm is actually used. But any reasonable sorting algorithm should terminate very quickly even with the incorrect comparison function. Which is one of the reasons I found the article annoying, lots of general claims but very little analysis in the end.

I usually don't post much but for some reason the article struck me as designed to have just enough technical content to seem authoritative but that the intent was simply a chance to get in some cheap shots at Microsoft.
 

I agree with your general point. The particular implementation was not good. Violating method contracts leads to bugs. Yes, obviously. But issue was poor distribution in the random numbers. And the author never determined why this was the case. Was it the implementation of quicksort, an issue with seeding when run in a tight test harness, as you mention does it used different sorts for different input sizes, etc?

So yes, we have a program that is poorly written and produces the wrong answer. We also have an article that is poorly written and does not explain why the results are what they are (other than don't violate method contracts, which is good advice but not very enlightening).

Most likely I graduated from a different school but I appreciate that you asked.

You are quite right the formal precondition of the sort method is violated and this implementation is quite sketchy in that respect. However, that does not tell us what the distribution errors are caused by. As Rob is making other strange statements like possible non-termination (which should be impossible in any reasonable quicksort), I am not particularly happy to just believe him without a more careful analysis (e.g. seeding, how the test harness was implemented, pivot selection, etc.).

Yes I am well aware of this, in my post I state a "simple quicksort" algorithm which precludes several of the issues you mention and I discusses the possibility of problems in the pivot selection. But as you will note the article does not discuss any of these issues so we have no idea if it is one of these or not (it just claims it must be the sorting).

So we basically have an article that says I ran a benchmark and I can't explain the results so I'll just make up something that sounds good.

And to follow up after re-reading the article he claims that non-termination is possible. But since in quick-sort each recursive call is to a smaller list (we removed the pivot element otherwise the algorithm has real problems) the sort must always terminate.

Now this might not be a very elegant solution and definitely violates the abstract specifications of a sort routine but the problems pointed out by Rob are not actually the real problems. Way to go slashdot, always making sure articles that slag on Microsoft are factually accurate .

Well unless there is something else going on Rob needs to go back to school too. A simple quicksort algorithm with the comparator replaced with a random choice becomes a recursive random partition of the array. A simple inductive argument shows that this will not produce the unbalanced results he found. So the problem is elsewhere (most likely in the RNG seeding or a bias in the pivot selection, if he is running it in a tight loop and the seed is something like, current second, then the same seed may appear several times).