On Father’s Day, 2020, my wife got me something that I have been looking forward to for a long time: The Art Of Computer Programming Boxset.

See, while I see myself as a Software Engineer, I also see myself as a Computer Scientist (and I consider those two very separate things). I love things like algorithms, and learning about novel ways to attack problems, but as I grow older, I realized that my fundamental Computer Science skills were waning. I just don’t use the knowledge enough in day-to-day work. I wanted to reconnect to those fundamentals, and picking up the “Bible of Computer Science” seemed like a decent way to do it. I knew what I was getting into, and thought I’d share my thoughts and reviews of the first volume, which I completed in January 2024, three and a half years after picking it up.

The Challenge

I picked this up knowing that it was an ancient text (Knuth started writing it in the 60s). I knew it would be in a custom assembly language. I didn’t care, I wanted to really give this my all. I started reading immediately, and was met with a wave of mathematics. The entire first half of the first chapter (about a quarter of the book) was based on math review. While some of it (analysis of algorithms, induction and modular arithmetic) was quite familiar, the rest of it I found impenetrable (generating functions, binomial coefficients, asymptotic calculations). At the same time period, I was starting to get a renewed interest in mathematics (watching Numberphile videos and 3 blue 1 brown videos), so I tried my best, but this revealed something to myself. While I was great at calculus during school, I really never learned how to apply the math to problems. I understand math facts about statistics and derivatives and so on, and I have a basic fundamental grasp on what they do, but knowing which math tool to use was my first barrier to this book.

Nonetheless, I told myself I would still attempt exercises. And boy was there a lot of them. Knuth has exercises at the end of each section, and I found that these were the most worthwhile of the book. Any raw programming problem (minus lengthy simulations or research) I would shoot for. Any math problem that just required algebra or basic calculus would be fine. However, if I didn’t understand what the math problem was asking for (or I didn’t even understand why it was in the chapter it was), I skipped. I would attempt proofs, even if they were not rigorous. And I trudged through some problems. But I got there eventually.

After the math section, Knuth introduced his own assembly language. I’ve worked a little in assembly before (mostly in a graduate level class where every assignment was using the MIPS language), so I wasn’t afraid of instructions at that level. And Advent Of Code has more than enough “write a computer” problems that I wasn’t too worried. I implemented each assembly language invocation in a VM written in Rust. I don’t use Rust much at all, so it was a nice way to play around with it and I got to learn a bit about it.

At first, I created a way for the program to read raw instructions from a “card” that I simulated through a card punch. This was painstaking, but watching the program work was nice. The assembly language (MIX, designed by Knuth) is a little archaic (jump registers, self modifying code, 5 byte words and 6 bit bytes), but that was part of the challenge. I didn’t want to do this in a higher level language (although I would probably have learned the same amount at a higher-level). I like writing little VMs, so it was fun.

However, what really got going was once I wrote my assembler for MIX. I could now write text programs and actually execute them. This worked by assembling the instructions into their binary code, breaking them up into different cards, and then going through a bootloader routine (that knuth helps you write) to load your cards and read them into memory. I kinda want to write a very rudimentary OS for this VM, but that might come another day. Some of the problems that I enjoyed in this section were writing a magic square generator and a crossword layout generator.

Of course, something I’ve never done before but was nice to figure out was to actually write a debugger that I could step through the computer with:

