Reading 8: Mutability & Immutability

Recall from Basic TypeScript when we discussed snapshot diagrams that some objects are immutable: once created, they always represent the same value. Other objects are mutable: they have methods that change the value of the object.

String is an example of an immutable type. A string object always represents the same string. Array is an example of a mutable type.

Since string is immutable, once created, a string object always has the same value. To add something to the end of a string, you have to create a new string object:

let s = "a";
s = s.concat("b"); // s+="b" and s=s+"b" also mean the same thing

By contrast, Array objects are mutable. This class has methods that change the value of the object, rather than just returning new values:

let sarr:Array<string> = [ "a" ];
sarr.push("b");

So what? In both cases, you end up with s and sarr basically referring to the sequence of characters ab. The difference between mutability and immutability doesn’t matter much when there’s only one reference to the object. But there are big differences in how they behave when there are other references to the object. For example, when another variable t points to the same string object as s, and another variable tarr points to the same Array as sarr, then the differences between the immutable and mutable objects become more evident:

let t = s;
t = t + "c";

let tarr = sarr;
tarr.push("c");

The snapshot diagram shows that changing t had no effect on s, but changing tarr affected sarr too — possibly to the surprise of the programmer. That’s the essence of the problem we’re going to look at in this reading.

The collection types Array, Set, and Map have corresponding interfaces ReadonlyArray, ReadonlySet, and ReadonlyMap that omit the mutating operations. Declaring a variable with one of these types tells the TypeScript compiler that you don’t intend to mutate the collection, and you will get a static error if you call a mutating operation:

const arr:ReadonlyArray<number> = [1,2,3];
arr.push(4); // static error -- ReadonlyArray doesn't have the push() operation

const set:ReadonlySet<number> = new Set([1,2,3]);
set.add(4); // static error -- ReadonlySet doesn't have the add() operation

const map:ReadonlyMap<string, number> = new Map(Object.entries({ "apple": 5, "banana": 7 }));
map.set("pear", 9); // static error -- ReadonlyMap doesn't have the set() operation

This is an example of where the static type of a variable differs from the dynamic type of the object that it actually points to at runtime. The snapshot diagram at right shows what this means: the variable arr has static type ReadonlyArray, but it points to an object whose type is Array. When we discuss subtyping in a future reading, we will see the specific relationship that must hold between the static type and the dynamic type, but for now it’s enough to say that arr must point to an object whose dynamic type has all the operations that its static type does. Since ReadonlyArray is a subset of the methods on Array, any operation that could be called on the ReadonlyArray will be available on the actual runtime Array as well.

Unfortunately, this design also has a risk: a ReadonlyArray is not guaranteed to be immutable. The readonly collections are just interfaces, so they have methods but no constructors. So you can’t make a ReadonlyArray directly. Instead, you make an Array and then assign it to a ReadonlyArray. If another part of the program has an alias to the underlying Array, then the array can change under your feet. We’ll see more examples of the problems that arise from unexpected mutations in the rest of this reading.

The truly-immutable types in TypeScript — number, boolean, string, bigint — do not have this risk. There is no way to mutate a value of these types.

Mutable types seem much more powerful than immutable types. If you were shopping in the Data Type Supermarket, and you had to choose between an immutable ReadonlyArray and a super-powerful-do-anything mutable Array, why on earth would you choose the immutable one? Array should be able to do everything that ReadonlyArray can do, plus push() and pop() and everything else.

The answer is that immutable types are safer from bugs, easier to understand, and more ready for change. Mutability makes it harder to understand what your program is doing, and much harder to enforce contracts. Here are two examples that illustrate why.

Risky example #1: passing mutable values

/**
 * @returns the sum of the numbers in the array
 */
function sum(arr:Array<number>):number {
    let sum = 0;
    for (const x of arr) {
        sum += x;
    }
    return sum;
}

/**
 * @returns the sum of the absolute values of the numbers in the array
 */
