Book Thoughts: Crafting Interpreters by Robert Nystrom

This is the inaugural part of an intended series of posts collecting my thoughts on books related to programming language implementation. It focuses on Crafting Interpreters by Robert Nystrom. The purpose of these posts is mainly to organize my own thoughts rather than to serve as some kind of public review or critique, but I'm sharing it in case my experience can help inform folks.

Note

The book is available for free online directly from the author, although I encourage you to purchase a copy if you find value in it and your financial situation allows it.

Overview

Crafting Interpreters is a practical book. It reproduces every single line of code across two complete interpreters interwoven with the explanations and anecdotes, and this makes me irrationally happy. As a reader, I have personally been irritated on more than one occasion to pick up a book only to have it start by instructing me to download some bespoke, undocumented library that intentionally hides all the significant complexity about the very material I'm trying to learn.

My first-ever formal course about computer programming was taught in C++. Early on, we were shown how to write a "hello world" program using the standard library's streams from iostream. Once I learned that the standard library was just more code, I recall asking the teacher how to write my own printing code so that I did not have to use what was, to me at the time, a completely opaque interface authored by someone else. I don't recall her exact response, but it was dismissive. Of course kernels, system calls, and writing directly to memory aren't reasonable things to explain to a student who just printed their first ever line of text, but having that hidden from me was immensely frustrating. I prefer to learn bottom-up, and my experience has been that the majority of educational material is presented in a top-down style.

Nystrom's structure suits me perfectly. The chapter ordering exactly mirrors how I build software. Each section adds a small feature, with every step explicitly shown, and ends with you being able to run your code and verify that it's doing what you expect. The first chapter on the bytecode interpreter, for example, ends with having defined 2 simple opcodes, and the functionality to disassemble them into a textual representation so that you can run your code with various inputs and actually see it starting to work.

Audience and Informality

Nystrom is clear about the intended audience for this book.

I assume this is your first foray into languages [...]

In order to cram two full implementations inside one book without it turning into a doorstop, this text is lighter on theory than others [...]

I want you to come away with a solid intuition of how a real language lives and breathes. My hope is that when you read other, more theoretical books later, the concepts there will firmly stick in your mind, adhered to this tangible substrate.

It would be unfair to pass judgment on how well the book suits me directly, since I do not consider myself a member of the intended audience—this is certainly not my first foray into languages. My own goal in reading Crafting Interpreters was simply to work through some fun projects and to use it as an opportunity to refresh my knowledge of Rust by translating the book's Java and C code chapter-by-chapter.

If you're a software engineer or student looking to learn how to build your own scripting language, you'll probably love this book. But if you have studied programming languages before, or are looking for insight into how to design a language or its implementation, I would suggest you work through a chapter or two online before committing to the book to see if it suits you. You'll find very little discussion of competing alternative implementations here.

Language choice (Java and C) for included code

The most contentious part of this book is probably the choice of implementation languages. The simpler but slower interpreter from the first section is implemented in Java. The more complex and performant bytecode interpreter is written in C.

Both are rational choices. The tree-walk interpreter makes heavy use of its host language, and memory allocations are scattered all over. It makes sense to use a cross-platform language with reasonable performance, garbage collection, and high-level constructs. Using C for the more advanced interpreter is admirable. It forces readers to think about memory management, which is important for a virtual machine, without the monstrous complexity of C++, or the polarizing type system of Rust.

That said, I do think the particular use of Java is flawed in a few ways. I'm generally skeptical of object-oriented design patterns. I often find the seemingly endless abstractions to be unintuitive and therefore unhelpful. The book makes heavy use of the visitor pattern as a workaround for the expression problem. It's admittedly subjective, but I consider this a code smell.

Another, more egregious issue is that each AST node is its own class and, due to the overwhelming amount of boilerplate this requires in Java, Nystrom opts to take a metaprogramming approach, implementing a string-mangling Java code generator to spit out the many class definitions. While metaprogramming isn't inherently problematic, the fact that it's easier to stop discussing interpreters entirely in order to instead build a little string-mangling domain-specific language strikes me as a red flag. I'm not a Java programmer, so take my opinion with a grain of salt, but by just avoiding a hard-line object-oriented approach it seems like we avoid a tremendous amount of both complexity and boilerplate.

Finally, I am a proponent of strong type systems in nearly all scenarios. Sometimes they lead to verbose code if type inference lets you down, but I have yet to see a single convincing example of a program that can't be statically type checked, but is dynamically type-correct and a genuinely well-designed chunk of code.

While Java is certainly statically typed, the book uses escape hatches for the type system on a regular basis. Various bits of data get cast to be an Object, and then get dynamically checked with instanceof a bit later, effectively forcing type-checking to happen at runtime. This hurts performance, but more importantly it makes the code harder to understand. Maybe this is accepted practice in the Java world, but its exactly this kind of design that makes dynamic languages hard to use at scale.

Closing Remarks

Nystrom has done a good job of staking out a stable place in the spectrum of competing, incompatible requirements. The book covers a lot of ground, doesn't spare the implementation details, and is structured impeccably. Folks with programming language expertise probably won't learn as much as they'd like, and the provided Java code has some dubious bits of design, but the positives significantly outweigh the negatives.