4 ms·

My experience crafting an interpreter with Rust (2021)

176 points by airstrike 4y ago

nsajko 4y ago
A downside of Rust for applications like virtual machines is that it doesn't have a goto statement. Ideally, both a labelled and a computed goto would be available in the language.
- chc4 4y ago
  Not only does it not have computed goto (almost no languages do, tbh), it also doesn't have guaranteed tall-call elimination or allow you to use the GHC calling convention. Which are more egregious, imo.
  - LoganDark 4y ago
    Why is the lack of "GHC calling convention" egregious? I've never heard this before as an argument against Rust.
  - margorczynski 4y ago
    I was looking for that (tail recursion) and it seems the story and feature request goes back years ago and still hasn't been added. Somewhere someone wrote that the issue is with LLVM but can't the tail call be transformed to an iteration before that?
    - shadowofneptune 4y ago
      The most practical uses of recursive functions are those that cannot be easily eliminated. For an interpreter, it could mean dozens of functions all calling each other in a pattern determined at runtime. 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.
      - User23 4y ago
        Tail call optimization isn’t just for recursive functions. Any tail call can be optimized to little more than a jump, which makes implementing threaded code or similar much nicer. Your compiled code will just push the instruction pointer along an array of opcodes in a tight loop with no function call overhead.
        shadowofneptune 4y ago
        Exactly, though I do not see how it is not an example of recursion.
  - bmitc 4y ago
    > it also doesn't have guaranteed tall-call elimination I had no idea about that. Is there a specific reason why that choice was made?
    - pornel 4y ago
      AFAIK guaranteed TCE wasn't supported in LLVM at all when Rust was still being designed and considered adding it. Support for musttail in LLVM has been added relatively recently. WASM doesn't support guaranteed TCE yet (it's a proposal), and that's an important target for Rust. https://github.com/rust-lang/rfcs/issues/2691 https://github.com/rust-lang/rfcs/issues/2691
  - kzrdude 4y ago
    `become` is still a reserved keyword for this in Rust, so there's that.
- ufo 4y ago
  In what situations do you miss goto the most, when implementing a VM?
- mughinn 4y ago
  As someone not versed in Virtual Machine development, is goto so important? What do you gain by using it?
  - c0balt 4y ago
    Goto is quite a powerful tool for having a full, imperative grip on control flow. It is quite often useful due it's simple yet powerful ability to "just" work. Virtual machines may often encounter situations where a tight control over the flow can be advantagous for performance etc. reasons. 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.
  - nsajko 4y ago
    > What do you gain by using it? 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-efficient-dispatch-tables https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e... Some prior HN discussion: https://news.ycombinator.com/item?id=18678920 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 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.
- mamcx 4y ago
  I think a bigger one from what I have looked is the complexity of (en^de)code bytes around. 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>
  - celeritascelery 4y ago
    There are some crates that let you do that. For example enum-ptr https://crates.io/crates/enum-ptr https://crates.io/crates/enum-ptr
- kaba0 4y ago
  I solved it in case of an interpreter with 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.
habibur 4y ago
.
- khochesh_kushat 4y ago
  Seems up to me at the moment.
- detaro 4y ago
  nope, works
fuzzy_biscuit 4y ago
Does Crafting Interpreters require preexisting C knowledge? I'm curious to follow the book, but my experience with X is beginner level at best.
- crop_rotation 4y ago
  It doesn't. Half of the book is not even in C (The book is half java (simpler interpreter), half C (bytecode compiler + VM)). The book explains what the code needs to do very very clearly, so even without looking at the C code you would gain a lot of value.
- erichocean 4y ago
  I've been teaching a class the lasts few weeks with a dozen people who have never programmed before using that book. It's going well.
- bmitc 4y ago
  I have the book but haven't gone through it. When I do eventually get to it, I will probably ignore all of the implementation languages, instead choosing something like F# or Racket. You could do something similar.
- chlorion 4y ago
  I think you should at least understand the basic concepts like loops, variables, pointers and whatnot before trying to follow the book, otherwise it may be a little rough. 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).
