Follow Slashdot stories on Twitter


Forgot your password?
DEAL: For $25 - Add A Second Phone Number To Your Smartphone for life! Use promo code SLASHDOT25. Also, Slashdot's Facebook page has a chat bot now. Message it for stories and more. Check out the new SourceForge HTML5 Internet speed test! ×

Comment Re:Might be a mistake but not where Rob is pointin (Score 1) 436

If you define correctness as "producing the desired results on one particular version of one particular platform", then you have a recipe for non-robust code that won't survive in the real world.

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.

Damn, I've been wasting my time. Now I know you didn't properly read the article. He includes the test programs he used. ...
Not worth responding to, just reinforces that you never looked at the source code

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.

Conference proceedings don't count for much. I can't see any evidence that you know anything about devloping robust programs. Not that I'd expect you to, it is quite a different game to developing verification software anyway (although if the verification software itself needs tp be robust, then we have a problem).

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.

Comment Re:Might be a mistake but not where Rob is pointin (Score 1) 436

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?

Comment Re:Might be a mistake but not where Rob is pointin (Score 1) 436

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.

Comment Re:Might be a mistake but not where Rob is pointin (Score 1) 436

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.

Comment Re:Might be a mistake but not where Rob is pointin (Score 1) 436

If you want to analyze the behavior of a specific implementation of an algorithm given input that violates the preconditions, then lookup the source code for your javascript interpreter. That may be a fun exercise to do, if you are bored, but it isn't very illuminating unless you want to understand why browser X produced that specific distribution.

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

Comment Re:Might be a mistake but not where Rob is pointin (Score 1) 436

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.

Comment Re:Might be a mistake but not where Rob is pointin (Score 1) 436

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

Comment Re:Might be a mistake but not where Rob is pointin (Score 1) 436

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

Comment Re:Might be a mistake but not where Rob is pointin (Score 1) 436

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.

Comment Re:Might be a mistake but not where Rob is pointin (Score 1) 436

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 .


Comment Might be a mistake but not where Rob is pointing (Score 1) 436

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


Colliding Particles Can Make Black Holes After All 269

cremeglace writes with this excerpt from ScienceNOW: "You've heard the controversy. Particle physicists predict the world's new highest-energy atom smasher, the Large Hadron Collider (LHC) near Geneva, Switzerland, might create tiny black holes, which they say would be a fantastic discovery. Some doomsayers fear those black holes might gobble up the Earth — physicists say that's impossible — and have petitioned the United Nations to stop the $5.5 billion LHC. Curiously, though, nobody had ever shown that the prevailing theory of gravity, Einstein's theory of general relativity, actually predicts that a black hole can be made this way. Now a computer model shows conclusively for the first time that a particle collision really can make a black hole." That said, they estimate the required energy for creating a black hole this way to be roughly "a quintillion times higher than the LHC's maximum"; though if one of the theories requiring compact extra dimensions is true, the energy could be lower.

Submission + - Climate change cover-up? You better believe it ( 1

jamie writes: "Was Sen. James Inhofe right when he declared 2009 the year of the climate contrarian? A slew of emails stolen from the University of East Anglia's Climatic Research Unit highlight definite character flaws among some climate scientists, [but] sadly for the potential fate of human civilization, rumors of the demise of climate change have been much exaggerated. ...the opposition here is not grounded in any robust scientific theory or alternative hypotheses (all of those, in their time, have been shot down and nothing new has been offered in years)... There is, in fact, a climate conspiracy. It just happens to be one launched by the fossil fuel industry to obscure the truth about climate change and delay any action."

Submission + - Bozeman, MT speaks up, city at a loss (

indrora writes: "Yesterday, the city of Bozeman, Montana decided to put into effect the ridiculous bill that made applicants for city jobs to pony up their usernames and passwords on what equivocates to be any website or system they use. The residents baulked at it and began to deluge the city officials building with emails and phone calls in protest. This morning, they held a closed-door hearing to determine what to do. They have not however said anything about what the result was (granted, they will have to soon, because of the Open Meetings Act). The local news station held a vote; the results? Astonishingly un-astonishing:

As of 10 a.m. 6,454 people had voted in a poll on asking "What do you think of the City of Bozeman requiring job applicants to provide social network site login and password information?" So 6,347 people have voted "I'm against it — It's an invasion of privacy," 62 people have voted "I'm for it — It's important for the City to judge the applicant's character," and 45 people have said they don't care either way.

The same local news station has a consistent stream of updates that those interested can take a look at."

Slashdot Top Deals

Executive ability is deciding quickly and getting somebody else to do the work. -- John G. Pollard