Robert Nystrom - Crafting Interpreters

To Ginny, I miss your stupid face.

When the first copy of Game Programming Patterns sold, I guess I hadthe right to call myself an author. But it took time to feel comfortable withthat label. Thank you to everyone who bought copies of my first book, and to thepublishers and translators who brought it to other languages. You gave me theconfidence to believe I could tackle a project of this scope. Well, that, andmassively underestimating what I was getting myself into, but thats on me.

A fear particular to technical writing is getting stuff wrong. Tests andstatic analysis only get you so far. Once the code and prose is in ink on paper,theres no fixing it. I am deeply grateful to the many people who filed issuesand pull requests on the open source repo for the book. Special thanksgo to cm1776, who filed 145 tactfully worded issues pointing out hundreds ofcode errors, typos, and unclear sentences. The book is more accurate andreadable because of you all.

Im grateful to my copy editor Kari Somerton who braved a heap of computerscience jargon and an unfamilar workflow in order to fix my many grammar errorsand stylistic inconsistencies.

When the pandemic turned everyones life upside down, a number of people reachedout to tell me that my book provided a helpful distraction. This book that Ispent six years writing forms a chapter in my own lifes story and Im gratefulto the readers who contacted me and made that chapter more meaningful.

Finally, the deepest thanks go to my wife Megan and my daughters Lily andGretchen. You patiently endured the time I had to sink into the book, and mystress while writing it. Theres no one Id rather be stuck at home with.

• 1.
• 2.
• 3.

• 4.
• 5.
• 6.
• 7.
• 8.
• 9.
• 10.
• 11.
• 12.
• 13.

• 14.
• 15.
• 16.
• 17.
• 18.
• 19.
• 20.
• 21.
• 22.
• 23.
• 24.
• 25.
• 26.
• 27.
• 28.
• 29.
• 30.

This may be the beginning of a grand adventure. Programming languages encompassa huge space to explore and play in. Plenty of room for your own creations toshare with others or just enjoy yourself. Brilliant computer scientists andsoftware engineers have spent entire careers traversing this land without everreaching the end. If this book is your first entry into the country, welcome.

The pages of this book give you a guided tour through some of the world oflanguages. But before we strap on our hiking boots and venture out, we shouldfamiliarize ourselves with the territory. The chapters in this part introduceyou to the basic concepts used by programming languages and how those conceptsare organized.

We will also get acquainted with Lox, the language well spend the rest of thebook implementing (twice).

Fairy tales are more than true: not because they tell us that dragons exist,but because they tell us that dragons can be beaten.

G.K. Chesterton by way of Neil Gaiman, Coraline

Im really excited were going on this journey together. This is a book onimplementing interpreters for programming languages. Its also a book on how todesign a language worth implementing. Its the book I wish Id had when I firststarted getting into languages, and its the book Ive been writing in my head for nearly a decade.

To my friends and family, sorry Ive been so absentminded!

In these pages, we will walk step-by-step through two complete interpreters fora full-featured language. I assume this is your first foray into languages, soIll cover each concept and line of code you need to build a complete, usable,fast language implementation.

In order to cram two full implementations inside one book without it turninginto a doorstop, this text is lighter on theory than others. As we build eachpiece of the system, I will introduce the history and concepts behind it. Illtry to get you familiar with the lingo so that if you ever find yourself at acocktail party full of PL (programming language)researchers, youll fit in.

Strangely enough, a situation I have found myself in multiple times. Youwouldnt believe how much some of them can drink.

But were mostly going to spend our brain juice getting the language up andrunning. This is not to say theory isnt important. Being able to reasonprecisely and formally about syntax and semantics isa vital skill when working on a language. But, personally, I learn best bydoing. Its hard for me to wade through paragraphs full of abstract concepts andreally absorb them. But if Ive coded something, run it, and debugged it, then Iget it.

Static type systems in particular require rigorous formal reasoning. Hacking ona type system has the same feel as proving a theorem in mathematics.

It turns out this is no coincidence. In the early half of last century, HaskellCurry and William Alvin Howard showed that they are two sides of the same coin:the Curry-Howard isomorphism.

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

Every introduction to every compiler book seems to have this section. I dontknow what it is about programming languages that causes such existential doubt.I dont think ornithology books worry about justifying their existence. Theyassume the reader loves birds and start teaching.

But programming languages are a little different. I suppose it is true that theodds of any of us creating a broadly successful, general-purpose programminglanguage are slim. The designers of the worlds widely used languages could fitin a Volkswagen bus, even without putting the pop-top camper up. If joining thatelite group was the only reason to learn languages, it would be hard tojustify. Fortunately, it isnt.

For every successful general-purpose language, there are a thousand successfulniche ones. We used to call them little languages, but inflation in the jargoneconomy led to the name domain-specific languages. These are pidginstailor-built to a specific task. Think application scripting languages, templateengines, markup formats, and configuration files.

A random selection of some little languages you might run into.

Almost every large software project needs a handful of these. When you can, itsgood to reuse an existing one instead of rolling your own. Once you factor indocumentation, debuggers, editor support, syntax highlighting, and all of theother trappings, doing it yourself becomes a tall order.

But theres still a good chance youll find yourself needing to whip up a parseror other tool when there isnt an existing library that fits your needs. Evenwhen you are reusing some existing implementation, youll inevitably end upneeding to debug and maintain it and poke around in its guts.