My experience crafting an interpreter with Rust (2021)
ceronman.com
ceronman.com
Is the first half of the book boring or is it just me?
I wasn't really expecting the scanner/lexer to be interesting, but the interpreter part as well feels like an absolute slog. I started with a lot of enthusiasm but just couldn't keep going after implementing functions. I downloaded someone else's JsLox implementation and was planning on just skipping to the VM part of the book and hopefully would find it more engaging.
I also am a pretty jr developer. I have about 5 years experience since I started learning to code so I just may not "get" it yet. But I found writing the interpreter to be incredibly boring.
Crafting Interpreters, IMHO, is the most accessible book on the subject. If you didn't find the implementation of the first part exciting, I would suggest to probably ignore the book code after reading the text and implement it yourself, and later compare with the book implementation. I encountered several pleasent surprises using this approach.
i really don't know how to describe this, but if you have no specific goal, you are not going to do, or learn how to do, anything. why do you deeply, deeply want to learn how to write an interpreter? what problem will writing an interpreter solve for you?
I think it has already yielded benefits in my better understanding of environments and lexical scoping, grammars + LALR. It has just given me different conceptual tools that I can use to learn new concepts.
A concrete example was that I was playing around with a recursive prompt with ChatGPT the other day trying to figure out if I could get it to write a more specific version of a prompt I had given it and sort of bootstrap its way to a very specialized "train-of-thought". I was thinking about grammars and how recursive prompting is sort of like a meta-grammar. It's just a new way of thinking about things.
Yeah this can often be a problem because the borrow checker doesn't kick in until the refactoring is done and no other errors are left.
It does take time and effort to really internalize these rules. But eventually you should be able to have a mental model of how ownership and borrowing work; consider what owns the data, if it can be borrowed within statically known scopes, will it need to mix sharing and mutation, and then apply Rust-specific types and design patterns to match.
Conversely, there are things that you just can't do, like using temporary references for parent-child relationships. Knowing this will save you time from even trying.
Perhaps learning materials need to be more explicit about it. For example, I suspect lots of people are discovering the limitation of self-referential structs the hard way.
I agree that it should be more prominent in some place. I got most of my info about that in StackOverflow and I tried using a hashmap to simulate the tree structure, but I don't think I finished that one.
I wrote a mini Lisp interpreter in Rust while following along with the book! I ended up using a generational arena to store objects too, but I used a "slotmap", which I wrote myself but is similar to the slotmap crate (see link below).
I am surprised and also sad that the arena had such a large performance impact, because it's a very nice pattern and lets you completely avoid unsafe code and raw pointer wrangling.
I do wonder whether changes could have been made to speed up the safe arena style object store! Ideally accessing objects would be as fast as a regular index into a vector which should be pretty fast.
Boxing the inner object in the GcHeader is going to make accessing objects from the Gc do some extra pointer chasing, I think you could avoid this and the dynamic dispatch in general using enums and static generics!
Anyways this was fun to read, thanks!
The issue used to be with LLVM, yes, but that appears to be solved (see Clang's 'musttail' attribute). Instead it's more about language design. Constructors, destructors, and all of the fancy language features Rust has must work with this new feature, with no changes being visible elsewhere.
I had no idea about that. Is there a specific reason why that choice was made?
WASM doesn't support guaranteed TCE yet (it's a proposal), and that's an important target for Rust.
Goto has been iirc a point of discussion from the language design pov for Rust. I don't think it promotes good design for most applications but ymmv.
Performance, although this possibly depends on your compiler, whether you use PGO, and similar finicky issues.
Example: https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e...
Some prior HN discussion: https://news.ycombinator.com/item?id=18678920
Another example where goto is relevant is implementing finite automata. A (very short) paper from 1988 that discusses three different ways of implementing a finite state machine is "How (Not) to Code a Finite State Machine". The documentation of RE2C may be even more interesting: https://re2c.org
RE2C is a program that compiles finite automata into C, Go, or Rust code. It provides many implementation strategies: it can make use of computed or labelled gotos when the language provides them.
Implementing pushdown automata comes with similar issues.
I suspect if you could use UNION better and be the same as Enum in Rust you could do us a favor! Also I wish I could do this easily:
enum Tag {
Int,
Bool
}
enum Data {
Int(Vec<i32>),
Bool(Vec<bool>)
}
struct Val {
tag:Tag,
data:Data
}
let n = val.as_i32::<Tag::Int>(&self) -> Vec<i32> outer: loop {
loop {
let res = self.interpreter_loop(…);
match res {
Continue => {}
Return => { break 'outer; }
Exception => { break; }
}
}
I also made sure that the interpreter_loop call had an inline pragma, but that was otherwise a naive switch-case for the instructions. I didn’t find a way to make a template interpreter with safe Rust.You can try the interpreter in the browser for computing the prime numbers: https://loda-lang.org/edit/?oeis=40
The language is "LODA", a math AI, using OEIS as training data. https://loda-lang.org/
If you weren't going to expose clox to the web or other untrusted input (and why would you), it's not a concern.
You can do both overflow and underflow checks without any efficiently loss by using virtual memory page faults to "catch" the resulting access (which in any case is a fatal error).
You definitely don't need any expert knowledge though! Also following the book will increase your C knowledge as you go (at least in the second half).
A simple Lisp Interpreter in Rust