Reading 8: Mutability & Immutability

Recall from Basic Java 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. StringBuilder is an example of a mutable type. It has methods to delete parts of the string, insert or replace characters, etc.

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:

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

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

StringBuilder sb = new StringBuilder("a");
sb.append("b");

StringBuilder has other methods as well, for deleting parts of the string, inserting in the middle, or changing individual characters.

So what? In both cases, you end up with s and sb referring to the string 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 tb points to the same StringBuilder as sb, then the differences between the immutable and mutable objects become more evident:

String t = s;
t = t + "c";

StringBuilder tb = sb;
tb.append("c");

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

Since we have the immutable String class already, why do we even need the mutable StringBuilder in programming? A common use for it is to concatenate a large number of strings together. Consider this code:

String s = "";
for (int i = 0; i < n; ++i) {
    s = s + i;
}

Using immutable strings, this makes a lot of temporary copies — the first number of the string ("0") is actually copied n times in the course of building up the final string, the second number is copied n-1 times, and so on. It costs O(n²) time to do all that copying, even though we only concatenated n elements.

StringBuilder is designed to minimize this copying. It uses a simple but clever internal data structure to avoid doing any copying at all until the very end, when you ask for the final String with a toString() call:

StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; ++i) {
  sb.append(String.valueOf(i));
}
String s = sb.toString();

So StringBuilder enables fast string concatenation, and an “Implementation Note” in the String API docs says that Java may actually implement the + operator using a StringBuilder behind the scenes.

Optimizing performance is one reason why we might use mutable objects. Another reason is convenient sharing: two parts of your program can communicate by deliberately sharing a common mutable data structure.

Mutable types seem much more powerful than immutable types. If you were shopping in the Datatype Supermarket, and you had to choose between a boring immutable String and a super-powerful-do-anything mutable StringBuilder, why on earth would you choose the immutable one? StringBuilder should be able to do everything that String can do, plus set() and append() 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

/**
 * @return the sum of the numbers in the list
 */
public static int sum(List<Integer> list) {
    int sum = 0;
    for (int x : list) {
        sum += x;
    }
    return sum;
}

/**
 * @return the sum of the absolute values of the numbers in the list
 */
public static int sumAbsolute(List<Integer> list) {
    // let's reuse sum(), because DRY, so first we take absolute values
    for (int i = 0; i < list.size(); ++i) {
        list.set(i, Math.abs(list.get(i)));
    }
    return sum(list);
}

// meanwhile, somewhere else in the code...
public static void main(String[] args) {
    // ...
    List<Integer> myData = Arrays.asList(-5, -3, -2);
    System.out.println(sumAbsolute(myData));
    System.out.println(sum(myData));
}

Risky example #2: returning mutable values

/**
 * @return the first day of spring this year
 */
public static Date startOfSpring() {
    return askGroundhog();
}

// somewhere else in the code...
public static void partyPlanning() {
    Date partyDate = startOfSpring();
    // ...
}

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

// somewhere else in the code...
public static void partyPlanning() {
    // let's have a party one month after spring starts!
    Date partyDate = startOfSpring();
    partyDate.setMonth(partyDate.getMonth() + 1);
    // ... uh-oh. what just happened?
}

    return new Date(groundhogAnswer.getTime());

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.

List<String> a = new ArrayList<>();
a.add("cat");
List<String> b = a;
b.add("dog");
System.out.println(a);
System.out.println(b);

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

• In the List example, the same list is pointed to by both list (in sum and sumAbsolute) and myData (in main). One programmer (sumAbsolute’s) thinks it’s ok to modify the list; another programmer (main’s) wants the list to stay the same. Because of the aliases, main’s 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 method performs mutation, it is crucial to include that mutation in the method’s spec, using the structure we discussed in Specifications.

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

Here’s an example of a mutating method:

static void sort(List<String> list)

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

static List<String> toLowerCase(List<String> list)

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 Java when you’re using a for (... : ...) loop to step through a List or array. This code:

List<String> list = ...;
for (String str : list) {
    System.out.println(str);
}

is rewritten by the compiler into something like this:

List<String> list = ...;
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {
    String str = iter.next();
    System.out.println(str);
}

An iterator has two methods:

• next() returns the next element in the collection
• hasNext() tests whether the iterator has reached the end of the collection.

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 Java API definition of Iterator.

MyIterator

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

    private final List<String> list;
    private int index;
    // list[index] is the next element that will be returned
    //   by next()
    // index == list.size() means no more elements to return

    /**
     * Make an iterator.
     * @param list list to iterate over
     */
    public MyIterator(List<String> list) {
        this.list = list;
        this.index = 0;
    }

    /**
     * Test whether the iterator has more elements to return.
     * @return true if next() will return another element,
     *         false if all elements have been returned
     */
    public boolean hasNext() {
        return index < list.size();
    }

    /**
     * Get the next element of the list.
     * Requires: hasNext() returns true.
     * Modifies: this iterator to advance it to the element 
     *           following the returned element.
     * @return next element of the list
     */
    public String next() {
        final String element = list.get(index);
        ++index;
        return element;
    }
}

public class MyIterator {

    private final ArrayList<String> list;
    private int index;

    ...

    /**
     * Get the next element of the list.
     * Requires: hasNext() returns true.
     * Modifies: this iterator to advance it to the element 
     *           following the returned element.
     * @return next element of the list
     */
    public String next() {
        final String element = list.get(index);
        ++index;
        return element;
    }
}

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