dhosek 4y ago
I’m curious about the extent to which DOS is a concern for an interpreter like this. I can see it be an issue if you’re exposing a service to external actors, but how big of a concern is it really in this context?
- mastax 4y ago
  I'm going to assume that at least one popular interpreter uses a weak hash function for its hashtables/objects, and I haven't ever heard about it being an issue.
- loeg 4y ago
  It was a big problem for web-facing services in interpreted languages "back in the day." All the dynamic languages basically fixed this problem ten years ago (or 20 years ago for Perl): https://lwn.net/Articles/474912/ https://lwn.net/Articles/474912/ If you weren't going to expose clox to the web or other untrusted input (and why would you), it's not a concern.
- rstuart4133 4y ago
  I went down that rabbit hole myself after reading the article. This sums up the situation: https://sudonull.com/post/127497-Non-cryptographic-hash-functions-and-DoS-attack-on-them https://sudonull.com/post/127497-Non-cryptographic-hash-func...
BoardsOfCanada 4y ago
> I would often write huge refactorings thinking that they would be a solution to a borrow checker error, just to get another one at the end of the refactoring. 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.
- winrid 4y ago
  This was my experience too. Although, it's less of an issue now. It was definitely frustrating, though.
- pornel 4y ago
  Proficiency in Rust requires learning what won't work, rather than trying various things until they compile. Borrow checking is a set of rules to design for, rather than an oracle to test against. 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.
  - jbrr25 4y ago
    Count me in. I was doing the advent of code and tried to solve one problem with a tree that had parent references. Much thinking was done trying to please the borrow checker with no results, add some inner mutability and I got stucked. 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.
crop_rotation 4y ago
Crafting interpreters is the best compiler/interpreter book I read. I had tried both the Dragon book and Andrew Appel's "Modern Compiler Implementation in Java" and Crafting Interpreters feels like a masterclass in how to write an accessible book. The author just has a special talent for explaining complex concepts simply.
- green_man_lives 4y ago
  I have a question about the book. I haven't been able to ask anyone else because I don't know anyone else who is working through the book. 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.
  - shadowofneptune 4y ago
    Compiler writing does involve a fair amount of tedium. I don't think it has anything to do with experience, either. It's why tools like Yacc, Lemon, or ANTLR exist.
  - crop_rotation 4y ago
    It's possible the subject itself is "boring", and I have found other compiler books to mostly be intolerable. 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.
  - ufo 4y ago
    Could be worth a try. I didn't find the first half as boring as you did, but I did find the second part more fun.
erichocean 4y ago
> While the clox compiler does prevent a lot of these cases, it does not prevent stack overflows. The author intentionally decided to skip this check because it would require a lot of boilerplate code. Real-world interpreters using unsafe structures like these must absolutely do it though. 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).
- loeg 4y ago
  Only if under/overflow can be bounded. E.g., with stack probing.
chlorion 4y ago
This is really interesting! 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! https://crates.io/crates/slotmap https://crates.io/crates/slotmap
qubit0ne 4y ago
https://github.com/vishpat/lisp-rs https://github.com/vishpat/lisp-rs A simple Lisp Interpreter in Rust
neoneye2 4y ago
I have also made an interpreter using Rust. https://github.com/loda-lang/loda-rust/tree/develop/rust_project/loda-rust-core/src https://github.com/loda-lang/loda-rust/tree/develop/rust_pro... You can try the interpreter in the browser for computing the prime numbers: https://loda-lang.org/edit/?oeis=40 https://loda-lang.org/edit/?oeis=40 The language is "LODA", a math AI, using OEIS as training data. https://loda-lang.org/ https://loda-lang.org/
loeg 4y ago
I like how the author identified that his program was slower than he thought it should be, profiled, and identified some low-hanging fruit. He tried quite a lot of things, some of which panned out and some of which did not. Interpreters and Rust aside, this is a perfect example of software performance work.

