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

11–20 of 61 posts

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

#11

Post by tialaramex »

measurablefunc wrote: post #8

More accurate title would be to say it is a tail call optimized interpreter. Tail calls alone aren't special b/c what matters is that the compiler or runtime properly reuses caller's frame instead of pushing another call frame & growing the stack.

Maybe, it probably depends on how you're looking at it. The optimization is obvious, I expect any optimizing compiler will TCO all naive tail calls - but the trouble in Rust or C++ or a dozen other languages is that you can so easily write code which you think can be optimized but the compiler either can't see how or can see that it's not possible and (without this keyword) you don't find out about this because growing the stack is a valid implementation of what you wrote even though it's not what you meant.

The "become" keyword allows us to express our meaning, we want the tail call, and, duh, of course the compiler will optimize that if it can be a tail call but also now the compiler is authorized to say "Sorry Dave, that's not possible" rather than grow the stack. Most often you wrote something silly. "Oh, the debug logging happens after the call, that's never going to work, I will shuffle things around".

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

#12

Post by sa46 »

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

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

#13

Post by kryptiskt »

measurablefunc wrote: post #8

More accurate title would be to say it is a tail call optimized interpreter. Tail calls alone aren't special b/c what matters is that the compiler or runtime properly reuses caller's frame instead of pushing another call frame & growing the stack.

I wouldn't call it optimized, since that implies that it gains performance due to the tail calls and would work otherwise, but the tail calls are integral to the function of the interpreter. It simply wouldn't work if the compiler can't be forced to emit them.

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

#14

Post by measurablefunc »

kryptiskt wrote: post #13
measurablefunc wrote: post #8

More accurate title would be to say it is a tail call optimized interpreter. Tail calls alone aren't special b/c what matters is that the compiler or runtime properly reuses caller's frame instead of pushing another call frame & growing the stack.

I wouldn't call it optimized, since that implies that it gains performance due to the tail calls and would work otherwise, but the tail calls are integral to the function of the interpreter. It simply wouldn't work if the compiler can't be forced to emit them.

What I wrote is standard nomenclature

> Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is no longer needed, and can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail-call elimination or tail-call optimization. (https://en.wikipedia.org/wiki/Tail_call)

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

#15

Post by saghm »

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.

What are some examples of macros that your would be able to be written with tail cails? Because macros in Rust can already be recursive (and I've written plenty of ones that take advantage of it over the years), it's not immediately obvious what doors better optimization of tail calls in Rust would open up for them.

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

#16

Post by saghm »

tialaramex wrote: post #10
iknowstuff wrote: post #4

Earlier quoted context omitted.

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

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…

"Either it works or doesn't compile" compared to "oops it silently degraded to the less performant thing because an invariant stopped being true" is remarkably similar to how I tend to describe the benefit of having move semantics by default with opt-in copies in Rust compared to in C++ where you need to set up things right and might still accidentally have it copy if you mess it up.

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

#17

Post by marcyb5st »

tialaramex wrote: post #10
iknowstuff wrote: post #4

Earlier quoted context omitted.

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

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…

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 is not something you do often you might not reach for it when actually needed. Having this signal in the function signature means that people would be exposed to it just by reading the documentation and eventually will learn it exists and (hopefully) how to wield it.

What do you folks think?

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

#18

Post by tialaramex »

marcyb5st wrote: post #17
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…

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…

The property we care about isn't a property of functions but of callers, so marking a function doesn't help.

`become blah(foo, bar)` is the same thing as `blah(foo, bar)` except that we, the caller are promising that we have nothing further to do and so when blah returns it can return to our caller.

If somebody else calls blah they don't want that behaviour, they might have lots more to do and if they were skipped over that's a disaster.

In some languages it's very obvious when you're going to get TCO anyway, but Rust has what C++ calls RAII, when a function ends all the local variables get destroyed and this may be non-trivial work. Presumably destroying a local i32 is trivial & so is a [u8; 32] but destroying a local String isn't, let alone a HashMap and who knows how complicated it is to destroy a File or a DBQuery or a Foo...

So in a sense "all" become does is try to bring that destruction sooner a little, so it happens before the call, leaving nothing to do afterwards. We weren't using that String any more anyway, lets just destroy it first, and the HashMap? Sure, and oh... no, actually if we destroy that Foo before calling blah which needs the Foo that messes things up... Rust's borrowck comes in clutch here to help us avoid a terrible mistake, our code was nonsense, it doesn't build.

Edited: Improve explanation

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

#19

Post by zozbot234 »

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…

You could probably rephrase almost any enum dispatch whatsoever as a "bytecode interpreter" of a sort, especially if run recursively to parse over some kind of sequence. If bytecode helps you achieve a more succinct representation of some program code than the native binary representation for your architecture, it makes sense that this could be faster in some cases.

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

#20

Post by drob518 »

tialaramex wrote: post #10
iknowstuff wrote: post #4

Earlier quoted context omitted.

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

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.
Post reply on HN