3 ms·

So originally, lifetimes were lexical only. And when the move towards non-lexical lifetimes was being considered, this aspect was discussed heavily. It turns o

So originally, lifetimes were lexical only. And when the move towards non-lexical lifetimes was being considered, this aspect was discussed heavily. It turns out that programmers seem to think about scope in a cfg style, and don’t really think in lexical scope, even though it’s “easier.” Tons of people, even new ones, would look at some code Rust rejects and be like “but obviously this is safe because:” and then state the non-lexical reasoning. People generally find the non-lexical borrow checker to be far easier to use. I think it is actually one of the larger things Rust has discovered, that doesn’t get talked about very much. And it’s also a great demonstration that simpler doesn’t always mean easier.

sfink 3y ago
This is rather fascinating to me, as someone who maintains a flow-sensitive checker. No relation to the Rust borrow checker, since mine is an unsound linter for C++ code. Though there are similarities, as mine is also about memory safety (it looks for pointers that are live across a function call that might GC, and therefore could invalidate them by moving the data they're pointing to.) I spend a lot of effort trying to make the errors comprehensible, so I have to think about the mental models people are using. The entry point for people is almost always a reported error. The notion "live across a GC call" isn't natural to most people, so I dump out the entire live range (which might be from the previous iteration of a loop, for example) in the hopes that it'll sort of tell a story: "see, you set the variable's value to a pointer here, then you run this code, and this function call within it might GC, and then you use the variable's value here". But that's just an example path through the function, and potentially confusing if that particular path is not possible in practice (but another unmentioned path is). That's the risk of having a more precise analysis: there are more ways that the specific error can be wrong even though the report is a true positive. Earlier, the analysis was simpler to mentally model: is there a path fragment that mentions variable X, then calls something that can GC, and finally mentions X again? But since then, I've added much more precise data flow to check whether the final use of X is an actual use and not clobbering the previous value (in which case, its live range ended sometime earlier). As with the borrow checker, that just provides reasons to not report an error that the simpler analysis would have, but those do matter to the user. Especially when they're struggling to restructure code, and having to mentally do the same analysis to figure out what changes will fix the problem. In my experience, there are usually simple code fixes that eliminate a problem entirely and would have worked with the simpler analysis. For the more complicated cases, users are generally pretty appreciative when the analysis is smart enough to allow fixes to be more targeted and natural. (They aren't appreciative of the false positives that the more sophisticated analysis never showed them, because they pretty much only think of this stuff when they get an error report. But that's ok!)
- steveklabnik 3y ago
  That sounds like an interesting project! I wonder if the soundness is part of it, see nicoburns' sibling comment. But error messages are quite hard. If I recall correctly, in Rust's case, error messages got better with NLL, but that may have been because a tremendous amount of work was put into it by people who were concerned that it was going to become harder to understand, rather than some property of NLL itself. It certainly was an active concern at the time, though the exact timelines and steps are a bit fuzzy to me these days.
nicoburns 3y ago
Given that: - The cfg style checker accepts a strict superset of the programs that a lexical checker would (so if you're thinking lexically then your thinking will still work). - The checker is (modulo bugs) sound, so if it thinks a program is valid then it is (so you don't actually have to think deeply about the complex cases if you don't want to). it makes sense that this would be easier to use.
- steveklabnik 3y ago
  Yes, I think these things are important factors too.
- lmm 3y ago
  Not necessarily. Imagine a checker that accepted lexically valid programs and also cfg-valid but lexically-invalid programs where the number of lines was odd; such a checker would fulfil your criteria but probably be more difficult to use than a purely lexical checker. IMO Rust has already handicapped their language evolution with NLL and the more complex they make the checker the worse a pit they're going to dig themselves into. As long as it's simple enough to understand it's not too bad, but if we get to the point where people can't reason about the checker there'll be no coming back.
  - GolDDranks 3y ago
    > IMO Rust has already handicapped their language evolution with NLL Do you see alternative paths from lexical lifetimes?
    - lmm 3y ago
      I think they should have focused on making lexical lifetimes more usable and lightweight, in a general way that was available to functions rather than just language keywords. Think making it possible to write if/while/for as regular functions in the language - which would also make it possible to write async a lot less painfully, because you'd be able to write your async control flow functions "in userspace". Instead they've chosen to deeply intertwine their particular control flow model with their borrow checker, which means changing or experimenting with those control flow keywords (or introducing new ones) is going to be a lot more costly, and any radical new ideas (whatever the next 10-20 years' equivalent of async is) are going to be much harder to introduce.
rayiner 3y ago
Is it that the CFG version better reflects programmer’s intuition about “what should pass the borrow checker,” or that programmers can more easily predict, after understanding the rules, whether the CFG version will accept or reject particular code?
- vacuity 3y ago
  Yes. The first code example in the blog post, referred to as "Problem Case #3", shows a case that intuitively should work, is rejected currently, and would be accepted by Polonius.
- steveklabnik 3y ago
  I describe it as intuition because people talk about these things intuitively. They say things like "the borrow checker finally accepts code I know it should have accepted all along". For example, let's look at the example used in the very first part of the NLL RFC: fn capitalize(data: &mut [char]) { todo!() } fn foo() { let mut data = vec!['a', 'b', 'c']; capitalize(&mut data[..]); data.push('d'); } This code works just fine. But maybe we want to pull the slice out into a variable. So we do this: fn foo() { let mut data = vec!['a', 'b', 'c']; let slice = &mut data[..]; capitalize(slice); data.push('d'); } This code would fail to compile under the old borrow checker. Why? Because you have two &mut references pointing to the same thing. People are, I think, rightfully surprised that this code doesn't just work. It is very unintuitive that extracting a temporary to a variable causes code to no longer work. But that is exactly it: you are now changing the scope from small to large, thanks to lexical scoping. But people didn't talk about this code as like "Oh I understand that I am introducing a lexical scope and that means it conflicts." They talk about it like "but I don't use slice anywhere after the capitalize call. This code is safe. There's no point where these two mutable references are active at the same time. And you know I'm right because the temporary version works just fine, and this is equivalent." That is, their perception of scope maps closer to a CFG than to lexical rules. Frankly, I am not even sure that many Rust programmers could describe what a control flow graph is, let alone that they somehow learn the exact rules and then apply them. People don't learn programming languages that way, just like they don't learn human languages that way. It is largely a practice of building up intuitions and testing them out.

sfink 3y ago

This is rather fascinating to me, as someone who maintains a flow-sensitive checker. No relation to the Rust borrow checker, since mine is an unsound linter for C++ code. Though there are similarities, as mine is also about memory safety (it looks for pointers that are live across a function call that might GC, and therefore could invalidate them by moving the data they're pointing to.) I spend a lot of effort trying to make the errors comprehensible, so I have to think about the mental models people are using. The entry point for people is almost always a reported error. The notion "live across a GC call" isn't natural to most people, so I dump out the entire live range (which might be from the previous iteration of a loop, for example) in the hopes that it'll sort of tell a story: "see, you set the variable's value to a pointer here, then you run this code, and this function call within it might GC, and then you use the variable's value here". But that's just an example path through the function, and potentially confusing if that particular path is not possible in practice (but another unmentioned path is). That's the risk of having a more precise analysis: there are more ways that the specific error can be wrong even though the report is a true positive. Earlier, the analysis was simpler to mentally model: is there a path fragment that mentions variable X, then calls something that can GC, and finally mentions X again? But since then, I've added much more precise data flow to check whether the final use of X is an actual use and not clobbering the previous value (in which case, its live range ended sometime earlier). As with the borrow checker, that just provides reasons to not report an error that the simpler analysis would have, but those do matter to the user. Especially when they're struggling to restructure code, and having to mentally do the same analysis to figure out what changes will fix the problem. In my experience, there are usually simple code fixes that eliminate a problem entirely and would have worked with the simpler analysis. For the more complicated cases, users are generally pretty appreciative when the analysis is smart enough to allow fixes to be more targeted and natural. (They aren't appreciative of the false positives that the more sophisticated analysis never showed them, because they pretty much only think of this stuff when they get an error report. But that's ok!)

steveklabnik 3y ago
That sounds like an interesting project! I wonder if the soundness is part of it, see nicoburns' sibling comment. But error messages are quite hard. If I recall correctly, in Rust's case, error messages got better with NLL, but that may have been because a tremendous amount of work was put into it by people who were concerned that it was going to become harder to understand, rather than some property of NLL itself. It certainly was an active concern at the time, though the exact timelines and steps are a bit fuzzy to me these days.

nicoburns 3y ago

Given that: - The cfg style checker accepts a strict superset of the programs that a lexical checker would (so if you're thinking lexically then your thinking will still work). - The checker is (modulo bugs) sound, so if it thinks a program is valid then it is (so you don't actually have to think deeply about the complex cases if you don't want to). it makes sense that this would be easier to use.

steveklabnik 3y ago
Yes, I think these things are important factors too.
lmm 3y ago
Not necessarily. Imagine a checker that accepted lexically valid programs and also cfg-valid but lexically-invalid programs where the number of lines was odd; such a checker would fulfil your criteria but probably be more difficult to use than a purely lexical checker. IMO Rust has already handicapped their language evolution with NLL and the more complex they make the checker the worse a pit they're going to dig themselves into. As long as it's simple enough to understand it's not too bad, but if we get to the point where people can't reason about the checker there'll be no coming back.
- GolDDranks 3y ago
  > IMO Rust has already handicapped their language evolution with NLL Do you see alternative paths from lexical lifetimes?
  - lmm 3y ago
    I think they should have focused on making lexical lifetimes more usable and lightweight, in a general way that was available to functions rather than just language keywords. Think making it possible to write if/while/for as regular functions in the language - which would also make it possible to write async a lot less painfully, because you'd be able to write your async control flow functions "in userspace". Instead they've chosen to deeply intertwine their particular control flow model with their borrow checker, which means changing or experimenting with those control flow keywords (or introducing new ones) is going to be a lot more costly, and any radical new ideas (whatever the next 10-20 years' equivalent of async is) are going to be much harder to introduce.

rayiner 3y ago

Is it that the CFG version better reflects programmer’s intuition about “what should pass the borrow checker,” or that programmers can more easily predict, after understanding the rules, whether the CFG version will accept or reject particular code?

vacuity 3y ago
Yes. The first code example in the blog post, referred to as "Problem Case #3", shows a case that intuitively should work, is rejected currently, and would be accepted by Polonius.
steveklabnik 3y ago
I describe it as intuition because people talk about these things intuitively. They say things like "the borrow checker finally accepts code I know it should have accepted all along". For example, let's look at the example used in the very first part of the NLL RFC: fn capitalize(data: &mut [char]) { todo!() } fn foo() { let mut data = vec!['a', 'b', 'c']; capitalize(&mut data[..]); data.push('d'); } This code works just fine. But maybe we want to pull the slice out into a variable. So we do this: fn foo() { let mut data = vec!['a', 'b', 'c']; let slice = &mut data[..]; capitalize(slice); data.push('d'); } This code would fail to compile under the old borrow checker. Why? Because you have two &mut references pointing to the same thing. People are, I think, rightfully surprised that this code doesn't just work. It is very unintuitive that extracting a temporary to a variable causes code to no longer work. But that is exactly it: you are now changing the scope from small to large, thanks to lexical scoping. But people didn't talk about this code as like "Oh I understand that I am introducing a lexical scope and that means it conflicts." They talk about it like "but I don't use slice anywhere after the capitalize call. This code is safe. There's no point where these two mutable references are active at the same time. And you know I'm right because the temporary version works just fine, and this is equivalent." That is, their perception of scope maps closer to a CFG than to lexical rules. Frankly, I am not even sure that many Rust programmers could describe what a control flow graph is, let alone that they somehow learn the exact rules and then apply them. People don't learn programming languages that way, just like they don't learn human languages that way. It is largely a practice of building up intuitions and testing them out.