Immutability across programming languages

Question

I'm quite confused about the concept of mutability (or mutation?), especially across different languages. In a language like Python:

x = 10 
x = 20

I believe this is called shadowing (or rebinding) and not mutability, because the literal 10 will evaluate to an integer object that is immutable.

In some languages like Racket, if I write (define x 10), I can no longer change it. Isn't that a form of immutability?

In the C++ case, I hear people say that this is an example of mutability:

int x = 10;
x = 20;

and that if I want to enforce immutability, I have to use const int x = 10; That got me quite confused. Would you please clarify this for me? Also, is there a difference between the concept of mutability in functional languages and non-functional languages, and do purely functional languages have something to do with this?

Answer 1

This is a common confusion with immutability. There's a difference between an immutable value and an immutable reference.

For example, say you have x = 10. You can't do something like 10 = 20 to change the value of x. The 10 is immutable. You can do x = 20, unless x is declared to be immutable. But that doesn't change the value of 10, just the value of x.

On the other hand, you can have const x = SomeObject(), where you can change stuff inside SomeObject, but you can't reassign x to point to a different object.

Values of value types (like numbers and strings in most languages) are immutable, but variables aren't unless declared to be such, even variables pointing to immutable values.

Answer 2

Welcome to one of the fun quirks of programming in different languages (and their different semantics)

In a general sense, whether something has the property of mutability, or if there is simply rebinding going on is one of perspective.

using a modified example like this:

a = new list(0, 1)
b = new list(1, 2, 3)
x=a
x=b

After this code runs, you would expect if you examined x for it to be a list of the values 1, 2 and 3. This is an example of x being mutable.

If you looked at the value of a you would see it still contained a list of the values 0 and 1. This might imply that the implementation of mutability of the variable x was done by rebinding its value to reference the variable b.

Now imagine if we then added the line

x.add(7)

now if we look at the value of x we know it will contain a list of 1,2,3 and 7 However what will be the value in b ??

If x was mutated by being assigned a copy of b then b will only contain 1,2 and 3 If x was mutated by being rebound to b then b will contain 1,2,3 and 7

Most programmers will refer to being rebound as "copying by reference", and this is the only option in most programming languages. However, some languages also enable copy by value. In which case a new list object was created and the list of items was copied into the new list. C++ is a language where copy by value is implemented, and is the default - you include a reference modifier to a variable declaration to mean that the variable contains references (bindings) to other objects.

Functional languages are typically immutable. It is this immutability that makes them functional, and that makes not only repeated variable assignments impossible, but also prevents code like this:

a = new list(1, 2, 3)
foreach (x in a)
  print(x)

The value of x is no longer immutable, and functional programming does not allow this.

Answer 3

In general, the mutability says that the values of object can be changed. Your C++ example is indeed mutability, because x is an int object, that the value 10 is stored in the object and that the assignment operator will OVERWRITE the old value to set it to 20.

C++ has by default a value semantic: objects are copied by value by default, unless you define another semantic or decide knowingly to work with pointers or references. Other languages such as Java are primarily reference based. When you copy an object, you duplicate in reality a reference and two variables then allow to change the same object. In this context, mutability is life critical, to not accidentally alter an object owned by someone else. The whole class is made immutable.

In C++ immutability can be controlled at the object level. const allows to qualify any object of any type to be immutable:

const int x=10;  
const Person p("Graddy","Booch");

The objects x and p can then no longer be changed. The concept of immutability is of surgical precision in C++, as you can also define member functions (methods) that are guaranteed to leave the object unchanged:

class MyTemperature {
public:
   MyTemperature(int t):temp(t){}
   int get() const;
   void set(int t); // can't be used on a const object
private:
   int temp;
};

Last but not least, one could imagine having some internal temporary fields that could change despite an object is const because they are not really relevant for the object state (e.g. like a ca he or memoization that could be rebuilt whenever needed). These members can be labelled as mutable.

The concept is similar to immutability in functional language although not the same. Functional languages avoid side effects. So if you'd have variables like in Java or C++, and the object would be mutable, you would have plenty of side effects. So you'll have to have immutable objects passed as parameters or returned by the functions.

Answer 4

