Beautiful Code: Testing a Binary Search Implementation

The Binary Search algorithm has been around for quite a while. I remember doing an implementation (in Fortran) as part of course work in 1977. Hence it was a surprise to read about it in Joshua Bloch's blog post. I am  pretty sure that what I, and the rest of the course, implemented had the same defect.

Alberto Savola in his essay "Beautiful Tests" in Beautiful Code, quotes Donald Knuth as saying that though the first binary search was published in 1946, it took 12 more years for the first binary search without bugs to be published. However, defective implementations could, and did recur.

All very humbling. To quote Joshua, "The general lesson that I take away from this bug is humility".

Alberto Savola's piece uses the Binary Search program to show how tests should be developed. Here are some topics that I found educative:

• The utility of smoke tests.
• Re-factoring code to improve testability. A side-effect of this is to improve the design and the readability of the program.
• The design of tests to verify that neither a true condition is detected as false nor a false condition detected as true. What in radar theory are called failed detection and false alarm.
• Formulating theories (I think calling them hypotheses, would be more appropriate) of the forms: If A is true then B should be true; If A is not true then B should not be true. 
• Random generation of tests. This is most intriguing. I wonder if genetic algorithms could be used to generate tests.
• The use of helper tests that give an alternate way of checking. These are simple tests whose correctness are easy to verify by visual inspection. For the binary search a test using a linear search is also implemented. The linear search is used to cross check results obtained using the binary search.

A quote from Savola:
"Truly beautiful testing requires a developer to make an effort, think outside the box, explore weird scenarios, look for weaknesses, and try to break things".
(Note 1: The emphasis is mine.
Note 2: A side note: "outside the box", I think, is a more appropriate expression, in such contexts, rather than the more commonly used "out of the box".)

Are Business Models, Values Not Tested?

In a post made some months back, Seth Godin talks of the culture of testing at Netflix. According to Seth, Netflix tests everything, except for three things: their business model, their culture, and the change in business model by switching from postal delivery to online delivery. According to Seth these could not be tested.

Is it really true that these cannot be tested?

It is true that these cannot be tested like DVD cases. (Netflix tested 200 of those before deciding on the design.) Yes, they cannot be tested in-house, on a test-bench. But they are tested - and have to be tested - in the market place. Values too are a result of testing in the market place of life.  And like all testing these too involve time and costs.

All start-ups are based on memes that the founders bring with them. Values are memes. Business models too are memes. Memes like genes, are subject to Darwinian testing.

Netflix's early story gives an idea of the memes that led to the initial business model.

It is, I think, safe to assume that Netflix's values are largely based on what the founders had experienced, and seen, and absorbed, at other companies. These were the result of "testing" in their earlier work life. It is also safe to assume that these values are put to the test every day at Netflix. If the values are practiced they are reinforced, otherwise they mutate, or die.

QA Myths

Deloitte has a very educative document on QA myths.

Incredible!

Watch this video.

Why have a biometric mechanism for preventing access, and then provide a regular lock and key in case the mechanism does not work?

If the biometric device is prone to malfunction (hence the need for a mechanical lock) why incorporate it at all? Why not spend on a better mechanical lock?

Lesson for testing: A system under test should be tested not only for what it is supposed to do (opens and with its key), but also that it does not do what it is not supposed to do (opens by any other means). To write tests for the latter is difficult. It needs knowledge of the implementation. It needs white box tests. It needs reviewers of code - and locks - to check for vulnerablity.

Reminds me of a true story. We had, in one our compilers, an implementation of some tricky optimization. Unfortunately it tripped up more often than it worked. The code had to be disabled. One of the developers was so attached to this clever piece of optimizing that he just could not bring himself to disable it. I suppose some people were attached to the biometric device.