News for hackers. Stuff that matters.
Re:Are you one of the 10% of programmers who can write a bin... by raganwald on Monday April 19, 2010 @02:42PM (#1277504)
To be precise, the post says that only 10% of programmers can write it correctly without testing. I agree that this is an interesting statistic, however the industry has been deprecating implementing an entire algorithm in one go in favour of implementing algorithms incrementally. Were I to write it without testing I would probably write it incrementally and try to perform the testing in my head as I went along. It feels very retrograde to try to write the whole thing out and only then start thinking about off-by-one errors, computer arithmetic issues, and other edge cases.
Re:Are you one of the 10% of programmers who can write a bin... by cschneid on Monday April 19, 2010 @03:11PM (#1277562)
It feels like a totally made up problem:

"Here's a binary search algo description, implement it perfectly without testing".

That's not even close to how developers work, and he amplifies the disconnect with the real world by choosing a problem known for it's boundary and off-by-one risks.

Re:Are you one of the 10% of programmers who can write a bin... by DLarsen on Monday April 19, 2010 @03:51PM (#1277656)
While this scenario may not allow developers to work like they normally do, I think the author's point is that a simple binary search isn't that complicated. A decent dev should still be able to a pretty good job despite those artificial constraints.
Re:Are you one of the 10% of programmers who can write a bin... by brazzy on Monday April 19, 2010 @04:19PM (#1277735)
And the author is simply wrong about his point (if that is indeed his point). A binary search is that complicated. It just doesn't look like it until you've considered all the possible edge cases, and chances are that most "decent devs" will miss some and be part of the 90%.
Re:Are you one of the 10% of programmers who can write a bin... by dkarl on Monday April 19, 2010 @05:36PM (#1277915)
It isn't complicated compared to the convoluted stuff that programmers code to implement business "logic." The dirty secret of software development, however, is that 90% of industrial software developers can't handle abstraction at all and rely heavily on domain knowledge when coding anything. Programmers handle the cases that are normal for the problem domain, and QA tests the cases that are unusual in the domain context (and makes the programmer fix them.)

The code will behave incorrectly on some edge cases, but if the developers and QA have covered the problem domain pretty well, it won't matter. First, most of the edge cases will never happen. Second, people get angry when software fails for no obvious reason, but they tend to be a lot more forgiving when software fails on inputs that are "freakish" or "wrong" in the domain context. Searching the widget catalog results in "500 Internal server error" when the widget catalog is empty? Well, duh! When should the widget catalog ever be empty?! The search page shows screwy results because someone entered an item with a negative price? Well, duh! Get that stupid item out of the catalog! Instead of thinking like a mathematician or a system designer in order to avoid mistakes, the typical development approach is to think like the customer so you only make mistakes that the customer can sympathize with.

Re:Are you one of the 10% of programmers who can write a bin... by weichi on Monday April 19, 2010 @07:03PM (#1278119)
I think there's a lot of truth here.

I would also point out that for a lot of programming tasks, particularly in a corporate IT environment, "thinking like the customer" can be a good thing: it helps you make sure that you are building something that truly helps the customer do their job.

The risk is that no matter how much "domain experience" you have, the customer has more, and you can fool yourself into thinking that you understand what they need better than they do.

Re:Are you one of the 10% of programmers who can write a bin... by MikeTaylor on Monday April 19, 2010 @05:18PM (#1277877)
Speaking as the author: his point, if any, is more along the lines that if we need a test-as-you-go approach to get something this simple to work, it's no wonder we have problems when we have to implement something that's actually complex.

Also: no amount of test-drivenness can save you from just not grokking the problem (as Peter Norvig's Sudoku solver showed ... er, by counter-example.)

Re:Are you one of the 10% of programmers who can write a bin... by 124816 on Tuesday April 20, 2010 @12:24AM (#1278625)
I'm missing the back story -- tell me more about Peter Norvig's solver?
Re:Are you one of the 10% of programmers who can write a bin... by nicko on Tuesday April 20, 2010 @01:15AM (#1278712)
Re:Are you one of the 10% of programmers who can write a bin... by dkarl on Monday April 19, 2010 @06:46PM (#1278080)
A binary search is that complicated. It just doesn't look like it until you've considered all the possible edge cases

The fact that it's tractable to rigorously consider all the edge cases means it is ridiculously simple compared to common real-world programming tasks.

Re:Are you one of the 10% of programmers who can write a bin... by tdmackey on Monday April 19, 2010 @06:39PM (#1278064)
If you read Bentley's original work that the article is based on then the point is exactly that even the most seemingly simple tasks like implementing a binary search are incredibly difficult if not near impossible to get "right."
Re:Are you one of the 10% of programmers who can write a bin... by beagle3 on Monday April 19, 2010 @05:35PM (#1277914)
If binary search is complicated, what is _simple_ by your standards?
Re:Are you one of the 10% of programmers who can write a bin... by DougBTX on Monday April 19, 2010 @06:10PM (#1278006)
FizzBuzz?
Re:Are you one of the 10% of programmers who can write a bin... by WildUtah on Monday April 19, 2010 @09:29PM (#1278352)
Which only 50% of us can solve correctly the first time?
Re:Are you one of the 10% of programmers who can write a bin... by pavel_lishin on Monday April 19, 2010 @05:21PM (#1277886)
> "Here's a description, implement it perfectly without testing". > That's not even close to how developers work

You'd be surprised. Also, terrified.

Re:Are you one of the 10% of programmers who can write a bin... by ams6110 on Monday April 19, 2010 @10:56PM (#1278487)
My first job after college (1992) was with Andersen Consulting. All new staff consultants went to a "boot camp" to learn how to program (they hired many people who did not have a programming background, as well as some who did). They emphasized "desk checking" as part of the development process (for this reason: submitting a compile job on the mainframe might have a turnaround time of hours).

So, one of the assignments was to write a program, and desk check it until you were confident that it would compile and run correctly on the first try. It was a one-chance, pass/fail assignment: it either worked, or there was a compile or runtime error.

Re:Are you one of the 10% of programmers who can write a bin... by count on Tuesday April 20, 2010 @12:03AM (#1278593)
Another reason is that by desk checking, you spend substantially more time working on the program - which means more billable time as a consultant.
Re:Are you one of the 10% of programmers who can write a bin... by joe_the_user on Monday April 19, 2010 @07:49PM (#1278188)
Maybe it's not "real world" to have to implement a simple but serious algorithm in a few lines.

Maybe in the "real world", the programming is just the simple gluing together of hard stuff like databases, compilers and operating system, since they have already been written. Once you have some bullet-proof method, it really is better to just be a consumer of it.

There is still some hard stuff that needs to be done, though. I suspect that to do "the hard stuff" you need to be able to implement simple-but-serious algorithms in a few lines. This makes your overall code smaller, more readable and allows optimization for the particular cases you're working with.

Re:Are you one of the 10% of programmers who can write a bin... by abstractbill on Monday April 19, 2010 @07:56PM (#1278207)
Maybe it's not "real world" to have to implement a simple but serious algorithm in a few lines.

I don't think the parent was objecting to implementing a simple but serious algorithm in a few lines, but to doing so without performing any testing at all.

There is still some hard stuff that needs to be done, though.

Yes, and I'm pretty sure the people doing that hard stuff do some testing ;)

Re:Are you one of the 10% of programmers who can write a bin... by FutureNerd on Monday April 19, 2010 @11:40PM (#1278563)
Going back to Bentley, the point was not to code without testing but whether you could think through a small piece of code <i>before</i> testing.

raganwald says, "It feels very retrograde to try to write the whole thing out and only then start thinking about [...] edge cases." Nobody said you had to write it before thinking about edge cases! The idea is to think about the edge cases and incorporate that thinking into the code before you actually test the code--whether you can be--actually whether you know the steps to be--that thorough in your head.

One way to think about edge cases, of course, is to write the test code before the function. But after writing the tests, try writing the function correctly before testing it.

Of course, one of the potential bugs in binary search doesn't occur to people before they write and then try it. And, that bug is hard to test for, ahem, don't want to explain why.

Re:Are you one of the 10% of programmers who can write a bin... by RiderOfGiraffes on Monday April 19, 2010 @03:07PM (#1277556)
Of course you shouldn't just write the whole thing out and then start to think about the errors. And these days most code is developed incrementally.

However, not all code is developed incrementally, testing miniscule details on the way. Some code is written perhaps 20 lines at a time before testing. Binary search is only about 20 lines, my implementation is significantly less.

So there are cases where 20 lines are written, then tested. The thought experiment here is to assume that this is one of those cases, one instance of which there are probably 5 or 10 in a moderate sized project. Places where people perhaps got a little lazy, it was obviously easy, or didn't bother following the full TDD.

And as I say in a comment elsewhere, only 1 in 3 of the people who tested passed my test suite.

Your point is valid, but misses some of the point of the article, and the exercise.

Re:Are you one of the 10% of programmers who can write a bin... by hammerdr on Monday April 19, 2010 @03:19PM (#1277584)
I think that writing a binary search algorithm without tests is evidence of a poor programmer (or, at the very least, poor programming practice; there are talented programmers out there that can just sling code). This is a difficult and, as the sibling comment noted, error prone algorithm.

These types of problems are poster children for TDD and testing. There is under 20 lines of code but several ways to make logical errors. If we test drive the code, we can ensure that the algorithm performs exactly how we want it to.

Re:Are you one of the 10% of programmers who can write a bin... by queensnake on Monday April 19, 2010 @08:47PM (#1278279)
I hate to break it to you but you'll fail interviews at the better companies with that attitude(1). No matter much support your work methods give you, you have to be able to hold and work with a few moving parts in your head at once, correctly.

(1) Don't ask me how I know :)

Re:Are you one of the 10% of programmers who can write a bin... by hammerdr on Tuesday April 20, 2010 @11:18PM (#1281302)
In my experience, this isn't true.

In fact, my 'attitude' of approaching work like a craftsman has served me very well in job interviews (even landing me opportunities at pie-in-the-sky type of jobs).

Re:Are you one of the 10% of programmers who can write a bin... by raganwald on Monday April 19, 2010 @03:14PM (#1277571)
Well I wouldn't say the point of the exercise and my point are entirely disconnected, perhaps the point of the exercise is to remind people that the size of their increments is really driven by the complexity of the test suite and not by the expected length of the code.

It's an idea I explored very poorly in an old blog post:

http://github.com/raganwald/homoiconic/blob/master/2009-06-0...

Re:Are you one of the 10% of programmers who can write a bin... by jheriko on Monday April 19, 2010 @04:00PM (#1277675)
"however the industry has been deprecating implementing an entire algorithm in one go in favour of implementing algorithms incrementally"

I dunno - for something as simple as a binary search there is nothing to increment. Maybe I misunderstand and you meant "incremental" as in where you write a whole algorithm, make sure it works, and then improve it (optimise/remove bugs/add features - not finish it)?

"It feels very retrograde to try to write the whole thing out and only then start thinking about off-by-one errors, computer arithmetic issues, and other edge cases."

Yeah... that is backwards. You should think of these things in advance, and if you have experience, you might have had to deal with them already. Binary search is especially simple - if you get the algorithm wrong I'm inclined to believe you are inexperienced, but if you just make typos and such, well... I'd expect that from anyone.

Then again all the rapid application development options today mean that anyone can use a binary search without writing one... or even write complete software with no real understanding of how it works.

Maybe I'm just out of date?

Re:Are you one of the 10% of programmers who can write a bin... by raganwald on Monday April 19, 2010 @04:09PM (#1277698)
> for something as simple as a binary search there is nothing to increment. Maybe I misunderstand and you meant "incremental" as in where you write a whole algorithm, make sure it works, and then improve it (optimise/remove bugs/add features - not finish it)?

I strongly suspect--and I am not being sarcastic or falsely modest--that I am not up to scratch as far as programming is concerned. I almost always get stuff like this wrong when I implement it. My code breaks for empty lists, or with just one element, or lists with an odd number of elements, or something else I can't imagine.

Exposure to recursive algorithms has taught me to build this kind of thing up from simple cases like an empty list or a list with one element. So yes, I really would write a version that works for the empty list, a version that works for either the empty list or just one element, and go from there.

Re:Are you one of the 10% of programmers who can write a bin... by eru on Monday April 19, 2010 @04:59PM (#1277835)
You'll love "How to Design Programs" (http://www.htdp.org/), they put a lot of emphasis on structural recursion.