I'd start with C and C++, where things are reasonably simple. You have "objects" in memory, not in the sense of object oriented programming, but items that can be read or changed. These "objects" can be "const", which means an attempt to modify them invokes undefined behaviour. Often the compiler will not allow you to modify a const object, but there are ways around that. Typically behaviours when you try to modify a const object are:

Your application crashes
Your application doesn't store the value
Your application gets into a schizophrenic state whether the object is modified or not
The object is modified

And most common: You don't notice anything wrong in development, but as soon as you deliver your software to a customer, it will fail in the worst possible way.

Apart from objects being constant, pointers to objects may allow modification or not. There are rules for this that are usually sensible, but this being C or C++ you can override them.

int i = 10;
const int* p = &i;
int* q = (int*) p; 

The object i is not constant, but you are not allowed to modify it through the pointer p. You are allowed to modify it through q though. Now take the example

const int i = 10;
const int* p = &i;
int* q = (int*) p; 

i is not modifiable. The compiler won't let you change i through the pointer p. The compiler will let you attempt to change i through the pointer q, but will produce undefined behaviour.

If you have a class or struct that is const, then normally all members are const. There are two exceptions: When you run a C++ constructor, the object members can be modified until the constructor has finished (const instances of class would be quite useless otherwise). There is another exception: If a member is "mutable" then it can be modified and is not const even when it is part of a const object. This is useful for caches, for example. Consider a string class with 0-terminated strings and a function that returns the length. To determine the length, you need to go through all the elements until you find the trailing 0 which is expensive, so you would like to store the length. You can do that by storing the length in a mutable member. So calling the len(function) changes the object, but doesn't logically change it.

In C and C++, classes and structs are not const; it is the individual instances that are const or not. const pointer members mean that the pointer value cannot be changed, but if the pointer points to modifiable data then the data it points to can be changed. This means that you may be able for example to change the title of a const button, which may come very unexpected. So you need to distinguish between "logically unmodifiable" and "physically unmodifiable".

Another unexpected thing: You can have a modifiable object, and both a const and a non-const pointer to it. If I pass a const int * p to a function, the developer may assume that *p cannot change. But if I have an int *q pointing to the same variable then it can change. And a compiler can usually create better code if it knows that an object cannot change - which it often can’t.

Answer 5

The dangers of mutation specifically apply to alias mutation; a lot of times when people claim "immutability", what they really claim (or want) is alias immutability.

---

An alias is a value that is referenced by multiple variables. For example in C:

int x = 4;
int* y = &x;

x and y are aliases of each other. If one of them is mutated, the other changes.

x = 5;
printf("%d", *y); // prints 5
*y = 3
printf("%d", x); // prints 3

The problem with alias mutation is that it's hard (sometimes literally impossible) to know whether a variable's alias was mutated. For example:

int* y;

int main() {
  int x = 4;
  y = &x;
  f();
  printf("%d", x);
  return 0;
}

What will this print? To know the answer, we need to know the body of f, because it could re-assign *y. Moreover, if f is:

void f() {
    g();
    h();
    i();
}

Now we need to know the body of g, h, i...

---

Alias mutation has real-world consequences. Every day, a developer has a variable that they assume isn't going to mutate, but it was aliased somewhere, and some function mutates that alias, so it mutates the variable. The developer can't keep track of every alias of every variable, so they can't know at a glance "is this call to f going to change x" for some fs and xs; they assume, and when these assumptions turn out to be wrong, it's a pain to debug.

But mutation without aliases doesn't have this issue. If the only way x can be mutated is through a statement x =, a developer can be certain that it remains constant throughout some lines, by checking that none of the lines contain x =. In fact, even if the language has a "mutable borrow" that temporarily lets other functions mutate a value, e.g. f(&mut x) lets that particular call to f mutate x, a developer can still be certain that x remains constant throughout every line that doesn't contain an assignment or mutable borrow of x.

---

And this basically the generic pitch for Rust, a language that permits mutability but exclusively forbids alias mutability (except for explicitly-allowed "interior mutability"). But even outside of Rust, understanding the unique danger of alias mutation is useful. For example, if you're careful not to leak variables, i.e. assign them globally or pass them to functions except behind "read-only" wrappers, you can be certain that they aren't mutated within a particular code region even in C++ and Java.

