Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A tail-call interpreter in (nightly) Rust

mattkeeter.com

Post reply on HN
Print view View original

41–50 of 61 posts

Re: A tail-call interpreter in (nightly) Rust

#41

Post by IshKebab »

aw1621107 wrote: post #35
jakewins wrote: post #32

Earlier quoted context omitted.

I feel like I’ve seen elsewhere that the argument there is that you often must have this optimisation working in algos that rely on it or you will get stack overflows. Having a keyword to force it then becomes a very useful thing, vs relying on hopes that future compiler versions and different arch targets will all discover the optimisation opportunity.

> Having a keyword to force it then becomes a very useful thing, vs relying on hopes that future compiler versions and different arch targets will all discover the optimisation opportunity. Having a way to guarantee TCO/TCE is essential for some cases, yes. GP's question, though, was why a keyword specifically and not a hypothetical attribute that effectively does the same thing.

A keyword seems nicer to me. I think the only reason to use attributes is to avoid the work of adding actual new syntax, but seeing as they've already done that...

Re: A tail-call interpreter in (nightly) Rust

#42

Post by VorpalWay »

mananaysiempre wrote: post #9
gavinray wrote: post #5

Earlier quoted context omitted.

It doesn't make sense to me that an embedded VM/interpreter could ever outperform direct code You're adding a layer of abstraction and indirection, so how is it possible that a more indirect solution can have better performance? This seems counterintuitive, so I googled it. Apparently, it boils down to instruction cache efficiency and branch prediction, largely. The best content I could find was this post, as well as…

> It doesn't make sense to me that an embedded VM/interpreter could ever outperform direct code. You're adding a layer of abstraction and indirection, so how is it possible that a more indirect solution can have better performance? It is funny, but (like I’ve already mentioned[1] a few months ago) for serialization(-adjacent) formats in particular the preferential position of bytecode interpreters has been rediscover…

> Also, bytecode-based serde when?

Not in serde itself, but people have been experimenting with serde alternatives that are bytecode based. Nothing stable as far as I know, just experiments.

One early experiment is described in https://sdr-podcast.com/episodes/a-different-serde/ , which used a FORTH inspired stack based VM generated by derive macros at compile time (iirc).

Another experiment is https://lib.rs/crates/facet which is a more general derives to generate compile time introspection to generate metadata tables approach.

Re: A tail-call interpreter in (nightly) Rust

#43

Post by tialaramex »

saghm wrote: post #24
marcyb5st wrote: post #17

Earlier quoted context omitted.

I like this change. I was wondering if I would've preferred to have something on the function signature (eg `tcc_fn foo() ...` as in Tail Call Constrained fn) and when encountering that the rust compiler would make checks about whether the body of the function is tail-callable. My fear is that adding yet another keyword it might get lost in the sea of keywords that a Rust developer needs to remember. And if recursion…

Given that it's not really that uncommon to see something like `pub(crate) async fn foo() ...`, the concern of function signatures starting to get unwieldy feels a lot more concrete than hypotheticals about a "sea of keywords". From looking at the list of keywords in the language currently (listed here: https://doc.rust-lang.org/std/#keywords ), I don't really see a whole lot that I think the average Rust programmer…

I'd actually say that for people learning Rust after something like C or C++ in particular the rare cases where a keyword means something else are the most confusing. In particular `const` in Rust means constant whereas in several languages it means an immutable variable.

    const NINE: i32 = // Some arbitrary *constant* expression;
In K&R C this qualifier didn't exist so there's no confusion, but C89, all versions of C++ and several other languages inspired by them use "const" to mean an immutable variable.

Re: A tail-call interpreter in (nightly) Rust

#44

Post by eru »

drob518 wrote: post #20
tialaramex wrote: post #10

Earlier quoted context omitted.

The article explains most of this, but the key takeaway for beginners once this lands is: With `become` you can write tail calls in Rust and it will promise they either work or don't compile, you can't have the case (which exists in several languages) where you thought you'd written a tail call but you hadn't (or maybe you had but you switched to a different compiler or made a seemingly inconsequential change to the…

Clojure’s “recur” form works similarly in that it’s guaranteed to be tail recursive, and if it isn’t the compiler will throw an exception.

But I guess it's only works for functions that just call themselves? That's nice, but a very limited subset of TCO.

Re: A tail-call interpreter in (nightly) Rust

#47

Post by tmp10423288442 »

iknowstuff wrote: post #4
bjoli wrote: post #3

Finally! Tail calls! I had to write rust some years ago, and the ocaml person in me itched to get to write tail recursion. Tail recursion opens up for people to write really really neat looping facilities using macros.

Rust has the become keyword now I believe for TCO. https://doc.rust-lang.org/std/keyword.become.html

I was wondering how they solved the `drop` problem (the fact that `return foo;` is not the last code executed in most functions, because Rust values are all implicitly dropped at the end of scope), and it seems that they cut the Gordian knot so that values are all implicitly dropped before `become` instead. Hope that works out - probably why it's still nightly for now.

Re: A tail-call interpreter in (nightly) Rust

#48

Post by pstuart »

sa46 wrote: post #12
dathinab wrote: post #2

> resulting VM outperforms both my previous Rust implementation and my hand-coded ARM64 assembly it's always surprising for me how absurdly efficient "highly specialized VM/instruction interpreters" are like e.g. two independent research projects into how to have better (fast, more compact) serialization in rust ended up with something like a VM/interpreter for serialization instructions leading to both higher perfor…

A new Go protobuf parser [1] made the rounds here eight months ago [2] with a specialized VM that outperforms the default generated protobuf code by 3x. [1]: https://mcyoung.xyz/2025/07/16/hyperpb/ [2]: https://news.ycombinator.com/item?id=44591605

I missed that, that could come in handy. Thanks!

Re: A tail-call interpreter in (nightly) Rust

#49

Post by drob518 »

eru wrote: post #44
drob518 wrote: post #20

Earlier quoted context omitted.

Clojure’s “recur” form works similarly in that it’s guaranteed to be tail recursive, and if it isn’t the compiler will throw an exception.

But I guess it's only works for functions that just call themselves? That's nice, but a very limited subset of TCO.

No, it is used for loops within functions as well. But it’s not fully generalized like in Scheme. You can’t have mutually recursive functions using tail recursion via “recur,” for instance. There is another Clojure technique for that (“trampoline”). Clojure runs on the JVM and is limited by the JVM’s original omission of TCO. When I started using Clojure, I was concerned about these limitations, but in practice I haven’t found them to be a problem. Most of the time, I just need a loop and “recur” works fine. I rarely use “trampoline” (just for state machines).

Re: A tail-call interpreter in (nightly) Rust

#50

Post by [deleted] »

kelnos wrote: post #29

Ah that's great! I wonder why they went with a new keyword; I assumed the compiler would opportunistically do TCO when it thinks it's possible, and I figured that the simplest way to require TCO (or else fail compilation) could be done with an attribute. (Not sure if the article addressed that... I only skimmed it.)

[deleted]
Post reply on HN