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.
Thanks for the suggestion. I updated it with more explicit citations. After seeing your comment, I just looked around and saw that no license was given for the images.
Though now that I look at it, I apparently completely forgot to specify how the images should be licensed. Oops.
It's not a big deal and I really appreciate you reading and writing about the book, but I would prefer to not have the images reused without attribution.
Thanks for writing the book! I've had an amazing experience tinkering with it over the years.
I see that the license now includes images. I was unsure of how to have proper attribution and had just a link to a particular section of the book containing the image. I've updated it with a link to your profile, and now I should also add a link to the license.
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.
Lox must have the highest ratio of (implementations : production usage) of any language on the planet. And I mean that as the highest praise -- it's proven a fantastic teaching language, and your book is infectious at encouraging others to jump in and follow along in various different languages.
I've also found the exercise of implementing Lox in another language as highly instructive in learning how to write idiomatic code in that language. I continue to learn more about the best way to express patterns as I work on my own implementation. I'd recommend the journey to any professional developer for this side-benefit alone.
> Lox must have the highest ratio of (implementations :
> production usage) of any language on the planet.
It's probably up there, for sure! But I'd guess that there are a million toy Lisp implementations, and more people are interested in writing a FORTH interpreter than actually using one in production. So I'd guess if we tried to get statistics it wouldn't be at the top.
Though there's probably a similar claim to be made for the Monkey-language from Torsten Bell, via his books on compilers and interpreters.
On a more serious note, have you thought about trying to aim lightning at the same spot again and write another book about implementing something most programmers take for granted?
I've definitely thought about writing a third book. I don't know if it would be about "something most programmers take for granted". I'm more interested in writing about whatever happens to excite me the most at that time.
I may be projecting, but I feel like the kind of person to get excited about crafting interpreters wod also get excited about crafting databases or OSes.
That's so many languages and implementations that this could be used as a new Programming Language Popularity Ranking, with a bias towards languages people want to use or learn :D.
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 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.
> 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'll echo this recommendation.
I haven't gone through Crafting Interpreters yet (it's on the bookshelf) but I did go through a big chunk of Building Git and instead of Ruby I did it in Rust, to get back into the language and go a little deeper.
It was really great and it gave me a lot more than if I'd just copy paste the code as you say.
My only issue with Crafting Interpreters is that it relies too much on writing code and then explaining it instead of getting the concepts across first and then providing the code. Another thing I disliked was some code was structured in a way that it would go well with concepts that came further down the implementation which can lead to confusion since it seems overcomplicated/overabstracted at first.
One of the biggest challenges with writing is linearizing: deciding what order to present the material so that it makes the most sense.
There's really no perfect solution. Some readers prefer bottom up where they are given individual pieces they can understand which then get composed. Others prefer top down where they are given the high level problem being solved in terms of intermediate steps which then get incrementally defined. Some want to see code first so that they have something concrete to hang concepts off of. Others want concepts first and then to see the code as an illustration of it.
This is made even harder with Crafting Interpreters because the book's central conceit is that every line of code in the interpreters is shown in the book. There's nothing left to the reader. And, also, the book tries to give the user a program they can compile and run as often as possible as they work through things.
I did the best I could, but there are definitely some places where it's really hard to figure out a good order. Sometimes the book explicitly says "sorry, this won't make sense but bear with me and we'll circle back".
Also, at the macro structure, the entire book is organized into two parts where the first one is higher-level and more concept driven and then the second part circles all the way back to build the entire language from scratch again but at a much lower level of abstraction.
I appreciate your feedback. It's a hard problem and a skill I'm always trying to improve.
Just to throw a positive word out there from one of the quiet majority of your readers, I think you absolutely nailed it with Crafting Interpreters.
It's by far the best introductory book on this topic I've come across yet. It's a fun read and completely demystifies the "magic" of how interpreters work.
Thanks for the answer! While my comment pointed out some issues I had, I do wanna make it clear that I still found it incredibly helpful and its probably the best practical introduction to the topic out there, so huge respect to you.
I think it also heavily depends on the reader. I also followed the book in a different lang than Java and only then I had the aforementioned problems.
As another one of your quiet readers, more specifically a soon-to-be uni grad who's at a crossroads about choosing to pursue my interests in either game engineering or systems engineering as a career path in this hellfire of a world we live in, I ADORE both your books. I think your writing consistently does an amazing job of motivating a practical yet elegant design from first principles.
And yeah, as someone who's trying to start writing a blog on ~technical topics, I get what you mean. Not every explanation can be linearized perfectly, because sometimes two concepts are coupled, motivating and influencing each other's design. Sometimes there are just, so to say, dependency cycles in the "knowledge graph". Can't turn that into a directed acyclic graph no matter how hard you try. The most prudent solution probably is just resolving the cycle iteratively by starting somewhere.
My minor nit pick is that it uses mostly the Java language to implement a Java-like language. What have we gained? Surely something Python-like in C would be more rewarding, one would be gaining a level of abstraction.
Also, I should note that even in the first half of the book, the language isn't Java-like. It has Java-ish syntax, but the semantics are much closer to JavaScript/Python/Lua.
In the first half, what we gain from implementing it in Java is mostly the garbage collector. The rest of the static and runtime semantics basically have to be implemented from scratch on top of the JVM.
There is significance coverage of OOP features, hence my Java-like comment. I would have personally left OOP out for a beginner book, it isn't really fundamental. Another advantage to using Java in the first half, could be to use Java closures to implement Lox closures.
> I would have personally left OOP out for a beginner book, it isn't really fundamental.
This was a deliberate choice. Most intro compiler/interpreter books don't do OOP. But most languages in wide use today are object oriented. That felt like a significant gap to me. One of the main goals with my book is to give people insight on how the languages they actually use work under the hood. Skipping objects and method dispatch would limit that.
There's also more recent implementations such as https://github.com/chc4/samsara (quite similar to https://github.com/pebal/sgcl , which is for C++. Both implement a concurrent tracing algorithm which allows for reduced latency compared to a naïve stop-the-world GC).
Thanks for sharing! That's a much more interesting project compared to mine xD. I had the intuition that rust-gc could be implemented in a simpler fashion by not being generic. Glad to see someone actually had it done.
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:
I get tripped up by variance too and thinking about that stuff is literally my job. If it helps, I wrote a blog post recently about Go's type system and it happens to touch in variance in a way that might help it click:
The very first sentence of that article got me excited:
>I’ve been noodling on a static type system for my current hobby language.
As an inveterate language tinkerer for decades, Crafting Interpreters is like the intersection of Class A narcotic addiction, Feynman level understanding and religious enlightenment. It's in my top 3 favourite books of all time.
If you were to /happen/ to write an extension/follow up book that addressed static typing, then I can personally guarantee at least one sale.
Independent of that, thanks for the work as it stands. My copy is healthily dog-eared and still gets lugged around on holidays for refresh reading.
Thanks for sharing. I've enjoyed every single piece of your writing so far. This will be in the arsenal of materials I'll use when I again get confused about variance.
Definitely not the only one. I am not a stupid person*, but every single time I read the section on variance in the Nomicon I feel like an utter moron.
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.
If someone else depends on this project, I'd definitely not implement the questionable stuff. You're right that proving whether it's safe can be lots of fun, and I'm planning to try it out.
Based on what I've read, it's entirely possible. If my Rust knowledge is correct, there are 2 things that have to be proven - the object's lifetime and the borrow rules.
Proving the lifetime can be done at compile-time based on what was discussed in these articles https://without.boats/tags/shifgrethor/. But that still leaves us with proving that we don't violate the borrow rules. AFAIK, the only way to do it in my implementation is with Cell and RefCell enforcing the borrow rules at runtime.
Before removing all the safety checks, I actually used Gc<RefCell<T>> for mutable objects, so the borrow rules were enforced but not the lifetime. However, I decided to remove RefCell<T> to have some fun and see how I could shoot myself in the foot.
You don't want to use `RefCell` for something like this- it is still too strict for Lox's semantics.
Doing this properly means putting `GcData`'s fields (and/or `ObjFun`/`ObjClosure`/etc's fields) in plain `Cell`s, and using that for all mutation without ever forming any `&mut` references.
Can you elaborate on why it's too strict? I got RefCell working and passed to test suite just fine. Maybe the suite don't take into account some that's specific to Rust.
If I remember correctly, there were some panics cause by RefCell borrows. But those got sorted out once I handled borrowing in the correct order.
I guess a better way to put it is, if you got Lox working with RefCells, then you didn't need RefCells (or their overhead) to begin with - you must not have been holding those dynamic borrows any longer than a single VM instruction, or something close to that.
Yes, the borrows were only held for roughly a single instruction. But I don't see how you can mutate the Table/HashMap of fields in an object with only Cell tho
Technically it is possible to swap the HashMap out of the Cell, mutate it, and put it back, but that is maybe even worse than the RefCell.
What I would expect a production language implementation to do is build its own table that integrates its solution for interior mutability into its design. There are several other things (e.g. iterators, concurrent GC) that will also contribute to the need for a custom table, so (again for a production language) this is not too crazy.
Ah! I could imagine a table backed by an array of Cell since all the possible values in that table implement Copy. There is probably a better way for the table to have interior immutability. But I think I get what you were saying.
Just for reference, the gc-arena crate (https://github.com/kyren/gc-arena) we use in Ruffle's Actionscript 1/2/3 interpreters and across the entire engine, does this. As far as we know, it's safe and sound, at the cost of some limitations, mainly: to compile-time prevent sweeping while holding onto Gc references, every struct and function touching Gc objects passes an extra 'gc lifetime. And not being able to run the GC at arbitrary time can be major issue depending on what you're doing; in Ruffle we incrementally collect between frames and pray that no single frame will ever allocate enough to OOM in the middle of it :)
Thanks a lot for the insight. I think if I do it the way shifgrethor did, I can have GC at arbitrary time. But I'm not so sure about that.
With the way Rust may perform optimizations on the assumption of no alias, I guess there's currently no way to avoid RefCell if we want to be 100% on the safe side.
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.
Yeah true, this breaks all sorts of contracts that we have with Rust xD. But if mark-and-sweep is implemented correctly, then no reference is ever held across the GC. Though, there's gonna be lots of pain debugging when you got it wrong, speaking from experience.
Do you have any resources about Rust inlining and the issues it might cause? I'd love to read more about that.
I would be really careful with those deref methods. They return references, not pointers, which means you need to follow the Rust rules:
- You can have any number of simultaneous readers,
- Or one writer and no readers.
- But if you ever break these rules, the world may burn.
Using unsafe and violating these rules is one of the cases where the Rust compiler can inflict worlds of misery: Incorrect code generation, CPUs seeing different versions of the same memory location, etc., depending on the exact context. Once you use "unsafe" and break the rules, Rust can be more dangerous than C. Rust even reserves the right to generate code using "noalias" (except doing so often triggers LLVM bugs, so it's usually turned off).
"Undefined behavior" means "anything at all can happen, and some of it is deeply weird and awful and counterintuitive."
You could enforce the borrowing rules at runtime by using std::cell::Cell in your heap objects, which is exactly what it exists for. Or you could package everything inside a tiny core module and audit it extremely carefully.
You would probably want to use RefCell instead of Cell. It allows you to safely upgrade into a &mut using only a constant reference to RefCell, but it dynamically verifies that it's actually safe using ref counting. The ref counting also isn't too expensive since it isn't atomic.
I'm aware of all the issues mentioned. But for this particular project, I simply don't care as long as it passes Lox's test suite xD. I went this path just to see how easy it is to get tripped by unsafe while knowing that there's a technique to get safety with Pin<T> that this can get refactored into. I actually implemented this with Cell and RefCell but didn't find that interesting.
Mark and sweep doesn't stop you from holding references across GC.
If you write e.g.
```
let obj = some_object();
let len : &mut usize = &mut obj.len; // deref_mut
trigger_gc();
use(*len);
```
then you held a reference across the GC, and while it's mark/sweeping created an aliases `&mut` to `len`.
Inlining was mention just because it causes function bodies to be splatting together, and so puts together code that is fine in isolation in a way that may allow Rust to observe UB: if `trigger_gc` was inlined for example then Rust has more information and code available at once, and might use the knowledge to apply some optimizations that are invalid because you caused UB.
Actually, looking at your code the much larger issue is that nothing stops you from doing
```
let obj = some_object();
let obj2 = obj.clone();
let len1 = &mut obj.len;
let len2 = &mut obj2.len;
let n = *len1;
*len2 = 0;
println!("{n}"); // what does this print?
```
because your Deref mut are just creating unconstrained borrow from pointer types that you can copy. This is almost definitely going to cause you bugs in the future, since it opens you up to accidentally writing iterator invalidation and other issues (and even worse than C++ does, because C++ doesn't optimize references as heavily as Rust does borrows)
The issue is that it's a simple footgun as soon as you start adding non-trivial native methods (say, string methods, array.map etc). The only way to make sure that they don't exist is removing the DerefMut impl entirely.
It's not just that it's possible to break the code, but that lack of any checks makes it impossible to detect at either compile-time or runtime and have it "appear to work".
One way to solve it to remove the DerefMut implementation and have it work more like Rc - as in, the user is forced to write `Gc<Cell<T>>` or `Gc<RefCell<T>>` if they want mutability. This solves the aliasing borrows issue at the cost of extra runtime checks with RefCell (and still doesn't prevent you from unsoundly calling `sweep()` while holding a Gc)
With a borrowchecker what does GC let you do that is more ergonomic? I have never used a borrowchecked and garbage colected language so I have no experience to consult.
The borrow-checker helps when you're writing Rust code. But when writing an interpreter for another language, you kinda have to support its semantics. In Lox, there's no move semantic, no borrowing, almost everything is a heap-allocated object, variables can alias, etc. Thus, you need to have a way to manage the memory of the implemented language without the borrow-checker. Here, the borrow-checker can help with implementing the GC safely and correctly, but I didn't utilize it.
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.
This was used in linux kernel and they were removing it later because it was a huge pain as far as I can remember. Seems like it causes problems because entire system is built assuming stack/heap work in a certain way.
Oh right. I read about this once or twice and have never looked at it again. I've made the (wrong) assumption that this function needs some compile-time help. Is it all done at runtime? Or does that depend on the actual C implementation?
Stack allocation is always done at runtime. Baring special optimizations, the CPU and the code work together to (stack grows downward) decrement the CPU stack pointer register. This register keeps track of where the bottom of the stack is.
What is done at compile time by the compiler, is calculating the amount to decrement the CPU stack pointer register at runtime for every stack variables.
The compiler and alloca must work together, because optimization can easily break something here. For example, when a function return, the stack pointer register better be restored properly. Furthermore, in Rust you must not forget to call Drop::drop() for all types that have such a destructor.
There's another reason: we need to do string stuff and we absolutely can't stall. Malloc always has some chance of stalling due to heap fragmentation. The leaf function requirement is also not necessary. You just have to make sure you don't alloca too much memory given how much is remaining on the stack and roughly how much memory you know subsequent calls will take.
It's not all that much worse than using a huge, static stack allocation. In fact, there are cases where alloca is safer since you can take into account how much stack memory you already have available before incrementing the stack pointer.
With a huge static stack allocation the stack check must be done within a parent function instead of within the same function.
In any case it is up to you to do the stack check. Though alloca can easily be wrapped by a function running the check.
In Rust I would write a check stack function that takes a function/closure as parameters. Within the closure, you are guaranteed to have at least the requested stack space.
The compiler will inline it all nicely, while preserving the semantic of the stack allocation.
Conceptually, if the compiler could just inline all of the child calls, it's fine. But if this call won't return for a long time, or may be called again (even worse). You're setting aside stack that you'll never get back. Which is a memory leak, and your program will crash.
The stack grab is as permanent as any other stack variable. There is nothing special about it. The only difference is that you can decide at runtime how much to add to the current stack frame.
If the memory's lifetime correctly coincides with the function (which is why you might use alloca in the first place), I don't see how this would be a memory leak nor why it would lead to a crash. Maybe on systems which limit stack size...?
int a(){
void* mem = allocal(some_number);
b();
}
int b(){
a();
}
if a() is a leaf (or can be trivially inlined) it's fine!
on the other hand, if a() calls something else, that's complicated, it's way way harder to figure out why you're crashing. I think you'll segfault as a() eventually overwrites malloc'ed memory. but different systems are going to have different characteristics.
It's not that you can't, you just have to be real damn smart and make sure no one ever messes with your code.
or you can just make sure it's a leaf. much easier rule, much easier to explain.
Maybe if alloca is used with a runtime value uncapped, a user could then trigger a stack overflow with too big of an allocation. This is the same problem when allocating on the heap, with the difference that the heap is a few order of magnitude larger.
That is really the only difference between `in foo[...N] = ...N` and alloca(n). alloca works with a value computed at runtime. And this value could be from an input.
That reasoning leads me to conclude the function should be short lived or the memory in use by all child functions, rather than it has to be a leaf function?
yeah. Leaf is a good rule of thumb, but if you need a little helper to do something it's generally fine.
you really do need confidence the little helper can be fully inlined. if the helper is out of your control, and someone greatly expands its responsibility, it can suck.
Additionally, recursion and function pointers (including dynamic dispatch) are the other two "normal" language features that can defeat static stack analysis. There are techniques for working around this (bounded annotations, languages with strong types can narrow potential dispatch options), but it's a little harder.
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.
Thanks for the suggestion. I updated it with more explicit citations. After seeing your comment, I just looked around and saw that no license was given for the images.
I should probably draw my own.
The license is here:
https://github.com/munificent/craftinginterpreters/blob/mast...
Though now that I look at it, I apparently completely forgot to specify how the images should be licensed. Oops.
It's not a big deal and I really appreciate you reading and writing about the book, but I would prefer to not have the images reused without attribution.
Thanks for writing the book! I've had an amazing experience tinkering with it over the years.
I see that the license now includes images. I was unsure of how to have proper attribution and had just a link to a particular section of the book containing the image. I've updated it with a link to your profile, and now I should also add a link to the license.
idk if he/she change it, but i see the name big and center after each use.
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.
There are a whole pile of Lox implementations in Rust (as well as many other lanugages):
https://github.com/munificent/craftinginterpreters/wiki/Lox-...
Lox must have the highest ratio of (implementations : production usage) of any language on the planet. And I mean that as the highest praise -- it's proven a fantastic teaching language, and your book is infectious at encouraging others to jump in and follow along in various different languages.
I've also found the exercise of implementing Lox in another language as highly instructive in learning how to write idiomatic code in that language. I continue to learn more about the best way to express patterns as I work on my own implementation. I'd recommend the journey to any professional developer for this side-benefit alone.
Though there's probably a similar claim to be made for the Monkey-language from Torsten Bell, via his books on compilers and interpreters.
https://monkeylang.org/
> Lox must have the highest ratio of (implementations : production usage) of any language on the planet.
Maybe! It's definitely getting there. I suspect "semi-arbitrary subset of C" still has me beat but who knows for how much longer.
All praise Bob!
On a more serious note, have you thought about trying to aim lightning at the same spot again and write another book about implementing something most programmers take for granted?
I've definitely thought about writing a third book. I don't know if it would be about "something most programmers take for granted". I'm more interested in writing about whatever happens to excite me the most at that time.
I may be projecting, but I feel like the kind of person to get excited about crafting interpreters wod also get excited about crafting databases or OSes.
Maybe, but alas I don't know enough about either of those to write those books.
Hey Bob just made an account to let you know how much I appreciate both of your books and how much of an influence you've made on my life choices
Just want to hopefully make you feel warm inside knowing you've made a really big difference to people's lives
Thanks for being you
A type system sequel to Crafting Interpreters, please. Or a JIT compiler sequel.
I'd imagine cool is up there as well: https://nguyenthanhvuh.github.io/class-compilers/cool.html
I think Brainfuck might be more widespread. :)
That's so many languages and implementations that this could be used as a new Programming Language Popularity Ranking, with a bias towards languages people want to use or learn :D.
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
I'd read your article, and it was lovely. It nudged me to just go unsafe and implement some of the data structures from scratch.
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.
> 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'll echo this recommendation.
I haven't gone through Crafting Interpreters yet (it's on the bookshelf) but I did go through a big chunk of Building Git and instead of Ruby I did it in Rust, to get back into the language and go a little deeper.
It was really great and it gave me a lot more than if I'd just copy paste the code as you say.
My only issue with Crafting Interpreters is that it relies too much on writing code and then explaining it instead of getting the concepts across first and then providing the code. Another thing I disliked was some code was structured in a way that it would go well with concepts that came further down the implementation which can lead to confusion since it seems overcomplicated/overabstracted at first.
One of the biggest challenges with writing is linearizing: deciding what order to present the material so that it makes the most sense.
There's really no perfect solution. Some readers prefer bottom up where they are given individual pieces they can understand which then get composed. Others prefer top down where they are given the high level problem being solved in terms of intermediate steps which then get incrementally defined. Some want to see code first so that they have something concrete to hang concepts off of. Others want concepts first and then to see the code as an illustration of it.
This is made even harder with Crafting Interpreters because the book's central conceit is that every line of code in the interpreters is shown in the book. There's nothing left to the reader. And, also, the book tries to give the user a program they can compile and run as often as possible as they work through things.
I did the best I could, but there are definitely some places where it's really hard to figure out a good order. Sometimes the book explicitly says "sorry, this won't make sense but bear with me and we'll circle back".
Also, at the macro structure, the entire book is organized into two parts where the first one is higher-level and more concept driven and then the second part circles all the way back to build the entire language from scratch again but at a much lower level of abstraction.
I appreciate your feedback. It's a hard problem and a skill I'm always trying to improve.
Just to throw a positive word out there from one of the quiet majority of your readers, I think you absolutely nailed it with Crafting Interpreters.
It's by far the best introductory book on this topic I've come across yet. It's a fun read and completely demystifies the "magic" of how interpreters work.
Thank you! :D
Thanks for the answer! While my comment pointed out some issues I had, I do wanna make it clear that I still found it incredibly helpful and its probably the best practical introduction to the topic out there, so huge respect to you.
I think it also heavily depends on the reader. I also followed the book in a different lang than Java and only then I had the aforementioned problems.
As another one of your quiet readers, more specifically a soon-to-be uni grad who's at a crossroads about choosing to pursue my interests in either game engineering or systems engineering as a career path in this hellfire of a world we live in, I ADORE both your books. I think your writing consistently does an amazing job of motivating a practical yet elegant design from first principles.
And yeah, as someone who's trying to start writing a blog on ~technical topics, I get what you mean. Not every explanation can be linearized perfectly, because sometimes two concepts are coupled, motivating and influencing each other's design. Sometimes there are just, so to say, dependency cycles in the "knowledge graph". Can't turn that into a directed acyclic graph no matter how hard you try. The most prudent solution probably is just resolving the cycle iteratively by starting somewhere.
I love the code-first approach. It was a revelation to me when I first read Mark Pilgrim's Dive Into Python (https://diveintopython3.net/).
My minor nit pick is that it uses mostly the Java language to implement a Java-like language. What have we gained? Surely something Python-like in C would be more rewarding, one would be gaining a level of abstraction.
> Surely something Python-like in C would be more rewarding, one would be gaining a level of abstraction.
That's the second half of the book.
My apologies, that does indeed seem like a reasonable way of doing it.
Also, I should note that even in the first half of the book, the language isn't Java-like. It has Java-ish syntax, but the semantics are much closer to JavaScript/Python/Lua.
In the first half, what we gain from implementing it in Java is mostly the garbage collector. The rest of the static and runtime semantics basically have to be implemented from scratch on top of the JVM.
There is significance coverage of OOP features, hence my Java-like comment. I would have personally left OOP out for a beginner book, it isn't really fundamental. Another advantage to using Java in the first half, could be to use Java closures to implement Lox closures.
> I would have personally left OOP out for a beginner book, it isn't really fundamental.
This was a deliberate choice. Most intro compiler/interpreter books don't do OOP. But most languages in wide use today are object oriented. That felt like a significant gap to me. One of the main goals with my book is to give people insight on how the languages they actually use work under the hood. Skipping objects and method dispatch would limit that.
did you not want anyone to ever find rulox on github? it has no descriptive information about it in the repo
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...
There's also more recent implementations such as https://github.com/chc4/samsara (quite similar to https://github.com/pebal/sgcl , which is for C++. Both implement a concurrent tracing algorithm which allows for reduced latency compared to a naïve stop-the-world GC).
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.
Thanks for sharing! That's a much more interesting project compared to mine xD. I had the intuition that rust-gc could be implemented in a simpler fashion by not being generic. Glad to see someone actually had it done.
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.
haha, glad to know that I'm not the only one
I get tripped up by variance too and thinking about that stuff is literally my job. If it helps, I wrote a blog post recently about Go's type system and it happens to touch in variance in a way that might help it click:
https://journal.stuffwithstuff.com/2023/10/19/does-go-have-s...
The very first sentence of that article got me excited:
>I’ve been noodling on a static type system for my current hobby language.
As an inveterate language tinkerer for decades, Crafting Interpreters is like the intersection of Class A narcotic addiction, Feynman level understanding and religious enlightenment. It's in my top 3 favourite books of all time.
If you were to /happen/ to write an extension/follow up book that addressed static typing, then I can personally guarantee at least one sale.
Independent of that, thanks for the work as it stands. My copy is healthily dog-eared and still gets lugged around on holidays for refresh reading.
Thanks for sharing. I've enjoyed every single piece of your writing so far. This will be in the arsenal of materials I'll use when I again get confused about variance.
Definitely not the only one. I am not a stupid person*, but every single time I read the section on variance in the Nomicon I feel like an utter moron.
*source: trust me bro
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.
Nice, thanks for sharing. Definitely gonna look into how you do it, I couldn't get as close to clox like you did
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.
If someone else depends on this project, I'd definitely not implement the questionable stuff. You're right that proving whether it's safe can be lots of fun, and I'm planning to try it out.
Based on what I've read, it's entirely possible. If my Rust knowledge is correct, there are 2 things that have to be proven - the object's lifetime and the borrow rules.
Proving the lifetime can be done at compile-time based on what was discussed in these articles https://without.boats/tags/shifgrethor/. But that still leaves us with proving that we don't violate the borrow rules. AFAIK, the only way to do it in my implementation is with Cell and RefCell enforcing the borrow rules at runtime.
Before removing all the safety checks, I actually used Gc<RefCell<T>> for mutable objects, so the borrow rules were enforced but not the lifetime. However, I decided to remove RefCell<T> to have some fun and see how I could shoot myself in the foot.
You don't want to use `RefCell` for something like this- it is still too strict for Lox's semantics.
Doing this properly means putting `GcData`'s fields (and/or `ObjFun`/`ObjClosure`/etc's fields) in plain `Cell`s, and using that for all mutation without ever forming any `&mut` references.
Can you elaborate on why it's too strict? I got RefCell working and passed to test suite just fine. Maybe the suite don't take into account some that's specific to Rust.
If I remember correctly, there were some panics cause by RefCell borrows. But those got sorted out once I handled borrowing in the correct order.
I guess a better way to put it is, if you got Lox working with RefCells, then you didn't need RefCells (or their overhead) to begin with - you must not have been holding those dynamic borrows any longer than a single VM instruction, or something close to that.
Yes, the borrows were only held for roughly a single instruction. But I don't see how you can mutate the Table/HashMap of fields in an object with only Cell tho
Technically it is possible to swap the HashMap out of the Cell, mutate it, and put it back, but that is maybe even worse than the RefCell.
What I would expect a production language implementation to do is build its own table that integrates its solution for interior mutability into its design. There are several other things (e.g. iterators, concurrent GC) that will also contribute to the need for a custom table, so (again for a production language) this is not too crazy.
Ah! I could imagine a table backed by an array of Cell since all the possible values in that table implement Copy. There is probably a better way for the table to have interior immutability. But I think I get what you were saying.
Just for reference, the gc-arena crate (https://github.com/kyren/gc-arena) we use in Ruffle's Actionscript 1/2/3 interpreters and across the entire engine, does this. As far as we know, it's safe and sound, at the cost of some limitations, mainly: to compile-time prevent sweeping while holding onto Gc references, every struct and function touching Gc objects passes an extra 'gc lifetime. And not being able to run the GC at arbitrary time can be major issue depending on what you're doing; in Ruffle we incrementally collect between frames and pray that no single frame will ever allocate enough to OOM in the middle of it :)
And yeah, RefCells everywhere.
Thanks a lot for the insight. I think if I do it the way shifgrethor did, I can have GC at arbitrary time. But I'm not so sure about that.
With the way Rust may perform optimizations on the assumption of no alias, I guess there's currently no way to avoid RefCell if we want to be 100% on the safe side.
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.
Yeah true, this breaks all sorts of contracts that we have with Rust xD. But if mark-and-sweep is implemented correctly, then no reference is ever held across the GC. Though, there's gonna be lots of pain debugging when you got it wrong, speaking from experience.
Do you have any resources about Rust inlining and the issues it might cause? I'd love to read more about that.
I would be really careful with those deref methods. They return references, not pointers, which means you need to follow the Rust rules:
- You can have any number of simultaneous readers,
- Or one writer and no readers.
- But if you ever break these rules, the world may burn.
Using unsafe and violating these rules is one of the cases where the Rust compiler can inflict worlds of misery: Incorrect code generation, CPUs seeing different versions of the same memory location, etc., depending on the exact context. Once you use "unsafe" and break the rules, Rust can be more dangerous than C. Rust even reserves the right to generate code using "noalias" (except doing so often triggers LLVM bugs, so it's usually turned off).
"Undefined behavior" means "anything at all can happen, and some of it is deeply weird and awful and counterintuitive."
You could enforce the borrowing rules at runtime by using std::cell::Cell in your heap objects, which is exactly what it exists for. Or you could package everything inside a tiny core module and audit it extremely carefully.
You would probably want to use RefCell instead of Cell. It allows you to safely upgrade into a &mut using only a constant reference to RefCell, but it dynamically verifies that it's actually safe using ref counting. The ref counting also isn't too expensive since it isn't atomic.
> (except doing so often triggers LLVM bugs, so it's usually turned off).
It's been enabled for a couple years now.
I'm aware of all the issues mentioned. But for this particular project, I simply don't care as long as it passes Lox's test suite xD. I went this path just to see how easy it is to get tripped by unsafe while knowing that there's a technique to get safety with Pin<T> that this can get refactored into. I actually implemented this with Cell and RefCell but didn't find that interesting.
Mark and sweep doesn't stop you from holding references across GC.
If you write e.g.
``` let obj = some_object(); let len : &mut usize = &mut obj.len; // deref_mut trigger_gc(); use(*len); ```
then you held a reference across the GC, and while it's mark/sweeping created an aliases `&mut` to `len`.
Inlining was mention just because it causes function bodies to be splatting together, and so puts together code that is fine in isolation in a way that may allow Rust to observe UB: if `trigger_gc` was inlined for example then Rust has more information and code available at once, and might use the knowledge to apply some optimizations that are invalid because you caused UB.
Actually, looking at your code the much larger issue is that nothing stops you from doing
``` let obj = some_object(); let obj2 = obj.clone(); let len1 = &mut obj.len; let len2 = &mut obj2.len; let n = *len1; *len2 = 0; println!("{n}"); // what does this print? ``` because your Deref mut are just creating unconstrained borrow from pointer types that you can copy. This is almost definitely going to cause you bugs in the future, since it opens you up to accidentally writing iterator invalidation and other issues (and even worse than C++ does, because C++ doesn't optimize references as heavily as Rust does borrows)
Yeah, it's a self-enforced contract that objects of type Gc<T> are only ever touched by the virtual machine, but I get your point.
The issue is that it's a simple footgun as soon as you start adding non-trivial native methods (say, string methods, array.map etc). The only way to make sure that they don't exist is removing the DerefMut impl entirely.
It's not just that it's possible to break the code, but that lack of any checks makes it impossible to detect at either compile-time or runtime and have it "appear to work".
One way to solve it to remove the DerefMut implementation and have it work more like Rc - as in, the user is forced to write `Gc<Cell<T>>` or `Gc<RefCell<T>>` if they want mutability. This solves the aliasing borrows issue at the cost of extra runtime checks with RefCell (and still doesn't prevent you from unsoundly calling `sweep()` while holding a Gc)
I implemented exactly what you were saying here (https://github.com/ltungv/rox/commit/6a611e7acb3b36d0a3a4376...). But where's the fun in that?
With a borrowchecker what does GC let you do that is more ergonomic? I have never used a borrowchecked and garbage colected language so I have no experience to consult.
The borrow-checker helps when you're writing Rust code. But when writing an interpreter for another language, you kinda have to support its semantics. In Lox, there's no move semantic, no borrowing, almost everything is a heap-allocated object, variables can alias, etc. Thus, you need to have a way to manage the memory of the implemented language without the borrow-checker. Here, the borrow-checker can help with implementing the GC safely and correctly, but I didn't utilize it.
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.
This was used in linux kernel and they were removing it later because it was a huge pain as far as I can remember. Seems like it causes problems because entire system is built assuming stack/heap work in a certain way.
Oh right. I read about this once or twice and have never looked at it again. I've made the (wrong) assumption that this function needs some compile-time help. Is it all done at runtime? Or does that depend on the actual C implementation?
Stack allocation is always done at runtime. Baring special optimizations, the CPU and the code work together to (stack grows downward) decrement the CPU stack pointer register. This register keeps track of where the bottom of the stack is.
What is done at compile time by the compiler, is calculating the amount to decrement the CPU stack pointer register at runtime for every stack variables.
The compiler and alloca must work together, because optimization can easily break something here. For example, when a function return, the stack pointer register better be restored properly. Furthermore, in Rust you must not forget to call Drop::drop() for all types that have such a destructor.
I mean it's basically the fastest allocation possible. It's amazing under a very very unique situation.
- you need a lot of memory
- it needs to be as fast as possible
- it's a leaf function that can never call another function
99.9% of the time those aren't all true.
There's another reason: we need to do string stuff and we absolutely can't stall. Malloc always has some chance of stalling due to heap fragmentation. The leaf function requirement is also not necessary. You just have to make sure you don't alloca too much memory given how much is remaining on the stack and roughly how much memory you know subsequent calls will take.
It's not all that much worse than using a huge, static stack allocation. In fact, there are cases where alloca is safer since you can take into account how much stack memory you already have available before incrementing the stack pointer.
With a huge static stack allocation the stack check must be done within a parent function instead of within the same function.
In any case it is up to you to do the stack check. Though alloca can easily be wrapped by a function running the check.
In Rust I would write a check stack function that takes a function/closure as parameters. Within the closure, you are guaranteed to have at least the requested stack space.
The compiler will inline it all nicely, while preserving the semantic of the stack allocation.
Why does it have to be a leaf function?
So the massive stack grab isn't permanent.
Conceptually, if the compiler could just inline all of the child calls, it's fine. But if this call won't return for a long time, or may be called again (even worse). You're setting aside stack that you'll never get back. Which is a memory leak, and your program will crash.
The stack grab is as permanent as any other stack variable. There is nothing special about it. The only difference is that you can decide at runtime how much to add to the current stack frame.
If the memory's lifetime correctly coincides with the function (which is why you might use alloca in the first place), I don't see how this would be a memory leak nor why it would lead to a crash. Maybe on systems which limit stack size...?
just don't do this.
if a() is a leaf (or can be trivially inlined) it's fine!on the other hand, if a() calls something else, that's complicated, it's way way harder to figure out why you're crashing. I think you'll segfault as a() eventually overwrites malloc'ed memory. but different systems are going to have different characteristics.
It's not that you can't, you just have to be real damn smart and make sure no one ever messes with your code.
or you can just make sure it's a leaf. much easier rule, much easier to explain.
Your example behaves the same with or without alloca.
It will run until it runs out of stack. Or it might just run forever because the compiler optimized it as an infinite loop.
In any case, same behavior.
True. How would you modify it to get the point across?
Or am I crazy, and there is no point to being careful with alloca?
Maybe if alloca is used with a runtime value uncapped, a user could then trigger a stack overflow with too big of an allocation. This is the same problem when allocating on the heap, with the difference that the heap is a few order of magnitude larger.
That is really the only difference between `in foo[...N] = ...N` and alloca(n). alloca works with a value computed at runtime. And this value could be from an input.
That reasoning leads me to conclude the function should be short lived or the memory in use by all child functions, rather than it has to be a leaf function?
yeah. Leaf is a good rule of thumb, but if you need a little helper to do something it's generally fine.
you really do need confidence the little helper can be fully inlined. if the helper is out of your control, and someone greatly expands its responsibility, it can suck.
So, yeah, effectively a leaf.
Additionally, recursion and function pointers (including dynamic dispatch) are the other two "normal" language features that can defeat static stack analysis. There are techniques for working around this (bounded annotations, languages with strong types can narrow potential dispatch options), but it's a little harder.