developing algorithms
practicing programming
benchmarking code
pursuing efficiency
discovering algorithms
teaching programming
documenting code
pursuing elegance
Consider the two lists above. What distinguishes all the items of list B from all the items of list A? Your answer may be different from mine; what I had in mind was, for lack of a better term, softness. Most of us, I think, would describe the B items as softer, or less rigorous, than the A items. The items in list A have to do with mathematics, logic, and problem solving. The items in list B have to do with psychology, pedagogy, and taste.
Lots of books and articles have been written about A list topics, and most of them take a mathematical, logical, or problem-solving approach. A number of B list books and articles have been written, too, and some of them are excellent -- Polya's books, How to Solve It and Mathematical Discovery, for example.
What we rarely see are books on B list topics that approach their subject matter from a rigorous mathematical or logical or problem-solving perspective. I've found one. It's called On the Shape of Mathematical Arguments, but I think it should be called The Programmer Over Your Shoulder.
The digression which follows will explain why.
I've long thought that there should be a software developer's version of The Reader Over Your Shoulder, a gutsy book by Robert Graves and Alan Hodges for writers and editors. It's gutsy in two ways. In the first half of the book, Graves and Hodges have the courage to lay down a list of principles to which good writing should adhere, and it is a long and explicit list. Many other pedagogues of writing have set down lists of basic writing principles, but the principles are usually vague, and when they aren't they are often wrong. Graves and Hodges manage to be precise and correct at the same time. This is impressive not only as an achievement, but also as a gutsy move, because an awful lot of writers would prefer not to believe that there are that many rigorous rules of good writing. It's art, and they'd like to keep it that way.
(I hope it's clear that this digression is not wholly irrelevant to the process of software development and to the mental processes of some software developers.)
Back to the digression: The second half of The Reader Over Your Shoulder is more audacious. In it, Graves and Hodges present what they call "examinations" and "fair copies." They reprint short passages from known writers such as H.G. Wells, George Bernard Shaw, and Winston Churchill. Each passage looks as it did on original publication, except for the intrusion of dozens of superscripted number and letters. These refer to the pointed and often funny footnotes in which Graves and Hodges detail the writing errors committed by the famous author. Then Graves and Hodges rewrite the passage in good English.
As I say, gutsy. It's an old book; a lot of these authors were alive when it was written.
I was so taken with The Reader Over Your Shoulder that I included a chapter titled "The Programmer over your Shoulder" in my HyperTalk book. (Yes, this is a Personal Aside within a Digression. Only expert writers should attempt such a tricky maneuver.) My chapter didn't live up to its title. The point I was trying to make with the title was that HyperCard gave HyperTalk scripters an unprecedented opportunity to study other scripters' code and critique it, because there was a lot of it around and because HyperCard retained the source code in its stacks, not that I had actually done an examination and fair copy on professional programmers' work.
Antonetta van Gasteren has done just that.
Or something very much like it. (Digression over, man.) In On the Shape of Mathematical Arguments, van Gasteren, a colleague of Edsger Dijkstra, doesn't take on programmers so much as algorists. She examines and fa~-copies several published algorithms and proofs, making their authors look a little foolish.
The logic behind her book's title, incidentally, is that she thinks the term mathematical argument covers a ~~~ Everything from formal mathematical proofs through the expression of algorithms for publication and the writing of readable and maintainable code, to the writing of documentation and teaching of programming, computer science, and mathematics in textbooks and lectures. The intriguing thing, at least if you buy Dijkstra's argument in the Foreword, is that all these things do fit together, precisely because of ~~~ rigorous approach she has taken to the shape of mathematical arguments. Design and presentation emerge as two sides of the same coin. Dijkstra says, because in this united setting, the issues involved are purely technical ~~~ and have nothing to do with in~ or taste.
Here's how van Gasteren puts ~...many hold the opinion that mathematical and expositional style are purely (or at best largely) a matter of personal taste. Admittedly, there is no such thing as the best proof or the rule of thumb that always works, but what I hope to show is the existence of a variety of technical criteria by which one argument can be shown to be objectively less streamlined than another.... It has turned out that a lot can be said about mathematical arguments in general that is independent of the particular area of mathematics that the argument comes from.
Just as with Graves and Hodges's book, van Gasteren's critiques of published algorithms and proofs takes up only half her book, the other half being devoted to laying out objective principles for the presentation of algorithms and other mathematical arguments. Her examinations and fair copies are there to exemplify her principles.
Here's an example of how she recasts a mathematical argument. The following is a typical statement of a particular maximization problem, as she paraphrases it from the literature.
Given an ascending sequence ai, 0<=i<N, of natural numbers and a sequence bi of natural numbers, we are requested to maximize (i: 0<=i<N: ai *bp(i)), where p ranges over the permutations of i: 0<=i<N.
The immediate question that occurs to anyone reading this is, "Why would I want to maximize that?" Tempus fugit. It would occur to anyone but a mathematician, at least.
The problem is a mystery, and it need not be; the trouble with the problem as stated is that it isn't really asking the question that it wants to ask.
What the problem is really after does not depend on the order of the bi, but because the statement of the problem is unfortunately written in terms of sequences, we have to deal with order. This is an error of overspecificity, and we can see the consequences of it. In order to undo the overspecificity, we have to unsequence the bi by permuting their subscripts. That's why we have this p ranging over permutations of subscripts. A problem that has nothing to do with permutations gets permutations slipped into its formulation in order to undo the damage caused by introducing sequences where order is not important, and the result is a mess.
In fact, one group of authors (mathematicians Hardy, Littlewood, and Polya) discuss this very problem as an example of a problem in rearrangements, apparently deluded by their own notation into thinking that the problem is some other problem than the problem it is, which van Gasteren gently ridicules.
She dumps sequences entirely in favor of bags -- unordered collections -- of natural numbers, and the real problem becomes much clearer. Here's the problem expressed without sequences:
Match up pairs of natural numbers from two bags, so as to maximize a simple function. The function is computed by multiplying together the two numbers in each pair, and summing.
That's my version of van Gasteren's statement of the problem, and I've cheated, of course. It's not at all rigorous. But it does state a problem one can imagine running into in real (programming) life, and you can tell what it's about. It's obviously not about sequences or permutations. The van Gasteren version is rigorous, and it still has the virtues she's championing:
...consider couplings, i.e., one-to-one correspondences, between two equally sized finite bags of natural numbers. Hence, a coupling can be considered a bag of -- ordered -- pairs of numbers, the subbags of which are as usual called its sub-couplings. The value of a coupling is defined recursively by - the value of an empty coupling is 0; the value of a one-element coupling is the product of the members in the single pair; the value of a nonempty coupling is the value of one element + the value of the remaining sub-coupling.
The problem is to construct a coupling with maximum value.
This is longer than the statement of the problem in terms of sequences and permutations, but if you are familiar with the terminology and with the format of recursive definitions, this statement of the problem is very clear. Some of its bulk is devoted to introducing the terminology of bags and couplings, and some comes from using words that represent concepts rather than symbols that represent nonce variables. There are no symbols at all here except the numeral 0.
Not introducing names that you don't need is one of van Gasteren's principles. The original formulation of the problem introduced names for all the elements in the sequences and consequently for the lengths of the sequences and for the permutation. We don't need any of these names, nor do we care about the things that they name.
By not introducing names for things that don't matter, van Gasteren forces herself to come up with a formulation for the thing she's trying to maximize, and this in turn leads her to a simple recursive construction for the maximum.
Since, in this problem, van Gasteren's goal is to develop a proof rather than an algorithm, I won't spell out further details. Her proof, though, does turn out to be short and simple, and proofs of this problem are generally messy.
Another principle demonstrated in this problem is the principle of maintaining symmetry. The original statement of the problem speaks of an ascending sequence a and a sequence b. In fact, the problem is symmetric in the two collections of numbers, but this formulation masks that symmetry. It is van Gasteren's contention that breaking symmetry is bad, and that maintaining symmetry can lead to deeper insights into problems and to simpler solutions.
A very simple demonstration of this uses a game involving bit strings. The problem is to prove that the game terminates. In this game, a finite-length bit string is repeatedly transformed as follows:
00 --> 01 11 --> 10,
wherever in the string and for as long as such transformations are possible.
There are two cases here, but building a solution around the two cases overlooks the symmetry in the problem. The approach van Gasteren recommends is to define x as a pair of matching adjacent bits and y as a pair of nonmatching adjacent bits. Then the game becomes
x --> y,
and the argument for termination is simple: The leftmost bit does not change, and every x is eventually turned into a y.
The key to the approach is the recognition and exploitation of the problem's symmetry in 0 and 1.
Choosing what to name and what not to name and exploiting symmetries in problems are two of the areas van Gasteren delves into. Others include: avoiding proof by cases, the exploitation of equivalence, degree of detail in arguments, and linearization of arguments. Here are some of her principles regarding naming:
Name as little as possible. The arbitrary identifier that is used only once is easy to spot, but still occurs in mathematical arguments regularly. Names used more than once can often be entirely unnecessary: In triangle ABC, the bisectors of the angles A, B, and C respectively are concurrent. That can be rewritten: In a triangle the angle bisectors are concurrent.
Watch out for the phrase without loss of generality we can choose ... It is a warning that the author is about to introduce an overspecific nomenclature that will cover up symmetries in the problem.
Name everything that needs a name. The warning sign here is the repetition of long or similar expressions. If you really need the expression, then it probably needs a name.
Name appropriately. Some objects have internal structure and some don't. Some arguments depend on the internal structure of some objects, and some don't. Don't use a name that emphasizes the internal structure of an object if you don't need that internal structure in the argument.
Name the right thing. If it's the function or its value that you're talking about, rather than the application of the function to its argument or parameter, use f instead of f(x). If you're deriving an algorithm for computing the coordinates of a pixel on the screen and you're derivation is full of expressions like (X-XO) and (Y-YO), you're probably naming the wrong thing. Change coordinate systems, define X to be (x+XO) and Y to be (y+YO), and you can replace all the (X-XO)s and (Y-YO)s with x's and y's.
One more naming topic: van Gasteren discusses symmetry-preserving and symmetry-masking terminology, and presents the example of the binomial coefficient. A lot of space in mathematics books is taken up with presenting identities involving binomial coefficients. She thinks that a symmetry-preserving notation would eliminate the need for a lot of those identities. She points out that
[n] [k]is a function of n, k, and n-k, and is symmetric in k and n-k. The conventional notation obfuscates the symmetry, and the fact that
[n] = [ n ] [k] [k-1]has to be presented as a theorem. She suggests using some such notation as P.i.j, in which i and j stand in the place of k and n-k in the conventional formulation above. This reflects, as well as a left-to-right writing system can, the symmetry between i and j, and it cuts a wide swath through those long lists of binomial identities. It also brings an interesting symmetry into some of the identities it leaves behind.
I have focused on van Gasteren's naming principles here, but she has a lot to say about symmetry, too, and about the other topics mentioned. It's a readable book, with some ideas definitely worth considering. It was published by Springer-Verlag in 1990.
A note on van Gasteren and computer science. Although van Gasteren more often speaks of proofs than of algorithms, her work was motivated more by the needs of computer science than of mathematics, "... the explorations reported here," she says, "have been inspired by computing's needs and challenges...."
That's interesting, since the advent of computers has brought into mathematics a new proof technique that van Gasteren probably hates: the zillion-case proof, as employed in solving the four-color problem. You know, the approach in which a problem is broken down into a huge number of special cases and these are cranked through via computer, and you end up knowing what but having no idea why.
Copyright © 1991, Dr. Dobb's Journal