Reading 8: Mutability & Immutability

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(list:Array<number>):number {
    let sum = 0;
    for (const x of list) {
        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(list:Array<number>):number {
    // let's reuse sum(), because DRY, so first we take absolute values
    for (let i = 0; i < list.length; ++i) {
        list[i] = Math.abs(list[i]);
    }
    return sum(list);
}

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?

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?

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
 */
public static startOfSpring():Date {
    return this.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...
public static partyPlanning():void {
    let partyDate:Date = this.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:

/**
 * @returns the first day of spring this year
 */
public static startOfSpring():Date {
    if (this.groundhogAnswer === null) {
        this.groundhogAnswer = this.askGroundhog();
    }
    return this.groundhogAnswer;
}
private static groundhogAnswer:Date = null;

(Aside: note the use of a private static variable for the cached answer. Would you consider this a global variable, or not?)

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...
public static partyPlanning():void {
    // let's have a party one month after spring starts!
    let partyDate:Date = this.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()?

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(this.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.

To better understand how an iterator works, here’s a simple implementation of an iterator for Array<string>:

/**
 * 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 list:Array<string>;
    private index:number;
    // list[index] is the next element that will be returned
    //   by next()
    // index === list.length means no more elements to return

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

    /**
     * Get the next element of the array.
     * Modifies: this iterator to advance it to the element 
     *           following the returned element.
     * @returns 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
     */
    public next():{done:boolean, value?:string} {
        if (this.index >= this.list.length) {
            return { done: true };
        } else {
            const value = this.list[this.index];
            ++this.index;
            return { done: false, value: 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 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. Where is the constructor of My­Iterator?

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.list 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 list 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).

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

Note that we draw the arrow from list 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 list 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.

class MyIterator {

    private readonly list: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 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
     */
    public next():{done:boolean, value?:string} {
        if (this.index >= this.list.length) {
            return { done: true };
        } else {
            const value = this.list[this.index];
            ++this.index;
            return { done: false, value: value };
        }
    }
}

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

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> 

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

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.

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