Answer 6

x = 10  
x = 20

This is not shadowing.

This is shadowing:

x = 0

def outer():
    x = 1

    def inner():
        x = 2
        print("inner:", x)

    inner()
    print("outer:", x)

outer()
print("global:", x)

# prints
# inner: 2
# outer: 1
# global: 0

Each x belongs to a different scope. So they lead completely different lives. You just can't use them all at the same time because they get in each others way. Ya know, casting shadows on each other.

x = 10  
x = 20

Same scope, same x. With this code that 10 is gone. You ain't getting it back. The question is, why?

• Rebinding is a change to the referencing identifier.
• Assignment is a change to (the referenced) variable.
• Mutation is a change to an object in memory, possibly referenced by a variable or bound to an identifier.

It depends on how your language implements that code.

• Rebinding -> The 10 is lost. It exists somewhere but we forgot where. But we know where this nifty 20 is.

• Assignment -> The 10 is dead. It now looks like a 20.

• Mutation -> Can happen to values and to references. Which happened here depends on your language.

Answer 7

Immutability is not a very fundamental notion in programming; what it means (if anything) is highly dependent on details of programming language semantics, such as argument passing conventions. Strictly speaking, there is no such thing as a mutable value: whenever one changes something, it is not the values (in the mathematical sense) themselves that change, just the question which values are contained in storage.

What is visible to the programmer is the association of expressions (including mere identifiers) to their values. In purely functional programming languages, that association once it exists can never be modified (the same expression in the same context will always continue to refer to the same value) so mutability is not a thing there. In other languages, there is usually at least the assignment of a new value to a variable that can change this association. The fact that this is possible for variables of a given type does not make the type mutable; what makes a type mutable is when the value of a variable of this type can change by something else than assignment to the variable, presumably by manipulation of the memory accessed by that variable. This applies almost exclusively to large, composite, types like arrays, strings or classes: if an integer variable resides in a register then there is no way to alter its value other than by assignment to the variable.

Often higher level languages will have an implicit pointer/reference level between the location of the variable and the value stored, in particular if the type allows values requiring vastly different amounts of storage (like unrestricted strings). Then typically assignment to the variable will be implemented by making it refer to a different memory region rather than modifying the values stored in the original memory region. Also often passing the value to a different variable (as happens in argument passing) is often implemented by just copying the reference, so original and copy are aliases for the same storage. If the language provides in addition operations that do transform the value in-place, then such operations applied to an alias will also be visible through the original variable, which then has mutable behaviour. However, if no such in-place operations are provided, then it can be ensured that in the absence of direct assignments (and of memory corruption, or cosmic rays), the value will continue to access the same value; in this case the type can be said to be immutable. This property is important in some cases, as in Python dictionaries: the integrity of the dictionary depends on the fact that no unexpected changes can occur to the key-part of its key-value pairs, so it insists that key are of an immutable type.

In C++, the user has control over everything (and the responsibility to not abuse this power), so immutability is not an issue as such. One can declare a type to be a reference or pointer to constant, which means one is protected against altering the corresponding memory contents through this reference/pointer, but if some part of the program already had non-const access to the memory, that part can still modify the memory contents, so there is no guarantee of immutability here. Classes can make it impossible for decent clients (those who refrain from const-casting and out-of-bounds writing and such) to alter storage in a way that violates their integrity, and so to effectively enforce immutability of critical values.

In interesting case of true immutability in C/C++ is function values. There is simply no way to ask for changes in function code ("please nuke the third assignment in the function body for me"). Variables of function type do not exist, but function pointers are effectively just that, if we just think of making a function pointer point to a function as "storing the function, of the proper type, in the variable". Then all assignments are in fact realised as making the variable refer to different code, not of course as moving code into the memory originally holding other code (and programmers know this, which is why the variable is called a pointer). One could apply the same method to other types, implementing all assignments as rebinding of a reference. It is conceivable to have a non functional programming language in which all values are immutable, because all assignments are implemented this way. (There are efficiency issues to be dealt with, which might explain why I cannot think of examples of such languages, but they might well exist.)