A tail-call interpreter in (nightly) Rust
45 points by tekknolagi
45 points by tekknolagi
become is an interesting specific instantiation of something I'd love to see more of (hard compiler guarantees).
Specifically, it would be great to have the ability to say more general statements of the form "if this doesn't end up optimized how I expect it to be, emit a compile error" to prevent random performance degradation when something e.g. monomorphizes very weirdly.
This is a drum I bang whenever something reminds me I have it. Performance characteristics are a property of the program that can and therefore should be encoded in source code explicitly. Like SIMD, but for everything.
I hope that proper tail calls move from nightly Rust into stable.
However, I note that "Explicit Tail Calls" has been under development since 2023, and the RFC has not been accepted yet.
https://doc.rust-lang.org/nightly/std/keyword.become.html
https://github.com/rust-lang/rust/issues/112788
https://github.com/rust-lang/rfcs/pull/3407
The lack of proper tail calls is one of the show-stoppers preventing me from writing the next version of my VM in Rust. I am currently using C++.
C++ has explicit tail calls? I assume this is a compiler extension or some annotation and compiler flag?
clang (for 5 years now) and gcc have a musttail annotation.
see also https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html
It's nice that Rust's become is usable now, and it definitely came to mind as an alternative for the LLM assembly interpreter from the last blog post. The codegen being bad, unfortunately, matches a lot of my experiments using Rust for interpreters :(
One of the issues here is also that for values with non-trivial representation that aren't just numbers, you can't become because the Drop implementation still needs to run. This is an issue you also hit with Clang [[musttail], however IMO it's much easier to hit with Rust because idiomatic Rust uses so many more Drop-able values, and avoiding them means you have to write some painful C-like code. Trying to use become to emit Copy-and-Patch stencils didn't work out when I tried it a few months ago for this reason.
You can't transfer ownership of a value implementing Drop through a become call? That's an unfortunate limitation... surely it's the responsibility of the function you're becoming to deal with dropping those values, right? It feels like it should be possible to automatically drop all the values not used in a become call before the call and not run drop on the stuff the newly called function takes ownership of.
You can transfer ownership just fine. The problem is actually when you don't transfer ownership (the Drop wants to run at the end of scope, but that's after the become call)
Is there anything preventing you from using mem::drop before the become on everything with a non-trivial Drop? It’s repetitive, but it seems like it should work fine.
Hmmm, might not work for things that have been partially moved, or conditionally moved?
Not unavoidable, but definitely annoying.
Nice article. This interpreter reminds me of this "Iota machine" one I built some time ago (don't judge the code, I was young, and Rust reached 1.0 very recently), which was used to generate programs with a genetic algorithm. That was a cool Christmas project.