I found your book online (it was less complete back then -- this was 2017), and in 3 or 4 days I had a working prototype. In another week or two, I had a working product. Thank you so much for creating this resource -- learning from it and leveraging it gave me a huge confidence boost, and was super interesting and fun. One of the very best resources I've come across. I still reference that project as one of my very favorite I've ever worked on. Best wishes

PS: the lexical analygator is the best and has shown up (with attributions of course) in several of the internal presentations at $WORK. At one point we even had fan art of him on the whiteboard, but it had to be sacrificed when we had a particularly large diagram to put on there. :|

https://news.ycombinator.com/item?id=40956138

I'm not sure if I'm the best person to write a compiler book, or, at least, not yet. I've written a lot of language front ends and interpreters, but I don't have much experience targeting native code. It's something I've wanted to do for a long time, but haven't made the time to make it happen.

Static types are also hard for the reasons the linked comment talks about.

I still think about it sometimes, but writing a book is a lot of work and I've been enjoying not writing a book for the past couple of years. :)

Putting the book online is one of those things that turned out to be a real non-zero-sum proposition. It draws a lot of people into the book and gives them the ability to check it out before they buy it, which has certainly increased total sales and made me more money.

But, also, for those who can't easily afford it, it ensures they still have access to it, which is good for them.

Kind of an honor system market segmentation.

Thanks for both the books, cheers.

I spent a lot of time trying to figure out how I wanted to handle generics and heterogeneous data in a way that felt simple enough for me to design and implement it. I think I have something more or less figured out. It's about a 50/50 blend of Go interfaces and Rust traits.

I have a prototype implementation in progress but haven't had much time to work on it. I broke my ankle a couple of months ago and while I've had plenty of time being stuck on the couch, I just haven't had the brainpower to work on it.

I haven't given up on it, though.

It’s so well written, full of personality and beautifully illustrated - for me this book is a 10 and the bar I’d use to judge other programming books.

I'm guessing no publisher will show up wanting to do an Esperanto translation. :)

I'd like to say "yes", but I also have to worry about sending a confusing signal to other people who might think I'm giving a blanket yes to translations.

I really do appreciate the offer, though.

At a personal level, this book contained so much that I had always wanted to know, from how hashmaps work, to how to compile in a single pass. And I connected with your note on getting into writing languages partly due to a feeling of being less-than programmers who could create their own language.

One thing I wanted to share: I found a small design change to Clox that eliminates an entire class of hard-to-debug GC bugs.

Basically, the change is that garbage collection never occurs during the execution of an instruction.

Instead, garbage collection is an instruction which is never emitted by the compiler. When the heap size crosses the garbage collection threshold, we schedule a garbage collection, which will occur after the current instruction is done executing, and before the next instruction executes.

To implement this, in the Self-Adjusting Heap[1] section, we set a global variable (let's call it "resume pointer") to the next instruction, similar to the return pointer in a call frame. Then we set the instruction pointer to point to a global constant which contains only the garbage collection instruction.

The way this works: let's say the current instruction allocates something, and the allocation needs to trigger a GC. To trigger the GC, we set the resume pointer to the next instruction, and the instruction pointer to the global constant garbage collection instruction (let's call this GCGCI). When the current instruction completes, the VM goes to the instruction pointer to get the next instruction, and finds it pointing to the GCGCI. It then executes the garbage collection instruction, which runs the garbage collection. The final step of the garbage collection instruction is to set the instruction pointer to the resume pointer (similar to a return pointer) so that when the VM goes to execute the next instruction it resumes the execution of the user program right where it left off.

This adds a bit of performance overhead to garbage collection, but I would guess we more than get it back from the fact that it's no longer necessary to temporarily push objects onto the stack to prevent them from getting GCed mid-instruction. And this eliminates that entire class of GC bugs; code stability and programmer time are worth something!

An alternative implementation might observe that the resume pointer is basically a return pointer, so you could potentially store this on the call stack. I didn't really think through the pros and cons of this as it seemed like just adding a global resume pointer solved the problem more simply. However, one thing I was working on is making my interpreter multithreaded, and this means that most of the global variables used by the VM get stuffed into a "Thread" struct. Keeping the size of this thread struct low is a high priority because that memory usage is a limiting factor in the number of threads you can reasonably run simultaneously, so in this case moving the resume pointer onto the call stack starts to look like a bigger benefit.

[1] https://craftinginterpreters.com/garbage-collection.html#sel...

Yes, that sounds like it would work fine to me. The only downside to keep in mind is that you will periods of time where you need to allocate more memory and have to do that first and then only free up memory in a GC after that allocation takes place. If you're very memory constrained or you need to allocate a lot, that could potentially be a problem.

