|
The
Art of Computer Programming - Donald Knuth
|
First
a confession. Although I am putting this book in the "hard to put
down" category, I have merely leafed through the first volume,
without having actually read it. Nor am I likely to do so. This puts
it in the same category as The Complete Works of William Shakespeare
or Gibbon's Decline and Fall of the Roman Empire. Besides, Professor
Knuth is still laboring on Volume 4 of The Art of Computer Programming,
and the completed work is planned to comprise seven volumes.
I may not be alone in praising the book without having read it, however. According to folklore, Steve Jobs (co-founder of Apple Computers) once invited Knuth to give a lecture. Jobs welcomed him thus: "It's a pleasure to meet you, Professor Knuth. I've read all of your books." "You're full of shit", Knuth responded.
Nevertheless, there are good reasons for drawing attention to the book. Its influence in the field of computer programming cannot be overestimated. In one way or another we all benefit from it every day, whether as developers of computer programs or as users. Approximately one million copies have already been printed. Besides, Donald Knuth himself is a fascinating character and a great teacher. Unfortunately, I just missed him at Stanford University, where he was appointed professor of computer science in 1968, one year after I left.
He first became famous as an expert on compilers (programs that convert high-level programs into machine executable code), but his main contribution to computer programming has been to lay the foundation for rigorous analysis of algorithms ("recipes" for things such as sorting and searching data, generating random numbers etc.). Once he impishly warned his readers: "Beware of bugs in the above code; I have only proved it correct, not tried it." He is also famous for writing clear, structured, commented programs, pointing out that "The time I spend on organization is more than made up for in time saved debugging". Programs should be written to be understandable to humans, not just to machines.
|
 |
Knuth is no ivory-tower scientist. He spent ten years of his life developing
and perfecting a computer program for typesetting, TeX. His interest
also extends to the fonts used in publishing. The program is still almost
universally used to lay out and print mathematical texts in magazines
and books. It is also emblematic of his obsession with neatness and
perfection. He offers a money prize to anyone who finds an error in
his program, starting at $ 2.56 (or 28 cents). Most recipients
of his checks are said to frame them on their walls as a badge of honor,
rather than cashing them. Another quirky habit of his is that he names
successive versions of his program by adding decimals from π: 3.14,
3.141, 3.1415 etc.
|
He is also a revered teacher. Happily, some of his disciples have recorded his seminars in the form of detailed notes. They make for fascinating reading, showing how he continuously challenges them (and himself!) by posing intricate problems, highly varied in content and scope. "Here are two encrypted messages, each 256 bytes long. One of them is an English text. The other is a Pascal program. Try to decode them." Or "Produce a machine-aided self portrait". I really recommend reading the notes, they bear witness to a truly Socratic way of teaching gifted students: "If he is indeed wise, he does not bid you enter the house of wisdom, but rather leads you to the threshold of your own mind." (Gibran)
And here is a teaser for the notes taken by a student from Knuth's seminars on "Mathematical Writing":
The Story So Far. Readers will recall that our hero, "Prof" Don, is locked in mortal combat with Scientific American, a journal whose global reach is exceeded only by its editorial hubris. Will Don's definitive Algorithms article reach the world unscathed? Or will it suffer the death of a thousand "improvements" at the hands of a hoard of dyslexic copy-editors? Now Read On . . .
Somewhat unexpectedly, perhaps, he has a strong interest in Christian religion, in a low-key manner. Taking John 3:16 as an inspiration, he has written a book commenting on all verses numbered 3:16 in the Bible, as a sample of the whole book. (When he submitted his manuscript entitled "3:16" to a publisher in Singapore, it came back as "John 3:16". He comments: "Now all these people at football games hold up signs advertising my book!").
What
is it about programming that holds such a powerful attraction to many
of us? Knuth remarks: "My main conclusion after spending ten
years of my life working on the TeX project is that software is hard.
Its harder than anything else Ive ever had to do." Perhaps
that is the explanation. But there is also its property of consisting
of small pieces that can be tested, allowing you to win a small victory
at every step of the way. It is deeply satisfying to "bend the
machine to your will".
I find it interesting that Knuth considers the "art" of programming to be more closely related to the term "artisan" than to "artist". He sees himself as a craftsman more than an artist.
Let me also reminisce about my own dealings with computers:
My first exposure to computer programming came before my first encounter with a computer. In 1961 I took an optional course in "number machines" (siffermaskiner) at the R. Institute of Technology. We learnt to write primitive programs in Algol on paper. Its culmination was when the class was divided into 5 groups, each of which was assigned a problem that would be run on a real computer, an IBM 7090 at the Defense Research Establishment. We marched there at midnight. (The computer was not available to students during office hours, or even in the evening.) All of our programs had been checked by a research assistant. It turned out that three out of our five programs crashed. My group had written a program to print out a formatted table of all prime numbers smaller than 1000. Happily, it worked.
My next brush with a computer came at Stanford in 1966, where I spent a year as a graduate student. Here, I took a crash course in Algol and was shown how to punch my written program on Hollerith cards. A pack of cards was submitted in a pidgeon hole in the computer center, and the printout of the results could be picked up a few hours later. This was the first time that I was able to use a computer (a Burroughs B5500) in my work, such as simulating a rocket flight (the Europa-B rocket) and determining its trajectory (assuming noisy radar data) using a Kalman filter. But I wasted many hours correcting small mistakes, such as having written a comma instead of a period, or an "O" instead of a "0". When the program finally worked, it did so with a vengeance: I got a printout ending with the phrase "Satellite in orbit!" repeated until the built-in 5000 line limit was exceeded... Time pressure and the turnaround delays at the computer center forced us to work odd hours. A friend of mine, who was about to visit the computer center after a happy evening at a local beer place, managed to drop a pack of punched cards on the rainy street, and had a miserable time trying to salvage his work of many days.
After returning to Sweden, I started work at Saab Aircraft Co. Here computers were an essential tool (but I had a colleague who performed Monte Carlo simulations using a desk calculator and a table of random numbers). I became familiar with Saab's internally developed computers D21 and D22. Again, the modus operandi was to submit a job (in this case a punched paper tape) in a pidgeon hole in the computer center. A funny thing happened when my colleague Johnny Andersson pointed out to senior management that all the secrets of Swedish national defense systems lay unprotected in the form of paper tapes in the pidgeon holes. He was issued a personal locked metal box to safeguard his tapes - but all the other tapes lay as unprotected as before!
After moving to Swedish Space Corp. in 1970, I suffered a 10-year period of abstinence from computers. There were some programmable calculators. One was the Olivetti Programma. It could be programmed, but the program must be saved on a magnetic card before the calculator was turned off. A few years later we got a HP-9800 (I forget which model) which could save instructions. I did not work with any of them. Later I bought myself a programmable HP-67 handheld calculator but just used it as a hobby. Around this time I was mightily impressed when a colleague began to develop and run programs on a large computer in downtown Stockholm remotely from his office.
 |
