5 ms·

Crafting Interpreters

274 points by vvoruganti 4y ago

webmaven 4y ago
The link should really be to https://craftinginterpreters.com/ https://craftinginterpreters.com/
sixstringtheory 4y ago
Previous discussion from when it came out in print, including discussion with the author: https://news.ycombinator.com/item?id=27997167 https://news.ycombinator.com/item?id=27997167
henrikeh 4y ago
I have been reading it and implementing the interpreter in Ada to learn about both interpreters and Ada better. It is a wonderful way to learn, since I constantly have to go beyond the surface level. What is the purpose of this and that in the interpreter? How do I model/implement this well in Ada? If you are curious about languages, I can only recommend trying to learn a new one while following this book. https://gitlab.com/henrikenggaard/ada-lox https://gitlab.com/henrikenggaard/ada-lox
- berkeleynerd 4y ago
  Oddly enough I just started down the same path learning Ada by following Crafting Interpreters in both Java and Ada. If you decide to write anything up about your journey I'll look forward to reading it.
  - henrikeh 4y ago
    I do plan to write about the overall experience, but for now I keep a diary in the repo.
- PartiallyTyped 4y ago
  I am doing the same with scala.
thundergolfer 4y ago
I'm working through this right now and it's awesome. I've completed the Java interpreter and I'm halfway through the C bytecode stack-based interpreter[1]. I'd estimate I've spent around 30-40 hours with the book. Throughout I've used both the website and the dead-tree version of the book. The website is great with 2 monitors, but you might be too tempted to copy-paste the code. The one thing the book doesn't mandate is the use of the Lox test suite, but I think it should be incorporated into the book. It's easier to hack on your implementation when there's a test suite to validate that everything still works as it should at Chapter X. 1. https://github.com/thundergolfer/uni/tree/main/books/crafting_interpreters https://github.com/thundergolfer/uni/tree/main/books/craftin...
- spinningslate 4y ago
  > I'm working through this right now and it's awesome. Hard agree. This is one of my favourite technical books ever. As an amateur language design junkie, I've been through a raft of books. Just counted and there are 10 on my bookshelf, including the Dragon book [0]. This is my favourite. It's beautifully written, very approachable but definitely not trivial. A really impressive piece of work. [0]: https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniq...
  - bogomipz 4y ago
    It seems like many people agree CI is very engaging. Would you recommend any of those other language design books on your bookshelf as similarly fun and engaging? If so which ones?
    - JohnDeHope 4y ago
      Up until Robert's book, my favorite was Building Parsers with Java by Steven John Metsker. I'm a high level garbage collected language programmer by trade. I can't simultaneously learn a very technical topic and also keep up with my pointers. Having guidance in how to do this in Java or some other similar language makes it tractable for me. I know you probably wouldn't want to implement or use a programming language built on top of another GC'd language. But for learning it's helpful.
dragonelite 4y ago
I have bought a copy of this book to support the author, but haven't had time yet to implement any of it. Still wondering if i should do the implementation in Rust or Zig.
- mynameismon 4y ago
  Why not both?
- mhh__ 4y ago
  Do it in whatever you have fun with but KISS
- jwmerrill 4y ago
  I’d recommend a language with automatic memory management for the AST walking interpreter in the first half of the book so you don’t have to worry about how everything gets allocated. Either Zig or Rust would be great for the bytecode compiler/interpreter in the second half of the book, which is written with the expectation of manual memory management. I personally chose Zig and it was fun.
