Moderator note: thread split from An immutable loop structure `loop let` - #9
what's wrong with become? to me it seems pretty reasonable, we replace the current stack frame with one corresponding to another function.
recur is simply incorrect, as the keyword represents a tail call, not necessarily recursion. it is possible (and frequently desirable) to recurse without using a tail call, and it is also possible to perform a tail call in a non-recursive context.
I also think become is a bad name. That the stack frame gets replaced is how it is technically implemented, not what it means.
It's kind of like BinaryHeap and BTreeSet are bad names because the names talk about implementation details rather than what functionality they are implementing.
How about tail <expr>?
I would argue the opposite, the stack frame replacing is the only meaning of become.
No, the stack frame is not even a concept in the abstract machine.
The meaning of become is that it is a tail call, i.e. everything else the function has to do has been done.
Arguably this is useless. People care about tail calls because of the associated optimization, not because everything after it has been done.
Moreover there are tail call optimizations that allow some operations to be done after the tail call.
The guarantee isn't supposed to be useful to the programmer. It's the other way around: the programmer is giving the guarantee to the compiler.
It's kind of like declaring a variable private: the programmer is putting a constraint on him/herself.
false, the abstract machine absolutely deals in stack frames.
quoting the rust reference chapter on variables:
A variable is a component of a stack frame, either a named function parameter, an anonymous temporary, or a named local variable.
is that so? every usecase i've seen for become is "this will make your code not stack overflow". it's not supposed to be commonly used, it's supposed to be a niche feature that is a lifesaver for certain embedded programs, or increases robustness for programs that must accept any untrusted input and not crash.
The term "tail call" implies this. The ability to deallocate local variables is what makes the call "tail".
The word "become" does not describe what happens with stack frames. The old stack frame doesn't "become" the new stack frame, except maybe for directly recursive tail calls. The old stack frame gets deallocated, and a new stack frame, of a different size and with different variable types, gets allocated.
The wikipedia article about this topic uses the word "tail" 127 times and "become" 2 times.
The only AM impl (miri) does have a stack and frames and implements become by replacing the last stack frame
It must be for backtraces to be a thing which exist on the abstract machine. Stack frames certainly don't look like they do on a concrete machine, but the AM does keep track of the stack of function calls which are the current execution state.
The opsem would indeed be to deallocate the old frame and allocate the new frame. But two different lenses both support the "become" presentation:
f > g becomes f > h then returns to f, instead of adding a call to the stack to get f > g > h, returning to f > g, then returning to f.am.frames[call_depth] becomes the frame of h instead of the frame of g.It doesn't particularly matter that frame g is removed and then frame h is added, because this is done in a single "step" of the AM; the intermediate state is never observable.
There are two camps here. One does want become to guarantee that the call will not result in a stack overflow (gets TCOd). This may require become to have target dependent semantics based on when tail calls can be generated. The other camp would like become to be weaker, and only have the AM effects — that any locals' lifetime ends before the become along with whatever language applies for controlling when frames may or may not appear in backtraces.
I've been a proponent of the latter camp, because I'm sensitive to the missed optimizations due to places' lifetime ending after a "tail" call, independent of the applicability of TCO, and the former camp has many more active voices supporting it. I'm not insensitive to the desire for guaranteed TCO for specific code dispatch patterns that LLVM fails to optimize the trampolined form of, but I think both are needed.
Perhaps become not requiring TCO and something like #[tail] become guaranteeing it would improve your opinion of the naming?
Then those should be done on plain return. Keyword become is necessary because it has impact on the drop ordering of function locals and temporaries.
For my use cases it seems fairly useless without the guarantee that TCO is happening. And the ergonomics of having to also add an attribute for this common case seems bad. Perhaps a attribute for the unusual case "I'm OK with this not turning into a tail call" would make more sense.
I still think become is totally a wrong verb, for two reasons. For concreteness, suppose you write:
become sin(x);
The first reason is that the target of speech is wrong. Whom are you telling to become something? You could argue the stack frame becomes some other stack frame, but we're not talking to the stack frame, we are telling the computer to do something. It makes no sense to be telling the computer to "become" something. replace_stack_frame would be better.
The second reason is that the level of abstraction is wrong. sin(x) is not a stack frame, it's an expression. It makes no sense to be talking about replacing stack frames at this level. It's as if instead of return; you wrote delete; because what happens on the stack is that a stack frame is getting deleted. But that's not what we want to express at this level of notation.
How about:
#[tail] return sin(x);
This argument seems to me to apply nearly as much to return as it does to become. Who should return what object to what other party? “The computer” is not returning a value to a party outside itself. The other party is whatever is on the rest of the stack.
Regarding your broader point, I would put the whole explanation as:
return expr, the rest of the control flow consists of returning expr to the caller.become expr, the rest of the control flow consists of whatever the control flow of expr is; the control flow becomes expr’s.We are asking the computer (really the CPU) to go back (return) to executing the caller.
Alternatively, we are asking the CPU to move (return) an object from the callee to the caller.
tail is far too common of an identifier to be made into a keyword. it's even used in the compiler multiple times
The thing doing the "becoming" is the callee, and it becomes a new callee after discarding locals. I don't think you even need to introduce the language of stack frames to make sense of this, it only requires an understanding of referential transparency.
OK but couldn't it be an attribute, as I proposed above?
#[tail]
return sin(x);
To me become is a variant of return with slightly different semantics.
One could also allow the attribute on the whole function that simply uses a block expression rather than a return:
#[tail]
fn foo(x: f64) -> f64 { something(); sin(x) }
Not all branches might return by tail call. For example some will usually return a value as the bottom case of recursion.
I think you would have to flesh out the details of how that should work: for example should any function calls in the return expression (including implicit ones that are not using the return keyword) cause a compile error if they cannot be turned into tail calls? What about something like return sin(x) + cos(y) in such a function?
The attribute on the whole function wouldn't apply to early returns, only to the final block expression. I guess putting the attribute on the final expression directly might be cleaner:
fn foo(x: f64) -> f64 {
something();
#[tail]
sin(x)
}
These wouldn't compile, but that's a separate issue that is orthogonal to whether the syntax is become or #[tail].