function sumAbsolute(arr:Array<number>):number {
    // let's reuse sum(), because DRY, so first we take absolute values
    for (let i = 0; i < arr.length; ++i) {
        arr[i] = Math.abs(arr[i]);
    }
    return sum(arr);
}

// meanwhile, somewhere else in the code...
let myData:Array<number> = [-5, -3, -2];
console.log(sumAbsolute(myData));
console.log(sum(myData));

Risky example #2: returning mutable values

/**
 * @returns the first day of spring this year
 */
function startOfSpring():Date {
    return askGroundhog();
}

// somewhere else in the code...
function partyPlanning():void {
    let partyDate:Date = startOfSpring();
    // ...
}

let groundhogAnswer:Date|undefined = undefined;

/**
 * @returns the first day of spring this year
 */
function startOfSpring():Date {
    if (groundhogAnswer === undefined) {
        groundhogAnswer = askGroundhog();
    }
    return groundhogAnswer;
}

// somewhere else in the code...
function partyPlanning():void {
    // let's have a party one month after spring starts!
    let partyDate:Date = startOfSpring();
    partyDate.setMonth(partyDate.getMonth() + 1);
    // ...
}

    return new Date(groundhogAnswer.valueOf());

Actually, using mutable objects is just fine if you are using them entirely locally within a method, and with only one reference to the object. What led to the problem in the two examples we just looked at was having multiple references, also called aliases, for the same mutable object.

let a:Array<string> = [];
a.push("cat");
let b:Array<string> = a;
b.push("dog");
console.log(a);
console.log(b);

Walking through the risky examples above with a snapshot diagram will make the problem of aliasing clear – here’s the outline:

• In the Array example, the same array is pointed to by both arr (in sum and sumAbsolute) and myData. One programmer (sumAbsolute’s) thinks it’s ok to modify the array; the other programmer wants the array to stay the same. Because of the aliases, the other programmer loses.

• In the Date example, there are two variable names that point to the Date object, groundhogAnswer and partyDate. These aliases are in completely different parts of the code, under the control of different programmers who may have no idea what the other is doing.

Draw snapshot diagrams on paper first, but your real goal should be to develop the snapshot diagram in your head, so you can visualize what’s happening in the code.

At this point it should be clear that when a function performs mutation, it is crucial to include that mutation in the function’s spec, using the structure we discussed in Specifications.

(Now we’ve seen that even when a particular function doesn’t mutate an object, that object’s mutability can still be a source of bugs.)

Here’s an example of a mutating function:

function sort(arr: Array<string>):void

And an example of a function that does not mutate its argument:

function toLowerCase(arr: Array<string>):Array<string>

If the effects do not explicitly say that an input can be mutated, then mutation of the input is implicitly disallowed. Surprise mutations lead to terrible bugs.

The next mutable object we’re going to look at is an iterator — an object that steps through a collection of elements and returns the elements one by one. Iterators are used under the covers in TypeScript when you’re using a for (... of ...) loop to step through an array. This code:

let arr:Array<string> = ...;
for (const str of arr) {
    console.log(str);
}

is implemented by TypeScript by code roughly equivalent (this translation ignores some details) to this:

let arr:Array<string> = ...;
let iter:Iterator<string> = arr.iterator();
for (let result = iter.next(); ! result.done; result = iter.next()) {
    const str:string = result.value;
    console.log(str);
}

An Iterator<E> over a collection of elements of type E has one method:

• next() returns an object {done:boolean, value?:string}
  • where value is the next element in the collection if done is false
  • and there are no more elements if done is true

Note that the next() method is a mutator method, not only returning an element but also advancing the iterator so that the subsequent call to next() will return a different element.

You can also look at the JavaScript API definition of an iterator.

MyIterator

/**
 * A MyIterator is a mutable object that iterates over
 * the elements of a Array<string>, from first to last.
 * This is just an example to show how an iterator works.
 * In practice, you should use the Array's own iterator
 * object, returned by its iterator() method.
 */
