https://github.com/vishpat/lisp-rs
A simple Lisp Interpreter in Rust
My experience crafting an interpreter with Rust (2021)
41–50 of 53 posts
Re: My experience crafting an interpreter with Rust (2021)
#42Earlier quoted context omitted.
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.
Exactly, though I do not see how it is not an example of recursion.
Re: My experience crafting an interpreter with Rust (2021)
#43A 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?
> 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-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.
Re: My experience crafting an interpreter with Rust (2021)
#44> 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.
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 statica…
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.
Re: My experience crafting an interpreter with Rust (2021)
#45A 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 solved it in case of an interpreter with
outer: loop {
loop {
let res = self.interpreter_loop(…);
match res {
Continue => {}
Return => { break 'outer; }
Exception => { break; }
}
}
Re: My experience crafting an interpreter with Rust (2021)
#46Crafting 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…
Except where comparisons being made, the first and second halves are mostly independent. If the tree-walking interpreter might not be what you have hope for, you can, in principle, skip finishing it. The bytecode VM half is a re-implementation (in C instead of Java as the first half) and only the scanner/tokenizer has some inevitable redundancies in implementation. For me, who had less prior knowledge in interpreters, it is still good to have fully gone through both halves to relate to the comparisons and trade-offs of both implementations.
Re: My experience crafting an interpreter with Rust (2021)
#47Crafting 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.
Modern Compiler Implementation in Java is not really comparable to Crafting Interpreters, is it? I've read the former cover to cover (the ML version) and I've looked through Crafting Interpreters, and I don't feel there is much overlap between the two.
Re: My experience crafting an interpreter with Rust (2021)
#48I have also made an interpreter using Rust.
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
The language is "LODA", a math AI, using OEIS as training data. https://loda-lang.org/
Re: My experience crafting an interpreter with Rust (2021)
#49A 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.
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.
`become` is still a reserved keyword for this in Rust, so there's that.
Re: My experience crafting an interpreter with Rust (2021)
#50I’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?
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/
If you weren't going to expose clox to the web or other untrusted input (and why would you), it's not a concern.