I don't see how that follow. I'm not saying that the lack of this feature makes rust useless. I'm saying that become without TCO doesn't add anything useful to the language for me, and as such the feature would be useless.
I would much rather get a compile error if it doesn't manage to make it TCO rather than have a footgun where it might stack overflow on obscure architectures (or on processing especially deep data structures).
Yes, but it is the silent footgun where the error moves to runtime that is the problem. That is very much the opposite of what rust usually aims to do. Errors at compile time are better.
become without guaranteed TCO adds to the language, by changing the semantics such that none of the known blockers to TCO are present in the source code. This, in turn, allows you to make it more likely that TCO will happen, because you can remove blockers.
Guaranteeing TCO is more problematic, not least because guaranteeing TCO would imply that (for example) you get TCO in development builds with no optimizations applied.
I see value in a become type change that does not guarantee TCO, but does guarantee that if TCO doesn't take place, it's a missed optimization opportunity, rather than because you've written code that prevents TCO.
You are saying that because this is just a "quality of implementation" concern, not a hard guarantee, it's useless -- right?
But we have tons of things that you absolutely already rely on, that are just "quality of implementation" concerns. So your argument doesn't make sense to me.
There is no framework that we could feasibly use to even state a proper semantic guarantee about stack usage, so I don't think it is possible to do any better than "quality of implementation" here.
Yeah we do definitely want TCO in debug builds. Really calling this an "optimization" is a misnomer. It should just be called tail calls.
I don't see how this is a problem in terms of making this an attribute. Is there a rule that attributes = syntax sugar? For example, #[repr(...)] is not just syntax sugar for something else.
why can't we give an upper bound of stack usage in the abstract machine? we already have stack frames in the abstract machine.
in general, i don't think it makes sense to say we "can't" do something. with enough technical writing and cooperation with llvm, we should be able to provide any guarantees we want[1], it's just a matter of if it's worth it, both in terms of labor, and in terms of ruling out future implementation possibilities.
aside from things like uncomputable problems âŠī¸
"can't" here means "it's completely unpractical". We'd have to systematically constrain how many variables the compiler adds to the stack frame, e.g. via spilling, during loop unrolling, in inlining, when hoisting potentially dead code, and so on. I don't know a single compiler for a single language that does this, outside some research prototypes geared towards formal proofs (and those don't have anything that one would typically call an "optimizer"). To my knowledge, everybody who cares about guaranteed upper bounds for stack usage analyzes the assembly.
So, sure, if you want to embark on a multi-year research project to make stack bounds practical in a production-grade optimizing compiler, please do so. But don't expect anyone else to do this as part of e.g. making tail calls work in Rust, and certainly don't think that this is somehow a "solved problem" or so.
So okay, I see why making guarantees would be hard. Would it still be possible to get compiler errors whenever become fails to turn into a tail call? As opposed to the code silently compiling into a normal call. Because that is the part I care about: if I have done something wrong that means TCO doesn't work, I want the compiler to tell me so I can fix it.
Counterpoint: clang::musttail exists. This is not trying to solve the general "guaranteed stack usage" (which no one was asking for, you seem to have been conflating issues here), but it does have guaranteed tail calls.
(Please try to keep the discussion on topic instead of expanding the scope.)
Yeah it exists but its guarantees are rather meaningless, since being a tail call or not is not an observable property unless you look at the assembly -- and clang can't actually make guarantees about the assembly. As long as your memory is finite, the fact that stack growth is "bounded" (but without giving a bound) is also a completely meaningless statement. I'm happy to declare that stack growth is bounded to "as much stack space as can be stored in the observable universe".
So this is sloppy verbiage on the side of clang, which I don't think we should copy for rustc.
What's the difference on the Rust abstract machine between a musttail call and a maytail call, given that the Rust abstract machine does not have a concept of stack usage and permits a stack overflow to occur on any call? This is how it matters that we provide no guarantees around stack usage; if musttail can only be stated in terms of codegen properties and not as a property on the abstract machine, then it must by definition be a QOI issue and not language semantic.
The best I've come up with has been quite painful â roughly that if the program execution has previously passed through a given stack frame configuration, a call to that same stack frame configuration with the same control flow will not cause a stack overflow the latter times if the first instance did not cause one. And this still has issues once you start poking at it.
Now, rustc can and does test for and essentially guarantee plenty of QOI properties, such as that the "zero cost" abstractions used in std actually optimize out and are "zero cost." This is plenty sufficient for writing real programs, but the difference in what is providing the "guarantees" matters to some of us.
On targets where tail calls are possible, that is definitely the intent. That's why become is a separate keyword -- it only gets accepted when the requirements for tail calls are satisfied.
The tricky question is what to do on targets that just don't support tail calls. I don't know if we have such a target, so this may be hypothetical.
Current/MVP wasm. Wasm tail calls are phase 5 â standardized but not yet merged into the main spec draft â but even once tail calls eventually become part of the default target feature set, rustc will still support wasm without enabling the target feature.
I'd argue the semantic difference to drop order is the reason for a new keyword, and am a supporter of a "weak" become being available, but the default mode of become being to only be available where tier 1 targets can do TCO and as QOI attempting to guarantee TCO seems completely reasonable to me.
I think we may have different definitions of guarantee. I'm considering guarantees in terms of the generated machine code. What the Rust AM does, doesn't really matter.
The rust AM is as far as I'm concerned (as a user of Rust) an implementation detail of the language. Yes it is a formalism that the code passes through on it's way to machine code, and reasoning in terms of it can be helpful (necessary even if writing unsafe or atomic code). But ultimately it is a means to an end, and if a guarantee cannot be represented by it, so be it, let's be pragmatic.
And it seems rustc developers recognise this, since there are indeed codegen tests. They do provide guarantees as far as I'm concerned (at least on tier 1 targets).
I would prefer my library to error out on a target without TCO support, rather than get bug reports about mysterious crashes caused by my library. WASM might have sensible detection of stack overflow (I have no idea), but many embedded targets have no support for a guard page between the stack and the heap. So stack overflow would cause silent corruption. Please let me have a compile error instead if TCO doesn't work on that target.
(Yes, you may be able to swap the order of stack and heap so they grow away from each other using linker scripts. I don't know that it works on all architectures. And I have no way of enforcing that users of my library uses that.)
if a program's stack usage is bounded, and it has 100% test coverage, and its testsuite doesn't stack overflow, it is (practically, if not formally) guaranteed to not stack overflow during normal operation.
if a program's stack usage is unbonded, it is likely to stack overflow for sufficiently large runtime, or for sufficiently large input.
This is demonstrably untrue. My program's stack usage is bounded... by 2^64 bytes, because it's running on an x86 machine. (And my test suite passes because I tested it on simple inputs and not crazy torture tests which turn out to be indistinguishable from actual user reports.) Doesn't mean I won't get a stack overflow.
if you a stricter definition (e.g. an increase in the size of user input will not cause an increase in stack usage), you can once again get useful guarantees.
It's the literal definition of bounded, and the point of @RalfJung 's post. You need an actual bound, not just a "pinky promise the bound is out there somewhere", for the claim to have any teeth at all. But tooling for producing actual bounds on stack usage (i.e. "this program will use at most 165 KB stack on any input") are somewhere between pipe dream and research software right now, and in particular there is no commercial compiler that can produce this kind of output.
Again, no one asked for this (in the context of this thread). Inlining and so on can make the stack frame size vary. All people are asking for is a way to get a warning/error when a become fails to apply TCO. Which is a far simpler problem.
I am afraid then you are wrong. The exact assembly code we emit is an implementation detail (and it changes all the time with each release, even if you don't change the source code); the AM is in fact the only part that is actually making any hard guarantees. Specifically, we are promising that the assembly code behaves like a faithful implementation of the AM (for UB-free programs). That's generally the only constraint we place on the assembly code, though in practice there are some other details e.g. to enable linking with compilation units produced by other compilers.
FWIW that's a soundness bug on these targets as it actually violates guarantees we are making.
@binarycat did. Maybe you didn't, but you are replying to a reply to someone else's comment.
So you are saying it is better for code to be non-portable to some targets, than to still make a "best effort" attempt at executing it on that target?
What if we make a promise that if the target doesn't support proper tail calls, the compiler must detect and report stack overflows? (I don't know if that promise is actually practical, I am just trying to figure out your position here.)
You can have that position, but I hope you understand that this is not a trivial tradeoff and there are multiple reasonable answers here.
