August 3rd, 2004

Splinter: Sensei

Programming Musings

I was thinking back this morning, I don't know why, through some of my early programming experiences. One interesting lesson I thought I'd repeat here, in hopes that people (non-programmers, too) might find it interesting.

Way back ('91), my high school programming teacher (Dave Wisler) held up a pocket calculator in front of the class. This was one of your common freebie-four-function jobs. He posed the interesting question, "How do you know that, when you enter any two numbers you choose and hit x, it will multiply them correctly?"

Obviously, the engineers who made the calculator didn't test every possible pair of numbers. Instead, they tested the algorithm by which multiplication was performed. They probably tested only a small subset of possible multiplicands, but selected them in such a way that they fully tested the multiplication implementation in their hardware.

Thus, verification relies on checking the algorithm not the output. [1]

But the calculator's version of multiplication is also flawed. If you multiply 1,111,111 by 1,111,111 you will not get 1,234,567,654,321 (which is pretty nifty, numerically). You'll probably get 0 or "E" since you've exceeded the number of digits supported by the calculator.

This isn't terribly surprising, since we're all used to this. But the general principle it hints at is interesting and too-often overlooked by programmers. Did this multiplication fail? Yes. Did the calculator fail? No.

We simply ran up against the limits of the calculator's design. It presents to us an abstraction of mathmatical multiplication, while it implements a limited model of it using bits and adders. How the calculator works is encapsulated, yet the limitations of its use depends on this architecture. (In this physical example, we also have the clue of how many digits are in the LED display; I could present other less intuitive examples which don't have such clues.) So, to understand the limits, you have to attain some knowledge of the calculator's design.

Thus, encapsulation breaks down as you approach the limits of the system. Perfect abstractions (despite what software architects like to tell you) are rare. [2]

[1] As always, trivial cases do exist, but they are rarely interesting. Verification, BTW, is now about half of my job.
[2] Joel Spolsky wrote an excellent tech article on this Leaky Abstraction problem.
  • Current Music
    Carbon Leaf - The Boxer