[External] : Re: ReversibleCollection proposal

[forax at univ-mlv.fr]

----- Mail original -----
> De: "Stuart Marks" <stuart.marks at oracle.com>
> À: "Remi Forax" <forax at univ-mlv.fr>
> Cc: "core-libs-dev" <core-libs-dev at openjdk.java.net>
> Envoyé: Mercredi 12 Mai 2021 07:27:51
> Objet: Re: [External] : Re: ReversibleCollection proposal

>>> I'm certain that uses of RC/RS will be rare in the beginning, because they will
>>> be
>>> new, and people won't be familar with them. And then there will the people who
>>> say
>>> "I can't use them because I'm stuck on JDK 11 / 8 / 7 / 6 ...." It was the same
>>> thing with lambdas and streams in Java 8, with List.of() etc in Java 9, records
>>> in
>>> Java 16, etc. This wasn't an argument not to add them, and it isn't an argument
>>> not
>>> to add RC/RS.
>> 
>> All the changes you are listing here are "client side" changes, the ones that
>> can be adopted quickly because they do not require to change the API side of
>> any libraries.
>> ReversibleCollection is an API side change, like generics is, those changes have
>> a far higher cost because you have to wait your library dependencies to be
>> updated.
>> On the Valhalla list, we have discussed several times about how to alleviate
>> those API side change cost using automatic bridging or methods forwarding, even
>> for Valhalla, we are currently moving in a state where those mechanisms are not
>> needed.
> 
> This isn't an argument against RC/RS. Application code can find uses for the new
> APIs, e.g. getFirst and addLast on List, or more ordering flexibility on
> LinkedHashSet, on day one. Applications' internal APIs can also benefit on day
> one.
> Certainly libraries will have to wait for their clients to catch up to later
> JDKs.
> This has *always* been the case, even for library internals (such as use of
> lambdas
> or APIs introduced in newer JDKs) because libraries need to be compiled for the
> lowest version of the JDK their clients support. For example, you can't use
> List.of() in a library -- even internally -- if your clients are still on JDK 8.
> There are no new issues here.

First, i think we have overlooked ReversibleMap, if you have a LinkedHashMap, the keySet should be a ReversibleSet.

It is because with RC/RS/RM, you have to wait far longer, being able to use the JDK version is not enough to be able to introduce a public method that takes a ReversibleCollection, you also need to be sure that all clients of your library are using collections that have been upgraded to implement ReversibleCollection. In practice, enough client might be Ok, but that's a huge difference. Instead, if we follow the path of using default methods on Collection and not new interfaces, you only need to wait until you decide to upgrade the library to the JDK version, because with default methods all existing collections are "automatically" upgraded.

> 
>> The abstraction already exists but it's not defined in term of interface because
>> it's an implementation decision and those are cleanly separated in the current
>> Collection design.
>> 
>> Let take a step back, the collection API defines basic data structure operations
>> in term of interfaces like List, Deque, Set, etc those interfaces are decoupled
>> from implementation capabilities like mutable, nullable, ordered and checked.
>> 
>> Depending on the implementation capabilities, the interfaces method
>> implementation may throw an exception, non-mutable implementations use
>> UnsupportedOperationException, non-nullable implementations use NPE and checked
>> implementations use CCE.
>> 
>> So what is missing is methods on Collection interfaces that require the
>> collection implementation to be ordered like descendingList(), getFirst(), etc.
>> Those methods that may throw a specific exception if the implementation is not
>> ordered, not UnsupportedOperationException but a new one like
>> NotOrderedException.
>> 
>> So to answer to your question about LinkedHashSet, the reverse-ordered
>> LinkedHashSet is a Set with a method descendingSet() that do not throw
>> NotOrderedException like any Set with an order.
>> 
>> To summarize, if we introduce ReversibleCollection, we should also introduce
>> ImmutableCollection, NonNullableCollection and CheckedCollection.
>> I think it's better to consider the fact that being ordered as a capability
>> (hint: this is already what the Spliterator API does) and not as a specific
>> interface.
> 
> This discussion, and your ensuing proposal to add a bunch of throwing default
> methods to Collection, is based on a flawed premise. That premise is that there
> is a fundamental distinction between "data structure operations" which must be embodied
> as types, and "implementation capabilities" which must manifest at runtime either by
> allowing the operation or by throwing an exception.

The collection framework doesn't respect one of the principle of OOP which is that you should not have a method on a type if you are not able to implement it.
This design decision was done for good, it drastically reduces the number of interfaces, thus simplify the mental image people have when using the API.
But it means that Collection.add or Iterator.remove can throw an UnsupportedOperationException, this is how the collection framework was designed.

> 
> But this distinction isn't fundamental. In what way is being ordered not a
> "basic data structure" issue? In what way is indexed access (as for List) not an
> "implementation capability"? Really, these are two different aspects of the same
> thing. Over time, new "data structure operations" and new "implementation
> capabilities" have been added to the collections framework. Some of them were
> embodied as types, and some were not. Which ones were embodied as types was the
> result of design decisions that considered a bunch of tradeoffs.

This is the first time we have actually the choice between adding new interfaces as it was done in the past (for NavigableSet/NavigableMap by example) or adding default methods on existing interfaces.
Before, we did not have that choice because default methods did not exist. We are post Java 8, and we want to add more capabilities to the collection API, so having this discussion about new interfaces vs new default methods is sane in my opinion. 

> 
> What you're attempting to do is to declare absolutes. 

It's something Brian says to me a lot, i believe part is the way i think part is the fact that i'm not a native English speaker, so my dictionary of words is reduced.

> This drives you to one of two extremes, which is either 1) to never add new types and to always add
> possibly-throwing operations to existing types (which seems to be what you're
> describing as an alternative); or 2) to claim that everything needs to be
> manifested as a new type (giving rise to your straw-man argument that we should also have
> ImmutableCollection, NonNullableCollection, CheckedCollection, etc.). The
> argument seems to be that we wouldn't want to add all those other types, so we mustn't
> add ReversibleCollection either. No.
> 
> In summary, I reject the premise that adding ReversibleCollection implies that a
> bunch of other types also need to be added, so I don't accept this line of
> reasoning as an argument against ReversibleCollection.

Where to draw the line is one argument against ReversibleCollection, what's make ReversibleCollection, ReversibleSet and ReversibleMap so special that they deserve to be new interfaces and not new default methods.

Again, we have seen that introducing those interfaces
- is not source backward compatible thus it will be painful for some of our users,
  I believe NavigableSet/NavigableMap did not have that issue because only one existing implementation per interface was retrofitted to implement those interfaces, TreeSet for NavigableSet and TreeMap for NavigableMap.
  ConcurrentSkipListSet/ConcurrentSkipListMap were added at the same time, so there was no existing code doing a lub (lowest upper bound) between TreeSet and ConcurrentSkipListSet.
  Here, they are a lot of implementations that will implement be retrofitted to ReversibleCollection, ReversibleSet and ReversibleMap.
- people will have to wait a theoretically infinite time before being to introduce a public method that takes a ReversibleCollection, ReversibleSet and ReversibleMap to their library, because it requires
  all existing implementations of collection with an order to be retrofitted to implement those interfaces.
- adding any new interfaces has a real cognitive cost, the collection API is supposed to be simple, does being reversible really worth such new weight.

We now have the opportunity to introduce default methods instead of new interfaces which do not have those drawbacks.
Obviously, using default methods instead of new interfaces have drawbacks too, mostly, you can use a static type to say this is a collection with an order.


> 
> s'marks

Rémi