George V. Reilly

Review: Crafting Interpreters

Crafting Interpreters
Author: Robert Nystrom
Rating: ★ ★ ★ ★ ★
Publisher: Genever Benning
Copyright: 2021
Pages: 640
Keywords: pro­gram­ming, in­ter­preters
Reading period: 10–28 December, 2021

I’ve read hundreds of technical books over the last 40 years. Crafting In­ter­preters is an instant classic, and far more readable and fun than many of the classics.

Nystrom covers a lot of ground in this book, building two very different in­ter­preters for Lox, a small dynamic language of his own design. He takes us through every line of jlox, a Java-based tree-walk in­ter­preter, and of clox, a bytecode virtual machine written in C.

For the first im­ple­men­ta­tion, jlox, he covers such topics as scanning, parsing ex­pres­sions with recursive descent, evaluating ex­pres­sions, control flow, functions and closures, classes, and in­her­i­tance.

Starting with an empty slate, Nystrom adds just enough code to implement the topic of each chapter, having a working albeit incomplete im­ple­men­ta­tion of the in­ter­preter by the end of the chapter. He adds new code as he goes, inserting an extra case into a switch here or writing a new function there, or replacing a few lines of an earlier im­ple­men­ta­tion with something that’s just been explained. Knuth’s Literate Pro­gram­ming explains a finished im­ple­men­ta­tion, broken into separate pieces for exposition. Nystrom’s continual, ever-evolving exposition is slower to get to the point, but it’s excellent pedagogy. I would be remiss if I didn’t mention the hundreds of hand-drawn il­lus­tra­tions, which add a quirky flavor to the tone of the book. He has a blog post on how he pulled this or­ga­ni­za­tion off and another on how he created a physical book from the text.

clox is a very different second im­ple­men­ta­tion of a Lox in­ter­preter. Instead of a slow in­ter­preter walking an abstract syntax tree, he develops a stack-based virtual machine, compiles Lox into bytecode, and interprets the bytecode. He covers theory and practical con­sid­er­a­tions for creating a bytecode virtual machine, makes use of Pratt’s “top-down operator precedence parsing”, and implements closures and classes in C. In jlox, he used Java’s HashMap to manage iden­ti­fiers and relied on Java’s garbage collection for memory management. For clox, he implements a hash table and a mark-and-sweep garbage collector. Although he has to cover similar topics (parsing, local variables, closures) each time, he finds a fresh per­spec­tive for the second im­ple­men­ta­tion.

I read the entire book for free at https://crafting­in­ter­, but I liked it so much that I’ve ordered a physical copy. In fact, I actually read much of the book on the website in 2020, but life intervened and I didn’t finish it, so this month, I read it again from the start.

This book is not a textbook and you don’t get an exhaustive in­tro­duc­tion to building in­ter­preters, much less compilers. In the final year of my Computer Science degree at Trinity College Dublin in 1986–87, I studied the Dragon Book when the first edition was brand new. Crafting In­ter­preters is a lot more fun than the Dragon Book.

Highly rec­om­mend­ed!

blog comments powered by Disqus
Path Traversal Attacks » « On Circumnavigating the Aubreyiad Again