Crafting Interpreters: A Review
chidiwilliams.comI hesitated a little bit before deciding to purchase and go through the book. Had already read many glowing reviews then, but was not sure if the choice of language (Java) for the first half of the book would be a hindrance (it's not the stack I am most familiar with).
Decided to buy it anyway, primarily because the two implementations of the toy language piqued my interest (most other books only go through one implementation).
Boy was I glad I did.
Writing is superb, end-of-chapter challenges are instructive, code samples are meticulously and beautifully done. Here and there I also encountered references to other languages (e.g. had a brief detour to Lua internals [1], thanks to a side note), which I have enjoyed too.
Went through the first half twice: first using Java as it is written and then secondly implemented the interpreter in Rust (my initial fear turned out to be unfounded). Currently going through the second half.
So if you're reading this, thank you, Bob :).
You're welcome! :D
I wish people would be less opinionated about things like this. I've completed exercises for books or courses in C, C++, Lisp, Scheme, Go, Python, Javascript, Ruby, Rust, Java, Scala, Clojure, Prolog, Assembly, etc. It's not a big deal. Nobody is telling anybody they have to then program in that language for the rest of their lives. Be open to new experiences. Java really isn't difficult or alien or bad enough to complain that it's the wrong language and expecting book x to be in your preferred language z when there are dozens one could choose is so...closed-minded.
I wrote the first one in Python without issue. I guess any sufficiently expressive language should be fairly easy to “adjust the recipe to” while still following the book.
How was the performance?
Pythonic.
(I didn’t measure nor care about performance. That wasn’t the goal of the exercise)
Good one. If it works that's all that matters.
> was not sure if the choice of language (Java)
Two books I enjoyed despite, rather than because of the language:
"Program Generators with XML and Java" (aka "program generators for fun and profit") https://www.amazon.com/Program-Generators-Java-Craig-Cleavel...
And:
"Designing Active Server Pages" https://www.amazon.com/Designing-Active-Server-Pages-Mitchel...
The latter mostly for techniques to keep programs structured even when writing mostly in template soup (like php, asp, coldfusion etc).
I fully agree. Superb, "meticulously and beautifully done". I read it online and followed along writing code then bought the book just to support the author. Thanks Bob.
Does the book go into more „modern“ parser architectures ala Roslyn Red Green Trees?
Crafting is less about modern or production-grade anything and more about understanding fundamentals. It would be equally at home in a 1980s compilers and language design course or in a 2000s version of that course. It has a single motivating principle, which is that a learner who understands the bare basics of algorithms and data structures knows, in the truest sense of the word, what a compiler and an interpreter does. It achieves that principle beautifully.
The parser’s data structure is a more traditional Abstract Syntax Node design. Roslyn’s tree design is, IMO, a good internal structure for use in a production-grade compiler meant to be coupled with a developer environment (IDE and other tools) because the complexity pays off in terms of developer experience. However, Bob set out (as far as I can tell from the book and his talks/comments on the subject) to provide a fairly beginner friendly, introduction to the topic of language implementation. Within his chosen scope the parser implementation in Crafting Interpreters is more than sufficient and clearly presents the concepts intended.
IIRC, Roslyn's red-green tree approach is at least partly due to needing to support interactive editing without re-parsing everything. If that's what you're referring to, no, the book doesn't cover that; both interpreters run either in batch mode on a single file or in a simple REPL.
You can read it on the web here: https://craftinginterpreters.com/contents.html
(I don't know how to answer your question accurately)
If you're interested in Roslyn inspired compiler writing, Immo Landwerth who works on as a Program Manager on .NET made a Youtube series about writing a compiler, and my understanding from the part I watched is his work is heavily inspired by Roslyn.
https://www.youtube.com/playlist?list=PLRAdsfhKI4OWNOSfS7EUu...
See to me Java was an advantage because it ensured I would do part 1 in Not Java (in my case c#). Mind you c# is great because it is similar enough you can follow along while also being different enough that you still are forced to engage and think. At some point I want to redo part 1 in F# to REALLY push myself (and also force me to better engage with F#).
I did the first part in F#, and rather than translating Java to F#, I looked at what the author was trying to accomplish in each step, and did something functionally equivalent in idiomatic F#. That was fun & challenging.
haven't tackled the second part, I'm currently down the rabbit hole with Samuel Mimram's Program = Proof, which I'm just loving and the first book I've seen that focuses on the Curry Howard Isomorphism, covering essential logic, lambda calculus, type theory, and Agda... so good.
Any trouble with the Rust implementation? I wanted to give the book a go using Rust, but have been sitting on it because I don't want to get halfway through it only to find that Rust's intentional design and limitations might make it difficult to build an interpreter via the assumptions in the book.
You can do it pretty much verbatim, with dynamic dispatch using enums and lots of pattern matching.
It gets a bit trickier when you are nesting environments for closures and the like, but certainly nothing insurmountable without a few things from the standard library.
I've been loosely following the book with Rust, and no issues so far. Both the compiler and interpreter are implementable without much issues. You'll have to adapt a bit, but in general you can use the same methods.
Not really (for the first part at least, am not yet finished with the second part). I did deviate a little bit with my Rust implementation.
This was my goal anyway: implement Lox differently. Off the top of my head:
* I used ADTs to encapsulate error types and states as much as possible, this lead to heavy use of enums and pattern matching. * I implemented the `Environment` as an immutable, explicitly passed value. This was a little challenging at first, but overall quite satisfying to do.
> was not sure if the choice of language (Java) for the first half of the book would be a hindrance
I think it is refreshing he uses a "boring" language.
The way you phrase that makes it sound like you're implying there isn't an overwhelming dominance in terms of 'boring languages' and tutorials/content/books/training material. HN presumably doesn't upvote Java book #10^6 unless it is quite unique otherwise.
I didn't worry because of Java's perceived lack of 'excitement'.
Just that I am more familiar with other languages and I worried I'd get lost trying to understand Java and not digest the material properly. I tend to fall down rabbit holes sometimes ...
If anything, this has been another way for me to be more acquainted with Java, which I am happy for :).
Java is the opposite of boring. It lacks basic fundamentals such as algebraic data types and pattern matching. You will be kicking and screaming the whole ride.
A boring language would be a language where you aren't triggered/bothered by its basic ergonomics and hygiene. In Java, you must translate discrete variants into dogmatic OO paradigm instead of using language primitives.
Thanks to Java's poor design, it's fundamentally a hazard and a land mine thanks to null not being first class in type system. The use of null as a value inhabiting any type should result in a slap in the face upon opening a pull request (until Java adopts type-safe optionals like Kotlin)
P.S. Switch expressions and sealed interfaces aren't there yet, Kotlin and Scala are still the only options if you are imprisoned to JVM.
I have the same opinion about Java and I hesitated as well before starting to read the book, so I'll use either Kotlin or common lisp.
Using Java was a poor choice (especially without the latest improvements such as records and switch expressions):
* new books should use more modern popular languages to age well and to attract younger audience
* on the JVM there are languages better suited for the topic (e.g. Scala by a large margin)
* There's already the "Language Implementation Patterns" book (https://www.amazon.com/Language-Implementation-Patterns-Doma...) which not only is great for teaching because of its pattern-based approach but also gives you real life skills (e.g. ANTLR is used in most big data query engines)
> new books should use more modern popular languages to age well and to attract younger audience
That doesn't make sense. Java is one of the most popular programming language, more popular than a lot of other "modern popular languages". The only languages more popular are either as old as Java (JavaScript, Python) or older (C, C++). C# might be one option, but it's close to Java, and I don't know if the support for Linux/MacOS was here at the time this book was started. Same thing for JavaScript and Python's popularity, which are relatively recent trends. On the other hand, Java has stayed and endured. It's still here and will still probably be here in 20 years.
> on the JVM there are languages better suited for the topic (e.g. Scala by a large margin)
Scala is less popular than Java, and harder to master. Once you consider Scala, you get into endless arguments about whether to use Scala, SML, OCaml, Haskell, etc.
> There's already the "Language Implementation Patterns" book
There is also "Writing an interpreter in Go" and "Writing a compiler in Go" that seem to cover the same ground. But I'm certain than more people know about interpreters and compilers thanks to these three books than thanks to any one of them.
> but also gives you real life skills (e.g. ANTLR is used in most big data query engines)
The majority of programming languages don't use a generated parser but a handmade recursive descent parser, because it's the best at error reporting. There's a good post about different parsing approaches by Laurence Tratt: https://tratt.net/laurie/essays/entries/which_parsing_approa.... Generated parsers are great for DSLs but that won't teach you how the programming languages that you use work.
Didn't think I'd see 'attract younger audience' and 'Scala' in the same sentence.
A lot of young people know Java because it's what they learned in school and because a lot of employers use it so it's the first thing they learn on the job.
In my opinion, the language is designed in a way that makes it easy to pick up for beginners. The lack of obfuscated operators and foot guns is a plus, and the language forces you to avoid doing 'clever' code golf things, too.
You sound pretty smart! How about writing that book for the rest of us?
ANTLR may be used in big data query engines but I can’t think of a single language I’ve ever used that had a parser written with it. I know you can grab off the shelf parsers with antlr for a bunch of languages, but who cares?
And frankly, Scala’s build tool is way too slow and would be a slog to use for this book.
SBT and Scala are the biggest productivity killers for me at work purely based on the slow build time and lack of proper documentation. That and every release the ecosystem makes some breaking change.
Yeah, SBT is pretty awful. I feel like Scala suffers from design by committee, and by being the choice language of certain types of Enterprise Software Engineers TM.
It is not a language for getting things done imo. Even IntelliJ can’t figure out what’s going on sometimes.
I hear the code examples are in Java. I think that's unfortunate. (And a bit ironic about your post).> Language Implementation PatternsIf you actually take the time to read the book Bob explains the choice.
And fwiw modern Java is decently expressive without adding the unneeded complexity of Scala or something similar.
edit: replied to the wrong post. /shrug
Without a doubt one of the best technical books I have ever read.
To me, it was a missing piece of the big puzzle of "how do computers work". I read many a book to answer this question, and came away with three books:
- CODE by Charles Petzold explains the CPU
- Operating Systems: Three Easy Pieces by Arpaci-Dusseau explain OSes
- Crafting Interpreters by Robert Nystrom explains programming languages
Masterfully done.
These look great, and judging by other people's comments, are instances of a class of book I will poorly describe as "lovingly-crafted works of art on highly technical CS topics", a genre that I am always on the lookout for more examples of.
From my own experience, some examples might be:
- SICP, by Abelson and Sussman
- Paradigms of Artificial Intelligence Programming, by Norvig
By general acclaim, some examples might be:
- How to Design Programs, by Felleisen et al
- Beautiful Racket, by Butterick
- LISP In Small Pieces, by Queinnec
- The Art of Computer Programming, by Knuth
- The Elements of Computing Systems, by Nisan and Schocken
What else comes to mind? (My list is very LISPy, but that's just bc I have high awareness there.)
It's not really CS, but alongside the books you have listed (I have most of those physically and as eBooks!) I absolutely adore "The Art of Electronics" as the Bible to electronics. It's definitely helped me out immensely.
That's a great example -- I know people who have that and feel a religious zeal for it. That "religious zeal about a technical / science created with art and care" book is the feeling I'm really after.
Right, exactly: when that much care is put into a resource, I truly feel that I enjoy it more, even if the material itself might seem dry at first. Those kinds of feeling books are truly special.
100%, which reminds me: another example of books created with incredible care are anything by Douglas Hofstadter. The canonical example is Goedel, Escher, Bach; but one that I think is super under-rated is Le Ton beau de Marot -- not only does he care about the content, but the page layout, the font, everything. Truly a labor of love and obsession.
"Concepts, Techniques, and Models of Computer Programming", by Van Roy and Haridi
FYI there is a second edition of CODE coming out at the end of August.
I will check out Three Easy Pieces! Thanks for the rec.
“Code” 2nd Edition
Could you please consider this book?
Compiler Construction Using Java, JavaCC, and Yacc[0]
In my opinion, this has been underrated book. I learned a lot from this book. I enjoyed it and plan to read it again.
If you could check it out. It contains solid explanation from theory to implementation. I'm not affiliated with the author, I just wanted to show I'm grateful for his work.
[0] - https://onlinelibrary.wiley.com/doi/book/10.1002/97811181127...
OSTEP is the best technical book I’ve ever read.
Exercises are lacking.
YMMV but I found them to be pretty complex and required some in depth knowledge of both assembly and C. Implementing threads/clone at the sys call level required knowing how to set up the stack and registers for the new process. If I recall correctly there was also a hard problem about virtual memory, but this was 3 years ago.
Depends whether you have the international version or the north american one.
Could you elaborate on the differences?
Exactly the comment I was looking for. Thanks for the OS book recommendation.
PS: you might want to reformat your list.
I have started reading Introduction to Computer Organization by Bob Plantz, and I think it would also tell someone a lot about how computers work. It starts with hardware and builds into Assembly and eventually higher level concepts like OOP.
Similar vein re: CPU, targeted at an undergrad level, you might enjoy _Computer Systems: A Programmer's Perspective_ by Bryant and O'Hallaron (https://csapp.cs.cmu.edu/) At least I found it a really well-written and integrative text coming from knowing C and wanting to learn the next level down well. Ties in with the OS bits on the "top side" too.
Any defining book for databases? I'm interested in going deeper into the query planner and indexes.
Look up Designing Data-Intensive Applications by O'Reilly.
Database Internals by Alex Petrov
If you are into videos: https://www.youtube.com/playlist?list=PLSE8ODhjZXjbohkNBWQs_...
Any defining book for networks?
TCP/IP Illustrated, Volume 1, Richard Stevens.
I love this book! My only gripe is that I wish it was a whole series, no, a whole genre of books. We need more hands on, code first books that take you through 1-2 extended projects where you can type along and get working code at the end. These books should have CS theory, but still be fundamentally focused on implementation. It'd be really fun to have one of these for a more functional compiler (type checking, code generation, optimization), for a language service (query based compilation, concrete syntax trees, language server protocol), for databases, operating systems, and so on. Ideally they'd be a cross between an O'Reilly book and a SerenityOS stream
Yeah, I'd love to read this book with a more functional language as target, and compilers as you mentioned.
I agree. I would also like an example with static typing. Also I would like a book on how to create a visual scripting language.
Truly one of the best books in our field; very well done.
Doing the tree-walk interpreter (the first “half” of the book) took two weekends, working much of the day on Saturdays and Sundays.
When I went through it, I built my interpreter in another language, and added other features as I went along. Both helped solidify the concepts. I often had to pull out my additional features as I learned better in subsequent chapters; getting to see the difference between my amateur approach versus the author’s experienced methods was quite helpful!
Beautiful typeface. Clear writing. Passion and humor seeping out of every page.
The author has also kindly made a web version of his book freely available:
This book is a work of art. It's one of the best technical books I've ever read. Truly a masterpiece along every dimension.
As the footer on the online version of the book says "Handcrafted by Robert Nystorm" - it really is lovingly hand crafted. It shows that the author went over the content many, many times polishing it with every go. The content builds up really well as it goes along.
On a minor note, whenever I read a technical book I always come across some mistake in the copy-editing, a missed article, a misplaced article, a typo. I'm 70% of the way in and haven't come across any! Which again speaks to the well-craftedness and hand-craftedness of the book!
Though I do feel the author ran out of steam with respect to the lovely, quirky artwork in the book. I'm disappointed Bob, I want my money back.
> Though I do feel the author ran out of steam with respect to the lovely, quirky artwork in the book.
Definitely true. I was hoping to write the book in two years and it took me six. By the end (which was also during the pandemic) I was pretty fried and it was hard to summon much energy for whismy. I tried to pack as many illustrations in as I could, but by later chapters I was really just trying to get it done.
Also, pragmatically, I found the chapters on the bytecode VM really needed a lot more useful illustrations for things the execution flow so that left less space for the fun ones.
> I'm disappointed Bob, I want my money back.
Sorry, all sales are final. I've already spent the money on whiskey and synthesizers. That's what you get for not scrutinizing the later chapters on the free web version first to ensure that they were up to your standards.
Bob, your continued love of synths gives me hope we will see you take a real leap of faith and give us a ‘Crafting Real-time Audio via custom digital Synthesizers’. I would genuinely love a beginner friendly guide to audio programming in the style you developed for Crafting Interpreters. Help me get my friends into digital instrument programming Bob, it’s not like it would take that long!
I would love to write about audio programming. I've done some and am slowly learning more, but it's a real uphill battle. I get a lot of it, but the math behind filters is really hard for me.
If you can find a copy of Computer Music by Charles Dodge and Thomas Jerse, it's a relatively low-math high-practical walkthrough of lots of stuff including filters.
I'd be surprised if there isn't some beginner-friendly guide to audio programming, albeit not in the same author's style. Anyone have a favorite?
I really enjoyed "BasicSynth": https://basicsynth.com/
> I've already spent the money on whiskey and synthesizers
You know, after reading Game Programming Patterns years ago I knew I'd get CI eventually, and have only delayed because I know I don't have the time to give it what it deserves just yet (two kids under three, fulltime Senior Eng, yada yada you know the drill), but this line hits so close to home that it's getting purchased right now.
Everything I've taken the time to read on your blog has stuck with me Bob, but knowing you're a whiskey and synth lover too just makes it all the better. Crafting Interpreters will still wait though, I've got a bottle of JW Gold and my barely touched Dirtywave M8 to attend to first.
I'm basically a walking nerd stereotype.
The M8 looks so cool, but I just got a Syntakt so I definitely can't justify another groovebox.
I've got a Digitakt that I've gotten good mileage out of but know I haven't really scratched the surface of, so I haven't even let myself watch anything about the Syntakt. The M8 I got for all those times I need real portable groovebox, you know, working from home and all.
I’m pretty involved in Dart these days which is what Bob works on full time now, it’s one of my favourite things about the language, there are so many freaking smart people on a totally different level doing some very cool stuff behind the scenes there with the same level of love and care that went into that book.
highly, highly recommend this book
when i was given a compilers class to teach i wanted to teach hand-written recursive descent because it is simple, elegant and makes the recursive nature of grammars so readily apparent without hiding concepts behind obscure tools
i was despairing that there were no good books around on recursive descent, but stumbled on crafting interpreters before it was even released as a book and immediately structured my class around it
absolute life saver and my students all love it
cannot say enough good things about it!
This is one thing I find funny about this book. Despite the name, it's a great intro to compilers in general.
Thank you for the excellent review!
Also, I'll second the comments here: The design of your blog is beautiful.
Dear Bob, in case it helps FYI both the book's website http://craftinginterpreters.com/ and your blog https://journal.stuffwithstuff.com/ seem down right now.
And if anyone was curious like me to see the book's website, here is a archive link: https://web.archive.org/web/20220616005500/http://www.crafti...
They appear to be up for me now. Not sure if it was a temporary glitch or got swamped or what.
You're welcome - and thank you!
The author says it took about 6 months to thoroughly go through the book and examples.
This is really useful in setting expectations.
I got through all chapters in around 1.5 months, spending 50-60 hours[1]. I'd do solid 4-5 hour blocks on Saturdays and Sundays when I was most into it.
I'm following teachyourselfcs.com[2], so I'm hoping to solidify the concepts the book intro'd by reimplementing the bytecode interpeter in Rust (rlox) and following Alex Aiken's lectures online. OP appears to have reimplemented Lox in Golang (glox) for reinforcement.
So far the time has been well spent. Compilers are now much more 'just another program', and I have new conceptual tools for tackling software engineering problems.
1. https://github.com/thundergolfer/uni/tree/main/books/craftin...
Yes, you can go through the book in much less time than six months if you're more consistent with it than I was. I took a few breaks (for days and sometimes weeks) to study and write other things.
Did you read Computer Systems: A Programmer's Perspective first? I read about 300 pages of it (maybe 200 only, I forget) and got _extremely_ bored. I want to read Crafting Interpreters but I'm concerned that Computer Systems is too much of a prerequisite.
I read the first 3 chapters and worked through the in-chapter exercises (not the end-of-chapter exercises). I think that’s about 150-200 pages.
Yeah it’s quite a slog. I think I averaged 10-20 min per page of progress. I intend to return and finish it but it will take me ages.
It’s not a prerequisite at all though. Crafting Interpreters is pretty high level, in comparison.
That's great to hear, thanks for the response! That sounds about as far as I got, so I think probably I was closer to 200 pages, not 300. It was just so incredibly boring. I was making it through maybe 4 pages a day if I was lucky. And all the material was so similar, it wasn't like you got through one part and then built upon it to something very different; it was more of the same with only a small difference. So no new-topic-energy-burst at the start of a new section.
As another data point, I've taken about 1.5 months for Part 1 of the book, chipping away at it for 1-2 hours on weekday mornings.
Following a slightly different path, "Modern compiler implementation" goes over several topics mentioned in the review (lexing, parsing, type checking, code optimization and generation, runtime environments aspects e.g. garbage collection).
There exists various flavors of the book (in ML, Java, and C).
The only worthwhile version is the ML one though, see https://assignments.lrde.epita.fr/tools/modern_compiler_impl...
There's also Thorsten Ball's Writing an Interpreter in Go[1] and Writing a Compiler in Go[2].
Excellent book indeed. Note that Ball's interpreter uses Pratt parsing, which doesn't require you to delve into the theory of formal languages.
I've found Pratt parsing meshes rather well with formal grammars. Anything that is better described by an operator precedence table rather than BNF should be handled by the Pratt parser, rest can be done with recursive decent.
Yes! Thorsten's books are great!
The literature on interpreters (vs. compilers) is pretty thin. I enjoyed reading these:
1. Peter John Brown. 1979. Writing Interactive Compilers and Interpreters.
2. Timothy Budd. 1987. A Little Smalltalk.
3. Ralph E. Griswold. 2000. The Icon Programming Language, 3e.
4. Pat Shaughnessy. 2013. Ruby Under a Microscope: An Illustrated Guide to Ruby Internals.
This is a new one I haven't read yet, but it looks very practical:
5. Clinton L. Jeffery. 2021. Build Your Own Programming Language: A Programmer's Guide to Designing Compilers, Interpreters, and DSLs for Solving Modern Computing Problems.
I don't know anything about this one, but people have told me they prefer the first edition:
6. Ronald Mak. 1991. Writing Compilers and Interpreters: An Applied Approach.
This is the kind of book that really pays dividends into the future. Once you realize that lexing and parsing is not really that difficult, it makes a whole class of problems much easier.
> it makes a whole class of problems much easier.
The other big realisation is just how freaking enormous that class of problems is.
I've been wanting to read this book, but I'm not sure how I should go about it. Are you supposed to read and type out the code examples? I'm just wondering if I will learn anything that way?
The way that worked better for me was doing the book in a different language (I did it in Crystal and Rust). I had to fully understand the intent being every code example so I could translate it correctly.
This adds another layer of difficulty, depending on how comfortable you are with Java and the language of your choice, but it was the way that worked better for me. I truly felt that I created a language, not just copied some code.
I also took this approach, and I think it has really helped me understand what I'm doing as opposed to merely transcribing the code.
In my case, I chose to use C++ (more specifically, C++20 under GCC 11) with minimal external dependencies (currently just Boost for memory mapped IO and fmt). I'm working on the second part of the book now (only just getting started, really). My tree-walking interpreter works, but does have some limitations (I currently leak memory in a few locations, such as closures, due to reference-counting cycles).
I've had a few gotchas following along this way, but it's been entirely due to my choices.
One thing I'd highly recommend doing: setup tests to validate your code immediately! I don't have anything fancy setup, but basically what I have is mechanisms to hand a script to my interpreter and capture stdout/stderr. It's not the best level of testing, for sure, but it does allow me to basically place the lox snippets from the book into a reproducible framework to make sure my interpreter is doing what's expected. I also added tracing/memory dump facilities to my tree-walker to facilitate debugging as well (the byte-code interpreter builds this in from the start, so I've not deviated in that aspect, yet).
I'm really enjoying the book. It's definitely created a spark in me I've not felt in quite a while.
Another vote for doing it like this. I chose to learn Haskell by working through this book and they were a perfect match. One thing that really helped was trying to build things using a few different language constructs and seeing which ones worked well and which ones didn't. Really helped me independently arrive at a lot of concepts as I searched around trying to figure out how to make things work (a big one being an understanding of the kinds of ways you need to structure your code for a typesystem like Haskell vs. Java)
I would also vouch for this approach, it's what I did and it helped force me to understand instead of just copying. Honestly, working through this book was the most fun I've had programming in years.
It also helps to have a practical application that you're working towards - I was in the process of building a game server in Node and wanted a way to modify the state at runtime, so I used this book to build an embedded language for debug builds.
Question for you on Rust for part 2. Did you skip the data structure implementations part, did you use unsafe, or did you do shenanigans like Ids instead of pointers with backing vecs to handle them?
I also used Rust, though I only went up to chapter 21 in Part 2. I completely skipped the basic data structure implementations. I had no interest in implementing basic stuff like vectors and hashmaps, because it's not relevant to the problem.
I did go the ID route instead of pointers, because I didn't like the idea of shotgunning the heap with my AST, so I put the actual statements/expressions in vectors and everything else uses indices inside opaque ID types.
For fun, I did also start on doing compiler for part 2 based on the AST from part 1, though as I say, I didn't get far. I got distracted with a static, stack-based, natively compiled language instead.
Well yes, the code is pretty much there 1:1. However the juice is in the straight forward explanations and excellent writing.
I used the book by translating the code into my favorite programming languages and heavily played around with different approaches, which is way more time consuming but I don't think it is necessary at all.
I think if you are already a seasoned programmer you might find it even useful to just read the book and the code without doing much of coding at all. Given that you are good at understanding code without executing it.
He does a great job of breaking down the code samples into chunks that are small enough to be meaningful. The longest chunk I remember seeing was around 10 lines. Each of those small blocks of code is surrounded by lots of very helpful and approachable explanatory text. The results was, at least for me, that I never felt like I was copying something I didn't understand.
I copy/pasted the code examples, reformatted them so they'd work in a different language (javascript), and refactored it to write my own language instead of Lox.
Then I did it again with a different destination language design, and had to reference the book less.
Whenever I end up writing an interpreter for a third time, I'll probably be able to do it without referencing Crafting Interpreters at all, if I had to. But I expect I'll still check the book before doing certain fiddly parts of the parser.
I read the beginning sections of each chapter until I understand conceptually what the chapter implements by the end. (I needed more assistance for the initial chapters not knowing what the output of scanning or parsing would be, or where to start, but by the later chapters, it becomes pretty clear what the output of implementing say, classes, is).
Then I would try to implement it on my own without reading, having Chapter 3, the language specs, open in a different tab for reference. I chose Java because (1) I wasn't very familiar with it, and (2) I wanted the option to use their code snippets.
My goal is to pass all of the edge test cases the book mentions. So finally I would read the chapter and take some notes on the different design choices and test cases I missed. The reading is quite fast once you've already implemented because you know what to look for.
the approach i took was to read it for understanding, and then go back and see if i could implement what i had just learned, in a different language, without reference to book. (so implementation would use same strategy, but not be exactly the same.)
it worked well for me.
i think this book along w/ spivak's calculus is probably tied for position #1 in technical book that i found most enjoyable and had the biggest influence on me. cannot recommend it enough.
edit: i should mention if i got stuck i went back to reading the book! the point was, "read to understand, try to implement, if understanding not there, repeat". rather than just typing directly out.
I read the chapters and looked at the samples. If there was a place where several followed a similar pattern then I’d only follow the first one from the book and then figure the others out myself (eg different types of statement or expression). There are also some exercises that don’t provide immediate answers which encourage you to think ahead.
Talk about analysis paralysis. You won't read a book because you're not sure how the book _should_ be read?
I read it through but didn't type out the code, mainly as I know that I would get focused on the code rather than the concepts the book is teaching.
Yes, I read and typed out all the code snippets by hand and it worked really well.
And don't be too careful in your typing either. The times when I mistyped and had to crack out `gdb` were where my learning was actively tested.
I'm in the middle of this book at the moment and I have mixed feelings on it.
It's definitely well-written and you can feel the love and care that went into producing it. But I think it would have been stronger had Nystrom skipped the Java version and spent those pages on theory instead before jumping into the C implementation. While going through the Java stuff (implementing in C# instead because I have an emetic reaction to Java) I found myself just wanting to hurry up and get to the good stuff in C. And I found the visitor pattern and code generation stuff to be a distraction.
The code can also be a bit hard to follow at times because he jumps around from file to file and function to function. He'll present a function that calls a function that doesn't exist yet, and then define the new function, etc. He does it that way because he wanted to ensure that every single line of code was present in the book (he wrote a tool to ensure that was the case), and it certainly helps if you're trying to copy his code verbatim, but not so much for high-level understanding. Maybe that's a failing on my part.
Finally I wish he had gone into more detail on how one might implement a register-based VM because they are faster and more interesting (to me) than a stack-based one.
The Java part is probably very lucky to have if he ever writes a second edition though. The reason is, for many dynamic languages the best way to make an interpreter fast is now to use the Truffle framework, not write a bytecode interpreter in C. Truffle changes the whole space around language interpreters so radically that it feels like it should definitely be worth a mention in any future take on the topic.
With Truffle you start with a Java based tree walking interpreter (could use Kotlin too for less boilerplate), so the very easiest stuff. Then you annotate it in some places, add a dependency on Truffle and ... that's it. Now you have a JIT compiler for your interpreted language. The next step is to start refining the use of the annotations and to write specializations in order to accelerate your JIT by incorporating standard techniques like polymorphic inline caches.
Finally you can compile your new interpreter+JIT engine down to a Graal native image (single standalone native binary), thus ensuring it can start as fast as an interpreter written in C and can warm up as fast as V8. The binary can also be used as a shared library.
Given that this tech exists now, people who choose to write their interpreter in Java will have a massive edge in performance over people walking the traditional path. It's still relatively new technology but it's hard to see how it doesn't change interpreter design forever.
I sympathize with your criticisms about java because the language is... not my favorite. It would be helpful here to look at its choice as a result of Nystrom solving the intersection of multiple optimization problems:
- Manual Memory Management Is Hard. Interpreters are complex pieces of software, you don't need another rabbit hole to dive into while you're learning your first parser. You don't need to agonize over where to put the contents of the file buffer you're parsing before writing your first lexing switch. People spend years with C and C++ and still get MMM wrong. The book is supposed to be fun.
- Data Structures Are Hard. This doesn't apply to C++ or really any modern language, but since you wanted it done in C the first time, that would entail the obligatory "Implement your own universe from scratch" exercise C is infamous for. I don't mind, I always like implementing my own universes (although I despise C even more than Java, it can't be over-emphasized how badly engineered that language is). But again, Pedagogy says that you should introduce the minimum possible surface area while approaching a new topic, ideally a single topic at a time.
- Interpreters Should Be Fast, so overly dynamic languages like python and javascript are out.
- A teaching language should be popular and familiar. The obvious benefit is accessibility to as many learners as possible, but a less obvious one is the availability of tools and cross platform support.
Out of the vast array of available programming languages and their toolchains, the combination of GC, powerful standard library and reasonable performance excludes a whole lot. The popularity requirement basically only leaves Java, C# and Golang standing.
That's a really good summary. I didn't pick C# in part because it feels more tied to Microsoft and Windows than I wanted the book's language to be. Java (to me at least) feels fairly platform and corporation independent.
If you would have prefered I pick Go, you'll definitely like Thorsten Ball's two books.
Choosing a language for books is really hard these days. There are so many choose from and most are quite large and complex, so it's hard to find a single language that is familiar to a large enough segment of the audience.
Eh, you don't have to use Java for the first part. I didn't, and I've seen many other people in discussions of the book say they didn't either. It's readable enough, and the explanations are clear enough, that you can follow along in any other memory-managed language that you're comfortable with.
This is an excellent book. I got so much out the first half I keep building little toy interpreted languages and haven't got round to the second half yet!
This is the type of content I come here for. I also enjoyed the "other posts" listed at the bottom of this article. Well done, Chidi!
Just completed part 1 (used Python instead of Java to spice it up a bit) and it was a great experience! Looking forward to working through part 2, but it will be a while before I can get around to it. I hope more books follow this engaging writing pattern (when it makes sense). Kudos to Bob Nystrom for this great book.
And it's so much fun to go through. Most CS books are usually very dry, this one is such a fun read. I would encourage everyone to go and read at least the web version of the book, I'm sure that you will end up buying it at the end.
Nand2Tetris is another fun one IMO, you can do a chapter a week (an hour of reading and a couple of implementation sessions) and be done in a few months
this is awesome! I wasn't aware of it, now that I'm reaching my time for a midlife crisis, I'll give it a try as a way to feel young again and remember my college days. Thank you!
If you’ve never read it, a fun article on Bob from some years back.
https://www.wired.com/2013/01/comedy-in-the-hacker-world/amp
I was lucky enough to be working on the Dart team in Seattle at the time with Bob, who is one of the smartest, funniest and nicest people I have ever met (although the whole team was an exceptional bunch).
I think this book is ever so slightly overrated when it comes to actually implementing programming languages, but it contains such a nice introduction to parsing that I have for years been using it as my goto "You're not ready yet, read this" book when it comes go guiding people going down the dark unhappy path of working on language implementations.
PLT and implementing languages is something that's always fascinated me, so I enjoy hearing everyone's experiences in this domain. What makes you call it a "dark unhappy path"?
I was being sarcastic but also noting that 85% of the work is not in a book
Has anyone worked their way through both this and Beautiful Racket? I'd love to get a comparison of your experience with both.
I keep meaning to pick this back up. It was my go-to project during air travel and train travel for a while, but I stopped going in to the office so much and command line only projects have trouble competing for mind space with visual stuff, at least for me.
This is my favorite book!
But I think it could be more straight forward if the first interpreter didn't use Java, but a modern main stream language that can avoid code generation and Visitor Pattern. Those parts feels like unnecessary detour.
> but a modern main stream language that can avoid code generation and Visitor Pattern.
Yeah, a language with nice algebraic datatypes and pattern matching does eliminate the need for Visitor patterns.
But the reality is that many programmers are working in object-oriented languages where the Visitor pattern is useful, so I deliberately picked Java in order to teach that approach. The book tries to meet you where you are and not where you might wish you were.
Thanks Chidi for a great review and a blog with a lovely design.
What other books are of the same caliber that HN would recommend?
The programming meme books that you must have on your shelf (reading optional) are:
- The C Programming Language (original C book)
- The Art of Computer Programming (TAOCP)
- Structure and Interpretation of Computer Programs (SICP)
- Compilers: Principles, Techniques, and Tools (Dragon book)
- Don't Make Me Think (design)
- Zen and the Art of Motorcycle Maintenance
I'd also recommend (inter alia -- there's a lot of great works out there!) Friedman et al.'s Schemer books, Petzold's "Code" and "The Annotated Turing," McConnell's "Code Complete," Pierce's "Types and Programming Languages," and Warren's "Hacker's Delight."
The Dragon Book is a bad compiler book. Don’t recommend it just because it has a cool name.
Grune’s Parsing Techniques and Morgan’s Building an Optimizing Compiler are okay.
The author, Bob Nystrom, also wrote Game Programming Patterns which I think is just as good.
You might also like Charles Petzold's book Code.
CODE: The Hidden Language of Computer Hardware and Software - Charles Petzold
The Elements of Computing Systems - Noam Nisan, Shimon Schocken
Operating Systems: Three Easy Pieces - Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau
Huge plus one for OS: Three Easy Pieces. It sticks in my memory forever and I just confirmed, I had a random question about "why" from part of that book in 2014 and emailed Remzi and within a few days had a very detailed response back. It was much appreciated because I can get hung up on little details that I can't explain and it can really create a wall for me, so thanks Remzi for being responsive to a learner!
Worth mentioning (I think it was elsewhere in the overall thread) CODE is getting a 2nd edition later this year. I've always meant to read the book but never did, so I'm planning on using the second edition as my excuse to finally do so.
Same author wrote Game Programming Patterns: http://gameprogrammingpatterns.com/
The Nature of Code - Daniel Shiffman
I love this book.
It's one of my all-time favorite books about programming, I keep coming back and re-reading parts of it.
The author does excellent programming education through fun videos.
If by caliber you mean blow your socks off, The Little Schemer
I recommend "The Pragmatic Programmer" and "Code Complete" regularly. (2nd editions.)
I'm glad to see this book get the attention it deserves.
Beautiful typeface, well organized and very appealing to eyes.
Java is such a god damn turn off.
I think of it as an excuse to implement it in a language you actually like. Makes it more interesting and keeps you honest (since you can't copy pasta your way through it.)