Unit 25: Immutability

So far in this class, we have been focusing on three ways of dealing with software complexity: by encapsulating and hiding the complexity behind abstraction barriers, by using a language with a strong type system and adhering to the subtyping substitution principle, and applying the abstraction principles and reusing code written as functions, classes, and generics types.

Another useful strategy to reduce bugs when code complexity increases is to avoid change altogether. This can be done by making our classes immutable. we create an instance of an immutable class, the instance cannot have any visible changes outside its abstraction barrier. This means that every call of the instance's method must behave the same way throughout the lifetime of the instance.

There are many advantages of why we want to make our class immutable when possible. To start, let's revisit a common bug due to aliasing. Recall the following example from Unit 9, where we create two circles c1 and c2 centered at the origin (0, 0).

Point p = new Point(0, 0);
Circle c1 = new Circle(p, 1);
Circle c2 = new Circle(p, 4);

Let's say that we have the moveTo method in both Circle and Point, to move the circle and point respectively.

class Point {
    private double x;
    private double y;
      :
    public void moveTo(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

class Circle {
    private Point c;
    private double r;

    public Circle (Point c, double r) {
        this.c = c;
        this.r = r;
    }
      :

    public void moveTo(double x, double y) {
        c.moveTo(x, y);
    }
}

Suppose we want to move c1 and only c1 to be centered at (1,1).

c1.moveTo(1, 1);

The line of code above surprisingly moved the center of both c1 and c2, due to both circles c1 and c2 sharing the same point. We have explored a solution below:

Point p1 = new Point(0, 0);
Circle c1 = new Circle(p1, 1);

Point p2 = new Point(0, 0);
Circle c2 = new Circle(p2, 4);

c1.moveTo(1, 1);

This approach avoids sharing references by creating copies of our points so that no two references point to the same instance, avoiding aliasing altogether. This fix, however, comes with extra costs in computational resources as the number of objects may proliferate.

Let's now see how immutability can help us resolve our problem.

Immutable Points and Circles

Let's start by making our Point class immutable. We start by making the fields final to signal our intention that we do not intend to change them. Now that the x and y cannot be changed, to move a point, we shouldn't mutate the fields x and y anymore. Instead, we return a new Point instance, as follows:

final class Point {
    final private double x;
    final private double y;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    public Point moveTo(double x, double y) {
        return new Point(x, y);
    }
      :

    @Override
    public String toString() {
        return "(" + this.x + "," + this.y + ")";
    }
}

Note that, to avoid (likely malicious or ignorant) subclasses of Point overriding the methods to make it appears that the point has mutated, it is recommended that we declare immutable classes as final to disallow inheritance.

Now, let's make Circle immutable:

final class Circle {
    final private Point c;
    final private double r;

    public Circle (Point c, double r) {
        this.c = c;
        this.r = r;
    }

     :

    public Circle moveTo(double x, double y) {
        return new Circle(c.moveTo(x, y), r);
    }
}

With both Point and Circle immutable, we can be sure that once an instance is created, it remains unchanged (outside the abstraction barrier):

Point p = new Point(0, 0);
Circle c1 = new Circle(p, 1);
Circle c2 = new Circle(p, 4);
c1.moveTo(1, 1); // c1 remains unchanged

To update the variable c1, we need to explicitly reassign it.

c1 = c1.moveTo(1, 1);

Now, c1 moves to a new location, but c2 remains unchanged.

Compare our new immutable approach to the two approaches above. The first shares all the references and is bug-prone. The second creates a new copy of the instance every time and is resource-intensive. Our third approach, using immutable classes, allows us to share all the references until we need to modify the instance, in which case we make a copy. Such a copy-on-write semantic allows us to avoid aliasing bugs without creating excessive copies of objects.

Advantages of Being Immutable

We have seen how making our classes immutable helps us remove the risk of potential bugs when we use composition and aliasing. Immutability has other advantages as well.

Ease of Understanding

Code written with immutable objects is easier to reason with and easier to understand. Suppose we create a Circle and assign it to a local variable:

Circle c = new Circle(new Point(0, 0), 8);

We pass c around to many other methods. These other methods may invoke c's methods; we may invoke c's methods locally as well. But, despite putting c through so much, unless we have explicitly reassigned c, we can guarantee that c is still a circle centered at (0,0) with a radius of 8. This immutable property makes it significantly easier to read, understand, and debug our code.

Without this property, we have to trace through all the methods that we pass c to, and each call of c's methods to make sure that none of these codes modifies c.

Enabling Safe Sharing of Objects

Making a class immutable allows us to safely share instances of the class and therefore reducing the need to create multiple copies of the same object. For instance, the origin (0, 0) is commonly used. If the instance is immutable, we can just create and cache a single copy of the origin, and always return this copy when the origin is required.

Let modify our Point class so that it creates a single copy of the origin and returns the same copy every time the origin is required.

final class Point {
    private Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    private final static Point ORIGIN = new Point(0, 0);

    public static Point of(double x, double y) {
        if (x == 0 && y == 0) {
            return ORIGIN;
        }
        return new Point(x, y);
    }
      :
}

We made a few changes in the above:

• We made the constructor for Point private so that one cannot call the constructor directly.
• We provide a class factory method named of for the client to create a Point instance. The of method returns the same instance ORIGIN every time Point.of(0, 0) is called.

Such a design pattern is only safe when the class is immutable. Consider the mutable version of Point -- calling Point.of(0, 0).moveTo(1, 1) would change every reference to the origin to (1, 1), causing chaos in the code!

Enabling Safe Sharing of Internals

Immutable instances can also share their internals freely. Consider an immutable implementation of our Array<T>, called ImmutableArray<T>. Let's start with a simple version first.

// version 0.1
final class ImmutableArray<T> {
  private final T[] array;

  // Only items of type T goes into the array.
  @SafeVarargs
  public static <T> ImmutableArray<T> of(T... items) {
    return new ImmutableArray<>(items);
  }

  private ImmutableArray(T[] a) {
    this.array = a;
  }

  public T get(int index) {
    return this.array[index];
  }
}

There are a few things to note here.

Varargs The parameter to the class factory method of has the form T... items. The triple . notation is a Java syntax for a variable number of arguments of the same type (T). Often called varargs, this is just syntactic sugar for passing in an array of items to a method. We can then call of with a variable number of arguments, such as:

ImmutableArray<Integer> a;
a = ImmutableArray.of(1, 2, 3);
a = ImmutableArray.of(1, 2, 3, 4, 5);

@SafeVarargs Since the varargs is just an array, and array and generics do not mix well in Java, the compiler would throw us an unchecked warning. In this instance, however, we know that our code is safe because we never put anything other than items of type T into the array. We can use the @SafeVarargs annotation to tell the compiler that we know what we are doing and this varargs is safe.

Notice that we removed the set method and there is no other way an external client can modify the array once it is created.

Now, suppose that we wish to support a subarray method, that returns a new array containing only a range of elements in the original array. It behaves as follows:

ImmutableArray<Integer> a = ImmutableArray.of(10, 20, 30, 40, 50, 60);
ImmutableArray<Integer> b = a.subarray(2, 4); // b is [30, 40, 50]
b.get(0) // returns 30
ImmutableArray<Integer> c = b.subarray(1, 2); // c is [40, 50]
c.get(1) // returns 50

A typical way to implement subarray is to allocate a new T[] and copy the elements over. This operation can be expensive if our ImmutableArray has millions of elements. But, since our class is immutable and the internal field array is guaranteed not to mutate, we can safely let b and c refer to the same array from a, and only store the starting and ending index.

class ImmutableArray<T> {
  private final int start;
  private final int end;
  private final T[] array;

  @SafeVarargs
  public static <T> ImmutableArray<T> of(T... items) {
    return new ImmutableArray<>(items, 0, items.length-1);
  }

  private ImmutableArray(T[] a, int start, int end) {
    this.start = start;
    this.end = end;
    this.array = a;
  }

  public T get(int index) {
    if (index < 0 || this.start + index > this.end) {
      throw new IllegalArgumentException("Index out of bound");
    }
    return this.array[this.start + index];
  }

  public ImmutableArray<T> subarray(int start, int end) {
     return new ImmutableArray<>(this.array, this.start + start, this.start + end);
  }
}

Enabling Safe Concurrent Execution

We will explore concurrent execution of code towards the end of the module, but making our classes immutable goes a long way in reducing bugs related to concurrent execution. Without going into details here (you will learn the details later), concurrent programming allows multiple threads of code to run in an interleaved fashion, in an arbitrary interleaving order. If we have complex code that is difficult to debug to begin with, imagine having code where we have to ensure its correctness regardless of how the execution interleaves! Immutability helps us ensure that regardless of how the code interleaves, our objects remain unchanged.