Why Java Collections Framework is a Cats & Dogs Library

It is nothing new that shared mutable state is the root of all evil. Especially concurrent programming requires a proper synchronization of shared mutable state. But even in single-threaded environments mutability is a problem.

Mutability is insecure

The document Java Secure Coding Guidelines for Java SE contains a whole chapter that covers security problems related to mutability. Summed up, these are the recommendations:

• Prefer immutability for value types
• Create copies of mutable output values
• Create safe copies of mutable and subclassable input values
• Support copy functionality for a mutable class
• Do not trust identity equality when overridable on input reference objects
• Treat passing input to untrusted object as output
• Treat output from untrusted object as input
• Define wrapper methods around modifiable internal state
• Make public static fields final
• Ensure public static final field values are constants
• Do not expose mutable statics
• Do not expose modifiable collections

I've marked the important parts bold. The rest is automatically secured in an application that uses immutable/persistent data structures like those of Javaslang.

Mutability is unnatural

In nature there is no mutability, we can't overwrite an existing state in the way that it disappears from the timeline. Programmers tend to think the way of changing things in place. For that reason J. W. Backus entitled his 1978 Turing Award lecture "Can Programming be Liberated from the von Neumann Style".

Mutability does not only introduce the security problems mentioned above. It does also introduce problems on the type-level. These problems are self-made problems. They falsely put bad light on Java's type system — it seems to be dissonant.

Let's consider this Pet example:

interface Pet {}

class Cat implements Pet {
    @Override public String toString() { return "Cat"; }
}

class Dog implements Pet {
    @Override public String toString() { return "Dog"; }
}

In an object-functional setting (having immutable/persistent data structures) the types behave like expected. Of course a sequence of Dogs is also a sequence of Pets, persistent collections are covariant. When adding a Cat, it remains a sequence of Pets.

Seq<Dog> dogs = Vector(new Dog());

// Type narrowing, pets = dogs does not compile!
Seq<Pet> pets = Seq.narrow(dogs);

// Vector(Dog, Cat)
println(pets.append(new Cat()));

// Vector(Dog)
println(pets);

// Vector(Dog)
println(dogs);

The need for narrowing makes me mad, the assignment pets = dogs should work out of the box (in an unsound type system). That problem could be solved by introducing declaration site variance to the Java language (which will most probably not happen in near future).

However, let's take a look how the mutable Java collections behave:

List<Dog> dogs = new ArrayList<>();
dogs.add(new Dog());

// Type narrowing, pets = dogs does not compile!
List<Pet> pets = narrow(dogs);

// Heap pollution!
pets.add(new Cat());

// [Dog, Cat]
println(pets);

// Huh!? [Dog, Cat]
println(dogs);

Java does not support narrowing 'out-of-the-box'. We use this helper function:

// This is unsafe!
static <T> List<T> narrow(List<? extends T> list) {
    return (List<T>) list;
}

As we see, heap pollution may occur if we narrow a mutable Java collection.

List<Dog> contains a Cat...

In an immutable/persistent environment such self-made problems cannot occur by design — one more reason to use persistent data structures like those of Javaslang.

Have fun!

- Daniel

The complete example can be found here.