But if I'm totally honest, I'm not sure how big of a problem that is in practice. One of the really annoying things about garbage collectors is how little literature there is on real-world collection strategies. You can find plenty of papers on collection algorithms, but it's hard to find material on when a GC should run.

Have you ever contacted the authors of The Garbage Collection Handbook[1]? It seems like they intend that book to have the most breadth of knowledge about GC, and if there's anybody out there who has studied when to collect they might know who.

[1] https://gchandbook.org/index.html

Incidentally, that book might contain information on when to GC; I haven't actually finished it yet.

It’s inspiring to see technical writing done like this. As an aspiring engineer, this sets a really high standard to aim for - excellent resource.

You already made it, no need to be humble. You don’t need to finish the CS to call yourself engineer :)

Great documentation and an awesome project. Good job.

It really depends on the kind of language you're trying to build an interpreter for, and what purpose it could serve. For dynamic languages, I'd say looking at the core types of Erlang is a great place to start (Integers, Symbols, Functions, etc.). For a statically typed language things get more complex, but even with just numeric types, characters, and some kind of aggregating type like a Struct you can build up more complex data structures in your language itself.

[1]: https://leonardschuetz.ch/blog/nan-boxing/

Wanted first class functions to simplify the parse step (they can be treated like any other value), but I needed a different mechanism to invoke “native code” vs user-defined methods, so there’s two different types for that.

Needed some kind of compound data type, but I didn’t want to deal with side effects from pass by reference, so Crumb implements lists, but they are always pass by value :)

P.s. theres some pretty neat stuff build with Crumb at https://github.com/topics/crumb if anyone’s interested!

I think it really allows you to grasp some of the more intricate and nuanced parts about building a programming language.

You can encounter all of the big ideas in the first half of the book and gain enough familiarity with them so that when you revisit them again in the second interpreter, you can actually absorb the interesting parts.

Such a phenomenal book!

https://www.youtube.com/playlist?list=PLRAdsfhKI4OWNOSfS7EUu...

$ cat this >/dev/null

Bonus points for redirecting standard error to standard output:

$ cat this >/dev/null 2>&1

Now no one will hear the screams ...

Which are some of those places? Parsing data formats could be one, I guess.

The text, code, structure and pacing, everything is clear and to the point.

„Crafting“ is the right word, because the book feels like it’s written by and for craftspeople.

The first step is to write an interpreter yourself, for a simple language you create, without knowing anything about interpreters or language design. The second step is to rewrite it, and make less mistakes! :)

If you don't do this, you are never going to appreciate the nuances of this topic. And you are going to skip over concepts that don't seem important.

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.

You could go out and fall down a few times by yourself so it’s more fulfilling when you have instruction, but I wouldn’t say that’s the most efficient path.

I don't think I would have ever attempted to write an interpreter without first reading something like CI... I never would have gotten to your step three.

The problem was that I didn't really understand parsing so most of the language was implemented using copious amounts of string.split and string.replace, predictably leading to some concepts not being nestable. Really wish I had archived the source code for that.

There were countless other restrictions too, some expressions could only take a variable name. Statements were delimited by lines (and optionally also by semicolons) so any loop or conditional, regardless of nesting depth, had to fit inside a single line. Due to usage of string.split, initially all semicolons had to have a space before them, I remember feeling very smart when I added automatic splitting of "abc;" into two tokens "abc" and ";"

That's just a crazy amount of work!

You could spend considerably more time implementing a Lisp dialect's math library than the interpreter. There are a lot of combinations.

Where are the objects, hash tables, exception handling, ...

Of course you can get some of these things from a host language, but someone had to make them.

I guess if you have a lot of fairly small ideas with a lot of novelty, I could see the appeal of a new language to express them in.

With Crafting Interpreters, I felt like there was a reasonably small self-contained language I could come up with that covered almost all of the concepts I wanted to teach: variable scope, functions, closures, classes and dynamic dispatch, control flow, etc.

With type systems, there are a lot of forks in the design space and no clear "best" path:

* Does the language have subtyping or not?

* Are generics erased or reified?

* Is generic code specialized at compile time or not?

* Is type inference local or Hindley-Milner?

Any choice I make here would miss out on a lot of important material from the unchosen branch and disappoint readers who wanted me to take the other path.

Maybe the right answer is a broader survey-style book that tries to cover a bunch of different options (like Types and Programming Languages). But then you lose the fun of building one coherent thing.

I will not fault you if you don't get to any such project (I remember discovering Crafting Interpreters around the time you were like... halfway through part one? and seeing how long it took you to get through the rest of the book. The care you take to both give useful technical information and make your writing clear takes a great deal of work), but I would certainly read it as I've read much of CI if it ever exists (I need to finish going through part 2, I'm up to Closures).

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

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.

I opted to translate into Go as I went, which meant:

- a lot more work/time

- slower progress

- no “if you fill in this missing piece, we’ve provided the rest so your compiler will work end-to-end”

- an annoying amount of trying to print ASTs exactly like the C++/Java code for validation purposes

But I got to use Go instead of those other languages! ;-)