|
When the Commodore 64 became available in 1983, I started playing with it at home. You could find listings of different simple games in magazines and enter them by typing. The language was Basic. (Programming guru Edsger Dijkstra had this opinion of Basic: "It is practically impossible to teach good programming style to students that have had prior exposure to BASIC; as potential programmers they are mentally mutilated beyond hope of regeneration", no doubt referring to the GOTO, PEEK and POKE commands. Knuth's attitude was slightly more permissive, at least with regard to GOTO.)
When we acquired a state-of-the-art Image Analysis System based on an Interdata 8-32 in 1979, my enthusiasm for serious programming was revived. Finally, I had access to a computer with immediate turnaround. (Actually, compilation and linking of a program could take as much as 15 minutes.) I was a bachelor, so there was nothing to prevent me from working late and over weekends. The computer language was Fortran 77, and the software we had to modify and improve was pure "spaghetti code". Still, those were exciting times, as we pioneered the use of satellite images and the use of computers in visualizing data. See details. I also used the Interdata to program an economic model developed by Klas Änggård for the evaluation of different financial scenarios when we set up our daughter company Satellitbild in Kiruna. It was written in Fortran.
During the 1980s we developed small, inexpensive image processing systems (EBBA) to promote the use of satellite data in academia in Sweden. See details. To me it was a revelation when I first saw Borland's Turbo Pascal 3 in action. The first time I compiled a Pascal program on an IBM PC, I thought something had gone wrong. It just seemed too good to be true to have a program compile in the blink of an eye. Gone were the days of submitting a "job" to a computer central and getting the result back several hours later. A simple typo could be discovered and corrected in seconds instead of hours! Productivity went up by a factor of 100! Eventually, I contributed a menu-driven shell written in Pascal to extend EBBA's command language, building on some recipes I found in a "Turbo Pascal Programmer's Library" by Jamsa and Nameroff. Later I used a Borland data base program as a template to write a program that enabled our salesmen to bring along searchable catalogs of SPOT satellite data on diskettes when they visited customers in Africa and southeast Asia. To search the central catalogue in Toulouse would usually take several minutes and required a modem hookup. Now a complete search of all available images of, say, Borneo could be done and sorted in seconds, in the field.
 |
|
A Knight's Tour solution.
|
It is sobering to realize that a typical PC today runs some 500 times faster than the original IBM PC. The original "killer application", the VisiCalc spreadsheet, would often take tens of seconds to recalculate a table, depending on its size and complexity.
Later in the 1980s I dabbled in Prolog, a language with a very different structure from Fortran or Pascal. I used it to solve combinatorial puzzles in New Scientist, similar to SEND + MORE = MONEY where each letter corresponds to a certain digit. (I suppose Prolog is a perfect fit for Sudoku puzzles?) I also solved the classic Knight's Tour problem: Find a sequence of moves so that a chess knight visits every square of the chess board exactly once. I let the Prolog program run overnight, and the next morning a solution was displayed on the screen. I have no idea how difficult the problem is without the use of a computer.
My interest in traditional programming waned when Microsoft Windows replaced MS-DOS as the standard for operating systems on PCs. It no longer seemed as straightforward to get a computer to display a "Hello world!" message. (See a humorous comment on the subject here.) Instead, I took up a different form of programming when I started composing web pages in the 1990s. As an oldtimer, I still like to have access to the underlying HTML code when I create a web page!
Further viewing and reading
1. There is a whole library of Knuth video lectures (about a hundred tapes) available on Youtube, including the seminars referred to above (with dialogs with his students.)
2. A one-hour video of Knuth discussing science vs. faith issues during a visit at Google headquarters.
3. A biography.
4. A 1996 interview in BYTE magazine: "Knuth comments on code".
5. "All Questions Answered". A summary of a Q & A session in Munich, 2001.
6. A collection of tributes from students and friends on his 70th birthday in 2008.
7. Knuth's home
page at Stanford.