• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

Effective Java: regarding Functional Collections

 
Greenhorn
Posts: 28
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Josh,

I’m a big fan of “Effective Java.” In it, you make a number of recommendations regarding the collections API. I use immutable objects to make my programs easier to reason about and thread safe. The difficulty I run into is that the collections API exposes lots of optional mutating operations. I can use the unmodifiable wrappers to prevent an internal collection from being mutated by clients of my classes, but the client still sees the optional mutating operations and can’t tell from just the interface whether a particular implementation allows mutation or will throw an exception. Does this violate the Liskov Substitution Principle? Also, I find myself making defensive copies if I want to retain a collection as a field in an object which incurs copying overhead.

Do you think Java would benefit from having a standardized functional collections library? The functional collections would be both immutable and persistent. “Immutable” in the sense that they can not be modified after they are created. “Persistent” in the sense that a collection returns a new version of itself when the client attempts to change it, and retains the current version of itself unmodified. For example, if you attempt to add an element to a collection, the return value of the “add” method is another collection containing the additional element. To avoid excessive copying overhead, structural sharing is used between the old version and the new version of the collection. The old version is garbage collected when it is no longer referenced.

Chris Okasaki has done a lot of work in this area, and his work has formed the basis of various functional collection libraries. However, the libraries are not part of the Java standard. They need to interoperate with the current collection API. Is it time to create a JEP to add a standardized functional collection library to Java?

Best Regards,

Bruce
 
Author and "Sun God"
Posts: 185
12
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Bruce. The collection interface's approach mutability does violate the Liskov substitution principle, but it wasn't done thoughtlessly. Here's what I said in the Collections design FAQ , written circa 1997:

1. Why don't you support immutability directly in the core collection interfaces so that you can do away with optional operations (and UnsupportedOperationException)?

This is the most controversial design decision in the whole API. Clearly, static (compile time) type checking is highly desirable, and is the norm in Java. We would have supported it if we believed it were feasible. Unfortunately, attempts to achieve this goal cause an explosion in the size of the interface hierarchy, and do not succeed in eliminating the need for runtime exceptions (though they reduce it substantially).

Doug Lea, who wrote a popular Java collections package that did reflect mutability distinctions in its interface hierarchy, no longer believes it is a viable approach, based on user experience with his collections package. In his words (from personal correspondence) "Much as it pains me to say it, strong static typing does not work for collection interfaces in Java."

To illustrate the problem in gory detail, suppose you want to add the notion of modifiability to the Hierarchy. You need four new interfaces: ModifiableCollection, ModifiableSet, ModifiableList, and ModifiableMap. What was previously a simple hierarchy is now a messy heterarchy. Also, you need a new Iterator interface for use with unmodifiable Collections, that does not contain the remove operation. Now can you do away with UnsupportedOperationException? Unfortunately not.

Consider arrays. They implement most of the List operations, but not remove and add. They are "fixed-size" Lists. If you want to capture this notion in the hierarchy, you have to add two new interfaces: VariableSizeList and VariableSizeMap. You don't have to add VariableSizeCollection and VariableSizeSet, because they'd be identical to ModifiableCollection and ModifiableSet, but you might choose to add them anyway for consistency's sake. Also, you need a new variety of ListIterator that doesn't support the add and remove operations, to go along with unmodifiable List. Now we're up to ten or twelve interfaces, plus two new Iterator interfaces, instead of our original four. Are we done? No.

Consider logs (such as error logs, audit logs and journals for recoverable data objects). They are natural append-only sequences, that support all of the List operations except for remove and set (replace). They require a new core interface, and a new iterator.

And what about immutable Collections, as opposed to unmodifiable ones? (i.e., Collections that cannot be changed by the client AND will never change for any other reason). Many argue that this is the most important distinction of all, because it allows multiple threads to access a collection concurrently without the need for synchronization. Adding this support to the type hierarchy requires four more interfaces.

Now we're up to twenty or so interfaces and five iterators, and it's almost certain that there are still collections arising in practice that don't fit cleanly into any of the interfaces. For example, the collection-views returned by Map are natural delete-only collections. Also, there are collections that will reject certain elements on the basis of their value, so we still haven't done away with runtime exceptions.

When all was said and done, we felt that it was a sound engineering compromise to sidestep the whole issue by providing a very small set of core interfaces that can throw a runtime exception.



After two decades, I'm still reasonably happy with this design compromise, but others (notably Guava) have worked around the compromise by extending the framework with types for immutable collections.


As for a purely functional collections library (à la Okasaki, who I knew at CMU in the '80s), I think various people have implemented this over the years, including, IIRC, my dear friend Tim Peierls. It's perhaps a bit of niche for inclusion in the JDK, and not a great fit for my APIs.
 
Bartender
Posts: 15737
368
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Great question, great answer.

When you say that you're reasonably happy, it implies there are some changes that you would make. Obviously, for the reasons you mentioned, it will still be a compromise, but what would you have done differently, looking back?
 
Joshua Bloch
Author and "Sun God"
Posts: 185
12
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The NUMBER ONE thing that I would have done differently is to return the target collection from practically every method in the core interfaces and the utility classes such as Collections. This would have enabled "fluent" programming with collections, greatly enhancing conciseness and convenience. For example, getting the intersection two sets should look like this:



instead of:



It was a very bad decision to instead return a boolean indicating whether the collection had changed as a result of the call, or to return void. In my defense, fluent programming was less of a thing back then, Java did not yet have covariant return types, and IDEs barely existed, but it would have been a different world if I had gotten this decision right. I think I learned a lot the right lessons from existing frameworks (e.g., C++ STL and Smalltalk collections), but I could have done even better.
 
please buy this thing and then I get a fat cut of the action:
We need your help - Coderanch server fundraiser
https://coderanch.com/wiki/782867/Coderanch-server-fundraiser
reply
    Bookmark Topic Watch Topic
  • New Topic