Crafting Interpreters

As the author of a POSIX standard utility, I would advise you to only reach for such utilities when portability is the most important thing.

POSIX utilities are not great. Lex and Yacc included.

Does a single production compiler use lex and yacc to generate any part of their system, beyond maybe a first pass to test out syntax before it gets rewritten into a hand written parser/lexer? I'm not going to say none exist since I don't know literally every production compiler ever written, but I have never heard of one that used them for the final code.

For a few reasons.

One, because actually building the lexer and parser from scratch is a useful exercise in a learning context, which is what this is.

Two, because the book wants to teach Pratt parsers, rather than LALR parsers. There’s a lot of literature out there on LALR parsers and generated parsers in general, but precious little on handrolled parsers. Covering material that hasn’t been covered to hell and back is a Good Thing.

Three, because lex and yacc generate C, and the book has two implementations of the interpreter, in C and Java. You could’ve used ANTLR to generate both parsers, but lex/yacc would only cater to the C version

And finally, because not everybody is on a POSIX system. Before WSL, using anything Unix-y on Windows was miserable. These days it’s mostly fine, but using WSL means you’re not actually building windows-native stuff anymore.

Parser generators create more problems than they solve.

Is there any reason to reach for them first?

The Unix Programming Environment tutorial for building hoc doesn’t even come close to what Nystrom gets into in Crafting Interpreters. Hoc is a very fun little language, but as Nystrom describes several times in the book…parsing just isn’t the interesting part of the game.

Bob addresses this in the introduction^:

We will abstain from using [parser generators] here. I want to ensure there are no dark corners where magic and confusion can hide, so we’ll write everything by hand. As you’ll see, it’s not as bad as it sounds, and it means you really will understand each line of code and how both interpreters work.

^ https://craftinginterpreters.com/introduction.html#the-code

When Java gets pattern matching, it will become a more reasonable choice to write an interpreter in.

For what it's worth, these days you could use an LLM to turn each code snippet into many other languages.

Or just focus on his words and use the snippets like generic code and figure out how to do it in whatever language of choice.

You don't need to "learn java" to become conversant or read it as pseudocode.

You can do the second part that is C!

The Java it uses is basically understandable regardless of what language you're used to.

I guess if you're extremely early in your career and have never written anything but Python, it might not be, but if you've ever touched any statically-typed language and a language with a somewhat C-like syntax, you should be fine.

Java is pretty readable, as long as your familiar with C-style languages you shouldn't have too many problems rewriting this in another language.

I’m glad it used Java. I wound up rewriting the code in Python and it really helped me understand the concepts a lot better.

Don't use Java then. The Java bits are just an example, you can write it in any language you want.

Lots of people have done implementations in other languages: https://github.com/munificent/craftinginterpreters/wiki/Lox-...

I did the first half in Clojure (in order to teach myself Clojure), worked just fine. I had to do a bit of translation but it's really not a lot.

It does. The second half is written in C. Java is just used for the simplified first part.

Yes, very much so. Why wouldn't it be? Can you recommend a better resource for learning how to create a programming language from first principles?

I just started it today, which I why I felt the inclination to create this post.

This is not a book about bleeding edge compiler techniques. It teaches the foundations that makes it easier to learn the more complex parts of writing a compiler.

Unless compiler design radically changes it will likely remain a relevant book for a very very long time. Especially since Java-adjacent languages are likely to remain in vogue and the odds of us losing C as a major language in the next few decades is basically zero.

CFG (context free grammar), which is explained in the book, is used here together with LLMs: https://tree-diffusion.github.io

Super. Bob’s way of presenting his content is what I feel the most important to get out of. Great communicator.

Definitely. I just went through the first 60% or so and it's great. The language is java but it's easy to translate to other languages, which would be a good learning exercise in its own right.

It's a 3 year old book on compilers, so if it was ever relevant once, it surely still is today!

Engineering a Compiler (Cooper and Torczon) seems to be widely recommended. I’ve got the second edition but there’s now a third - not sure how significant the changes are.

AFAIK the problem with the dragon book is the same as with most academic compiler courses. It spends most of its time on the theory-heavy front-end (parsing) and much less on the back-end (code generation). Real-world compilers are very much the opposite.

I’ve not read this book, so can’t offer a comparison but Thorsten Ball’s two books [1] are great.

The dragon book was my textbook in college, brings back memories, might be outdated but some concepts should still be useful.

[1] https://thorstenball.com/books/

"Writing An Interpreter In Go"[1] is also pretty good. I read it after finishing crafting interpreters.

[1] https://interpreterbook.com/

https://mitpress.mit.edu/9780262047760/essentials-of-compila...

Recent, that is the Racket version and the author has a Python version, too. Based on the nanopass compiler idea. It builds out the compilers over the course of the books.

This book is intended to be a cover to cover job. I tackled it about 2 or 3 chapters at a time while building alongside. But after the midway point where it swaps to a C based byte code compiler I just read it instead.

There are books like the dragon book which cover PL design in a more reference book style. But I don’t recommend them.

