[Im]mutable variable vs [Im]mutable data type vs compile time [un]known data size

I may understand things wrong
and would appreciate if someone could make it clearer if I am wrong,
but what I understand is as follows.

1)
Immutable data type is just another name for fixed in size (compile time known size) data type (so data size does not changes through program).
They can be kept in inexpensive stack.

Mutable data type is just another name for compile time unknown size data type (so data size may changes through program).
They have to be kept in expensive heap.

Or is data type mutability broader concept ?

2)
Immutable variable does not allows to change data it owns.
Mutable variable does allows to change data it owns.

let x = 5;                     // 5 pushed to stack and owned by x.
//x = 8;                       // ERROR - x does not allows change data it owns.

let mut y = 5;                 // 5 pushed to stack and owned by y.
y = 8;                         // y allows to change data its own
                               // so now 8 occupies the same "area" in stack that 5 previously.

let s1 = String::from("aaa");  // Memory for "aaa" allocated in heap and s1 owns it.
//s1 = String::from("bbb");    // ERROR - s1 does not allows change data it owns.
//s1.push_str("ccc");          // The same here.

let s2 = String::from("aaa");  // Memory for "aaa" allocated in heap and s2 owns it.
s2 = String::from("bbb");      // s2 allows to change data its own
                               // so old "area" for "aaa" is dropped from heap,
                               // new "area" in heap is allocated for "bbb"
                               // and s2 now owns this new "area".
s2.push_str("ccc");            // The same here (.just for "aaaccc").

The terminology of ”immutable data type” vs “mutable data type” comes up more typically in programming languages without Rust’s unique ownership and borrowing system. When applied to Rust, the typical distinction does not really apply as much anymore.

In more “traditional” (e.g. OOP) high-level programming languages, data types are allowed to be shared between multiple places, and thus mutating – say – some collection of elements can have “surprising” effects on other unrelated pieces of code that happen to have gotten a copy of the reference and suddenly may observe the data changing on them without warning. Rust can do the same thing with shared mutability, e.g. via Mutex or RefCell, but using those kinds of primitive is not the most common thing, and rarely done when you just want some “data types”. Of course, things like e.g. concurrent (shared mutable) hashmaps do exist, but one might consider such types more of a combination of data type and synchronization primitive.

For simple data types without shared mutability, there is an argument to be had that all data types in Rust are in a sense “immutable”. Of course, saying this is also somewhat confusing because Rust definitely has a notion of “mutation”. One interesting example to look at is Rust implementations of “immutable data types” in the more traditional sense. Since those kind of data types do have applications, of course people have implemented some in Rust, and what their API looks like tells an interesting story about Rust’s approach of “mutability”.

