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

51–60 of 61 posts

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

#51

Post by measurablefunc »

UncleEntity wrote: post #23
kryptiskt wrote: post #13

Earlier quoted context omitted.

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.

> but the tail calls are integral to the function of the interpreter Not really, a trampoline could emulate them effectively where the stack won't keep growing at the cost of a function call for every opcode dispatch. Tail calls just optimize out this dispatch loop (or tail call back to the trampoline, however you want to set it up).

Yup, standard practice for interpreters in languages that don't have tail call optimization.

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

#52

Post by saghm »

tialaramex wrote: post #43
saghm wrote: post #24

Earlier quoted context omitted.

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…

That's a fair point, and maybe even a case that there should be more keywords rather than fewer.

Relatedly, I still sometimes get tripped up by the nuances of using `const` versus `static` for top-level constants. Most of the time the difference is entirely opaque to the programmer (because it's not obvious when most things are getting inlined or being referenced from a single place in memory), but it's possible to run into cases where one works and the other won't (e.g. trying to be clever with `OnceCell` rather than `OnceLock`).

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

#53

Post by saghm »

moefh wrote: post #25
saghm wrote: post #15

Earlier quoted context omitted.

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.

I'm not sure how this would be useful in Rust, but macros and tail calls are what allows one to (for example) write iterative loops in Scheme, which doesn't have a native loop syntax. Maybe the same idea can be used in Rust where some constructs are easier to write in recursive form instead of a loop? In any case, here's a silly example of a `for-loop` macro in Scheme using a tail call: (define-syntax for-loop (synta…

Interesting, my lack of real experience in Scheme will make this take a bit more work for me to fully work through the implications of. It's not immediately clear to what this would mean for Rust, since there is already a loop construct (well, three of them, although two of them are syntactic sugar for the first). You could define a macro around it in Rust today, but it would be fairly uninteresting: https://play.rust-lang.org/?version=stable&mode=debug&editio...

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

#54

Post by moefh »

saghm wrote: post #53
moefh wrote: post #25

Earlier quoted context omitted.

I'm not sure how this would be useful in Rust, but macros and tail calls are what allows one to (for example) write iterative loops in Scheme, which doesn't have a native loop syntax. Maybe the same idea can be used in Rust where some constructs are easier to write in recursive form instead of a loop? In any case, here's a silly example of a `for-loop` macro in Scheme using a tail call: (define-syntax for-loop (synta…

Interesting, my lack of real experience in Scheme will make this take a bit more work for me to fully work through the implications of. It's not immediately clear to what this would mean for Rust, since there is already a loop construct (well, three of them, although two of them are syntactic sugar for the first). You could define a macro around it in Rust today, but it would be fairly uninteresting: https://play.rus…

Yes, I agree. Like I said, it might be useful when dealing with something that is easier to express in (tail) recursion form instead of an iteration.

Anyway, here's something more-or-less equivalent in Rust, which will blow the stack if made to loop too many times: https://play.rust-lang.org/?version=stable&mode=debug&editio...

(There may be a way to use a closure instead of a function to avoid hard-coding the type of `$i` in the macro, but I can't find an easy way to write a recursive closure call in Rust).

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

#55

Post by tialaramex »

saghm wrote: post #52
tialaramex wrote: post #43

Earlier quoted context omitted.

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…

That's a fair point, and maybe even a case that there should be more keywords rather than fewer. Relatedly, I still sometimes get tripped up by the nuances of using `const` versus `static` for top-level constants. Most of the time the difference is entirely opaque to the programmer (because it's not obvious when most things are getting inlined or being referenced from a single place in memory), but it's possible to r…

It might help to think about whether you want an actual singular concrete thing, which means you need static or whether you just want to talk about the idea and so it doesn't matter whether at runtime this exists many places or nowhere at all, which is a const.

Statics can be mutated - though not safely - because they are a single concrete thing so they can be changed, whereas it can't mean anything to mutate a constant, hence the word "constant".

For larger objects you might want a single concrete thing even though it might intuitively not seem important because it impacts performance. For example if we keep talking about FACTOR[n] where FACTOR is an array of a million numbers (maybe computed by scientist colleagues for your application) and n is a variable, if FACTOR is const Rust is going to just put a copy of that enormous array everywhere it needed to do this indexing operation, which gets out of hand really fast, whereas if we use static we get a single concrete thing, named FACTOR and everywhere in the program will use that one single million number array, much tidier and less likely to result in say, running out of RAM on a small computer.

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

#56

Post by eru »

drob518 wrote: post #49
eru wrote: post #44

Earlier quoted context omitted.

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

> No, it is used for loops within functions as well.

OK, but that's just equivalent to a nested function, nothing special?

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

#57

Post by saghm »

tialaramex wrote: post #55
saghm wrote: post #52

Earlier quoted context omitted.

That's a fair point, and maybe even a case that there should be more keywords rather than fewer. Relatedly, I still sometimes get tripped up by the nuances of using `const` versus `static` for top-level constants. Most of the time the difference is entirely opaque to the programmer (because it's not obvious when most things are getting inlined or being referenced from a single place in memory), but it's possible to r…

It might help to think about whether you want an actual singular concrete thing, which means you need static or whether you just want to talk about the idea and so it doesn't matter whether at runtime this exists many places or nowhere at all, which is a const. Statics can be mutated - though not safely - because they are a single concrete thing so they can be changed, whereas it can't mean anything to mutate a const…

Yeah, the problem is that I usually think about stuff like this up front and then select something, and when much later I happen to change something, I focus so much on the types and the values that I forget that I need to also look at the keyword itself.

For what it's worth, my rule of thumb is usually to start with `static` and then only swap to `const` if I have a reason to. If I recall correctly, the issue I alluded to above was around picking between `LazyCell` and `LazyLock` and swapping between `&Path` and `PathBuf`, and some combination of them only working with `const` and not `static`.

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

#58

Post by cranky908canuck »

steveklabnik wrote: post #6
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

From the first line of the post: > Last week, I wrote a tail-call interpreter using the become keyword, which was recently added to nightly Rust (seven months ago is recent, right?).

Recent enough... also, since it's not yet in stable, it'll be 'recent'/'new' for a lot of people once it does get there.

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

#59

Post by cranky908canuck »

measurablefunc wrote: post #14
kryptiskt wrote: post #13

Earlier quoted context omitted.

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…

I won't argue with wikipedia, but assuming it's correct the 'standard nomenclature' seems sloppy to me. The whole point of the original post was taking advantage of the guarantee of TCE (elimination), vs TCO ("give it a try but oops, oh well, whatever...").

I suppose maybe TCE (as distinct from TCO) should be expanded to include any mechanism that doesn't expand the stack / heap / whatever for things that rhyme with recursion (in which case the existing sloppiness may as well stand, but we need a new TLA).

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

#60

Post by cranky908canuck »

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

As a user of the feature, it's the caller that needs the guaranteed elimination (and, presumably, is willing to pay for it, in syntax / compile time / run time / cognitive load). The 'zero cost feature' (only pay if used) principle seems broken if the callee has to indicate something special.

The compiler is free to do something clever (eg., two versions of fn Foo(...), one guaranteeing TCE), but as a developer merely using Foo, I don't want to have to decorate it (or, in a library, have it already decorated) to make TCE (not just TCO) possible. That requirement would constitute delving into the internals.

Post reply on HN