How do languages ensure 'interior immutability'?

Question

In C#, i can declare an immutable field on a class using readonly. This works for value types, but if its a reference type, there is nothing stopping me calling methods on the object to change its internal state.

C# sort of solves this problem by providing concrete types and interfaces that simply dont present a way to modify state.

Languages like F# and Rust prevent this kind of change (and appear to do so at the language, rather than the type level). What approaches are used to achieve this? Do the developers mark each method / function etc. as mutating and this is picked up by the compiler? If this is the case, how would this work for user defined types? Alternatively, does the compiler somehow trace the entire path the function execution might take, and look for where it might change values in memory?

Answer 1

C, C++, and Rust have a concept of const (Rust: mut) types. Those are a type qualifier. I.e. you can have an int and qualify it as a const int. A const value cannot be mutated.

This becomes powerful when we consider pointers or references to const values. If I have an int* (C), int& (C++), &mut i64 (Rust), I can change the pointed-to value. If I have a const int*, const int&, &i64, I cannot change that value.

A function declares how it takes its arguments: by value, by pointer/reference, or by const pointer/reference. This determines which operations are possible within the function:

// C, C++
int function_a(int* x);
int function_b(const int* x);

// C++
auto function_a(int& x) -> int;
auto function_b(const int& x) -> int;

// Rust
fn function_a(x: &mut i64) -> i64;
fn function_b(x: &i64) -> i64;

I.e. not the function is marked as const or mutating, but its arguments as const or mutatable. If passed by value, it makes no difference whether that value is const or mutable, as the function operates on its individual copy, and not difference is externally visible.

C++ and Rust also support method syntax. Here, the syntax is slightly different. In particular, in C++ the this pointer is an implicit argument. So the const qualifier is on the outside of the argument list:

auto method_a() -> int;
auto method_b() const -> int;

fn method_a(&mut self) -> i64;
fn method_b(&self) -> i64;

So the compiler doesn't have to trace the whole function call graph to see whether a value might be mutated or can be const. Instead, the function signatures encode the necessary information in the type system. So for each function that is being type-checked, the compiler only has to see which functions, methods, and fields are accessed. If I try to perform a non-const operation with a const value, that is a type error.

Aliasing

As described here, this only prevents mutation through that reference. Other non-const references to the same value might exist. E.g. consider this C function:

int foo(int* mutable, const int* constant) {
  *mutable = 42;
   return *constant;
}

Which value is returned? If the pointers point to different objects, it will return the value pointed to by constant. But they could also point to the same object (an alias): int x; int result = foo(&x, &x). Now, the function will return 42. In Rust, this is prevented to the borrow checker. The type system proves that to any object, there is at most one mutable reference, or either any number of constant references. There can never be a mutable and constant reference to the same object at the same time. However, this only works because of a much more constraining type system compared to C++.

Interior mutability

There are ways to implement interior mutability, so that some field can still be modified even if it is part of a const value. In C and C++, you can subvert the type system by casting. C++ lets you annotate fields (not types!) as mutable. Rust supports Cell and RefCell abstractions in its standard library to similar effect.

Comparison with reference semantics

Note also that for these languages, there are only value types (which can be qualified as const or mut). To get reference semantics, you explicitly use a pointer or reference. This is in stark contrast to C# or Java, where readonly and final apply to variables, but not to values – and the value that is referenced by a variable can still be mutated if it is a reference type.

I am not sure how F# specifies immutability, but as a CLR language it cannot differ significantly from C# semantics.