> ...there is an entire field of pointer analysis and escape analysis that can and does infer uniqueness and reasons about whether two references can be aliases.
You can't do this automagically in the general case, you really do need something much like separation logic. (And of course the Rust borrow checking semantics can be seen as a simplified variety of separation logic.)
Classes and fields don't give you completely local reasoning about mutable state, because class/object A can end up depending on the mutable state of class/object B. And class inheritance as found in Java adds all sorts of further complexity of its own, especially as programs evolve over time.
>>I much prefer Rust's approach of "mutable references never alias"
>This rules out a vast majority of fundamental algorithms.
To be more precise, in Rust:
- '&mut T' (a mutable reference to T) can never alias.
- '(asterix) mut T' (a mutable pointer to T) can alias.
The advantage is that you can write most production code with a mix of '&T' and '&mut T', which allows the compiler to assume no mutable aliases anywhere. But if you're building a doubly-linked list, then you can explicitly choose '(asterix) mut T'. (For other options, see https://rust-unofficial.github.io/too-many-lists/.)
In practice, it depends a lot on the code you're writing. I've written tens of thousands of lines of production Rust without needing shared mutability. But if I were writing a traditional game or GUI toolkit, then I might miss shared mutability a lot more.
> Even the borrow checker is from research papers and languages from quite a while ago.
Eh, that's underselling Rust's contributions. Rust is more flexible than anything I know of when it comes to enforcing aliasing-xor-mutability. Cyclone for example was much more restrictive in disallowing aliasing (see Grossman's "Existential Types for Imperative Languages").
The key feature that Rust has is flow-sensitive permissions on unique loan paths, which is actually pretty novel as far as I'm aware.
> Haven't yet written any Rust code, but aren't those two things contradicting each other?
I don't think so.
One way to ensure that data isn't mutated by different parts of a program,
is to have immutable data structures.
The other way - the Rust way - is to seriously track who holds mutable
references to the same data and just not allow it.
So you can have more optimized mutable data structures, but can be sure,
that if you're holding a mutable reference, that no other can modify
the data during the lifetime/scope of your mutable reference.
> Is there anything inherently unsafe about multiple (even mutable) references to an object? Has it been shown by some rock-solid argument that such stringent ownership semantics are the only way to guarantee compile-time safety?
Nobody is claiming this is the only possible way to make safe programs, as far as I know formal proofs a la seL4, when done correctly, can also prove the absence of essentially any kind of defect. The problem with multiple mutable references is that if you have them, you need some way to validate that across all possible mutable references to a given piece of memory, there are no unsafe concurrent accesses. Rust's claim to fame is "fearless concurrency", and as far as I know borrow checking with one mutable reference exclusive with all other references is the simplest approach to providing concrete data race safety in the face of still having mutable shared state across code. Nothing on this page even mentions data races, and I'm not sure how you would accomplish safety against data races from this design alone.
> I'm asserting (perhaps mistakenly) that you don't need to address the aliasing issue as completely as (Safe) Rust does in order to achieve the same memory safety that (Safe) Rust does.
You need to address the aliasing, or address the mutability. They're two sides of the same coin.
> only its structure
I am not 100% sure what distinction you're making here, sorry. What's "the container" vs "its structure"?
> From a memory safety perspective, this is overkill.
Yes, in general, Rust takes a soundness-based approach. If you can't prove that it's safe, then it's not safe. This takes the other path, which is totally valid, mind you! But that means it will allow cases that are not safe.
> And for simple objects that do not have dynamic structure (or any indirect references), then the "mutable references are exclusive" restriction provides no memory safety benefit at all, right?
That's not right. You can have a data race to a plain old integer.
> Rust enforces single mutable ownership or multiple readonly aliases at a time. In fact, they are very good idioms to structure large codebase anyways, and normally they do not get in the way for ordinary applications.
No these limitations routinely get in the way for ordinary applications. The borrow checker is a source of frustration when ramping. Back-references get smuggled in as array indexes. Prohibiting global variables is tough. Any sort of app that can't be structured as a tree is going to have pain.
This safety is really valuable, but let's not pretend it comes for free.
> The complexity of Rust's ownership model is not added to an otherwise simple program, it is merely the compiler being extremely pedantic about your code obeying rules it had to obey anyway.
Not exactly.
I remember when I learned Rust a few years ago (so maybe things are different today), sometimes the compiler didn't let me do things that should have been perfectly fine things to do.
This forced me to write the code in a more complicated way than what should have been necessary.
I think this often happens beacuse the compiler's rules don't always match reality.
Like if I have a struct S that contains members X and Y, the compiler doesn't let me have two mutable references to that struct even if one of them only changes X and the other one Y.
In reality there is no problem but compiler thinks there is a problem so it forces me to write more complicated code.
I have had this almost exact problem in a program I was writing.
The reason I could not just pass X to one function and Y to the other is that one of those functions I had to call was from a library that could only take an S.
The solution was that I had to write a macro that extracted Y from S and call that macro every time I wanted to pass Y to a function.
Isn't that arguably because Rust has even stricter aliasing rules? Not only are you not allowed to have differently-typed mutable references to the same memory, you (approximately) aren't allowed to have multiple mutable references to the same memory, period, even if they are the same type.
> what most people would like is rust minus borrowing
It's already possible. Use Rust reference-counted smart pointers[1] for shareable immutable references and internal mutability[2] for non-shareable mutable references checked at runtime instead of compile time.
> What makes dealing with the borrow check hard is that it triggers on code that intuitively is correct, it can be hard to envision why it's not.
Because it's more expressive than just forbidding mutability. You could program in Rust the same way you program in Haskell, by encapsulating mutability in functions with different types (&mut). Then the flow sensitivity and other issues would never bother you.
Rust's flow-based control of mutability is strictly more expressive than the monad system of Haskell. If you don't like that expressivity, don't use it.
> It's not finished, though, and honestly I'm pretty sure that borrow checking isn't even that hard compared to all the other stuff a Rust compiler has to do, like generic/trait resolurion.
You can implement basic trait resolution via name mangling and a global map. I did this as an experiment a number of years ago to implement type class-like overloading in C. I'm not sure how far you could take that technique though. I don't think it would work for higher-kinded types, but Rust doesn't have those.
> Oddly, Rust's ownership system really does solve these problems
No. Rust's ownership problem solves it for trivial cases, at the cost of making it hard to do other things (such as sharing references past the lifetime of the owner without resorting to Rc<T> or Arc<T>, at which point you don't really have lifetime guarantees anymore).
The essential limitation of Rust is that (without resorting to Rc<T> and Arc<T>, which would put you back to square one) it is conceptually limited to the equivalent of reference counting with a maximum reference count of 1. In order to make this work, Rust needs move semantics and the ability to prove that an alias has a lifetime that is a subset of the lifetime of the original object) and may even sometimes have to copy objects, because it can never actually increase the (purely fictitious) reference count after object creation.
This inherent limitation makes a lot of things hard (or at least hard to do without copying or explicit reference counting). Structural sharing in general, hash consing, persistent data structures, global and shared caches, cyclic data structures, and so forth.
In short, you have the problem with shared references less, because Rust makes it hard to share data in the first place, for better or worse. (Again, unless you resort to reference counting, and then you get the issue back in full force.)
> AFAIK, you still have to be very careful since data races based on data dependencies can never be excluded in general
Hmm. Maybe I don't understand what you're getting at here. It seems like you're suggesting something like a[b] = x could race in safe Rust because we don't know b in advance and maybe it ends up being the same in two threads ?
But Rust's borrow checker won't allow both threads to have the same mutable array a so this is ruled out. You're going to have to either give them immutable references to a, which then can't be modified and so there's no data race, or else they need different arrays.
This is boringly easy to get right in theory, Rust just has to do a lot of work to make it usable while still delivering excellent runtime performance.
> I haven't thought through the details, but I suspect it's possible to adjust the semantics of rust in a way that allows multiple mutable references without sacrificing memory safety.
Please do think about the details deeply, because if you find a way to do this, you'll probably bring a revolution to Rust.
I'm kind of skeptical of course, but I'd be really happy to be wrong.
> I'd hoped that language features like the typestate stuff that used to be in Rust would someday make the work required to use sound analysis tools in production code smaller. I'm not sure if much thought has been given to what kinds of accommodations languages could give to ease static analysis while still being programmer friendly.
Well, since the Rust borrow check is basically a static analysis that's always on and is required to pass for the compiler to emit code, we've put a lot of thought into how to make it as programmer friendly as possible. The final trick that seemed to got it to fall into place was restricting data to only one mutable reference at all times—this was a restriction that's easy enough to understand and can be readily explained through error messages and tutorials. There's still a learning curve, of course, but I think we've got the system down to a reasonable level.
> My question to HN is: do any languages that really emphasize pointers and iterators over arrays and indices have a non-cumbersome way of telling the compiler when no aliasing is expected?
Rust has this concept baked into the language: any mutable reference is statically guaranteed to not alias anything else that is accessible. Non-mutable references can alias each other, but I don't think there are any optimizations that could be inhibited by this.
>You still have to fight with borrow checking in Rust as in C++, it’s just not automated.
It's not that easy. The borrow checker gives you memory safety and thread-safety. In C++, you always have to worry about memory safety, so here the ownership model and borrow checker is a pure win. However, in C++ you don't have to worry about thread safety in a single thread...there's no barrier to passing pointers around and mutating things from different places in your code. In rust, the borrowchecker disallows shared mutable state...that's a huge win if you want to parallelize your code later on, but it also means that things that are trivial in C++ take a lot of thought and effort in rust, especially if you're thinking in a C++ paradigm (as opposed to coming from a functional language).
> ETA: To me it feels a bit like the icky type coercion magic some languages have that lets you write code that kind of works even though you don't understand what you're doing. I don't know Rust though, so this may be totally different.
It is quite different.
In Rust already it is possible to proxy "pointer to a thing" as "the thing itself" in a lot of different places, making it a lot more pleasant to work with. This is a continuation of that trend.
It's pretty easy to know if most things are a pointer or not, but more importantly if it's not immediately obvious it rarely matters (i.e. you're not the one creating or consuming it; you're just sharing borrows to it). At which point sharing pointer-to-value vs pointer-to-pointer isn't very different, and Rust implicitly deals with that.
> I find a bit of solace in the fact that implementing a data structure like this in a non-garbage collected language without Rust is also quite tricky
What? No it isn't. The entire problem here is incorrectly assuming that "A owns B" implies "A has a pointer to B". I don't know if this is a Rust-imposed constraint, but it certainly isn't a logically necessary one. Just do what C++ (and C#, etc.) do: the data structure (std::list, etc.) owns all the nodes, and the nodes merely reference each other. The nodes don't own their siblings. It makes sense and it doesn't get tricky.
You can't do this automagically in the general case, you really do need something much like separation logic. (And of course the Rust borrow checking semantics can be seen as a simplified variety of separation logic.)
Classes and fields don't give you completely local reasoning about mutable state, because class/object A can end up depending on the mutable state of class/object B. And class inheritance as found in Java adds all sorts of further complexity of its own, especially as programs evolve over time.
reply