My experience crafting an interpreter with Rust (2021) • Hacker News Board

Re: My experience crafting an interpreter with Rust (2021)

#31

Post by pornel » Sun, Mar 26, 2023, 1:02 AM UTC

bmitc wrote: post #25

chc4 wrote: post #3

Earlier quoted context omitted.

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.

> 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?

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

Re: My experience crafting an interpreter with Rust (2021)

#32

Post by zabzonk » Sun, Mar 26, 2023, 1:04 AM UTC

green_man_lives wrote: post #14

crop_rotation wrote: post #12

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.

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 downl…

perhaps you had no motivation for writing an interpreter? almost all programming tasks that are of any interest require you to have some special problem to solve.

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?

Re: My experience crafting an interpreter with Rust (2021)

#33

Post by c0balt » Sun, Mar 26, 2023, 1:12 AM UTC

mughinn wrote: post #19

nsajko wrote: post #2

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.

As someone not versed in Virtual Machine development, is goto so important? What do you gain by using it?

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.

Re: My experience crafting an interpreter with Rust (2021)

#34

Post by chlorion » Sun, Mar 26, 2023, 1:14 AM UTC

fuzzy_biscuit wrote: post #8

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

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).

Re: My experience crafting an interpreter with Rust (2021)

#35

Post by chlorion » Sun, Mar 26, 2023, 2:04 AM UTC

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

Re: My experience crafting an interpreter with Rust (2021)

#36

Post by mamcx » Sun, Mar 26, 2023, 2:19 AM UTC

nsajko wrote: post #2

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.

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),
        Bool(Vec)
    }

    struct Val {
        tag:Tag,
        data:Data
    }

    let n = val.as_i32::(&self) -> Vec

Re: My experience crafting an interpreter with Rust (2021)

#37

Post by eru » Sun, Mar 26, 2023, 2:35 AM UTC

crop_rotation wrote: post #12

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.

Well, the dragon book is not very good and only really applicable if you want to write a compiler for an imperative language in an imperative language.

Re: My experience crafting an interpreter with Rust (2021)

#38

Post by avinassh » Sun, Mar 26, 2023, 2:51 AM UTC

green_man_lives wrote: post #14

crop_rotation wrote: post #12

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.

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 downl…

May I suggest Rob Pike’s video on writing a lexer? It will make the task far more interesting

https://youtu.be/HxaD_trXwRE

Re: My experience crafting an interpreter with Rust (2021)

#39

Post by celeritascelery » Sun, Mar 26, 2023, 3:05 AM UTC

mamcx wrote: post #36

nsajko wrote: post #2

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.

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 ), Bool(Vec ) } struct Val { tag:Tag, data:Data } let n = val.as_i32:: (&self) -> Vec

There are some crates that let you do that. For example enum-ptr

https://crates.io/crates/enum-ptr

Re: My experience crafting an interpreter with Rust (2021)

#40

Post by User23 » Sun, Mar 26, 2023, 3:42 AM UTC

shadowofneptune wrote: post #27

margorczynski wrote: post #17

Earlier quoted context omitted.

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?

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 h…

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.