boonsuan

Attention is a moral act: it creates, brings aspects of things into being, but in doing so makes others recede. What a thing is depends on who is attending to it, and in what way. The fact that a place is special to some because of its great peace and beauty may, by that very fact, make it for another a resource to exploit, in such a way that its peace and beauty are destroyed. Attention has consequences.

— Iain McGilchrist, The Master and his Emissary (2009)

a love letter to the art

you can roughly split the art of computer programming as currently written into ten major arcs, each around 300–400 pages (including the answers to exercises):

1 introduction (math prerequisites, assembly programming)

2 data structures (lists, stacks, queues, trees, memory allocation, etc.)

3 random numbers (generating random numbers, testing for randomness)

4 arithmetic (floating points, polynomial arithmetic, etc.)

5 sorting

6 searching (comparisons, hashing, etc.)

7.1 binary tricks (includes binary decision diagrams)

7.2.1 generating combinatorial structures (combinations, permutations, partitions, etc.)

7.2.2.1 the exact cover problem

7.2.2.2 satisfiability

now, in any other book, each of these parts would maybe be 50 pages or so, and the whole thing would fit in one 500 page book. but don knuth is interested in the art, and the art is in part about understanding things as clearly as possible. that means understanding at an instruction by instruction level what is happening in the machine, and finding the appropriate mathematical structures that give insight into what algorithms are really doing. don is interested in thinking and writing as clearly as possible, but without sacrificing detail and resorting to handwaving. this is a difficult balance, because the material itself is hard.

this means that when don wants to understand sorting, he devotes 50 pages to the mathematics of permutations (section 5.1), and that he creates an idealized RISC-V architecture (MMIX) with a meta-simulator that supports all sorts of pipelining, caching, virtual address translation, etc. systems, so that he can count the exact number of memory accesses made at the machine level, so as to analyze a sorting algorithm. this means that when he wants to investigate combinatorial structures like graphs, but lacks a good class of test cases, he goes off and writes a 600-page book (The Stanford GraphBase) so that he can have consistent example data for writing about graph algorithms.

another part of the art is to gain an appreciation of the tapestry of human thought as it is woven through the centuries and millennia. don does his best to trace the roots of ideas, carefully studying all sorts of manuscripts from the past, in German, Latin, French, and really anything he can get his hands on. he traces the full names in their original languages of all people mentioned in the art, with the index of volume 4A spanning 50 pages. section 7.2.1.7 explores the history of combinatorial generation through old Chinese manuscripts, Sanskrit prose, the meter of Greek poetry, and so much more, showcasing the spirit of the programmer as it goes back hundreds of years before the advent of the program.

much of the art lives in the exercises. there are more than 4000 of these exercises throughout the art; many sections ending with at least 50 of them. many of these exercises are an entire research paper, where don has digested it, as well as the papers surrounding it, and provides in the exercise a skeleton of essential ideas that gave life to the paper, leaving you to coat those bones with flesh. he reads a hundred papers or so before writing each section, working in what he calls “batch processing”, and studying in chronological order the papers that form the lineage of a topic from genesis to present day.

the art is a living work. the third edition of volume 1 has gone through 52 printings since 1997, and many more printings if we count from the first edition of 1968. since 1968, don has read through thousands upon thousands of letters from readers, with comments ranging from suggestions for new material, to petty remarks like “i think this comma here should be a semicolon instead.” he will read it all and think it through, because he wants to get it right. he then scribbles his reply in pencil to your email printed out, and you get it back by snail mail half a year later, with a reward ‘check’ if he used your suggestion. every printing incorporates many little changes all over the place, and no two printings of the art are the same. just last week he inserted a new exercise into section 1.3.3 for the 53rd printing of volume 1, to anticipate new material in 7.2.2.8 he just wrote on decoding the Enigma machine (https://www-cs-faculty.stanford.edu/~knuth/fasc9b.ps.gz), as an example of applying backtracking.

the art is the pursuit of beauty. after the galley proofs for the second edition came back in 1977 with shoddy typesetting, he spent a decade on TeX, because, well, the letters have to look right in the words, the words have to look right in the paragraphs, and the paragraphs have to look right on the page. and part of beauty is fun, without the search for applications. volume 4b is full of puzzles with little attempt to justify their utility — master the art, follow the beauty, and utility will come along naturally later.

the art is a love letter to the spirit of computation, written with the nothing less than the entire life and force of don knuth. and that’s a lot — don knuth works really, really hard, and he continues to write the art at the age of 85 today (he’s now writing 7.2.2.3).

so you ask, should you read the art? i say: if you are longing to find, to understand the beauty in these ideas, and to really come to see the very pulse of the machine. goals of utility and efficiency will not be best served here — there are many better books for such purposes — for to view through this lens the art, it would perhaps amount to mere diminishing returns. (that said, you will certainly be a better programmer if you read his book! it might just take a while.) don wants to get it perfect, as perfect as a human work can be, and has spent his life seeking this beauty. the art is his adventure logs, and thank God he should have chosen to share them with the world.

Don Knuth, now 85 years old, of The Art of Computer Programming fame, answers 40 interesting questions, each in exactly 280 characters. These questions are pretty fresh as far as Knuth interviews go. Also, a quote from one of his answers: “the purpose of machine learning should be insight, not results!”

check out https://zjkmxy.github.io/posts/2021/11/twos-complement-2-adi... for a discussion of some relevant mathematics; cool stuff

there is also a lot of good stuff concerning such computational tricks and their relation with 2-adics in section 7.1.3 (Bitwise Tricks and Techniques) of volume 4A of The Art of Computer Programming: https://www-cs-faculty.stanford.edu/~knuth/fasc1a.ps.gz

have you read his current draft of fascicle 7a (7.2.2.3 Constraint Satisfaction)? it is currently 145 pages and is available at https://cs.stanford.edu/~knuth/fasc7a.ps.gz

very amusingly, the entire 700+ page volume covers only Sections 7.2.2.1 and 7.2.2.2 of The Art.

The lyf so short, the craft so long to lerne

Fair enough, I agree with your advice. Thank you. In Singapore however there isn't really an equivalent of community college; there are polytechnics which are essentially associate degrees, and there are junior colleges which are like high school I guess (and besides I won't be able to just enter a junior college even if I wanted to).

But yeah I really do need to think more of their perspective and try to make myself more appealing somehow.