176 points by airstrike 4y ago

A downside of Rust for applications like virtual machines is that it doesn't have a goto statement. Ideally, both a labelled and a computed goto would be available in the language.

chc4 4y ago
Not only does it not have computed goto (almost no languages do, tbh), it also doesn't have guaranteed tall-call elimination or allow you to use the GHC calling convention. Which are more egregious, imo.
- LoganDark 4y ago
  Why is the lack of "GHC calling convention" egregious? I've never heard this before as an argument against Rust.
- margorczynski 4y ago
  I was looking for that (tail recursion) and it seems the story and feature request goes back years ago and still hasn't been added. Somewhere someone wrote that the issue is with LLVM but can't the tail call be transformed to an iteration before that?
  - shadowofneptune 4y ago
    The most practical uses of recursive functions are those that cannot be easily eliminated. For an interpreter, it could mean dozens of functions all calling each other in a pattern determined at runtime. 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.
    - User23 4y ago
      Tail call optimization isn’t just for recursive functions. Any tail call can be optimized to little more than a jump, which makes implementing threaded code or similar much nicer. Your compiled code will just push the instruction pointer along an array of opcodes in a tight loop with no function call overhead.
      - shadowofneptune 4y ago
        Exactly, though I do not see how it is not an example of recursion.
- bmitc 4y ago
  > it also doesn't have guaranteed tall-call elimination I had no idea about that. Is there a specific reason why that choice was made?
  - pornel 4y ago
    AFAIK guaranteed TCE wasn't supported in LLVM at all when Rust was still being designed and considered adding it. Support for musttail in LLVM has been added relatively recently. WASM doesn't support guaranteed TCE yet (it's a proposal), and that's an important target for Rust. https://github.com/rust-lang/rfcs/issues/2691 https://github.com/rust-lang/rfcs/issues/2691
- kzrdude 4y ago
  `become` is still a reserved keyword for this in Rust, so there's that.
ufo 4y ago
In what situations do you miss goto the most, when implementing a VM?
mughinn 4y ago
As someone not versed in Virtual Machine development, is goto so important? What do you gain by using it?
- c0balt 4y ago
  Goto is quite a powerful tool for having a full, imperative grip on control flow. It is quite often useful due it's simple yet powerful ability to "just" work. Virtual machines may often encounter situations where a tight control over the flow can be advantagous for performance etc. reasons. 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.
- nsajko 4y ago
  > What do you gain by using it? 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-efficient-dispatch-tables https://eli.thegreenplace.net/2012/07/12/computed-goto-for-e... Some prior HN discussion: https://news.ycombinator.com/item?id=18678920 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 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.
mamcx 4y ago
I think a bigger one from what I have looked is the complexity of (en^de)code bytes around. 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>
- celeritascelery 4y ago
  There are some crates that let you do that. For example enum-ptr https://crates.io/crates/enum-ptr https://crates.io/crates/enum-ptr
kaba0 4y ago
I solved it in case of an interpreter with 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.

habibur 4y ago

khochesh_kushat 4y ago
Seems up to me at the moment.
detaro 4y ago
nope, works

fuzzy_biscuit 4y ago

Does Crafting Interpreters require preexisting C knowledge? I'm curious to follow the book, but my experience with X is beginner level at best.

crop_rotation 4y ago
It doesn't. Half of the book is not even in C (The book is half java (simpler interpreter), half C (bytecode compiler + VM)). The book explains what the code needs to do very very clearly, so even without looking at the C code you would gain a lot of value.
erichocean 4y ago
I've been teaching a class the lasts few weeks with a dozen people who have never programmed before using that book. It's going well.
bmitc 4y ago
I have the book but haven't gone through it. When I do eventually get to it, I will probably ignore all of the implementation languages, instead choosing something like F# or Racket. You could do something similar.
chlorion 4y ago
I think you should at least understand the basic concepts like loops, variables, pointers and whatnot before trying to follow the book, otherwise it may be a little rough. 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).

