I took the “Crusty Interpreter” class!

Last week, I cleared everything else off my schedule to take the “Crusty Interpreter” course, an immersive 5-day “write an interpreter in Rust” course taught by Dave Beazley. I have a long history with Rust, but the language has moved on considerably from what I used to know. Worse, I’d barely written code in any language in years, except for a bit of Haskell for courses I teach and the occasional horrible one-off Python script to automate some task – so I was eager to change that.

The course was a blast! The idea was to write an interpreter for Lox, the toy language from Bob Nystrom’s Crafting Interpreters book. The book already presents a complete Lox interpreter in Java, but we were doing our own thing in Rust, and I pretty quickly stopped following the book’s code since it was very different from what I was trying to do in Rust. If you’re curious what I ended up with, my code is now public. It’s incomplete – I only got as far as section 8.1 of the book – but it runs and does stuff; give cargo run a whirl! If a course like this sounds fun to you, consider taking one of Dave’s various upcoming courses.

I posted lots of thoughts about the course on Mastodon after each day ended. Here are all of those, cleaned up and collected in one place.

Day 1

• We’re only on lexing so far. Dave mentioned that it’s kind of a bummer that the course has to start with tedious string processing stuff. It wouldn’t have to be that way! We could have gone back to front! But that’s the way the Nystrom book is written, and we’re following the book.
• I’m doing more talking than anyone else other than Dave. I wish other people would speak up more. I have no idea how far along they are, or if this is hard for them or easy for them or what.
• The Nystrom book uses Java as its implementation language. Rust is really different from Java along at least two axes: low-level memory layout concerns, and, uh, “object-orientedness”. It is kind of fun trying to figure out how to port the Java code to Rust while navigating both of those at once.
• We are doing quite a lot of talking about error handling. That’s probably a good thing!
• I find the ? thing for error handling in Rust to be rather mysterious so far, and I’d much rather write explicit matches on Results. I can always refactor later once I figure out what I’m doing. (Perhaps it’s not really different from a typical Haskell pattern for error chaining, as seen when programming with Maybe or Either, and so it ought to be familiar to me. But hey, I never claimed to be good at Haskell either.)
• We talked a lot today about how slicing strings doesn’t respect character widths. Someone had a cute example of slicing a ZWJ’d emoji in half and getting one of the constituent emoji.
• I don’t really know if I am writing idiomatic Rust. I don’t even know if anyone in the class can tell me whether I’m writing idiomatic Rust.
• I spent quite a while today trying to figure out how to implement Display on things, then trying to figure out if I could derive Display, all kind of needlessly.
• Dave mentioned that he didn’t want people to get hung up on fiddly details of Rust and thus lose sight of the big picture. On the one hand, I already feel very comfortable with the big picture of interpreters; fiddly details of Rust are exactly what I’m here to learn! On the other hand, I do want to actually “finish” the project by the end of the week, which will probably require sacrificing some attention to detail. We’ll see how it goes.

Day 2

