Why doesn't Java 8 include immutable collections?

Question

The Java team has done a ton of great work removing barriers to functional programming in Java 8. In particular, the changes to the java.util Collections do a great job of chaining transformations into very fast streamed operations. Considering how good a job they have done adding first class functions and functional methods on collections, why have they completely failed to provide immutable collections or even immutable collection interfaces?

Without changing any existing code, the Java team could at any time add immutable interfaces that are the same as the mutable ones, minus the setter methods and make the existing interfaces extend from them, like this:

                  ImmutableIterable
     ____________/       |
    /                    |
Iterable        ImmutableCollection
   |    _______/    /          \   \___________
   |   /           /            \              \
 Collection  ImmutableList  ImmutableSet  ImmutableMap  ...
    \  \  \_________|______________|__________   |
     \  \___________|____________  |          \  |
      \___________  |            \ |           \ |
                  List            Set           Map ...

Sure, operations like List.add() and Map.put() currently return a boolean or previous value for the given key to indicate whether the operation succeeded or failed. Immutable collections would have to treat such methods as factories and return a new collection containing the added element - which is incompatible with the current signature. But that could be worked-around by using a different method name like ImmutableList.append() or .addAt() and ImmutableMap.putEntry(). The resulting verbosity would be more than outweighed by the benefits of working with immutable collections, and the type system would prevent errors of calling the wrong method. Over time, the old methods could be deprecated.

Wins of immutable collections:

• Simplicity — reasoning about code is simpler when the underlying data does not change.
• Documentation — if a method takes an immutable collection interface, you know it isn't going to modify that collection. If a method returns an immutable collection, you know you can't modify it.
• Concurrency — immutable collections can be shared safely across threads.

As someone who has tasted languages which assume immutability, it is very hard to go back to the Wild West of rampant mutation. Clojure's collections (sequence abstraction) already have everything that Java 8 collections provide, plus immutability (though maybe using extra memory and time due to synchronized linked-lists instead of streams). Scala has both mutable and immutable collections with a full set of operations, and though those operations are eager, calling .iterator gives a lazy view (and there are other ways of lazily evaluating them). I don't see how Java can continue to compete without immutable collections.

Can someone point me to the history or discussion about this? Surely it's public somewhere.

Answer 1

Because immutable collections absolutely require sharing to be usable. Otherwise, every single operation drops a whole other list into the heap somewhere. Languages that are entirely immutable, like Haskell, generate astonishing amounts of garbage without aggressive optimizations and sharing. Having collection that's only usable with <50 elements is not worth putting in the standard library.

Further more, immutable collections often have fundamentally different implementations than their mutable counterparts. Consider for example ArrayList, an efficient immutable ArrayList wouldn't be an array at all! It should be implemented with a balanced tree with a large branching factor, Clojure uses 32 IIRC. Making mutable collections be "immutable" by just adding a functional update is a performance bug just as much as a memory leak is.

Furthermore, sharing isn't viable in Java. Java provides too many unrestricted hooks to mutability and reference equality to make sharing "just an optimization". It'd probably irk you a bit if you could modify an element in a list, and realize you just modified an element in the other 20 versions of that list you had.