/**
 * Drop all subjects that are from Course 6. 
 * Modifies subjects list by removing subjects that start with "6."
 * 
 * @param subjects list of MIT subject numbers
 */
public static void dropCourse6(ArrayList<String> subjects)

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.size: 0, 1, n > 1
//   partition on contents: no 6.xx, some 6.xx, all 6.xx
//   partition on position: 6.xx at start, 6.xx in middle, 6.xx at end

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

public static void dropCourse6(ArrayList<String> subjects) {
    MyIterator iter = new MyIterator(subjects);
    while (iter.hasNext()) {
        String subject = iter.next();
        if (subject.startsWith("6.")) {
            subjects.remove(subject);
        }
    }
}

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 list! Why? Trace through what happens. It will help to use a snapshot diagram showing the MyIterator object and the ArrayList 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 ArrayList suffers from the same problem, and so does the for loop that’s syntactic sugar for it. The problem just has a different symptom. If you used this code instead:

for (String subject : subjects) {
    if (subject.startsWith("6.")) {
        subjects.remove(subject);
    }
}

then you’ll get a Concurrent­Modification­Exception. The built-in iterator detects that you’re changing the list under its feet, and cries foul. (How do you think it does that?)

How can you fix this problem? One way is to use the remove() method of Iterator, so that the iterator adjusts its index appropriately:

Iterator iter = subjects.iterator();
while (iter.hasNext()) {
    String subject = iter.next();
    if (subject.startsWith("6.")) {
        iter.remove();
    }
}

This is actually more efficient as well, it turns out, because iter.remove() already knows where the element it should remove is, while subjects.remove() had to search for it again.

But this doesn’t fix the whole problem. What if there are other Iterators currently active over the same list? They won’t all be informed! And what if the mutation of the list is something more complicated than just removing an element or appending an element – say, sorting the list into a different order? How should an active Iterator’s position be adjusted in that case? 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
 * @return the 9-digit MIT identifier for username.
 * @throws NoSuchUserException if nobody with username is in MIT's database
 */
public static char[] getMitId(String username) throws NoSuchUserException {        
    // ... look up username in MIT's database and return the 9-digit ID
}

char[] id = getMitId("bitdiddle");
System.out.println(id);

char[] id = getMitId("bitdiddle");
for (int i = 0; i < 5; ++i) {
    id[i] = '*';
}
System.out.println(id);

private static Map<String, char[]> cache = new HashMap<String, char[]>();

public static char[] getMitId(String username) throws NoSuchUserException {        
    // see if it's in the cache already
    if (cache.containsKey(username)) {
        return cache.get(username);
    }

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

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

public static char[] getMitId(String username) throws NoSuchUserException 

public static char[] getMitId(String username) throws NoSuchUserException 

public static String getMitId(String username) throws NoSuchUserException

public class Zoo {
    private List<String> animals;

    public Zoo(List<String> animals) {
        this.animals = animals;
    }

    public List<String> getAnimals() {
        return this.animals;
    }
}

List<String> a = new ArrayList<>();
a.addAll(List.of("lion", "tiger", "bear"));
Zoo zoo = new Zoo(a);
a.add("zebra");
System.out.println(a);
System.out.println(zoo.getAnimals());

List<String> b = zoo.getAnimals();
b.add("flamingo");
System.out.println(a);

As we saw with StringBuilder above, 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.

Since immutable types avoid so many pitfalls, let’s enumerate some commonly-used immutable types in the Java API:

• The primitive types and primitive wrappers are all immutable. If you need to compute with large numbers, BigInteger and BigDecimal are immutable.

• Don’t use mutable Dates, use the appropriate immutable type from java.time based on the granularity of timekeeping you need.

• To create immutable collections from some known values, use List.of, Set.of, and Map.of.

• The usual implementations of List, Set, and Map are all mutable: ArrayList, HashMap, etc. The Collections utility class has methods for obtaining unmodifiable views of these mutable collections:

  • Collections.unmodifiableList
  • Collections.unmodifiableSet
  • Collections.unmodifiableMap

  The snapshot diagram at the right shows the result of list2 = Collections.unmodifiableList(list1).

  You can think of the unmodifiable view as a wrapper around the underlying list/set/map. The wrapper behaves just like the underlying collection for non-mutating operations like get, size, and iteration. So list2.size() is 3, and list2.get(0) is "a". But any attempt to mutate the wrapper — add, remove, put, etc. — triggers an Unsupported­Operation­Exception.

  Before we pass a mutable collection to another part of our program, we can wrap it in an unmodifiable wrapper. We should be careful at that point to forget our reference to the mutable collection (list1 in the example shown here), lest we accidentally mutate it. Just as a mutable object behind a final reference can be mutated, the mutable collection inside an unmodifiable wrapper can still be modified by someone with a reference to it, defeating the wrapper. One way to forget the reference is to let the local variable holding it (list1) go out of scope.

• Alternatively, use List.copyOf, etc., to create unmodifiable shallow copies of mutable collections.

• Collections also provides methods for obtaining immutable empty collections: Collections.emptyList, etc. Nothing’s worse than discovering your definitely very empty list is suddenly definitely not empty!

List<String> arraylist = new ArrayList<>();
arraylist.add("hello");
List<String> unmodlist = Collections.unmodifiableList(arraylist);
// unmodlist should now always be [ "hello" ]

unmodlist.add("goodbye");
System.out.println(unmodlist);

arraylist.add("goodbye");
System.out.println(unmodlist);

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