6.031
6.031 — Software Construction
Spring 2022

Reading 8: Mutability & Immutability

TypeScript Tutor exercises

Keep making progress on TypeScript by completing this category in the TypeScript Tutor:

Software in 6.031

Safe from bugsEasy to understandReady for change
Correct today and correct in the unknown future. Communicating clearly with future programmers, including future you. Designed to accommodate change without rewriting.

Objectives

  • Understand mutability and mutable objects
  • Identify aliasing and understand the dangers of mutability
  • Use immutability to improve correctness, clarity, & changeability

Creating and using objects

reading exercises

Classes and objects
class Tortoise:
    def __init__(self):
        self.position = 0

    def forward(self):
        self.position += 1

pokey = Tortoise()
pokey.forward()
print(pokey.position)

(missing explanation)

Under construction

In Python we declare an __init__ function to initialize new objects.

(missing explanation)

(missing explanation)

Methodical

To declare the forward method on Tortoise objects in TypeScript:

public forward():void {
    // self.position += 1 (Python)
}

(missing explanation)

On your mark

In Python, we used self.position = 0 to give Tortoise objects a position that starts at zero.

In TypeScript, we can do this either in one line…

class Tortoise {

    private position = 0;      // (1)

    public constructor() {
        let position = 0;          // (2)
        let self.position = 0;     // (3)
        let this.position = 0;     // (4)
    }
    // ...
}

… or in a combination of lines…

class Tortoise {

    private position:number;          // (1)

    public constructor() {
        position = 0;              // (2)
        self.position = 0;         // (3)
        this.position = 0;         // (4)
    }
    // ...
}

(missing explanation)

Get set

Let’s declare another method on Tortoise:

public jump(position:number):void {
    // set this Tortoise's position to the input value
}

(missing explanation)

Mutability

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.

sstring"a"string"ab"

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
sarrArray<string>01string"a"string"b"

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:

sstring"a"string"ab"tstring"abc"sarrArray<string>012string"a"string"b"string"c"tarr
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.

reading exercises

Follow me


(missing explanation)

(missing explanation)

Choose all correct answers.

(missing explanation)

Readonly collections in TypeScript

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
arr: ReadonlyArrayArray012123

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.

Risks of mutation

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

Let’s start with a simple function that sums the numbers in an array:

/**
 * @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;
}

Suppose we also need a function that sums the absolute values. Following good DRY practice (Don’t Repeat Yourself), the implementer writes a method that uses 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);
}

Notice that this method does its job by mutating the array directly. It seemed sensible to the implementer, because it’s more efficient to reuse the existing array. If the array is millions of items long, then you’re saving the time and memory of generating a new million-item array of absolute values. So the implementer has two very good reasons for this design: DRY, and performance.

But the resulting behavior will be very surprising to anybody who uses it! For example:

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

What will this code print? Will it be 10 followed by -10? Or something else?

reading exercises

Risky #1

(missing explanation)

Let’s think about the key points here:

  • Safe from bugs? In this example, it’s easy to blame the implementer of sum­Absolute() for going beyond what its spec allowed. But really, passing mutable objects around is a latent bug. It’s just waiting for some programmer to inadvertently mutate that array, often with very good intentions like reuse or performance, but resulting in a bug that may be very hard to track down.

  • Easy to understand? When reading this code, what would you assume about the calls sum(myData) and sum­Absolute(myData)? Is it clearly visible to the reader that myData gets changed by one of them?

Risky example #2: returning mutable values

We just saw an example where passing a mutable object to a method caused problems. What about returning a mutable object?

Let’s consider Date, one of the built-in JavaScript classes. Date happens to be a mutable type. Suppose we write a method that determines the first day of spring:

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

Here we’re using the well-known Groundhog algorithm for calculating when spring starts (Harold Ramis, Bill Murray, et al. Groundhog Day, 1993).

Clients start using this method, for example to plan their big parties:

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

All the code works and people are happy. Now, independently, two things happen. First, the implementer of startOfSpring() realizes that the groundhog is starting to get annoyed from being constantly asked when spring will start. So the code is rewritten to ask the groundhog at most once, and then cache the groundhog’s answer for future calls:

let groundhogAnswer:Date|undefined = undefined;

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

Second, one of the clients of startOfSpring() decides that the actual first day of spring is too cold for the party, so the party will be exactly a month later instead:

// 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);
    // ...
}

What happens when these two decisions interact? Even worse, think about who will first discover this bug — will it be startOfSpring()? Will it be partyPlanning()? Or will it be some completely innocent third piece of code that also calls startOfSpring()?

reading exercises

Risky #2

We don’t know how Date stores the month, so we’ll represent that with the abstract values ...march... and ...april... in an imagined month field of Date.

(missing explanation)

Key points:

  • Safe from bugs? Again we had a latent bug that reared its ugly head.

  • Ready for change? Obviously the mutation of the date object is a change, but that’s not the kind of change we’re talking about when we say “ready for change.” Instead, the question is whether the code of the program can be easily changed without rewriting a lot of it or introducing bugs. Here we had two apparently independent changes, by different programmers, that interacted to produce a bad bug.

In both of these examples — the Array<number> and the Date — the problems would have been completely avoided if the array and the date had been immutable types. The bugs would have been impossible by design.

This example also illustrates why using mutable objects can actually be bad for performance. The simplest solution to this bug, which avoids changing any of the specifications or method signatures, is for startOfSpring() to always return a copy of the groundhog’s answer:

    return new Date(groundhogAnswer.valueOf());

This pattern is defensive copying, and we’ll see much more of it when we talk about abstract data types. The defensive copy means partyPlanning() can freely stomp all over the returned date without affecting startOfSpring()’s cached date. But defensive copying forces startOfSpring() to do extra work and use extra space for every client — even if 99% of the clients never mutate the date it returns. We may end up with lots of copies of the first day of spring throughout memory. If we used an immutable type instead, then different parts of the program could safely share the same values in memory, so less copying and less memory space is required. Immutability can be more efficient than mutability, because immutable types never need to be defensively copied.

Aliasing is what makes mutable types risky

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.

reading exercises

Aliasing 1

What is the output from this code?

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

(missing explanation)

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.

Specifications for mutating methods

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
requires:
nothing
effects:
puts arr in sorted order, i.e. arr[i]arr[j] for all 0 ≤ i < j < arr.length

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

function toLowerCase(arr: Array<string>):Array<string>
requires:
nothing
effects:
returns a new array t where t[i] = arr[i].toLowerCase()

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.

Iterating over arrays

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

To better understand how an iterator works, here’s a simple implementation of an iterator for Array<string>. Because our simple iterator can only handle collections of strings, we’ll also simplify next() to return string|undefined – i.e., either the next value from the array, or undefined if we’ve reached the end. (Note that Iterator<E> can’t do this in general, because undefined might very well be one of the elements in the collection, if it’s part of the E type.)

/**
 * 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;
        }
    }
}

MyIterator makes use of a few TypeScript language features that we haven’t used in the readings up to this point.

Instance variables, also called fields or properties in JavaScript/TypeScript. What are the instance variables of My­Iterator?

A constructor, which makes a new object instance and initializes its instance variables.

My­Iterator’s functions are instance methods that must be called on an instance of the object, e.g. iter.next().

The this keyword is used to refer to the instance object, in particular to refer to instance variables like this.array and this.index.

private is used for the object’s internal state and internal helper methods, while public indicates methods and constructors that are intended for clients of the class.

readonly is used to indicate which of the object’s instance variables can be reassigned and which can’t. (Note that TypeScript uses readonly only for instance variables, and const only for local and global variables, but both readonly and const mean the same thing: unreassignable.) index is allowed to change (next() updates it as it steps through the array), but array cannot (the iterator has to keep pointing at the same array for its entire life — if you want to iterate through another array, you’re expected to create another iterator object).

iterMyIteratorarrayindex0arrArray<string>012"a""b""c"

Here’s a snapshot diagram showing a typical state for a MyIterator object in action:

Note that we draw the arrow from array with a double line, to indicate that it’s readonly. That means the arrow can’t change once it’s drawn. But the array object it points to is mutable — elements can be changed within it — and declaring array as readonly has no effect on that.

Why do iterators exist? There are many kinds of collection data structures (linked lists, maps, hash tables) with different kinds of internal representations. The iterator concept allows a single uniform way to access them all, so that client code is simpler and the collection implementation can change without changing the client code that iterates over it. Most modern languages (including Python, C#, and Ruby) use the notion of an iterator. It’s an effective design pattern (a well-tested solution to a common design problem). We’ll see many other design patterns as we move through the course.

reading exercises

MyIterator.next signature

This is one of the first times in class so far that we are talking about instance methods. Recall that an instance method operates on an instance of a class, takes an implicit this parameter (like the explicit self parameter in Python), and can access instance variables (also called fields).

Let’s examine one of the instance methods in MyIterator, the next method:

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;
        }
    }
}

Thinking about next as an operation as defined in Static Checking: Types, what are the types of the input(s) to next?

(missing explanation)

What are the types of the possible outputs from next?

(missing explanation)

MyIterator.next postcondition

Part of the postcondition of next is: returns the next element in the array, or undefined if there are no more elements.

(missing explanation)

Another part of the postcondition of next is modifies: this iterator to advance it to the element following the returned element.

(missing explanation)

Mutation undermines an iterator

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.

reading exercises

Draw a snapshot diagram

Let’s draw a snapshot diagram to illustrate the bug. You will need to refer back to the source code for the MyIterator class and the dropCourse6() method above.

We are running the test case dropCourse6(["6.045", "6.031", "6.036"]).

In the box below, use Snapdown to draw a snapshot diagram showing the state of the program right at the start of the body of dropCourse6(). Open the Snapdown help sidebar to get the details of Snapdown syntax – it’s a little language for drawing diagrams with text.

"6.045""6.031""6.036"TODOArray<fixme>01"change me!"

(missing explanation)

Adding an iterator

Now update your snapshot diagram to reflect the effect of the first line, let iter:MyIterator = new MyIterator(subjects);

"6.045""6.031""6.036"TODOArray<fixme>01"change me!"

(missing explanation)

Entering the loop

Now update your snapshot diagram to reflect the effect of the first call to iter.next().

"6.045""6.031""6.036"TODOArray<fixme>01"change me!"

(missing explanation)

Remove an item

Now update your snapshot diagram to reflect the effect of the call subjects.splice(subjects.indexOf(subject), 1). If an index no longer exists in the Array, you should remove it from the diagram.

"6.045""6.031""6.036"TODOArray<fixme>01"change me!"

(missing explanation)

Next iteration of the loop

Now update your snapshot diagram to reflect the effect of the next call to iter.next().

"6.045""6.031""6.036"TODOArray<fixme>01"change me!"

(missing explanation)

Analysis

(missing explanation)

(missing explanation)

(missing explanation)

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.

Mutation and contracts

Mutable objects can make simple contracts very complex

This is a fundamental issue with mutable data structures. Multiple references to the same mutable object (aliasing) may mean that multiple places in your program — possibly widely separated — are relying on that object to remain consistent.

To put it in terms of specifications, contracts can’t be enforced in just one place anymore, e.g. between the client of a class and the implementer of a class. Contracts involving mutable objects now depend on the good behavior of everyone who has a reference to the mutable object.

As a symptom of this non-local contract phenomenon, consider iterators. Try to find where it documents the crucial requirement on the client that we’ve just discovered — that you shouldn’t mutate an array while you’re iterating over it. Who takes responsibility for it? The iterator specification? Array? Can you find it?

The need to reason about global properties like this make it much harder to understand, and be confident in the correctness of, programs with mutable data structures. We still have to do it — for performance and convenience — but we pay a big cost in bug safety for doing so.

Mutable objects reduce changeability

Mutable objects make the contracts between clients and implementers more complicated, and reduce the freedom of the client and implementer to change. In other words, using objects that are allowed to change makes the code harder to change. Here’s an example to illustrate the point.

The crux of our example will be the specification for this function, which looks up a username in MIT’s database and returns the user’s 9-digit identifier:

/**
 * @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
}

A reasonable specification. Now suppose we have a client using this method to print out a user’s identifier:

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

Now both the client and the implementer separately decide to make a change. The client is worried about the user’s privacy, and decides to hide the first 5 digits of the id by deleting them:

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

The implementer is worried about the speed and load on the database, so the implementer introduces a cache that remembers usernames that have been looked up:

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;
}

These two changes have created a subtle bug. When the client looks up "bitdiddle" and gets back a digit array, now both the client and the implementer’s cache are pointing to the same digit array. The array is aliased. That means that the client’s obscuring code is actually overwriting the identifier in the cache, so future calls to getMitId("bitdiddle") will not return the full 9-digit number, like [9,2,8,4,3,2,0,3,3], but instead the obscured version [,,,,,2,0,3,3].

Sharing a mutable object complicates a contract. If this contract failure went to software engineering court, it would be contentious. Who’s to blame here? Was the client obliged not to modify the object it got back? Was the implementer obliged not to hold on to the object that it returned?

Here’s one way we could have clarified the spec:

function getMitId(username:string):Array<number> 
requires:
nothing
effects:
returns an array containing the 9-digit MIT identifier of username, or throws NoSuchUser­Error if nobody with username is in MIT’s database. Caller may never modify the returned array.

This is a bad way to do it. The problem with this approach is that it means the contract has to be in force for the entire rest of the program. It’s a lifetime contract! The other contracts we wrote were much narrower in scope; you could think about the precondition just before the call was made, and the postcondition just after, and you didn’t have to reason about what would happen for the rest of time.

Here’s a spec with a similar problem:

function getMitId(username:string):Array<number> 
requires:
nothing
effects:
returns a new array containing the 9-digit MIT identifier of username, or throws NoSuchUserError if nobody with username is in MIT’s database.

This doesn’t entirely fix the problem either. This spec at least says that the array has to be fresh. But does it keep the implementer from holding an alias to that new array? Does it keep the implementer from changing that array or reusing it in the future for something else?

Here’s a much better spec:

function getMitId(username:string):string
requires:
nothing
effects:
returns a length-9 string containing the 9-digit MIT identifier of username, or throws NoSuchUser­Error if nobody with username is in MIT’s database.

The immutable string return value provides a guarantee that the client and the implementer will never step on each other the way they could with string arrays. It doesn’t depend on a programmer reading the spec comment carefully. String is immutable. Not only that, but this approach (unlike the previous one) gives the implementer the freedom to introduce a cache — a performance improvement.

reading exercises

Given:

class Zoo {
    private animals:Array<string>;

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

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

What is the output from this code?

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

(missing explanation)

Aliasing 3

Continuing in the same program, what is the output?

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

(missing explanation)

Immutability and performance

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.

Aliases to mutable objects

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?

reading exercises

Risky aliasing

Given the declarations of yourArray and myArray above, which of the following expressions would end up changing myArray?

(missing explanation)

Immutability

(missing explanation)

Summary

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.