If you’re looking for a lighter alternative then “writing an Interpreter in Go” is worth a look.

Also Bob Nystrum has some other good material on his blog, and a chapter in game programming patterns about PL stuff.

Im my experience following - as in actually doing the steps - works wonders.

This book, unlike the infamous “Dragon Book” for compilers, can be read cover to cover. The Dragon Book has great detail but it is a slog, especially in early chapters. So many students drop their first course on compilers every year because of the Dragon Book and not the actual concepts

Well, in the instance of this book, you should follow along with the steps that Bob Nystrom writes for you. From reading it, it’s clear you’re supposed to follow along and write code “with him”. He even outlines exactly where each line of code should go, and explains why along the way.

Start at 1st chapter, try all the codes until you understand the concept. Then go to next chapter and repeat the process.

For this book, that is absolutely what you should do. It starts you off building a simple parser and interpreter, and then has you add features to both as you progress through the book. Skipping sections can mean that you end up missing functionality you might need.

I finished this book, wrote the two implementations in Python and Zig, genuinely one of the best set of projects I've ever built.

For me, this book demystified these topics and allowed me to do your second and third step in the first place :)

It's okay to not come up with/reinvent from first principles every technique on your own. It's normal to stand on the shoulders of giants.

That's exactly what I did. My own experience with the first step is to write a TeX-like language with macro definition and macro replacement. About a few days into the project I kept running into so many bugs that really instilled a more academic culture in me and I started to read books. But it was still a wonderful first step: without it you might not have even realized that this is a book-worthy topic.

It doesn't have to be a crazy amount of work, see Lisp-in-Lisp in the original SCIP book or a lambda calculus interpreter in Haskell (fits on a screen).

It’s a bit more theoretical, but working my way (slowly, with many re-watches of certain videos) through the Coursera compilers course was a major milestone for me: I highly recommend finding an accessible way to do one of the CS things you think only Wizards can do: once you tackle one or two such projects, and realize that it’s hard, but mostly just slogging your way through it, it can be an enormous confidence boost :-)

I’m always happy to help anyone going down this path: zellyn@(most things) if anyone reading this wants to try but is feeling nervous.

Modern compiler implementation in ML by A. W. Appel

There are (inferior) versions of the same in C and Java. I'd use them together with the ML version.

The main crux of parametric polymorphism and type inference is just implementing Algorithm W. Just find a toy implementation online and poke at it.

For me, when I learned it myself, I simply took the toy implementation at https://github.com/wh5a/Algorithm-W-Step-By-Step/blob/master... realized that it was written in an extremely outdated style, modernized it, cleaned up, and ended up with https://gist.github.com/kccqzy/fa8a8ae12a198b41c6339e8a5c459... Then I proceeded to change various things to "break" the algorithm and see how they are broken.

What do you think the author's intention was behind doing it this way?

I am the opposite. I think pedagogical materials like this should introduce things in the order that makes intuitive sense, and most of the time that means from the easiest to the hardest.

This looks cool! How did you decide on what data types to include?

when building Crumb (https://github.com/liam-ilan/crumb)

As an aspiring engineer

I’ve got some good news for you.

It's generally a good idea to judge a book by its explicitly expressed audience, where applicable. In this case Bob made his audience very clear in the first few paragraphs of the book [0]:

It’s the book I wish I’d had when I first started getting into languages, and it’s the book I’ve been writing in my head for nearly a decade.

In these pages, we will walk step-by-step through two complete interpreters for a full-featured language. I assume this is your first foray into languages, so I’ll 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 turning into a doorstop, this text is lighter on theory than others.

It sounds to me like you picked up the wrong book, skipped the introduction, and then were disappointed that it wasn't directed at you.

The good news is that it is free, so you aren't actually out anything but time.

[0] http://craftinginterpreters.com/introduction.html

Because it’s meant to be for those people

I trust that you're correct, but I'm glad that this is the case. There are books designed to be introductory, and there are books that serve as reference for advanced topics and state-of-the-art techniques. The first type can often serve as an enabler for the second type.

This comment sold me. Gonna keep this as an inactive tab for the next couple months.

Depends on your other goals for your language.

If it's a statically typed language along the lines of TypeScript (where the static typing is just for safety, not performance) and you don't have any opinions about how it runs (compiled vs interpreted) then you can totally follow the book and then strap your type checker on later.

If you have a compilation target in mind (llvm, wasm, jvm luajit), the first half of the book won't get you much closer to it (you'd have a parser) and the second half would have to be heavily adapted to output your target format instead of the highly specialized custom bytecode the book uses.

And in neither case does the book directly help you with using type information to improve efficiency, so without adaptation you'd end up with a language that has static typing for safety but still does type checking at runtime. That's not a bad problem to have, you can always come back and strip away checks later as you get more confident.

I think Dart is underappreciated. Almost the entire compiler is written in Dart. It has a VM, AOT compiler, FFI/Native, and first class Javascript interop with ability to compile to javascript. It has first class WASM support. Null sound safety. They have experimental support for macros. Pretty impressive.