class MyIterator {

    private readonly array:Array<string>;
    private index:number;
    // array[index] is the next element that will be returned
    //   by next()
    // index === array.length means no more elements to return

    /**
     * Make an iterator.
     * @param array array to iterate over
     */
    public constructor(array:Array<string>) {
        this.array = array;
        this.index = 0;
    }

    /**
     * Get the next element of the array.
     * Modifies: this iterator to advance it to the element 
     *           following the returned element.
     * @returns the next element in the array, 
     *          or undefined if there are no more elements
     */
    public next():string|undefined {
        if (this.index >= this.array.length) {
            return undefined;
        } else {
            const value = this.array[this.index];
            ++this.index;
            return value;
        }
    }
}

class MyIterator {

    private readonly array:Array<string>;
    private index:number;

    ...

    /**
     * Get the next element of the array.
     * Modifies: this iterator to advance it to the element 
     *           following the returned element.
     * @returns the next element in the array, 
     *          or undefined if there are no more elements
     */
    public next():string|undefined {
        if (this.index >= this.array.length) {
            return undefined;
        } else {
            const value = this.array[this.index];
            ++this.index;
            return value;
        }
    }
}

Let’s try using our iterator for a simple job. Suppose we have an array of MIT subjects represented as strings, like ["6.031", "8.03", "9.00"]. We want a function dropCourse6 that will delete the Course 6 subjects from the array, leaving the other subjects behind. Following good practices, we first write the spec:

/**
 * Drop all subjects that are from Course 6. 
 * Modifies subjects array by removing subjects that start with "6."
 * 
 * @param subjects array of MIT subject numbers
 */
 function dropCourse6(subjects:Array<string>):void

Note that dropCourse6 explicitly says in its spec that its subjects argument may be mutated.

Next, following test-first programming, we devise a testing strategy that partitions the input space, and choose test cases to cover that partition:

// Testing strategy:
//   partition on subjects.length: 0, 1, n > 1
//   partition on contents: no 6.xx, some (but not all) 6.xx, all 6.xx
//   partitions on position: subjects has a first element that is 6.xx? yes, no
//                                    ... a middle element 6.xx? yes, no
//                                    ... a last element 6.xx? yes, no

// Test cases:
//   [] => []
//   ["8.03"] => ["8.03"]
//   ["14.03", "9.00", "21L.005"] => ["14.03", "9.00", "21L.005"]
//   ["2.001", "6.01", "18.03"] => ["2.001", "18.03"]
//   ["6.045", "6.031", "6.036"] => []

Finally, we implement it:

function dropCourse6(subjects:Array<string>):void {
    let iter:MyIterator = new MyIterator(subjects);
    for (let subject = iter.next(); subject !== undefined; subject = iter.next()) {
        if (subject.startsWith("6.")) {
            // remove the subject from the array
            subjects.splice(subjects.indexOf(subject), 1);
        }
    }
}

Now we run our test cases, and they work! … almost. The last test case fails:

// dropCourse6(["6.045", "6.031", "6.036"])
//   expected [], actual ["6.031"]

We got the wrong answer: dropCourse6 left a course behind in the array! Why? Trace through what happens. It will help to use a snapshot diagram showing the MyIterator object and the Array object and update it while you work through the code.

Note that this isn’t just a bug in our MyIterator. The built-in iterator in Array suffers from the same problem, and so does the for loop that’s syntactic sugar for it. So do lists and for loops in Python. Mutating a list that is currently being iterated over is simply not safe in general.

Mutable objects can make simple contracts very complex

Mutable objects reduce changeability

/**
 * @param username username of person to look up
 * @returns an array containing the 9-digit MIT identifier for username, one digit per element.
 * @throws NoSuchUserError if nobody with username is in MIT's database
 */