One example crate to look at for this would be “im” (literally named after “immutable data types”. If you look at the API of their Vec equivalent, Vector, you will notice that there is apparent mutation involved. Lots of methods take &mut self and mutate the structure or elements of the vector. Really, the only noticeable difference in terms of type signatures is the large amount of Clone bounds appearing on most functions.

This is surprising to people familiar with other programming languages, where immutable data structures will differ in API in that ordinary/mutable data structures would have, say, a push(elem: T) method (assuming an implicit this argument!), and the immutable data structure would have a push(elem: T) -> List<T> method that returns a new list, leaving the original one unmodified.

While the same could of course also be done in Rust, the way the im crate does it is better in multiple ways. In your typical OOP language, even when the data structure is immutable, the variables that hold such data structures can still be changed. And indeed if you want to e.g. add an element to an immutable list, you might do something like list = list.push(x); mutating the variable to hold a reference to the newly created, modified list. This has some sense since while the variable is unique, everything it references can be shared, so mutating the variable is a lot safer and less surprising since this kind of “mutation” is always kept local. Rust’s ownership model allows us to extend this notion of safe mutation to the contents of the data structure itself, since unique ownership means that replacing the value in a variable with a new data structure, or mutating the existing one in-place, typically behaves the same. Well… except that in-place mutation is faster, so it’s the perfect optimization, changing nothing about the observed behavior, but making things faster.

And that’s the strength of APIs such as the one that im has: The methods still take &mut self arguments, but their behavior is essentially the same as replacing the whole value in the variable with a new data structure; just more efficiently. The main way in which the API of an immutable data structure such as the Vector linked above differs from Vec is that calling .clone() on a whole Vector<T> is super cheap and it’s implemented by sharing large parts of the data structure that didn’t change. Once one copy changes a part that was previously changed, the T: Clone bounds allow the implementation to copy the necessary elements on-demand, as needed, but there’s no need for any upfront bulk cloning of everything in the whole vector. Now, with the explanation of how it works, the concrete advantages that im has, leveraging Rust, compared to immutable data structures in typical OOP languages, are

  1. the data structures are more ergonomic to use; you can still write list.push(x), you don’t need to do the dance of refactoring your code into the list = list.push(x) style
  2. the data structure can be aware of which parts of it are actually shared, and which aren’t, since the .clone() operation that does the sharing is explicit and custom implemented. This way, mutations of parts of your data structure that happen not to have been shared at all in the first place, can just mutate the data in place after all, which can be a significant performance benefit compared to the conservative approach of always producing new copies of the parts of data structure and its elements, whenever a new modified version of the data structure gets made

Well that was a bit lengthy, but I hope it’s conveying my thoughts on this terminology in an understandable manner. Regarding your concrete questions, let me add…

This kind of distinction is typically not associated with the terminology of “[im]mutable data types”, though there is a case to be had that, in your typical OOP languages, a data structure that lives entirely on the stack (such e.g. primitive types like integer types or bool or char in many languages, like e.g. Java) is always an immutable data type, because the only way they do sharing is via heap data, and if there’s no shared mutability, then arguably there’s no true “mutability” at all. Interestingly, in Rust, even data on the stack could be shared mutably between multiple places (or even threads) and thus being more of a “mutable data type”. E.g. a Mutex<T> value does not involve heap allocations (anymore), and you can share it between threads using e.g. the thread::scope API.


While this kind of thing is, unsurprisingly, generally the case in Rust, the special case of “shared mutability” (also called “interior mutability”, because it’s mutating of things inside of a considered-immutable outer value/container) in Rust means that mutation of data contained inside of an immutable variable might still mutate. For example if you have a let x = Cell::new(42);, you can not replace the whole Cell, but the (at run-time equivalent) operation of replacing the value inside of the cell is still possible (via x.set(1337) for example, which is a &self method) (here’s the API docs for Cell).

7 Likes

These are both wrong, on at least three counts:

  1. There are no "immutable" and "mutable" types in Rust. Only bindings ("variables") have mutability or immutability. If you have a let mut x = … declaration, then you can assign a new value to the declared variable, no matter its type.

  2. Whether something is statically-sized or dynamically-sized doesn't affect its mutability. First of all, you can't have a direct, by-value binding to a dynamically-sized value in current Rust, so the question is not in itself meaningful to ask in the first place. But even if dynamically-sized locals are implemented one day, whether something is sized or not will still not affect the mutability of whatever variable it is bound to.

  3. Dynamically-sized values don't have to be on the heap. They have to be behind indirection, but a pointer can point anywhere, and the real backing value of a DST always has a concrete, statically-sized type, which can be on the stack. For example:

    let x: i32 = 0;
    let x_dyn: &dyn Display = &x; // x_dyn points to a DST that is on the stack
    
    let y: [i32; 3] = [1, 2, 3];
    let y_dyn: &[i32] = &y; // y_dyn points to a DST that is on the stack
    
2 Likes

Rust doesn't really have immutable data. (Im)mutability is dependent on how you access the data.

In simple cases, access via exclusive &mut can mutate, and access via shared & reference freezes the data and disallows mutation. But such loans can be temporary and change from scope to scope, so the same data can be immutable for one function, and mutable for another function.

Exclusive ownership can also mutate. When data has a single owner, and isn't already borrowed, it can be mutated. There's let and let mut, but it's is only a shallow "did you mean to use this variable for mutation?" type of check in Rust, and does not control mutability of the data behind the variable. Even data in a let x "immutable" binding can be moved to another binding or used in a temporary expression where it can be mutated.

Then there's interior mutability, which allows mutating some data types even via & reference. Rust does not care about immutability for the sake of it, it cares about preventing data races. Data types that can be shared and still somehow ensure mutation is safe, can be mutated via & reference too. This is true for types like Atomic*, Mutex and RefCell.

Types being sized has nothing to do with it. Stack vs heap has nothing to do with it. Arc<[u8]> is dynamically-sized and on the heap, but forbids mutating the slice.


let x: &'static str = "hello";

There's no way to mutate this "hello". The text could be in a read-only memory of the program, or even burned into a ROM chip that physically can't change.

but you can have the same data type stored very differently:

// very mutable, on the heap
let mut t = String::new();
t.push_str("HE"); t.push_str("LLO");

// doesn't have to be a String, and can even be 'static! 
// And dynamically sized too.
let x: &'static mut str = Box::leak(t.into_boxed_str());

// and still mutable!
x.make_ascii_lowercase();

// and become a &'static str that you're not allowed to mutate any more
let x: &'static str = x;
2 Likes

In general, don't get too hung-up on the words "mutable" and "immutable". mut bindings don't change the types of things and aren't an inherent property of the variable in question, they are more like a lint that makes you declare it's ok to take a &mut reference or overwrite a variable. You can always rebind the variable using mut, too.

Moreover, Rust features interior mutability, which allows mutating through a &. So "immutable reference" is definitely a bad name for &; a better name is "shared reference". Using this terminology, interior mutability can be thought of as shared mutability.

And following on from that, &mut references would be better named exclusive references. [1]


Others have noted that Rust doesn't have immutable data, but to hopefully illustrate another way:

use core::cell::RefCell;

//     v  Not a `mut` binding
fn foo(s: String) -> String {
    //  vvvvv  But I own it so I can rebind it as `mut`
    let mut s = s;
    // And then mutate it
    s += " world";
    s
}

fn main() {
    //  v  Not a `mut` binding
    let c = RefCell::new(String::new());
    // But `RefCell` has shared mutability, so I can still mutate the
    // contents (even without a `mut` binding)
    c.borrow_mut().push_str("Hello");
    
    let s = foo(c.into_inner());
    println!("{s}");
}

Playground.


  1. Not only because "mutable reference" implies there's such a thing as an "immutable reference", but also because the exclusiveness of &mut is sometimes the more important property. ↩︎

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.