• We talked a bunch about move semantics today. It’s funny, but the time I’ve spent thinking about choreographic programming – where all data and computation is located somewhere, and it moves around when communication occurs – actually seems like it could be helpful for reasoning about data movement in Rust.
• I’m worried about having enough time to write code. This course is really making obvious what a weird silo of knowledge I have as an academic PL person! I could have any number of deep conversations about PL concepts in the abstract, but I’m super slow at actually writing code; I don’t have the muscle memory for anything, I have to look every little thing up, and I usually know enough to know my code is inelegant, but not enough to know how to fix it.
• That said, I think I might waste time preemptively looking things up, when in Rust I could actually just try stuff and then let error messages tell me what to do. For example, it is really slick how if you don’t know, say, what functions you need to implement for a trait, you can just write impl Trait for Type { } (with the actual name of the trait and the type, of course!), and the compiler will tell you what’s missing.
• From the Nystrom book: “In Lox, as in most programming languages, the rules of that grammar are simple enough for the language to be classified a regular language.” Hmm, really? Are “most programming languages” regular languages? I don’t think so.¹
• I had to derive PartialEq on a bunch of my types so that I could write tests with assert_eq!. I was curious what “partial” meant. (In Haskell you would just use Eq , most of the time.) Welp, TIL that a partial equivalence relation is an equivalence relation that isn’t reflexive (!). The example in the docs for PartialEq is that NaN != NaN, so floating point types implement PartialEq but not Eq. 😬²
• Dave was using some types called Person and Pet for an example and kept saying things like “put the Pet in a Box” and “when the Person dies, the Pet dies, too” and it was all very sad.
• Recursive types have to be of finite size, so for example, for an Expr enum type for an AST, apparently you need to use Box when you refer to an Expr inside an Expr. For the record, this sucks and is ugly.
• It’s the end of day 2 of this 5-day course and I’m, uh, almost done with the lexer. :lolsob: Today I finally got the multi-character operators and string literals done. I still have to deal with numeric literals and keywords, and then I can finally move on. Also, my lexer is absolutely hideous and the error handling is laughably bad! Oh, well!

Day 3

• I finished my lexer and moved on to parsing today! I took some time to make my lexer nicer once I got it passing tests, and that brought me joy.
• The style Dave’s lexer is written in seems very different from mine. For instance, self doesn’t occur in my code at all. I think he hewed closely to the style of the Nystrom book, but I didn’t know how to do that in Rust, so – I didn’t.
• I got hung up on data structures today. I wanted a mapping from keywords to token types. This data structure will never change, so I wanted it to be static. Well, it turns out that you can’t have a static HashMap in Rust. After much flailing, I didn’t use a data structure at all and just wrote a function that pattern matches on strings and returns token types. The HashMap would’ve been overkill anyway – but I dunno what would’ve been idiomatic.
• We continued with the Pet and Person examples, and they got sillier and sillier. We kept saying things like, “Maybe the groomer should have borrowed your pet instead of taking ownership of your pet” or “When you get your dog back from the groomer is it the same dog or is it a different dog?”
• The first parsing-related project in the course was just coming up with an AST representation and then writing a pretty printer. That was easy, but parsing itself is going to kick my butt.
• I find the book’s example parsing code to be incredibly hard to follow. Dave doesn’t seem to be a big fan of it, either. His own example parsing code (in Python, for a tiny toy language) is more helpful to me, but I still think parsing is going to kick my butt. It is quite possible that parsing is as far as I manage to get this week. (Although, once I finally have an AST, I imagine that I can bang out an evaluator for at least a subset of the language really fast.)
• Sorry, but I’m going to get on my soapbox about the HashMap thing some more. Is there not a nice simple lightweight association list data structure in the standard library? I couldn’t find one. I would be happy to just call lookup on a vector of tuples, but do I have to write it myself? Surely it’s already there and I missed it, right? Like, come on. I really, really do not want or need “resistance against HashDoS attacks” for my *checks notes* toy interpreter’s token lookup table.
• Even if I don’t make it past parsing, this course is serving the purpose that I hoped it would, which is to get me writing Rust in a semi-serious way (again). Rust is nice. I know everyone says this, but I have to say it too: the user experience is nice – and I’m not even using any of the fancy-pants tooling that exists these days! I just mean simple stuff, like error messages are thoughtful, and it’s easy to write and run tests, and docs search works. So much love and care was put in. ❤️

Day 4

