Making Stack Immutable

PSA, just jump to the end if you think this is too long and just want a summary.

I’ll discuss how to make a Stack immutable in Java.

Before going further, let us recall what “immutable” means in CS2030S. In the course, a class is considered immutable if instances of that class do not undergo any observable change outside the abstraction barrier.

This is weaker than true immutability. True immutability means that once a value is created, it does not change at all.

Consider the following Java implementation of Stack.

public class Stack<T> {
    private T head;
    private Stack<T> tail;
    private static final Stack<?> EMPTY_STACK = new Stack<>(null, null);

    private Stack(T head, Stack<T> tail) {
        this.head = head;
        this.tail = tail;
    }

    public void push(T t) {
        this.tail = new Stack<T>(this.head, this.tail);
        this.head = t;
    }

    public void pop() {
        if (this.head == null) {
            throw new IllegalStateException("Stack is empty");
        }
        this.head = this.tail.head;
        this.tail = this.tail.tail;
    }

    public T head() {
        if (this.head == null) {
            throw new IllegalStateException("Stack is empty");
        }
        return head;
    }

    public boolean isEmpty() {
        return this.head == null;
    }

    public static <T> Stack<T> createNew() {
        @SuppressWarnings("unchecked")
        Stack<T> emptyStack = (Stack<T>) EMPTY_STACK;
        return emptyStack;
    }
}

This class is clearly mutable. In particular, both push and pop reassign the fields head and tail of the current object. So these two methods must change if we want Stack to be immutable.

Relating this to CS1101S lists

Students who have taken CS1101S may notice that the field names head and tail look familiar.

In fact, this Stack is essentially isomorphic (same form) to the list from CS1101S. A list is either:

null, or

a pair whose head is an element and whose tail is another list.

That is exactly the same shape as our Stack: it has a head of type T, a tail of type Stack<T>, and a distinguished empty stack value corresponding to the empty list.

So a natural way to think about immutability here is to use the same mindset as in the first half of CS1101S: instead of modifying an existing structure, we build and return a new one.

Making push immutable

In CS1101S terms, push is like a function that takes a list and an element, and returns a new list with that element added to the front.

function push(lst, ele) {
  return pair(ele, lst);
}

Since we are not allowed to do destructive updates, we must construct a new pair rather than modify the old list.

Now we translate that idea into Java. Although push is written as a non-static method, you can think of a method call as a function call with an extra this parameter. So a method like foo(int x) inside a class A can be viewed conceptually as something like foo(A this, int x)

So here, push conceptually behaves like push(Stack<T> this, T t). Since we want an immutable design, it should return a new Stack<T> rather than mutate the current one.

public Stack<T> push(T t) {
    return new Stack<>(t, this);
}

Making pop immutable

Similarly, pop corresponds to returning the tail of the list.

function pop(lst) {
  return tail(lst);
}

So in Java, we can simply return this.tail.

public Stack<T> pop() {
    return this.tail;
}

Notice that here we do not even need to allocate a new Stack, we can just reuse an existing one.

Making the fields final

Once the mutating methods are fixed, the next step is to make the fields final.

Strictly speaking, a class can be immutable even if its fields are not declared final, as long as they are never reassigned after construction. However, making fields final is still a very good idea. It lets the compiler help us enforce that we do not accidentally reassign them.

public class Stack<T> {
    private final T head;
    private final Stack<T> tail;
    // ...
}

Making the class itself final

It may seem that we are done, but there is one more point worth addressing: the class itself should also be declared final.

Why? Because otherwise someone could create a subclass of Stack and introduce mutability in the subclass. That would weaken the guarantee that values of this abstraction are immutable.

For example, a subclass could add its own mutable state and provide mutating operations. Even if the original Stack class itself remains immutable, allowing unrestricted subclassing allows someone to reintroduce mutability.

So it is good practice to write:

public final class Stack<T> {
    ...
}

Otherwise, someone could do the following

public class MutableStack extends Stack<T> {
    private T head;
    private Stack<T> tail;
    private static final Stack<?> EMPTY_STACK = new Stack<>(null, null);

    private Stack(T head, Stack<T> tail) {
        super(head, tail);
        this.head = head;
        this.tail = tail;
    }

    @Override
    public void push(T t) {
        this.tail = new Stack<T>(this.head, this.tail);
        this.head = t;
    }

    @Override
    public void pop() {
        if (this.head == null) {
            throw new IllegalStateException("Stack is empty");
        }
        this.head = this.tail.head;
        this.tail = this.tail.tail;
    }
}

This would violate LSP because, anywhere that a Stack is expected, we could put the subtype MutableStack, however Stack has a property of being immutable which MustableStack clearly violates.

Final version

Putting everything together, we get:

public final class Stack<T> {
    private final T head;
    private final Stack<T> tail;
    private static final Stack<?> EMPTY_STACK = new Stack<>(null, null);

    private Stack(T head, Stack<T> tail) {
        this.head = head;
        this.tail = tail;
    }

    public Stack<T> push(T t) {
        return new Stack<>(t, this);
    }

    public Stack<T> pop() {
        if (this.head == null) {
            throw new IllegalStateException("Stack is empty");
        }
        return this.tail;
    }

    public T head() {
        if (this.head == null) {
            throw new IllegalStateException("Stack is empty");
        }
        return this.head;
    }

    public boolean isEmpty() {
        return this.head == null;
    }

    public static <T> Stack<T> createNew() {
        @SuppressWarnings("unchecked")
        Stack<T> emptyStack = (Stack<T>) EMPTY_STACK;
        return emptyStack;
    }
}

Summary

To make classes immutable in general:

make the class final
make the fields final
change mutating methods so that they return new instances, or return existing ones, instead of modifying the current one

Read other posts

Immutable Stack