This also rules out huge classes of very vital optimizations for efficient immutability, sharing, stream fusion, you name it, mutability breaks it. (That'd make a good slogan for FP evangelists)

Answer 2

A mutable collection is not a subtype of an immutable collection. Instead, mutable and immutable collections are sibling descendants of readable collections. Unfortunately, the concepts of "readable", "read-only", and "immutable" seem to get blurred together, even though they mean three different things.

• A readable collection base class or interface type promises that one may read items, and does not provide any direct means of modifying the collection, but does not guarantee that code receiving the reference cannot cast or manipulate it in such a way as to permit modification.

• A read-only collection interface doesn't include any new members, but should only be implemented by a class which promises that there is no way to manipulate a reference to it in such a way as to mutate the collection nor receive a reference to something that could do so. It does not, however, promise that the collection won't be modified by something else which has a reference to the internals. Note that a read-only collection interface may not be able to prevent implementation by mutable classes, but can specify that any any implementation, or class derived from an implementation, which allows mutation shall be considered an "illegitimate" implementation or derivative of an implementation.

• An immutable collection is one which will always hold the same data as long as any reference to it exists. Any implementation of an immutable interface which does not always return the same data in response to a particular request is broken.

It is sometimes useful to have strongly-associated mutable and immutable collection types which both implement or derive from the same "readable" type, and to have the readable type include AsImmutable, AsMutable, and AsNewMutable methods. Such a design can allow code which wants to persist the data in a collection to call AsImmutable; that method will make a defensive copy if the collection is mutable, but skip the copy if it's already immutable.

Answer 3

The Java Collections Framework does provide the ability to create a read-only version of a collection by way of six static methods in the java.util.Collections class:

• unmodifiableCollection(Collection c)
• unmodifiableList(List list)
• unmodifiableMap(Map m)
• unmodifiableSet(Set s)
• unmodifiableSortedMap(SortedMap m)
• unmodifiableSortedSet(SortedSet s)

As someone has pointed out in the comments to the original question, the collections returned may not be considered immutable because even though the collections cannot be modified (no members can be added or removed from such a collection), the actual objects referenced by the collection can be modified if their object type allows it.

However, this problem would remain regardless of whether code returns a single object, or an unmodifiable collection of objects. If the type allows its objects to be mutated, then that decision was made in the design of the type and I don't see how a change to the JCF could alter that. If immutability is important, then the members of a collection should be of an immutable type.

Answer 4

This is a very good question. I enjoy entertaining the idea that of all the code written in java and running on millions of computers all over the world, every day, around the clock, about half the total clock cycles must be wasted doing nothing but making safety copies of collections returned by functions, which are garbage-collected milliseconds later.

A percentage of java programmers are aware of the existence of the unmodifiableCollection() family of methods of the Collections class, but most don't bother with it, and I can't blame them: an interface which pretends to be read-write but will slap you in the face with an UnsupportedOperationException if you make the mistake of invoking any of its 'write' methods is quite an evil thing to have!

Now, an interface like Collection which would be missing the add(), remove() and clear() methods would not be an "ImmutableCollection" interface; it would be an "UnmodifiableCollection" interface. As a matter of fact, there could never be an "ImmutableCollection" interface, because immutability is a nature of an implementation, not a characteristic of an interface. I know, that's not very clear; let me explain.

Suppose someone hands you such a read-only collection interface; is it safe to pass it to another thread? If you knew for sure that it represents a truly immutable collection, then the answer would be "yes"; unfortunately, since it is an interface, you do not know how it is implemented, so the answer has to be a no: for all you know, it may be an unmodifiable (to you) view of a collection which is in fact mutable, (like what you get with Collections.unmodifiableCollection(),) so attempting to read from it while another thread is modifying it would result in reading corrupt data.

So, what you have essentially described is a set of not "Immutable", but "Unmodifiable" collection interfaces. It is important to understand that "Unmodifiable" simply means that whoever has a reference to such an interface is prevented from modifying the underlying collection not because the underlying collection is necessarily immutable, but simply because the interface lacks any modification methods.

Now, I happened to be present at Devoxx Belgium 2017 where several people from Oracle gave talks, and one of them was Brian Goetz. I went to him after his talk and asked him precisely this: why are there no unmodifiable interfaces in Java? I must say that the answer he gave me was not particularly convincing: he said that they are not doing it due to a security concern: if you have a mutable collection class implementing a mutable collection interface which extends an unmodifiable collection interface, and you hand out the unmodifiable interface, whoever holds that interface can up-cast it to the mutable interface and modify the original collection.

This is not convincing because it describes a very simplistic scenario which can very easily be taken care of with some simple extra measures: If you have a security concern you can instantiate and hand-out an unmodifiable collection adaptor which wraps (delegates to) your mutable collection without implementing the mutable collection interface. As a matter of fact, you are already doing this structurally when you use the unmodifiableCollecton() family of methods, the only problem is that the interface you are handing out is secretly unmodifiable, meaning that it obtusely exposes mutation methods, but invoke any of them and you die. Thus, unmodifiable interfaces could eliminate this existing obtuseness while keeping everything else structurally the same if need be.

But of course, things would not have to be kept the same. The next step would be to add immutable collection classes, which implement the unmodifiable collection interfaces. When there is a need to guarantee immutability, (such as the case is, for example, when passing a collection from one thread to another,) such collections would be passed around as immutable classes, not as unmodifiable interfaces, so that the receiver knows for sure that what they have in their hands is immutable.

So, in order to have a complete set of collections in java, (or any other declarative imperative language,) we would need the following:

1. A set of unmodifiable collection interfaces.

2. A set of mutable collection interfaces, extending the unmodifiable ones.

3. A set of mutable collection classes implementing the mutable interfaces, and by extension also the unmodifiable interfaces.

4. A set of immutable collection classes, implementing the unmodifiable interfaces, but mostly passed around as classes, so as to guarantee immutability.

I have implemented all of the above for fun, and I am using them in projects, and they work like a charm.

The reason why they are not part of the java runtime is probably because it was thought that this would be too much / too complex / too difficult to understand.

Personally, I think that what I described above is not even enough; one more thing that appears to be needed is a set of mutable interfaces & classes for structural immutability. (Which may simply be called "Rigid" because the prefix "StructurallyImmutable" is too damn long.)

Answer 5

Immutable collections can be deeply recursive, compared to eachother, and not unreasonably inefficient if object equality is by secureHash. This is called a merkle forest. It can be per collection or within parts of them like an (self balancing binary) AVL tree for a sorted map.

Unless all java objects in these collections have a unique id or some bitstring to hash, the collection has nothing to hash to uniquely name itself.

Example: On my 4x1.6ghz laptop, I can run 200K sha256s per second of the smallest size that fits in 1 hash cycle (up to 55 bytes), compared to 500K HashMap ops or 3M ops in a hashtable of longs. 200K/log(collectionSize) new collections per second is fast enough for some things where data integrity and anonymous global scalability is important.

Answer 6

This is not immutable, but Read-Only. I.e. a type to represent an collection with only read operations. This is not a bad idea, and was done in C# collection framework. I think Java creators should consider this as a quite useful thing to do in future versions of Java.

Answer 7

Performance. Collections by their nature can be very large. Copying 1000 elements to a new structure with 1001 elements instead of inserting a single element is just plain horrible.

Concurrency. If you have several threads running they may want to get the current version of the collection and not the version that was passed 12 hours ago when the thread started.

Storage. With immutable objects in a multi threaded environment you can end up with dozens of copies of the "same" object at different points of its life cycle. Doesnt matter for a Calendar or Date object but when its a collection of 10,000 widgets this will kill you.