no i didn't. i said stack usage should be guaranteed bounded, not that it should have some actual not that this upper bound should actually be knowable...
3 Likes
a decent compromise would be a lint (either warn or deny by default) that individual packages could customize to their needs.
2 Likes
Given that address space is finite, an unknowable bound is logically equivalent to not stating any bound (since the stack is always bound by 2^64).
This goes well beyond what clang documents, and precludes things like inlining / unrolling the first "iterations" of the tail-call "loop". You would again have to resort to asymptotic statements, which are logically meaningless on computers with finite memory.
@CAD97 tried to make something like this precise above when they wrote:
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
But we are far from confident that this doesn't put undue limits on optimizations. In practice, you don't need this, you need something that's "good enough", and we can provide that -- we just won't label "good enough" as a hard guarantee.
This may all seem like pedantry, but in Rust we take the word "guarantee" very seriously and generally only use it for things that have a chance of being formally proven in a mathematically rigorous way. You may be used to a less rigorous meaning of "guarantee", but in this community that's how we use this word.
8 Likes
Absolutely. If I build on a target that can't do TCO and one of my dependnencies switches to use code that depends on TCO, I'd rather get a lint than a runtime error or even silent corruption. It is no fun debugging things at 4 am due to a failure in production.
In fact the code was already non-portable if it is for example an interpreter implemented using tail calls. The question is if I get the error at compile time or runtime.
As far as I know, the other option is to simply not support the vast majority of embedded targets. There are some devices that have a MPU (memory protection unit, a much cruder alternative to the more well known MMU). Most don't have this. Usually this allows you to set access control on a few blocks of power of two size (say, 8 total mappings). Much less fine grained than an MMU. But again, most don't have even an MPU.
2 Likes
Or maybe a cfg flag? We already have some target-specific like target_has_atomic, so we could also have something like target_has_tailcall
For usecases like threaded interpreters you'll likely be recursing so much that any "best effort" will fail anyway, so it makes sense to me to catch those cases at compile time. And if the user still wants a "best effort" they could just fall back to return, no?
6 Likes
So far Rust is proudly very portable, so having a core language feature just fail the build on some target would be a big departure from our usual stance. Anyway, I don't have a very strong opinion either way. As long as the word "guarantee" is not misused I will largely stay out of this discussion. 
No, due to drop order differences "opportunistic" TCO will rarely happen with return.
In a sense the problem here is that there are two things you way want to signal
- please drop everything before calling this function, so that maybe you can do tail calls if you like
- definitely tail call this!
Both of these are things someone might reasonably want to say, but we have to pick one of them for become.
2 Likes
Could we have an attribute on the become to switch between these? I think someone suggested that earlier in the thread.
My use cases fall squarely in the latter category (threaded interpreters, or other cases of potentially infinite recursion). If it isn't tail call optimised the code just won't work correctly.
I want to know the actual stack usage of all code I write, but realistically I can't. The next best alternative is to know whether it is bounded at all, and to then estimate that bound by profiling some edge and corner cases.
2 Likes
What about using trampolines to implement tail calls in platforms that don't support tail calls natively? It has a performance implication and I guess it's hard to do it for FFI / extern functions, but otherwise it should be doable.
(Here is a random link that talks about this in the context of Python, but this can be done in any language)
I think that failing to compile (if even a trampoline-based implementation is deemed non-viable in a given platform) is far more preferable than casually compiling broken binaries on some platforms. In particular, anyone that wants TCE to be optional can just put the code in a #[cfg] (and maybe have some helper macro that does this).
Regardless of whether this is just a quality of life feature or has semantics actually guaranteed by the AM, it makes no sense to purposefully ship a feature that sometimes don't do what it's intended to do, and compile normally with no warning. I think that's what killed placement new in the end, right? Rust aspires to be more of an "if it compiles, it works" kind of language.
However, a deny by default or even warning by default lint is probably good enough, because it at least gives people some tools to prevent compilation in targets that don't support the required feature for the code to actually work.
Doesn't Rust already use stack probes for this?
In either case, the problem is that guaranteed TCE is often paired with programs that without it would always overflow the stack, regardless of its limit, and until it does it will leak memory at an alarming rate. Such a program would always raise this error and would benefit from it being caught at compile time.
3 Likes
You are just repeating what has already been said, and the answer has already been given above: stack usage is definitely bounded by 2^64 bytes. So saying that stack usage is bounded without giving a concrete bound is a trivial, logically meaningless statement.
This has been discussed above. Please read before replying. 
Many targets don't support stack overflow checks via stack probes, in particular many embedded targets.
This is in the same vein as saying that no language is truly Turing Complete because we don't possess an infinite tape. The theoretical construct is still useful here as was already demonstrated above, and I'm not sure being pedantic here is helpful.
4 Likes
That's not what we were talking about though. We were commenting on whether Rust could promise absence of stack overflow in certain cases. You are picking a sentence from the middle of that discussion and commenting on it without taking account the context -- that's not productive.
The Rust AM is definitely not Turing Complete since its memory is finite. But this doesn't really matter here. We do not spell out a guarantee saying "every Turing Machine that halts can be translated into an equivalent Rust program that eventually terminates successfully".
But now people are asking us to spell out promises we can't keep, and that's what we are pushing back against. You may think "bounded" and "bounded with a known bound" are similar notions, but they are really qualitatively different -- the former is liveness, the latter is bounded liveness which is a safety property. Bounded liveness is a lot harder to reason about than liveness. Just because most people don't realize this, is not an excuse to be sloppy about terminology here.
The gist of it really is: there's no meaningful mapping from stack usage in the AM to stack usage in the final execution, so making any statement here is just not practical. The AM is the only thing that remains "invariant" under optimizations, everything else can change radically. Nobody even tried arguing with this, instead people think they can somehow get around the gap between the AM and the final execution, but you cannot. It's really quite pointless to endlessly belabor this...
4 Likes
Who exactly asked for this? When I looked through the long history, it looked like all people want is guaranteed TCO (or a lint when that is impossible). I see people pushing back against guaranteed stack usage but I don't see anyone asking for it.
It would be quite helpful to identify where this misunderstanding comes from. Becuse it looks like a strawman to me. And it is resulting the discussion going in needless circles.
4 Likes
This has been already answered above, but I guess I can try it again, by answering with a question:
What does this mean, if it's not about stack usage?
You can't talk about the assembly of the generated program when answering this question. You can only talk about what happens when the program is being run. The reason for this is that, as explained several times above, the shape of the assembly that we produce is highly unstable and we can't make any guarantees for it (except if you use inline assembly). This implies that we can't and won't guarantee that a become call translates to any particular assembly shape -- it may be inlined or unrolled or transformed in all sorts of ways.
4 Likes
For LLVM it means the musttail attribute on the call. Specifically:
- I don't care about inlining, yes it might grow the stack frame such that a single frame is now twice as large. Yes this makes things like "no more than 129 KB stack usage" impossible. And that is why I'm not asking for it.
- I do care that the depth of the call stack doesn't keep growing forever when an infite series of become are executed. That means the current stack frame is replaced eventually by a series of become calls (becuse infinitly deep inlining is not a thing).
In particular for a program that uses tail calls for it's main loop (instead of a loop it should apply TCO). Same for a threaded interpreter.
In particular this means that (on traditional CPUs, I don't know how wasm works on this level) become turns into a jump rather than a subroutine call. This means no new stack frame is allocated on the stack.
Note that at no point did we talk about specific stack usage in bytes. It is ok to not know that. But you can still reason about if you will allocate an infite number of stack frames (well, until you run out of memory) or if you won't. Without knowing the exact size of those stack frames.
Probably LLVM's definition isn't the perfect platonic ideal of this concept. But it is good enough to get the job done. I'm an engineer, and I prefer practical and doable over ideal but impossible.
This doesn't really need to consider assembly (well, apart form the jump vs call above). But the growth over time of number of stack frames vs how large each frame is, I believe is the important bit.
And llvm musttail (as opposed to just tail) seems to be exactly this: Error out of a tail call is impossible. So LLVM already have the required semantics. It isn't something rust has to implement (apart from emitting it and giving nice diagnostics on top).
9 Likes
LLVM is not even our only backend, so we can't use LLVM to define our language features. Also, the definition in LLVM is unfortunately incomplete, it just says "the musttail marker means that the call must be tail call optimized". That's a rather meaningless definition until someone says what exactly it means that the call "must be tail call optimized".
That's what I thought you meant, and it is a statement about the generated assembly, and therefore unsuited as a definition. I suspect it is also what the LLVM folks meant.
That's a way to put this... it says absolutely nothing, since it fails to define the core term it uses.
Our goal in Rust is to not repeat past mistakes in how we approach specification of systems languages. So no, just copying what LLVM/clang do is not good enough. In my view, they aren't actually saying anything -- if you are happy with what they are saying, you should be happy with a QoI guarantee.
Now I would claim that what you actually care about is not which assembly instruction is used when, it is whether your program blows the stack or not. And that's why we had a long discussion above about it being hard to make any statements about when that does or does not happen.
How do you measure the number of stack frames? We can talk about the number of stack frames in the AM, but that has little to do with the number of stack frames in the "real" stack -- inlining and outlining get in the way here. So that's not the number you care about. The actual number you care about is, again, an unstable implementation detail that we can't say much about, just like actual stack usage.
1 Like
IMO the best thing we could do is have a concrete litmus test and define "the target implements tail calls" via "we guarantee that that program will never cause a stack overflow". Something like:
fn count_down(x: u64) {
if x == 0 { return } else { become count_down(x-1) }
}
fn main() {
let x: u64 = /* read from stdin or whatever */;
count_down(x);
}
Of course this doesn't say anything about your concrete program. But if you trust us that we won't add any odd special cases, this should be good enough, maybe?
4 Likes
Okay, so would it be possible as a QOI thing to get a lint when become fails to apply (when using llvm as the backend)? Is that narrow enough to be possible?
Because again, having silent runtime bugs is not what I expect from Rust. Rather I expect errors to happen at compile time. And my interest is in threaded interpreters (for speed and better branch prediction than having a main dispatcher loop). So my code will actually be wrong if it fails to apply TCO.
I don't know what exactly you mean by "become fails to apply". But become is carefully designed to only be allowed when a tail call is, in principle, possible on almost all targets. IIUC, it will always add musttail.
I think the only actual open question is what become should do on wasm (or other targets without tail calls that we may get in the future). The RFC doesn't really speak to that and I think this will be an open question for a while, but must be resolved before stabilization. I agree with your arguments for just rejecting such code on wasm, though I worry that this might mean in practice Rust is just not usable on wasm (or at least, MVP wasm that doesn't have tail calls), since some core library will start using become. I don't have a strong position either way and I am happy that it's not going to be my decision. 
I like the proposal of treating it like atomics, and having a cfg(tail_calls) so code can use a non-become fallback implementation on such targets.
I don't know if there is sufficient need for a statement that behaves like become in terms of dropping local variables, but compiles to a regular call on targets where tail calls are not possible.
2 Likes
TBH, this is why it's not already stable. If we just wanted "yolo, might work, good luck" we could have just added something that emits musttail in LLVM years ago.
1 Like