hardware2win 4y ago
The worst thing is how much time building a compiler takes Cli, lsp, cicd, docs, reading about other langs And we arent even talking about the most important piece of code
catchclose8919 4y ago
How does it compare with "Writing An Interpreter In Go"? (https://interpreterbook.com/ https://interpreterbook.com/)
- signaru 4y ago
  Lox is a more featured language than Monkey, meaning that you'll learn more techniques to implement those features. Lox has classes and a garbage collector for the bytecode implementation and is closer to C++'ish languages. While I think Monkey is closer to Javascript. That being said, I've implemented both in C# (during peak quarantine seasons) and I don't regret doing both of them as they cover slightly different aspects or do the same things differently. Both books are well written, meant for non-CS programmers, and patiently guides you through small chunks of code, so that you end up with an actual working interpreter. As opposed to other books I've seen where there are long blocks of code explained by long paragraphs, and rely on you looking up the "accompanying source code" to figure out how the code pieces together. Thorsten Ball also acknowledges that he also learned from Nystrom's Wren, so there are some things that follow the same approach (the Pratt parser if I remember correctly). WAIG also documents some clever simple optimizations which is nice to know on top of having implemented Lox. What I appreciate most from WAIG that is absent in CI is how it re-uses its AST from the tree-walking interpreter to make a byte code interpreter. CI on the other hand, writes the bytecode interpreter from scratch (C instead of Java) and doesn't cover how to emit bytecode given an AST (something I had the fun of doing myself for Lox) as it took the single pass compilation approach (with focus on efficiency).
smcl 4y ago
This reminds me that I need to return to my implementation! I maybe bit off a bit more than I could chew by using it as an opportunity to learn D (which is very nice, thanks @WalterBright!) and ended up with a weird bug in my implementation of section 25 "Closures" in the bytecode interpreter, got distracted by Advent of Code and didn't come back to it yet. Anyway, heartily recommend both working through Crafting Interpreters and learning the D language.
agomez314 4y ago
Great book which took away my fears of making a compiler. It's analogous to the 4-minute mile, where it seems so daunting to do until someone else does it and suddenly it seems achievable. Wish there could be books like this but for other "scary" parts of computing like operating systems or windowing system
- jecel 4y ago
  The Oberon book describes the compiler, operating system, windowing system and other things. http://www.projectoberon.com/ http://www.projectoberon.com/
aidos 4y ago
If you’re wondering if you should invest your time in this exceptional book, you could read this first in order to fully appreciate how exceptional it is. https://journal.stuffwithstuff.com/2020/04/05/crafting-crafting-interpreters/ https://journal.stuffwithstuff.com/2020/04/05/crafting-craft...
- gjm 4y ago
  It's interesting that the author seems to have independently invented literate programming. At any rate, that page describes a home-grown literate programming system without mentioning the term "literate programming".
  - evacchi 4y ago
    I am not sure it really is literate programming, in the traditional sense. In literate programming source code and text are intertwined while Crafting Interpreters keeps code aligned to text but they are distinct https://github.com/munificent/craftinginterpreters https://github.com/munificent/craftinginterpreters EDIT: BTW the book is great, can't recommend it enough! :)
- returningfory2 4y ago
  I think the test infrastructure for the book described in that post is just so smart. For those who haven't read the post: the test infrastructure compiles (and runs?) the interpreter code as it exists at the end of each chapter in the book. So not only is the code as a whole guaranteed to compile, but if you follow along correctly, at the end of each chapter you are guaranteed to get something runnable.
p0nce 4y ago
Haven't got the book yet, but started using Wren. It's a nice language if you want scripting and OOP (though I haven't used Lua).
Derbasti 4y ago
One of the best books about programming I have ever read. Simply brilliant!
golergka 4y ago
Great book! Already implemented the first part with Typescript instead of Java, and still working through the second with Rust instead of C. I don't think I would ever learn to use unsafe is not for it.
olvy0 4y ago
Somewhat tangentially to this discussion, I've been burned by DSLs at work. Personal rant follows. Apologies for being vague about the details, I've also changed some of them. Our internal product has had 2 different DSLs written for it, one a graphical one written early in the 2000s, and another textual one written about 6 years ago. Both of them were partially driven by the same guy, the first one as an implementer and the second one as a manager. The second one was supposed to replace the first one. That first, graphical one, was disliked by many internal users, and was never actually fully completed. Many internal apps were written in both those DSLs, and so far we have kept full backwards compatibility with both of them, including still occasionally fixing bugs in the interpreter. We have a vague plan to retire the first (graphical) one in a couple of years, once everyone has migrated to the second one. I was against this second DSL from the beginning, and had a big fight against that manager guy who suggested it. I wanted to use an existing language instead of writing our own, again. However I was promptly shut out from the decision making process. From what I could tell this was because a guy on another team convinced that manager that writing a new language is trivial, using a commercial parser generator we have the license to. I might mention that the product has many other features and the language is just one of them. It might be the most user-visible one, but there are many layers beneath it. So that second language was built essentially by a commitee, without my direct involvement, with another team, which proved to be a long and painful process that took many hours. And to my great chagrin I did end up partially implementing the transpiler for this language and implementing some of framework required to bolt it into the existing product. This was sort of fun for a while but I was fully aware I was deep into NIH land. The language itself was simple enough, but many features added around it caused a large amount of bugs. Features included an in-app editor with full auto-complete, customized validations and warnings, automatic refactorings, a simple but performant on-line coverage engine, a primitive debugger, and so on. The bugs were mostly in the interface between our code and the code coming from the second team, since implementation of those features was split between us and them. Also a large number of bugs came from the effort to be fully backwards compatible with the older DSL language, which had some weird features due to its graphical nature, in order to allow conversion from the old language to the new. The initial rollout of the language was met with some success, but it was mainly users who were relieved they don't have to the first (graphical) DSL anymore. Then users of course started asking for more features in this language. However, just then, most of the team left. For about a year I was the only one left and I was swamped with work. Now we do have a team back, but it's mostly new people, and each of them is already responsible for an existing feature other than this DSL. As a result, this DSL has very little documentation, except a tutorial course and some bare-bones help. Also, to cut corners, me and the team lead purposefully made some design decisions that impact performance, making our app very slow at times when users write lots of long functions in this DSL. But now we're stuck. The current team lead is practically the only one who knows about this language and all the nitty gritty design issues in it. And as a team lead they don't have time to spend on it. My team lead tries to be continue being an IC (individual contributor), and fix one of more severe of the performance problems on her own, but since they also has to function as a team lead, it took a long time, and also led to a series of very difficult bugs which we still deal with to this day. I made some effort to wrote a post-transpiler phase which essentially bypasses some of the performance problems users have ran into, making her work somewhat redundant, but it's not quite enough. At the same time, there are requests from users and internal support to integrate "proper" scripting languages (python) or to expose APIs for our app. So all this soured writing compilers / interpreters, and DSLs in general, for me. I used to love learning new languages and wrote my own complete and fully tested parser for some small languages, including the C/C++ preprocessor. But now I can't bear thinking about doing it. Once you have customers for this DSL, with demands and bug reports, and you hardly have the manpower to actually dedicate to improving it, it isn't fun anymore. Not to mention I was against this NIH thing from the beginning, and it pains me to keep supporting it. Currently I'm thinking about integrating C# as a kind of scripting language, since we're already a Microsoft shop, although that has been changing in the last decade. TBH this was suggested years ago by the same guy who was responsible for the 2 DSLs, but I rejected it then due to performance issues. Now with AOT compilation, Roslyn, and VSCode / Monaco and its extensions, this might just be the correct time. I'm not yet sure how exactly this will play out, but we'll see.
shafin_ 4y ago
One of the two best technical books i've ever read is this one and the other one is os three easy pieces

274 points by vvoruganti 4y ago

The link should really be to https://craftinginterpreters.com/ https://craftinginterpreters.com/

Previous discussion from when it came out in print, including discussion with the author: https://news.ycombinator.com/item?id=27997167 https://news.ycombinator.com/item?id=27997167

henrikeh 4y ago

I have been reading it and implementing the interpreter in Ada to learn about both interpreters and Ada better. It is a wonderful way to learn, since I constantly have to go beyond the surface level. What is the purpose of this and that in the interpreter? How do I model/implement this well in Ada? If you are curious about languages, I can only recommend trying to learn a new one while following this book. https://gitlab.com/henrikenggaard/ada-lox https://gitlab.com/henrikenggaard/ada-lox

berkeleynerd 4y ago
Oddly enough I just started down the same path learning Ada by following Crafting Interpreters in both Java and Ada. If you decide to write anything up about your journey I'll look forward to reading it.
- henrikeh 4y ago
  I do plan to write about the overall experience, but for now I keep a diary in the repo.
PartiallyTyped 4y ago
I am doing the same with scala.

thundergolfer 4y ago

I'm working through this right now and it's awesome. I've completed the Java interpreter and I'm halfway through the C bytecode stack-based interpreter[1]. I'd estimate I've spent around 30-40 hours with the book. Throughout I've used both the website and the dead-tree version of the book. The website is great with 2 monitors, but you might be too tempted to copy-paste the code. The one thing the book doesn't mandate is the use of the Lox test suite, but I think it should be incorporated into the book. It's easier to hack on your implementation when there's a test suite to validate that everything still works as it should at Chapter X. 1. https://github.com/thundergolfer/uni/tree/main/books/crafting_interpreters https://github.com/thundergolfer/uni/tree/main/books/craftin...

spinningslate 4y ago
> I'm working through this right now and it's awesome. Hard agree. This is one of my favourite technical books ever. As an amateur language design junkie, I've been through a raft of books. Just counted and there are 10 on my bookshelf, including the Dragon book [0]. This is my favourite. It's beautifully written, very approachable but definitely not trivial. A really impressive piece of work. [0]: https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniq...
- bogomipz 4y ago
  It seems like many people agree CI is very engaging. Would you recommend any of those other language design books on your bookshelf as similarly fun and engaging? If so which ones?
  - JohnDeHope 4y ago
    Up until Robert's book, my favorite was Building Parsers with Java by Steven John Metsker. I'm a high level garbage collected language programmer by trade. I can't simultaneously learn a very technical topic and also keep up with my pointers. Having guidance in how to do this in Java or some other similar language makes it tractable for me. I know you probably wouldn't want to implement or use a programming language built on top of another GC'd language. But for learning it's helpful.

dragonelite 4y ago

I have bought a copy of this book to support the author, but haven't had time yet to implement any of it. Still wondering if i should do the implementation in Rust or Zig.

mynameismon 4y ago
Why not both?
mhh__ 4y ago
Do it in whatever you have fun with but KISS
jwmerrill 4y ago
I’d recommend a language with automatic memory management for the AST walking interpreter in the first half of the book so you don’t have to worry about how everything gets allocated. Either Zig or Rust would be great for the bytecode compiler/interpreter in the second half of the book, which is written with the expectation of manual memory management. I personally chose Zig and it was fun.

hardware2win 4y ago

The worst thing is how much time building a compiler takes Cli, lsp, cicd, docs, reading about other langs And we arent even talking about the most important piece of code

catchclose8919 4y ago

How does it compare with "Writing An Interpreter In Go"? (https://interpreterbook.com/ https://interpreterbook.com/)

signaru 4y ago
Lox is a more featured language than Monkey, meaning that you'll learn more techniques to implement those features. Lox has classes and a garbage collector for the bytecode implementation and is closer to C++'ish languages. While I think Monkey is closer to Javascript. That being said, I've implemented both in C# (during peak quarantine seasons) and I don't regret doing both of them as they cover slightly different aspects or do the same things differently. Both books are well written, meant for non-CS programmers, and patiently guides you through small chunks of code, so that you end up with an actual working interpreter. As opposed to other books I've seen where there are long blocks of code explained by long paragraphs, and rely on you looking up the "accompanying source code" to figure out how the code pieces together. Thorsten Ball also acknowledges that he also learned from Nystrom's Wren, so there are some things that follow the same approach (the Pratt parser if I remember correctly). WAIG also documents some clever simple optimizations which is nice to know on top of having implemented Lox. What I appreciate most from WAIG that is absent in CI is how it re-uses its AST from the tree-walking interpreter to make a byte code interpreter. CI on the other hand, writes the bytecode interpreter from scratch (C instead of Java) and doesn't cover how to emit bytecode given an AST (something I had the fun of doing myself for Lox) as it took the single pass compilation approach (with focus on efficiency).

smcl 4y ago

This reminds me that I need to return to my implementation! I maybe bit off a bit more than I could chew by using it as an opportunity to learn D (which is very nice, thanks @WalterBright!) and ended up with a weird bug in my implementation of section 25 "Closures" in the bytecode interpreter, got distracted by Advent of Code and didn't come back to it yet. Anyway, heartily recommend both working through Crafting Interpreters and learning the D language.

agomez314 4y ago

Great book which took away my fears of making a compiler. It's analogous to the 4-minute mile, where it seems so daunting to do until someone else does it and suddenly it seems achievable. Wish there could be books like this but for other "scary" parts of computing like operating systems or windowing system

jecel 4y ago
The Oberon book describes the compiler, operating system, windowing system and other things. http://www.projectoberon.com/ http://www.projectoberon.com/

aidos 4y ago

If you’re wondering if you should invest your time in this exceptional book, you could read this first in order to fully appreciate how exceptional it is. https://journal.stuffwithstuff.com/2020/04/05/crafting-crafting-interpreters/ https://journal.stuffwithstuff.com/2020/04/05/crafting-craft...

gjm 4y ago
It's interesting that the author seems to have independently invented literate programming. At any rate, that page describes a home-grown literate programming system without mentioning the term "literate programming".
- evacchi 4y ago
  I am not sure it really is literate programming, in the traditional sense. In literate programming source code and text are intertwined while Crafting Interpreters keeps code aligned to text but they are distinct https://github.com/munificent/craftinginterpreters https://github.com/munificent/craftinginterpreters EDIT: BTW the book is great, can't recommend it enough! :)
returningfory2 4y ago
I think the test infrastructure for the book described in that post is just so smart. For those who haven't read the post: the test infrastructure compiles (and runs?) the interpreter code as it exists at the end of each chapter in the book. So not only is the code as a whole guaranteed to compile, but if you follow along correctly, at the end of each chapter you are guaranteed to get something runnable.

p0nce 4y ago

Haven't got the book yet, but started using Wren. It's a nice language if you want scripting and OOP (though I haven't used Lua).

Derbasti 4y ago

One of the best books about programming I have ever read. Simply brilliant!

golergka 4y ago

Great book! Already implemented the first part with Typescript instead of Java, and still working through the second with Rust instead of C. I don't think I would ever learn to use unsafe is not for it.

olvy0 4y ago

Somewhat tangentially to this discussion, I've been burned by DSLs at work. Personal rant follows. Apologies for being vague about the details, I've also changed some of them. Our internal product has had 2 different DSLs written for it, one a graphical one written early in the 2000s, and another textual one written about 6 years ago. Both of them were partially driven by the same guy, the first one as an implementer and the second one as a manager. The second one was supposed to replace the first one. That first, graphical one, was disliked by many internal users, and was never actually fully completed. Many internal apps were written in both those DSLs, and so far we have kept full backwards compatibility with both of them, including still occasionally fixing bugs in the interpreter. We have a vague plan to retire the first (graphical) one in a couple of years, once everyone has migrated to the second one. I was against this second DSL from the beginning, and had a big fight against that manager guy who suggested it. I wanted to use an existing language instead of writing our own, again. However I was promptly shut out from the decision making process. From what I could tell this was because a guy on another team convinced that manager that writing a new language is trivial, using a commercial parser generator we have the license to. I might mention that the product has many other features and the language is just one of them. It might be the most user-visible one, but there are many layers beneath it. So that second language was built essentially by a commitee, without my direct involvement, with another team, which proved to be a long and painful process that took many hours. And to my great chagrin I did end up partially implementing the transpiler for this language and implementing some of framework required to bolt it into the existing product. This was sort of fun for a while but I was fully aware I was deep into NIH land. The language itself was simple enough, but many features added around it caused a large amount of bugs. Features included an in-app editor with full auto-complete, customized validations and warnings, automatic refactorings, a simple but performant on-line coverage engine, a primitive debugger, and so on. The bugs were mostly in the interface between our code and the code coming from the second team, since implementation of those features was split between us and them. Also a large number of bugs came from the effort to be fully backwards compatible with the older DSL language, which had some weird features due to its graphical nature, in order to allow conversion from the old language to the new. The initial rollout of the language was met with some success, but it was mainly users who were relieved they don't have to the first (graphical) DSL anymore. Then users of course started asking for more features in this language. However, just then, most of the team left. For about a year I was the only one left and I was swamped with work. Now we do have a team back, but it's mostly new people, and each of them is already responsible for an existing feature other than this DSL. As a result, this DSL has very little documentation, except a tutorial course and some bare-bones help. Also, to cut corners, me and the team lead purposefully made some design decisions that impact performance, making our app very slow at times when users write lots of long functions in this DSL. But now we're stuck. The current team lead is practically the only one who knows about this language and all the nitty gritty design issues in it. And as a team lead they don't have time to spend on it. My team lead tries to be continue being an IC (individual contributor), and fix one of more severe of the performance problems on her own, but since they also has to function as a team lead, it took a long time, and also led to a series of very difficult bugs which we still deal with to this day. I made some effort to wrote a post-transpiler phase which essentially bypasses some of the performance problems users have ran into, making her work somewhat redundant, but it's not quite enough. At the same time, there are requests from users and internal support to integrate "proper" scripting languages (python) or to expose APIs for our app. So all this soured writing compilers / interpreters, and DSLs in general, for me. I used to love learning new languages and wrote my own complete and fully tested parser for some small languages, including the C/C++ preprocessor. But now I can't bear thinking about doing it. Once you have customers for this DSL, with demands and bug reports, and you hardly have the manpower to actually dedicate to improving it, it isn't fun anymore. Not to mention I was against this NIH thing from the beginning, and it pains me to keep supporting it. Currently I'm thinking about integrating C# as a kind of scripting language, since we're already a Microsoft shop, although that has been changing in the last decade. TBH this was suggested years ago by the same guy who was responsible for the 2 DSLs, but I rejected it then due to performance issues. Now with AOT compilation, Roslyn, and VSCode / Monaco and its extensions, this might just be the correct time. I'm not yet sure how exactly this will play out, but we'll see.

shafin_ 4y ago

One of the two best technical books i've ever read is this one and the other one is os three easy pieces