Crafting Interpreters with Rust: On Garbage Collection

In case the author reads this: please explicitly cite all of Nystrom's figures. A link is not enough.

Even with a citation, I'm not quite comfortable just reusing someone else's figures so many times when they're doing so much heavy lifting. But an explicit citation is the minimum.

Crafting Interpreters is such an amazing work.

There's at least one other Rust implementation of lox that I know of (https://github.com/tdp2110/crafting-interpreters-rs) (no unsafe)

It's always interesting to see how different people approach the problems in their own language or relative isolation. I agree with others here, the real value of the original work lies in avoiding copy and paste.

Nice article. A couple of years ago I also implemented Lox in Rust. And I faced the exact same issues that the author describes here, and I also ended up with a very similar implementation.

I also wrote a post about it: https://ceronman.com/2021/07/22/my-experience-crafting-an-in...

I ended up having two implementations: One in purely safe Rust and another one with unsafe.

Note that if you're interesting in the "object manager" approach mentioned, I did that in my safe implementation, you can take a look at https://github.com/ceronman/loxido

Fun writeup. When I went through and implement the book in rust (https://github.com/jcdavis/rulox), I just used Rc and never really solved the cycle issue.

I'll +1 and say I highly recommend going through Crafting Interpreters, particularly as a way of building non-trivial programs in languages you are less familiar with - If you just follow the java/C example you are tempted to lean into copy/pasting the samples, but figuring things out in other languages is a great experience.

I spent a longass time tracking down an issue with how the reference interpreter implementation defines tokens: https://github.com/munificent/craftinginterpreters/issues/11... which was frustrating but good debugging practice.

Note that there is quite a bit of thinking and available implementations of GC implementations available in Rust: https://manishearth.github.io/blog/2021/04/05/a-tour-of-safe...

I did something very similar to this myself. My GC implementation was pretty heavily inspired by manishearth's Rust GC.

My swing at the Crafting Intepreters in Rust can be found here: https://github.com/mwerezak/sphinx-lang

Although, at the time I was really interested in Lua's syntax so for extra credit I designed a completely different syntax for Lox closer to Lua's.

I'd love to revisit this project sometime and implement a register-based VM similar to Lua's.

I have run into a lot of similar problems writing a state management framework for Rust (wip at https://gitlab.com/samsartor/hornpipe) and at one point despaired that I would have to abandon Rust and make a whole new reactive language. But the last couple years I've got it working really nicely with weak references and software transactional memory. Every reference is `Copy + Send + Sync + 'static`. And you can mutate objects by having a transaction make a local bitwise copy, which will get atomically merged and swapped on commit. The old copy gets kept around for undo/redo purposes. I've still got a boatload of algorithmic puzzles to solve to provide all the MVP features, which will take a while because it isn't my full-time job. But the details seem technically sound.

I did write a blog post about some of my design thoughts, although it doesn't dig into the technical guts: https://samsartor.com/guis-3/

> Don’t ask me about covariance since I honestly don’t know the answer. I recommend reading the section on subtyping and variance and The Rustonomicon. I went through them a few times but still don’t entirely get all the details. Then, we can define each type of object like so:

Haha this is gold. We ALL do this ALL the time.

This is really well-written!

Shameless plug: you may want to check out Loxcraft: https://github.com/ajeetdsouza/loxcraft

I too followed the path of "ignore safe Rust for maximum performance". It got pretty close to the C version, even beating it on some benchmarks.

TL;DR: Don't use unsafe to break the rules. Use unsafe to enforce the rules in new ways.

Great journey. That's the thing about "unsafe" and "questionable parts"... if they really are questionable, then don't do 'em. In this case, if it is the case that holding a reference to a GC object guarantees that that object can't be freed, then it's not questionable. Proving that to be case can be fun tho.

The question is: does my unsafe code allow violating the borrow rules?

Cell, RefCell, RwLock etc give you interior mutability, but there is no way to violate the borrow rules with them. On the surface, it looks like you are violating them because "I have a non-mut thing that I can mutate".

If you build a thing that allows two distinct &mut T's to the same thing, then you are basically asking for a bug. Don't use unsafe to break the rules. Use unsafe to enforce the rules in new ways.

The other major issue with the Deref implementation is that `&mut` needs to be an exclusive reference, and if you're doing mark/sweep of GC objects via references you break that invariant if you hold any `&mut` across a GC call and are causing UB. In practice this probably doesn't affect your program, but I suspect Miri would yell at you and there's the off chance the compiler gets really tricky with inlining somewhere and you are inflicted with horrible pain.

Just wanted to share that the Build your own Interpreters challenge on CodeCrafters is based on the Crafting Interpreters book and is free at the moment.

Link: https://app.codecrafters.io/courses/interpreter/overview

(Disclaimer: I work for CodeCrafters, and built this challenge).

> How much memory is used for the stack and when it is freed can always be determined at compile-time.

Technically, not always. You can allocate on the stack at runtime, see "alloca" in C.

But is alloca even that useful in practice? I struggle to find a good example.