• I talked with some people on Mastodon last night and I realized that maybe I could write a macro that solves the HashMap problem I was complaining about yesterday. I didn’t get a chance to attempt it, though, because…
• I spent the whole day on parsing. I had a complete mess that didn’t really work. Then, after a conversation with Dave late in the day, I overhauled it, and now it’s pretty and works!
• I’ve never actually written a parser from scratch before (except in Scheme, for Scheme, for my Scheme compiler course in grad school, and that totally doesn’t count), and I didn’t expect to actually like the code at the end. It’s really kind of magical.
• We talked a bunch about lifetimes and borrowing and stuff in class today, but I was honestly pretty distracted with the parsing stuff and wasn’t paying close attention.
• It will be a piece of cake to write a simple expression evaluator now. I’m not that worried about variables – I’ve written a lot of environment-passing interpreters – but I am worried about how to deal with variable mutation. I don’t know how I’m going to handle that, and I might run out of time for it, since there’s only one day left. That’s kind of too bad, because that’s the part of the project that would force me to confront interesting corners of Rust. Well, we’ll see.
• My parser, like my lexer, is in a very functional style. self still doesn’t occur anywhere in my code. Dave was like “sooner or later you’re gonna have to go over to the dark side”, but, empirically, no, I don’t. (It’s not actually that I’m opposed to writing things in a more object-oriented style! It’s that I literally do not even know how to do it in Rust. I guess I could look at Dave’s Rust code more. I haven’t been doing that.)
• There seems to have been a lot of attrition in the course. For a big chunk of today, it was only Dave, one other person, and me. Apparently someone dropped the course because it was moving too slow for them. (That has, uh, not been my experience.) Other people had to bail because life happened.
• I wonder if maybe I should have taken this other course, which is the one Dave suggested to Shriram. I think it would’ve been easier for me. Oh, well – challenge is good!

Day 5

• The course is officially over. I learned a ton! I didn’t get that far on the actual interpreter (lexing and parsing alone took four days, and then today I banged out a simple evaluator for a small subset of the whole language, but even that involved some interesting design choices and some stuff I hadn’t thought about before). I definitely got a lot better at Rust, which was the goal.
• I developed some strong opinions about the Nystrom book. Pedagogically, I don’t much care for it as an introduction to language design and implementation. As one example: Chapter 5 is supposed to be about ASTs. Java is so ill-suited for the task that the book instead does this metaprogramming thing to generate the AST code, which is a neat hack, but it’s completely beside the point of what an AST is all about! I would be very confused if it were my first exposure to the concept.
• Also! Modern Java has enums and pattern matching and stuff! It wouldn’t have to be done in this boilerplatey, verbose way that necessitates a bunch of automation just to *checks notes* define an AST type! But that’s how the book does it.³
• Another complaint about the book is that there’s so much ink spilled about operator precedence. Really? For Fisher-Price: My First Interpreter? Words can scarcely describe how little I care about operator precedence.
• Anyway, enough complaining. On my first quick 20-minute hack-up of the expression evaluator, I made a beginner mistake: I evaluated subexpressions and then tried to do Rust operations on them, but of course I couldn’t because they’re Lox values, not Rust values. But this raised a design question: implement a bunch of traits (like Neg, Not, Add, Sub, etc.) for Lox values, or convert Lox values to Rust values so you can do normal Rust operations on them? I went with the latter.
• I ended up having to think about some design choices more than I expected! For instance, I decided that it should be okay to use comparison operations on arguments of different types, but that the result should always be false. So, 3 <= "hello" evaluates to false, and 3 > "hello" does as well. I could imagine how this behavior might be surprising. There’s a lot of nuance here. (There might be a “correct” semantics for Lox, but I didn’t bother to read the book in detail to find out.)
• Part of the point of this course was supposed to be that dealing with things like mutable variables in Lox would force people to confront thorny issues with ownership in Rust. I didn’t get that far, but Dave said that in the multiple times he’s taught this course, everyone has implemented the environment incorrectly by using cloning where they shouldn’t – but they never notice the problem, apparently because it doesn’t surface until you get further in the book than this course goes!
• We spent a lot of time talking about ownership and borrowing. One interesting question is: how to express co-ownership of an object? Returning again to the “pet” example, we talked about how you could model a situation where two people co-own a pet and should both be able to feed the pet (which mutates the pet!). This made talking about the example even sillier, of course. We kept saying things like, “Instead of a person having a pet, they can have a ref-counted pet.”
• Had I gotten further on the interpreter, the ref-counting thing would have been relevant for correctly managing the environment in Lox. But I didn’t even get as far as implementing mutable variables, since, again, lexing and parsing took 80% of the time. I probably would’ve gotten through those parts faster if were either more familiar with Rust, or if I had ever in my life implemented a proper lexer or parser before! I’m still happy with how much I got done, though.
• I thought it was kind of a bummer how many people seemed to disappear from the course. One person apparently said the course was going too slow for them, which makes no sense to me. The project was very self-directed, and every aspect of it had fractal complexity. You could spend the week just thinking about how to make error reporting good. (Dave kind of did this.) Or you could spend the week just trying to figure out how to allocate the barest minimum of memory. (Dave did a little of this.)
• All in all, I’m really glad I did this! I didn’t get that far on the actual interpreter, but it runs and does stuff, and I implemented a few things I had never implemented before. I don’t think I had any new insights about interpretation as such, but that wasn’t what I was going for. I did get better at Rust, which was what I was going for.
• Dave invited us to sit in on the “Ruckus” course for free, so I hope to do that at some point, if I can make the time!
• Last thing: I now have a Rust thing I want to build! I want immutable association lists that are constructed at compile time, so you can use them in a static initializer. Basically, I think what I want is something with the interface of the alist crate, but instead of being backed by a Vec, it would just be backed by, I guess, a plain ol’ array of pairs. So, static, like the phf crate, but without all the complexity of phf.
• Okay, actually, that wasn’t the last thing. There’s something else: programming is cool and fun! I don’t write a lot of code in my day-to-day life, and it was really nice to spend a whole week doing almost nothing but that. tokei says I wrote 1262 lines of Rust this week (a huge fraction of which is tests), not counting my initial attempt at a parser, which was a non-working mess and got thrown away. It was extremely satisfying to make something come to life completely from scratch.
• Also: my laptop is getting a bit long in the tooth, and I grow weary of macOS. I had been thinking about getting one of those pretty purple Framework laptops, putting Arch or something on it, and using that for the course this week. I was stoked! And then the Framework fiasco happened, I no longer wanted to give them business, and I was bummed about my personal computing situation and by extension, less excited about the course. But it ended up being fine! The Rust tooling all worked great! ❤️

