Issue #04: Programming, Art Or Science?

The Art Of “The Art Of Computer Programming”

A quote from the cover of Volume One of Professor Donald Knuth’s Magnum Opus, The Art of Computer Programming (3rd edition):

If you think you’re a really good programmer… read (Knuth’s) Art of Computer Programming… You should definitely send me a résumé if you can read the whole thing.

“Me” here refers to the author of the quote, Bill Gates. This book (TAOCP hereafter) is a defining work in our field. The reason Gates would like your résumé is that the reason most of us bought our copies in the 1990s was twofold:

  1. We wanted to look like the sort of people who had read TAOCP; and
  2. They were handy for raising heavy Cathode Ray Tube monitors on our desks.

Gotta Catch ’em All

Bill Gates has never received a résumé from anyone who read all of TAOCP. There’s an urban legend (now sadly debunked) that Steve Jobs told Knuth he had “read all of his books”, to which Knuth replied “you are full of crap”.

While that tale is not true, nobody including Steve Jobs can say that they have read all of TAOCP. The reason is simple: it isn’t finished yet. I foolishly bought my copy of volumes 1-4A while abroad at Apple’s WorldWide Developer Conference, and had to travel back to the UK with it in my case. There are six fascicles available that comprise volumes 4A-4B. The predicted scope includes more sub-volumes 4, then volumes 5-7.

As all of volumes 4B-7 are somewhere between partially and completely incomplete, nobody has read all of TAOCP, Donald Ervin Knuth included. Therefore Gates has never received such a résumé.

The Art Of Yak Shaving

Some of the reason it has taken so long to produce the seven volumes is that Knuth is the master, maybe even the patron saint, of yak shaving.

In the Jargon File, Yak Shaving is a task you complete so that you can complete a task so that…

While reviewing an updated edition of TAOCP, Knuth saw that the pages were decidedly lower quality than the earlier edition. His printers had changed from a hot metal typesetting process to a computerised process to lay out text on the page, and it did not produce good results. Knuth felt that TAOCP needed to look and feel like a higher quality book.

He stopped working directly on TAOCP to create TeX, a text layout system based on virtual boxes and glue. To make families of related-looking fonts, so that italic text rendered in TeX looks similar to fixed-width typewriter text, roman text and other styles, he created METAFONT, a programming language for generating fonts from descriptions.

Meanwhile, he wanted to be able to describe his programs both for the machine to run, and for people to understand. So Knuth made Web, a Literate Programming tool that could “tangle” source into a Pascal program for the computer and “weave” it into a TeX document for a reader.

So Web allowed him to make TeX and METAFONT (and the five-volume Computers and Typesetting collection). TeX and METAFONT allowed Knuth to get back to TAOCP.

Sir MMIX-a-Lot

Meanwhile, the world of computing had not stood still. The original volumes 1-4A described algorithms implemented in an assembly language called MIXAL, targeting the hypothetical MIX computer. MIX contains features no longer found in popular computer architectures. Memory can be accessed as six-bit bytes, either in binary or decimal. Bytes are grouped into five-byte words, which each has an external sign bit. Dedicated device I/O instructions provide access to paper and magnetic tapes, a card punch, a card reader, and similar technology.

To reflect more recent advances in computing hardware, Knuth produced the MMIX architecture in collaboration with designers of the MIPS (John L. Hennessy) and Alpha (Richard L. Sites) CPUs. MMIX is a 64-bit RISC architecture with lots of general-purpose registers, and IEEE 754 floating-point arithmetic. MMIX was published in Volume 1 Fascicle 1 of TAOCP in 2005. Most of the rest of the book still uses MIXAL source code. But here we encounter another hairy yak: will Knuth press ahead with writing volumes 4B-7, or will he re-implement the volumes 1-4A algorithms in MMIXAL?

Further yaks: should Knuth move on to volume 4B or 5, he will find things that should have been in volumes 1-3 but did not exist when they were written. He is one man, trying to capture developments (the state of The Art, even) of a whole industry of commercial practitioners and academics. Like Lewis Carroll’s red queen, he must run in order to stand still.

So Is It Art?

TAOCP is definitely a work of art. Knuth has taken a great deal of care over the content, its preparation and its presentation. He continues to do so. The descriptions of algorithms in the book are clear: I have re-implemented a few of the algorithms where application performance required it. I found the discussions easy to understand and follow, so that rather than translate the MIXAL into C or some other language I was able to write my own implementation that followed the text.

There are many books that have been more useful in my career: NeXT’s developer documentation, Larry Wall’s “camel book”, and Aaron Hillegass’s Cocoa Programming for Mac OS X have all taught me more immediately useful knowledge on making software. But TAOCP occupies a special place as a book that is worth reading for the pleasure of reading it, a rare creature in the realm of software documentation.

My shelf of such books would be fairly small. Alongside TAOCP would be found The Structure and Interpretation of Computer Programs, Numerical Recipes, The Art of the Metaobject Protocol and Object-Oriented Software Construction. Maybe I could identify a handful of others. Perhaps others (including you?) will suggest a few more. I do not believe that I will be stretching Vitsoe’s logistics to find shelving for all of the works of art in computing writing.

And Is It Science?

Many would say that TAOCP is indeed a book on science. American Scientist describes it as one of the best monographs on physical science. Knuth has been elected to the National Academy of Sciences and to equivalent bodies in France, the UK, and possibly elsewhere.

Is it sufficient to say “people call this book a science monograph, and say the author is a scientist, therefore this book is about science”? Is computer programming a scientific discipline? For that matter, is computer science a science?

The Origins Of Computer Science

The phrase “computer science” has been used by academics since at least the 1960s (Cambridge University’s 1953 program was in “Numerical Analysis and Automatic Computing”), and was popularised by the Association of Computing Machinery in its curriculum recommendation. In effect this was a political move. “Computer science” can be seen to lend a gravity to the discipline that more abstract words like “Informatics” did not imply.

Uncharitable readers may note that “political science” and “management science” also seem to attach themselves to the intellectual heft of science. However, in the case of computer science, there is some additional support. Computer science is not so much the science of computers but the science of information. Computers themselves are the products of semiconductor physics and electronic engineering.

But computers are not about band gaps or voltage levels. When we use a computer, we do not use it so that we can induce free electrons in lumps of silicon. Computers are tools for information processing. Computers thus are the experimental labs in which information science is performed. Leibniz’s binary logic and Boole’s binary algebra give us language and philosophy with which to consider any problem. Computers are tools to let us express and manipulate those problems.

TAOCP is a book about algorithms in binary logic. It is a book about the applications and characteristics of the philosophy and logic to the real-world situations and problems we are modelling. It is very much about science.

Image credit: author’s own.

Graham is the chief labrarian of The Labrary, where the library and the laboratory intersect. He got hooked on making quality software in front of a NeXT TurboStation Color, and still has a lot to learn.