Beautiful Code [128]
Tests that are beautiful because they reveal ways to make code more elegant, maintainable, and testable
In other words, tests that help make code more beautiful. The process of writing tests often helps you realize not only logical problems, but also structural and design issues with your implementation. In this chapter, I demonstrate how, while trying to write tests, I have discovered a way to make my code more robust, readable, and well structured.
Tests that are beautiful for their breadth and depth
Very thorough and exhaustive tests boost the developer's confidence that the code functions as expected, not only in some basic or handpicked cases, but in all cases. This chapter shows how I write and run this category of tests using the concept of test theories.
Because most developers are already familiar with basic testing techniques, such as smoke testing and boundary testing, I will spend most of the time on highly effective types of tests and testing techniques that are seldom discussed and rarely practiced.
7.1. That Pesky Binary Search
To demonstrate various testing techniques while keeping this chapter reasonably short, I need an example that's simple to describe and that can be implemented in a few lines of code. At the same time, the example must be juicy enough to provide some interesting testing challenges. Ideally, this example should have a long history of buggy implementations, demonstrating the need for thorough testing. And, last but not least, it would be great if this example itself could be considered beautiful code.
It's hard to talk about beautiful code without thinking about Jon Bentley's classic book Programming Pearls (Addison-Wesley). As I was rereading the book, I hit the beautiful code example I was looking for: a binary search.
As a quick refresher, a binary search is a simple and effective algorithm (but, as we'll see, tricky to implement correctly) to determine whether a presorted array of numbers x[0..n-1] contains a target element t. If the array contains t, the program returns its position in the array; otherwise, it returns -1.
Here's how Jon Bentley described the algorithm to the students:
Binary search solves the problem by keeping track of the range within the array that holds t (if t is anywhere in the array). Initially, the range is the entire array. The range is shrunk by comparing its middle element to t and discarding half the range. The process continues until t is discovered in the array or until the range in which it must lie is known to be empty.
He adds:
Most programmers think that with the above description in hand, writing the code is easy. They are wrong. The only way to believe this is by putting down this column right now and writing the code yourself. Try it.
I second Bentley's suggestion. If you have never implemented binary search, or haven't done so in a few years, I suggest you try that yourself before going forward; it will give you greater appreciation for what follows.
Binary search is a great example because it's so simple and yet it's so easy to implement incorrectly. In Programming Pearls, Jon Bentley shares how, over the years, he asked hundreds of professional programmers to implement binary search after providing them with a description of the basic algorithm. He gave them a very generous two hours to write it, and even allowed them to use the high-level language of their choice (including pseudocode). Surprisingly, only about 10 percent of the professional programmers implemented binary search correctly.
More surprisingly, in his Sorting and Searching,[*] Donald Knuth points out that even though the first binary search was published in 1946, it took 12 more years for the first binary search without bugs to be published.
[*]The Art of Computer Programming, Vol. 3: Sorting and Searching, Second Edition, Addison-Wesley, 1998.
But most surprising of all is that even Jon Bentley's official and proven algorithm, which (I must assume) has been