I am new to Rust and one thing that stands out to me is that in Rust, constness/mutability is not bound to the type, but to a particular variable. So, it seems to me like it would be impossible in Rust to create a mutable container of immutable objects (e.g. std::vector<const int> in C++) without having to create a new, specialized container.
My question is, was Rust's decision to bind constness/mutability this way out of necessity to facilitate their barrowing system, or is it completely orthogonal? Basically I am asking if you could create a language with a borrow checker that still used constness as a type trait as C++ does.
Rust's "if you can form a mutable reference to something, you can mutate it" rule (sometimes called "exterior mutability") isn't essential to the way that Rust works, and in fact there have been discussions about adding types that don't have exterior mutability. As such, there's no particular reason why a hypothetical different borrow-checked language would need to follow the same rule.
There are basically two ways you could change an object that you have a reference to:
You could use the reference to reach inside the object and change some of its fields. In current Rust, the rules for that are:
Cell and RefCell, but also things like Mutex.)Both of these methods require you to be able to either have visibility of the object's fields, or the ability to call a method that has one. As such, it's possible to make an object impossible to mutate via this method by giving it no public fields, and defining no methods in the same module that change its fields (perhaps by creating a small module just to contain the type definition and getters, but no setters) – Rust's visibility mechanisms then prevent any field-at-a-time mutation. (This is an important and widely used programming technique in order to ensure that objects obey particular invariants; for example, NonZeroUsize has a single usize-type field, but no way to mutate it because it would be very bad if someone set it to 0.)
You could use the reference to swap out or overwrite the entire object, replacing it with a different object of the same type. This is currently available for any type, using standard library functions like mem::swap and mem::replace – it can't break any invariants because the entire object is changed at once. This technique is normally called "overwriting" the object, even though swapping is the more general version of it.
Technique 1. is easy enough to stop in current Rust, so the question basically boils down to "is it necessary for technique 2. to always be supported?". It's certainly useful to have a method like that – but it's useful precisely because it provides another mechanism for mutating things, so if you have an object that's supposed to be immutable it isn't useful. It also ends up getting in the way of other language features that you might want to add to Rust: this most famously affects async, which needs to use Pin as a workaround to stop people swapping out a future while it's borrowing data from itself and breaking the references in it, but it also means that Rust effectively doesn't have a concept of "object identity" and so it currently isn't able to add language features that would depend on a reference to always pointing to the same object.
As such, there have been a number of proposals made to allow creating types whose objects can't be overwritten. Here's an example by Niko Matsakis, who is a member of the Rust language team and one of the people who decide whether or not features are added to the language. The primary concern seems to be backward compatibility, rather than any conceptual problem with non-overwritable objects, so newly designed non-Rust borrow-checked languages would probably be able to design non-overwritable types and/or places without an issue.
Several people, including me, think that Rust would have been better if it were designed from the start to make objects non-overwritable by default (with a mechanism provided to allow particular objects to be marked as overwritable – it's currently unclear whether it would be best to do this at the type level, using an "overwritable place" system, or by using a wrapper type that makes its contents overwritable, but all three seem like viable options). It has a number of advantages, and the disadvantages are fairly small (mem::replace and mem::swap are genuinely useful, but not used all that often, so it wouldn't be a huge problem to have to explicitly declare things to be overwritable).
Why wasn't Rust designed like that? It was probably just a historical accident: Rust was designed gradually over time and it took a while for the rules to gel together into a coherent language (for example, very early Rust didn't even have the "you can't create aliasing &mut references" rule, which subsequently turned out to be its most important feature). Some of its rules subsequently turned out to be bad ideas (e.g. allowing mem::forget to be called on any object – the rule was originally added because you can leak an object of any type by using a reference cycle of Rc, but it subsequently turned out that "leak an object and repurpose its memory" (mem::forget) is significantly different from "leak an object and leave its memory allocated" (Box::leak) and allowing the former leads to problems). Allowing any object to be overwritten is likely to be a similar situation, in which the choice was made before the full implications were known, possibly in the context of a somewhat different surrounding language.
I sometimes like to think of this sort of situation as "Rust would be a better language if it had been worked on for another ten years before being released – but then nobody would use it". Eventually, you have to release something even though you know the design probably isn't perfect (because you won't find out where it falls short until later). But that doesn't mean that other languages (possibly including future versions of Rust!) couldn't learn from it, and do things slightly differnetly.