The main reason for asking is, I don't know if I'm lacking in natural gifts (really likely) but I can't seem to retain knowledge like that. It feels nice to onboard myself to a language or framework by doing so, but afterwards I will still struggle to connect pieces together.

I'm interested to learn more on how language interpreters work, I just don't know if the format is something that will assist me. I'm trying to compliment and assist my brain with note taking after reading the note taking thread that is currently in the front page, so perhaps that will change.

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.

I am on the language team now, but I'm just one of the team members and not a lead. The Dart team is really fantastic. Every day I'm grateful I get to work with such a good group of people.

I'm looking forward to macros and more fully featured record types.

For example, optional types ended up not working out, but I don't think I knew that then either.

But even before we released, I did tell the language team that I thought it would be good to do:

* Non-nullable types. We got there eventually with a ton of engineering effort and migration cost, but this could have been a really strong selling point at launch.

* Types on the right. Think `var x: int` instead of `int x`. It's a little more verbose in some cases, but it makes the language easier to parse and makes it easier to have complex syntax for type annotations like function types, union types, etc.

* Extension members. We added them years later, which is good, but was too late to affect the design of the core libraries. I suggested that it we had them in 1.0, then the core libraries and collection types could be designed around them.

* `val` instead of `final` for single-assignment variables. It's a small thing, but it means that the syntax for single-assignment variables isn't longer then mutable ones, which is good because it doesn't punish users for doing the "right" thing.

* No semicolons. Again, another small thing, but it does help the language feel cleaner and more modern. It's really hard to do this later when the syntax wasn't designed for it.

* Coroutines instead of futures and async/await. Coroutines are definitely hard to compile to JS, so there is a good argument that I'm just wrong. But I really hate what async does to API design (https://journal.stuffwithstuff.com/2015/02/01/what-color-is-...).

Other than that I’m mainly looking for the reasons code generation is required today to go away.