dhosek 4y ago

I’m curious about the extent to which DOS is a concern for an interpreter like this. I can see it be an issue if you’re exposing a service to external actors, but how big of a concern is it really in this context?

mastax 4y ago
I'm going to assume that at least one popular interpreter uses a weak hash function for its hashtables/objects, and I haven't ever heard about it being an issue.
loeg 4y ago
It was a big problem for web-facing services in interpreted languages "back in the day." All the dynamic languages basically fixed this problem ten years ago (or 20 years ago for Perl): https://lwn.net/Articles/474912/ https://lwn.net/Articles/474912/ If you weren't going to expose clox to the web or other untrusted input (and why would you), it's not a concern.
rstuart4133 4y ago
I went down that rabbit hole myself after reading the article. This sums up the situation: https://sudonull.com/post/127497-Non-cryptographic-hash-functions-and-DoS-attack-on-them https://sudonull.com/post/127497-Non-cryptographic-hash-func...

BoardsOfCanada 4y ago

> I would often write huge refactorings thinking that they would be a solution to a borrow checker error, just to get another one at the end of the refactoring. 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.

winrid 4y ago
This was my experience too. Although, it's less of an issue now. It was definitely frustrating, though.
pornel 4y ago
Proficiency in Rust requires learning what won't work, rather than trying various things until they compile. Borrow checking is a set of rules to design for, rather than an oracle to test against. 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.
- jbrr25 4y ago
  Count me in. I was doing the advent of code and tried to solve one problem with a tree that had parent references. Much thinking was done trying to please the borrow checker with no results, add some inner mutability and I got stucked. 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.

crop_rotation 4y ago

Crafting interpreters is the best compiler/interpreter book I read. I had tried both the Dragon book and Andrew Appel's "Modern Compiler Implementation in Java" and Crafting Interpreters feels like a masterclass in how to write an accessible book. The author just has a special talent for explaining complex concepts simply.

green_man_lives 4y ago
I have a question about the book. I haven't been able to ask anyone else because I don't know anyone else who is working through the book. 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.
- shadowofneptune 4y ago
  Compiler writing does involve a fair amount of tedium. I don't think it has anything to do with experience, either. It's why tools like Yacc, Lemon, or ANTLR exist.
- crop_rotation 4y ago
  It's possible the subject itself is "boring", and I have found other compiler books to mostly be intolerable. 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.
- ufo 4y ago
  Could be worth a try. I didn't find the first half as boring as you did, but I did find the second part more fun.

erichocean 4y ago

> While the clox compiler does prevent a lot of these cases, it does not prevent stack overflows. The author intentionally decided to skip this check because it would require a lot of boilerplate code. Real-world interpreters using unsafe structures like these must absolutely do it though. 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).

loeg 4y ago
Only if under/overflow can be bounded. E.g., with stack probing.

chlorion 4y ago

This is really interesting! 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! https://crates.io/crates/slotmap https://crates.io/crates/slotmap

qubit0ne 4y ago

https://github.com/vishpat/lisp-rs https://github.com/vishpat/lisp-rs A simple Lisp Interpreter in Rust

neoneye2 4y ago

I have also made an interpreter using Rust. https://github.com/loda-lang/loda-rust/tree/develop/rust_project/loda-rust-core/src https://github.com/loda-lang/loda-rust/tree/develop/rust_pro... You can try the interpreter in the browser for computing the prime numbers: https://loda-lang.org/edit/?oeis=40 https://loda-lang.org/edit/?oeis=40 The language is "LODA", a math AI, using OEIS as training data. https://loda-lang.org/ https://loda-lang.org/

loeg 4y ago

I like how the author identified that his program was slower than he thought it should be, profiled, and identified some low-hanging fruit. He tried quite a lot of things, some of which panned out and some of which did not. Interpreters and Rust aside, this is a perfect example of software performance work.