Book review: Crafting Interpreters

About twenty years ago I argued with my programming languages professor in front of the whole class about something I didn’t understand. I wrote about it a while back, and I still don’t remember exactly what the argument was, closures maybe. Last month, typing in the chapter of Crafting Interpreters where the C interpreter gets closures, I finally understood what she’d been trying to tell us. It took a couple of hundred lines of C and something called an upvalue.

The book has been free on the web for years, chapter by chapter, as Bob Nystrom wrote it, and I’d read bits of it. In July he finished the print and ebook editions, and I bought the paperback, which is 640 pages, about the size of a phone book, and beautifully made. He did the typesetting himself, and every diagram is hand-drawn and inked. It’s the nicest-looking programming book I own, and it’s not close.

The structure is what makes it work. You build a small dynamically typed language called Lox, with functions, closures and classes, twice. The first half is jlox, a tree-walking interpreter in Java: a scanner, a recursive descent parser that builds a syntax tree, and an interpreter that walks the tree. It’s slow, and simple enough that you understand every line. The second half throws it all away and builds clox in C, a single-pass compiler to bytecode and a stack-based virtual machine, with its own memory management, its own hash table for strings and globals, and a mark-sweep garbage collector.

Every line of code for both interpreters is in the book, in order, and at each step the thing compiles and runs, so you can type along and always have something working. I typed in all of clox, about two weeks of evenings, and skimmed jlox, because I’ve written a tree-walker before.

The writing is funny, which is rare in this kind of book, and he’s honest about which design choices are taste and which are forced on you. The best chapters for me were the Pratt parser in the compiling-expressions chapter, which is the clearest explanation of operator precedence parsing I’ve read, and the closures chapter, for the professor reasons. The NaN boxing section at the end, where every value is packed into the unused bits of a 64-bit double, is the kind of trick I loved when I was writing TSRs on DOS and counting bytes.

The complaints are small. There’s no static typing and not much optimization theory, and he’s clear that it isn’t trying to be a compilers textbook, so if you want the Dragon Book material you’ll still need the Dragon Book. And it’s long. You can’t do this in a weekend.

But I’ve recommended it to three people on my team already, and one of them is a front-end engineer who’s never written C, and she’s on chapter 17. If you’ve ever looked at the language you use every day and wondered what’s actually going on underneath, this is the book.