function getMitId(username:string):Array<number> {         
    // ... look up username in MIT's database and return the 9-digit ID
}

let id = getMitId("bitdiddle");
console.log(id);

let id = getMitId("bitdiddle");
for (let i = 0; i < 5; ++i) {
    delete id[i];
}
console.log(id);

const cache:Map<string, Array<number>> = new Map();

function getMitId(username:string):Array<number> {        
    // see if it's in the cache already
    if (cache.has(username)) {
        return cache.get(username);
    }

    // ... look up username in MIT's database ...

    // store it in the cache for future lookups
    cache.set(username, id);
    return id;
}

function getMitId(username:string):Array<number> 

function getMitId(username:string):Array<number> 

function getMitId(username:string):string

class Zoo {
    private animals:Array<string>;

    public constructor(animals:Array<string>) {
        this.animals = animals;
    }

    public getAnimals():Array<string> {
        return this.animals;
    }
}

let a = [];
a.push("lion", "tiger", "bear");
let zoo = new Zoo(a);
a.push("zebra");
console.log(a);
console.log(zoo.getAnimals());

let b = zoo.getAnimals();
b.push("flamingo");
console.log(a);

One common reason for choosing a mutable type is performance optimization. But it’s not correct to conclude that a mutable type is always more efficient than an immutable type.

The key question to think about is how much sharing is possible, and how much copying is required. An immutable value may be safely shared by many different parts of a program, where a mutable value in the same context would have to be defensively copied over and over, at a cost of both time and space. On the other hand, if a value needs to be edited, in the sense of having many small mutations made to it, then a mutable value may be more efficient, because it doesn’t require the whole value to be copied on every edit.

But even when an immutable value needs to be heavily edited, it may still be possible to design it in a way that exploits sharing in order to reduce copying. For example, if you have an immutable string that is a million characters long, editing a single character in the middle of the string seems to require copying all the unchanged characters too. But a clever string implementation might internally share the unchanged regions of characters before and after the edit, so that even though you get a new string object as a result of the edit, it actually occupies very little additional memory space. We will see an example of this kind of implementation in a few classes, when we talk about abstract data types. This kind of internal sharing is only possible because of immutability.

The git object graph is another example of the benefit of sharing. Because commits are immutable, other commits can point to them without fear that they will become broken because the parent commit is modified (e.g. reverted or undone). Without immutability, this kind of structural sharing is impossible.

We’ll close the reading with a warning about a pitfall, which shows up not just in TypeScript but in other langugages too. We may think we’ve made something immutable, for instance by declaring it const, and using ReadonlyArray instead of Array. But it may still be mutable if we’re not careful about aliases!

For example:

let yourArray: Array<number> = [ 1, 2, 3 ];
const myArray: ReadonlyArray<number> = yourArray;

I’m trying to keep myArray unchanged, so I declare it const and ReadonlyArray. What can you do with yourArray that undermines that?

In this reading, we saw that mutability is useful for performance and convenience, but it also creates risks of bugs by requiring the code that uses the objects to be well-behaved on a global level, greatly complicating the reasoning and testing we have to do to be confident in its correctness.

Make sure you understand the difference between an immutable object (like a string) and an unreassignable reference (like a readonly variable). Snapshot diagrams can help with this understanding, if you draw immutable objects with double borders and unreassignable references with doubled arrows.

The key design principle here is immutability: using immutable objects and unreassignable variables as much as possible. Let’s review how immutability helps with the main goals of this course:

• Safe from bugs. Immutable objects aren’t susceptible to bugs caused by aliasing. Unreassignable variables always point to the same object.

• Easy to understand. Because an immutable object or unreassignable variable always means the same thing, it’s simpler for a reader of the code to reason about — they don’t have to trace through all the code to find all the places where the object or variable might be changed, because it can’t be changed.

• Ready for change. If an object or a variable can’t be changed at runtime, then code that depends on that object or variable won’t have to be revised when the program changes.