book cover

A Small Matter of Programming
(A Sketch of Column 5 of Programming Pearls)

So far, you've done everything right. You dug deep to define the right problem. You balanced the true requirements with a careful selection of algorithms and data structures. You used the techniques of program verification to write elegant pseudocode that you're pretty sure is correct. How do you incorporate the resulting gem into your big system? All that's left is, well, a small matter of programming.

Programmers are optimists, and they are tempted to take the easy path: code up the function, slip it into the system, and fervently hope that it runs. Sometimes that works. But the other 999 times out of 1000, it leads to disaster: one has to grope around in the huge system to manipulate the little function.

Wise programmers instead build scaffolding to give them easy access to the function. This column is devoted to implementing the binary search described in pseudocode in the last column as a trustworthy C function. (The code would be very similar in C++ or Java, and the approach works for most other languages.) Once we have the code, we'll probe it with scaffolding, then move on to test it more thoroughly and conduct experiments on its running time. For a tiny function, our path is long. The result, though, is a program we can trust.

The Rest of the Column


5.1 From Pseudocode to C
5.2 A Test Harness
5.3 The Art of Assertion
5.4 Automated Testing
5.5 Timing
5.6 The Complete Program
5.7 Principles
5.8 Problems
5.9 Further Reading
5.10 Debugging

The code for Column 5 contains code for testing and timing search functions.

Copyright © 1999 Lucent Technologies. All rights reserved. Mon 28 Feb 2000