As you can kinda see, it’s super basic, but I could list source locations, break on symbolic locations, list all symbols. There’s a few other features that I didn’t show (timing, tracing, inspecting memory, deconstructing a word into bytes, etc.). It has saved so much of my time that it’s probably the best part of the project. (oh yeah, if you’d like to see how all of this works, you can check out the repo and play around with in at https://github.com/pviafore/taocp)

The rest of the chapter focused on applied problems in permutations (I liked this), subroutines and coroutines, interpreters, simulators and I/O. I was excited for coroutines, but it was at such a low mechanical level, that I couldn’t really transfer that knowledge for higher-level coroutines that we are more familiar with today. The most important of these later sections was I/O. It focused a lot on buffering strategies, blocking I/O design choices and dealing with different latency values. Again, I wouldn’t say it was super salient to how we do I/O in a modern programming world, but I enjoyed the section as it got me thinking of different ways to solve problems, and I felt connected to my forebears of computing.

It took me until September of 2021 to get to the I/O section, and I didn’t finish it until August of 2022. I started writing down my answers during the I/O section (you can see a markdown document in each chapter directory in the repo with my answers). I continued to write all of the answers to every exercise I felt I could complete. There’s no guarantees that it’s right, but I wanted to get better at writing down my answers and explaining information in text, so I went for it. I also used LaTeX for the first time (I’m not counting playing around with it and getting frustrated after half an hour in college) to pretty up some of my answers.

It’s definitely something I want to keep improving on as I go into later books.

Chapter 2 was all about data structures. I was hoping for lots of new tricks, but again, this is a volume about fundamentals, and was written with a worldview of the last century on how data structures are used. Arrays, stacks, queues, deques and linked lists (single, circular, and double are all covered, with some interesting problems around them, but nothing that really threw me for a loop. Then came the trees sections. Oh goodness, the tree sections. I like Graph Theory, but so much of these sections went over my head with the math on them (enumerating trees, the infinite lemma, etc.). Knuth even called out that the sections were going to get math-y. I gave it my best, but there were a fair bit of questions that I just had to skip (which probably let these sections go by faster.) I will say that I will keep a threaded tree implementation in my back pocket if I ever really need iteration speed with limited recursion capabilities, but the rest wasn’t groundbreaking for me (I’m sure the parts that I didn’t understand would have greatly expanded my horizons though).

Chapter 2 ended with some of my favorite parts of the book, with multi-linked structures (including parsing some cobol commands), garbage collection, and dynamic allocation. It was fun writing your own “defragmenters”, and learning how mark and sweep worked (along with variations). These are things that I didn’t cover as much in my undergrad or grad (and if I did, my memory is very sparse on it).

So after three and a half years, I’m done with Volume 1. I thoroughly enjoyed it, and found the book engaging, interesting, and tough. I figured that I’d answer a few questions while it’s fresh on my mind.

Questions

Should Every Programmer Read This?

I see it mentioned a lot on Hacker News and the like that this is something that is so fundamental that everyone should read it. I, however, think that very few people should read it. It’s not to create this elite air of it or gatekeep; I just don’t think it’s going to be game-changing for someone just working on a simple CRUD app or DevOps infrastructure. There are other resources that get you up to speed on data structures much better, and the assembly is not going to be something you reach for day to day.

So, who should read it. Well, if you fit in any of the categories below, you should read it

• You want to learn how computing was done in the 60s/70s and understand the challenges faced at the time
• You like writing VMs and toy assembly languages and solving interesting problems in them
• You want to get a deep deep mathematical understanding of how computing works, how trees can be used, and allocation schemes.
• You want to be challenged on topics that a typical programmer will not encounter in a day to day setting.

Did It Make Me a Better Programmer?

Yes, but not for the reasons you may think. It didn’t give me nirvana, or make me see modern computers in a different light. It didn’t teach me algorithmic tricks that would shave off an order of magnitude of my computing. But it did make me better. And that’s because it was deliberate practice. I’m a big believer that you if you aren’t failing at something while learning, you’re not doing hard enough stuff. You can only grow by challenging yourself. And some of this stuff was hard. Like legit hard (especially in a VM you wrote yourself with a debugger you wrote yourself). With so much minutia, I got really good at debugging, thinking through solutions, and planning out code, because the alternative would be a hodgepodge of self-modifying spaghetti code that I couldn’t debug. I also liked the constraint of 4k of memory (which has to fit your code as well), and 6 index registers total. Constraints make you a more inventive programmer.

Some of the problems that I thoroughly enjoyed along the way included:

• Writing my own VM
• The aforementioned crossword layout generator
• Writing your own trace routine
• Handling a 4-state state machine for circular pooled buffered storage to parallelize I/O
• Multiplying polynomials using quadruply linked circular lists
• Creating and simplifying derivatives with tree structures
• A self-compacting garbage collector

Is it outdated?

Yes and no. The things that people had to care about in the 60s and 70s are frankly things we don’t have to care a bout today. The assembly in the book is nowhere close to the assembly used today, and today’s processors have so much more to worry about (branch prediction, NUMA and caches, pipelining, barriers/latches/fences, offloading to GPU, threading, etc.) that reading this book will not make you an amazing assembly programmer.

But, if you are adjacent to any of these areas, the book may have some nuggets for you. A stack is still a stack. Linked lists still require memory in each node to hold a link. Dynamic storage is still a topic of debate. The techniques are still employed today on a lower level. If you want to get an idea of how some fundamentals of a computer work, this is still relevant. And the proofs, math, and exercises are still mostly relevant, because math doesn’t go out of date as often.

Can I just skim it?

I think you would do yourself a disservice if you just skim through it. It is a dense book. I didn’t realize how dense it was until a few sections in. Every word that Knuth writes is important. And if you think you understand everything he said, there’s a bunch of exercises to do that will prove that you may need to reread that last section a few more times. I really liked how dense this book was (and wish I had other textbooks like this).

The exercises are, in my opinion, the most important part of the book. These are the ones that spurred me to research questions, work out hard problems on my own time, hone my proof making skills, and really understand the material. None of it was rote (and Knuth has a nice rating system to give you an idea of how much of a doozy any individual problem is). Many other books could take a lesson from TAOCP on how to write engaging, interesting exercises for the reader.

Similarly, I don’t see this as a great reference book. Half of the learning is done in the exercises, so if you wanted it on a shelf so you could pick it’s paper-bound brain, you won’t get as much out of it.

In Review

I loved reading this book and working through it. I went into it with certain goals (connect with the CS topics of yesteryear, practice problems, and get better at writing and explaining my code) and most of them were met. I do feel like I didn’t learn a ton of new things that I could apply throughout the text itself, but I knew going into it that this may be the case. It did take me 3.5 years to get through it, but to be fair, there was a pandemic, job shift, three advent of codes, writing Robust Python, and family life all jammed in there as well.

I am looking forward to Volume 2, but I’m going to take a break for probably a year or so before I start it. I want to get through some other books on my reading list (next up is Crafting Interpreters, No Bullshit Guide to Linear Algebra, and probably something like High Performance Python or Python Architectural Patterns.) Oh yeah, I’ll probably want to find some open course and I need to write my second book, so it might be well into 2025 before I start Volume 2. That’s okay, this is a “life project” so it’s okay if I take all the time in the world.