Some final thoughts

I’m very happy to have now had the experience of (a) finally having written a lexer and parser from scratch, and (b) having done it in Rust specifically. But I agree with Shriram that this wouldn’t have been a good way to learn about “the essence of interpretation”! Fortunately, learning about “the essence of interpretation” wasn’t my goal – I already feel pretty comfortable with that topic.

Slava Pestov asked what language implementation book I do like, if not the Nystrom book. I don’t really know if I have a favorite – I learned about language implementation first by taking classes from Dan Friedman and Kent Dybvig at Indiana University (and those courses didn’t use books), and then by working on the Rust compiler as an intern. I don’t use a book in the PL course I teach now, either. That said, Jeremy Siek’s compilers book (in Racket and Python) attempts to distill the Indiana approach – which was particularly formative for me – into a book. So maybe that book is my favorite. (In fact, the Racket edition is the only book that I’ve ever written a back-cover blurb for.)

1. A few people replied to my Mastodon post to point out that I was taking this quote from the book out of context. They were right; it was actually about the lexical grammar of most programming languages (including Lox), not the syntax of most programming languages (including Lox). Brent Yorgey quipped, “Ah, yes, you have to parse the phrase ‘regular language’ context-sensitively, in which case it turns out to be a regular use of ‘regular’.” Ah, yes, you have to parse the phrase “regular language” context-sensitively, in which case it turns out to be a regular use of “regular”. ❤️ ↩

2. Carlo Angiuli pointed out that PERs are widely used in his line of work. ↩

3. Jordan Rose pointed out that you still can’t quite do this with Java enums, because they can’t have payloads (yet?); however, you could use sealed classes or interfaces to accomplish something similar. (However, the Crafting Interpreters book predates those features being added to the language. It would be cool to see what a revised version of the book would look like if it used all the new goodies in Java.) ↩