Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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 "set" methods and make the existing interfaces extend from them, like this:

                     Iterable (already immutable)
                         |
                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
  • 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.

share|improve this question
7  
Related to this - Ayende blogged recently about collections and immutable collections in C#, with benchmarks. ayende.com/blog/tags/performance - tl;dr - immutability is slow. –  Oded Dec 18 '13 at 15:05
11  
with your hierarchy I can give you a ImmutableList and then change it on you when you don't expect it which can break a lot of things, as is you only have const collections –  ratchet freak Dec 18 '13 at 15:16
6  
@Oded Immutability is slow, but so is locking. So is maintaining a history. Simplicity/Correctness is worth speed in many situations. With small collections, speed is not an issue. Ayende's analysis is based on the assumption that you don't need history, locking, or simplicity and that you are working with a large data set. Sometimes that's true, but it's not a one-is-always-better thing. There are trade-offs. –  GlenPeterson Dec 18 '13 at 15:36
2  
@Oded technically it isn't immutability that slows things down but copy-on-write. But we can expect these classes to get used like this (see the proliferation of string concatenation in loops). –  ratchet freak Dec 18 '13 at 15:52
4  
@GlenPeterson that's what defensive copies and Collections.unmodifiable*() are for. but don't treat these as immutable when they are not –  ratchet freak Dec 18 '13 at 15:56
show 11 more comments

5 Answers

up vote 37 down vote accepted
+50

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)

share|improve this answer
3  
My example talked about immutable interfaces. Java could provide a full suite of both mutable and immutable implementations of those interfaces that would make the necessary trade-offs. It's up to the programmer to choose mutable or immutable as appropriate. Programmers have to know when to use a List vs. Set now. You generally don't need the mutable version until you have a performance issue, and then it may only be necessary as a builder. In any case, having the immutable interface would be a win on its own. –  GlenPeterson Dec 18 '13 at 17:21
    
I read your answer again and I think you are saying that Java has a fundamental assumption of mutability (e.g. java beans) and that the collections are just the tip of the iceberg and carving off that tip won't solve the underlying problem. A valid point. I might accept this answer and speed up my adoption of Scala! :-) –  GlenPeterson Dec 18 '13 at 17:28
2  
Good points. This is why frege (a pure functional language in the spirit of Haskell that compiles to Java) has its own lists, maps, etc. The existing collections in Java are unusable in pure functional code due to the reasons you point out. –  Ingo Dec 19 '13 at 10:00
    
I'm not sure immutable collections require the ability to share common parts to be useful. The most common immutable type in Java, an immutable collection of characters, used to allow sharing but doesn't anymore. The key thing that makes it useful is the ability to quickly copy data from a String into a StringBuffer, manipulate it, and then copy the data into a new immutable String. Using such a pattern with sets and lists might be as good as using immutable types that are designed to facilitate the production of slightly-changed instances, but could still be better... –  supercat Jan 17 at 19:30
    
...than having to constantly make defensive copies of mutable types all the time. –  supercat Jan 17 at 19:31
add comment

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.

share|improve this answer
    
Great answer. Immutable collections can give you a pretty strong guarantee related to thread-safeness and how you can reason about them as time goes by. A Readable/Read-only collection does not. In fact, to honor the liskov substition principle, Read-Only and Immutable should probably be abstract base type with final method and private members to ensure that no derived class can destroy the garantee given by the type. Or they should be fully concrete type that either wrap a collection (Read-Only), or always take a defensive copy (Immutable). This is how guava ImmutableList does it. –  Laurent Bourgault-Roy Dec 23 '13 at 15:12
    
@LaurentBourgault-Roy: There are advantages to both sealed and inheritable immutable types. If one doesn't want to allow an illegitimate derived class to break one's invariants, sealed types can offer protection against that while inheritable classes offer none. On the other hand, it may be possible for code that knows something about the data it holds to store it much more compactly than would a type that knows nothing about it. Consider, for example, a ReadableIndexedIntSequence type which encapsulates a sequence of int, with methods getLength() and getItemAt(int). –  supercat Dec 23 '13 at 16:34
    
Indeed. No silver bullet here. And even a sealed class can be defeated using reflection. –  Laurent Bourgault-Roy Dec 23 '13 at 16:39
    
@LaurentBourgault-Roy: Given a ReadableIndexedIntSequence, one could produce an instance of an array-backed immutable type by copying all the items into an array, but suppose that a particular implementation simply returned 16777216 for length and ((long)index*index)>>24 for each item. That would be a legitimate immutable sequence of integers, but copying it to an array would be a huge waste of time and memory. –  supercat Dec 23 '13 at 16:39
    
I fully agree. My solution give you correctness (up to a point), but to get performance with large dataset, you must have persistent structure and design for immutability from the beginning. For small collection though you can get away with taking an immutable copy from time to time. I remember that Scala did some analysis of various program and found that something like 90% of the lists instanciated were 10 or less items long. –  Laurent Bourgault-Roy Dec 23 '13 at 16:43
show 2 more comments

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.

share|improve this answer
5  
Immutable collections only require copying if you can’t share because of pervasive mutability like Java has. Concurrency is generally easier with immutable collections because they don’t require locking; and for visibility you can always have a mutable reference to an immutable collection (common in OCaml). With sharing, updates can be essentially free. You may do logarithmically more allocations than with a mutable structure, but on update, many expired subobjects can be freed immediately or reused, so you don’t necessarily have higher memory overhead. –  Jon Purdy Dec 19 '13 at 1:32
1  
Couple problems. The collections in Clojure and Scala are both immutable, but support light-weight copies. Adding element 1001 means copying less than 33 elements, plus making a few new pointers. If you share a mutable collection across threads, you have all kinds of synchronization issues when you change it. Operations like "remove()" are nightmarish. Also, immutable collections can be built mutably, then copied once into an immutable version safe to share across threads. –  GlenPeterson Dec 19 '13 at 2:33
    
Using concurrency as an argument against immutability is unusual. Duplicates as well. –  Tom Hawtin - tackline Dec 20 '13 at 1:41
    
If several threads need to access the latest version then a classic immutable object does not work. Instead you have the performance overhead and complication of a "pretend" immutable object. –  James Anderson Dec 20 '13 at 3:27
1  
A little bit miffed about the down votes here. The OP asked why they did not implement immutable collections, and, I provided a considered answer to the question. Presumably the only acceptable answer among the fashion conscious is "because they made a mistake". I actually have some experience with this having to refactor large chunks of code using the otherwise excellent BigDecimal class purely because of poor perfomance due to immutability 512 times that of using a double plus some messing around to fix the decimals. –  James Anderson Dec 20 '13 at 3:33
show 3 more comments

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:

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.

share|improve this answer
add comment

I believe the java code that supports Clojure is usable separately as a library of immutable data constructs. It's not quite the same as being part of the language, but it's a start.

share|improve this answer
4  
Your answer would be stronger if you expanded it and addressed more of the OP's concerns. –  GlenH7 Dec 18 '13 at 19:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.