(Yes, powershell. Because I didn't have any other toolchain/compiler on the windows machine at some old work place and no admin rights to install anything. So I learned powershell.)

Since the project is designed in C, you can mostly write the exact same code in zig, with minimal modifications. If you want to use zig features, they’re easy to integrate, but Nystrom obviously won’t be giving you any hints.

But the language offers a lot of useful features (slices, optionals, error types) and makes some C paradigms syntactic realities (tagged enums, explicit pointer casts). Even more so, the standard library comes with very useful stuff (an ArrayList, a handful of different allocators, heck I replaced the trie of keywords with a StaticStringMap).

it’s a fun project, I would definitely recommend it!

You can actually appreciate how much nicer it is to write than in C, while still being a fairly 1-1 translation.

It probably would have been possible to make this work by introducing temporary scaffolding code which gets removed shortly after, but it would have made the book much longer and more tedious.

Balancing thoroughness and brevity is always a challenge when writing.

The code is compilable at the end of every chapter and usually compilable at the end of every heading within a chapter. One thing I could have done that I didn't would be to place some visual markers in the book whenever you reach a point where things should be compilable. I'll keep that in mind if I write a third book.

So if you do get a spare couple of thousand free hours, please ignore the pull of family, the economic safety of work and plunge head first into another oversized computer engineering project. You may now take my money.

1. It is challenging to distinguish the pertinent from the impertinent. People who are just starting won’t be able to tell what parts of the code deserve their attention now.

2. It is challenging to retroactively draw attention to previously dismissed details once they do become pertinent.

I think there are other ways to address this, with additional formatting considerations in the presentation of example code. But there’s still a problem once the reader wants to tinker with the code, as any such formatting will be lost between a carefully tailored example rendering and the user’s code editor.

> A very common example is the historically necessary boilerplate in Java’s Hello World, where quite a few concepts are present but handwaved away as you don’t need to worry about this now.

What I'm saying is exactly that. Handwave past all of the boilerplate like the static declaration and only focus on the most important to learn up front (ex what a string is).

Could you explain how your statement of initially teching the boilerplate is the same as my statement of ignoring it?

In my example, the entire time they are working with strings or readline/writeline method calls they are entirely ignoring what a static/class/args all mean and they are just boiler plate they have to type until they get to that stage in later lessons.

I specifically said that including the boilerplate is a common pitfall, and requires teaching around a bunch of impertinent concepts.

I also chose the example for a reason very close to your example with Racket: later versions of Java have similarly aimed to reduce the necessary boilerplate. And if I’m not mistaken, the learning experience is a motivating factor for that as well.

If emphatically agreeing with you in so many words isn’t enough to convince you that I agree with you, maybe you’re just looking for something to argue about?

And again, I'm saying I disagree with this. You are saying don't include the boilerplate at all when teaching. I a saying, do include the boilerplate and don't teach it until students are ready to understand it.

As a separate topic, if the language doesn't need boilerplate to make the program work (like Racket) that's spectacular. But if it does, then I'm explicitly saying "show the boilerplate and explain 'you don't need to focus on it now. You will learn it later'".

It is best give people a fully working program at all times, even if they don't understand all of it. So they can play around with it, rather than just read along while the author writes about what would have happened if it were fully functioning code they could play with.

And to make it very clear, the example I linked to explicitly includes all of the boilerplate, and I explained exactly the best method to teach a student with that specific concrete source code.

> https://www.geeksforgeeks.org/java-hello-world-program/

Now all of that said - this isn't really important enough to continue arguing on the internet over. I think we both had good intentions but just weren't communicating clearly. I hope you have a great day.

As you say, definitely not worth arguing further. But I appreciate your clarification!

If you're looking for a follow up, I might have a recommendation. I recently got Essentials Of Compilation by Jeremy G. Siek, and I'm very excited to find some time to read it. There is a version implemented in python and racket (two separate books), so you can pick what you're more comfortable with. (I chose python). Its very elegantly written and after each chapter you end up with a working compiler.

Currently free while the module is in beta. I spent today working through all of the lexer exercises in Rust (I'm currently learning it), and had a lot of fun.

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.

Also I did some searching to see past discussions of Engineering a Compiler and found this interesting comment thread from Bob Nystrom for anyone interested: https://news.ycombinator.com/item?id=21725581

Then, in the future, when I find myself needing some concept from the book, I usually remember at least that it is in the book. Then I go back and read that part more carefully. Now that it's relevant to a real problem I have, I tend to remember it much better after the second read through.

A lot of other "code yourself" books, on the other hand, simply slice already finished codebases, and there's no way to test a simpler incomplete version of the program unless the reader makes extra effort and go beyond what is presented in the book.

While there is a lot of overlapping topics in Nystrom's and Ball's books, there are also enough differences to learn something new from the other. Ball's books uses the same parser and AST as front ends to both tree-walking and VM interpreter. CI, on the other hand, skips the AST for the VM interpreter, and also teaches extra topics like implementing garbage collection, dictionaries/hashtables and class-based OOP.

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.

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.

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.

I did the Torsten Ball books in Kotlin rather than Go and learned a lot

Then just write it in whatever language you want. When I went through the first half of the book back in 2017, I wrote it in Scala. (I did know Java, too, though, so certainly I had an easier time understanding the code examples in the book.)

    switch (thing) {
        case Integer i when i > 0 -> println(“Positive…”);
        case …
    }

> 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

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

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.

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.

POSIX utilities are not great. Lex and Yacc included.

I remember reading that post of yours a year or so ago! It was so bizarre to me, but also really fun. I feel like you are among what is probably a very small group of people who could write something security-sensitive in C, and I would feel comfortable using it. (I am still less than thrilled that I have to rely on OpenSSL, regardless of the process improvements its developer team has made in more recent years.)

I still (unfortunately, IMO) write a lot of C. Back in 2004 I thought it was great fun. But now that I've worked in safer, batteries-included languages, I find C to be a huge drag. I'm so much more productive in Rust or even Java. I could never ever ever ever approach the level of rigor you bring to your C code; I just don't find doing all that stuff to be fun or interesting... to the contrary, it feels like a huge drag: if I were "required" to do all that, I just wouldn't write any code at all in C in the first place, knowing that having to do all the testing and fuzzing and static analysis stuff would burn me out.

Anyhow, I hope I don't sound like I'm being critical... quite the opposite. I just think we live in a magnificent world where people's brains can work so so so differently when it comes to the same topic.

> I feel like you are among what is probably a very small group of people who could write something security-sensitive in C, and I would feel comfortable using it.

This is probably the most complimentary thing anyone has ever said to me. Thank you! I hope I can live up to that.

My take on POSIX utilities would be only to use them on Linux platforms where they effectively form a "native" part of the platform.

Does Windows claim POSIX compatibility these days? I didn't think so? I remember NT's old POSIX subsystem, but is that even a thing anymore?

> My take on POSIX utilities would be only to use them on Linux platforms

I mean, only use them on POSIX-compliant systems. Linux is just one of them.

At the risk of sounding childishly derisive, when someone is talking about "portability", I think they're generally not bothering to include Windows in the mix, as Windows doesn't really share all that much of a common denominator with much else.

A language with as much going on as Ruby was not one I would have picked as a candidate for yacc

But indeed, last I checked, recursive descent was the most common choice overall.