[External] : Re: ReversibleCollection proposal

Fri May 14 07:16:07 UTC 2021

In reading all of the messages in this discussion, it becomes clear to
me that this is not a trivial change, because we are mostly hindered by
the Collection API as it currently exists.

Adding interfaces seems like the correct OOP way to do things, but it
may hinder adoption, because we have to wait for it to cascade through
the ecosystem.

Adding default methods seems like the most compatible way, but then we
create even more confusion in the Collection class. If add() can throw
an exception, but getFirst() never will but may just return a random
element, that does not seem consistent to me.

Has it ever been conceived to create an entire new API like how it was
done for Dates and Times? Obviously this would be a massive
undertaking, but it seems to me we've just about reached the limits of
how far we can stretch the current API.

When given the choice between the current proposals to add interfaces
or default methods, I'm kind of torn. Maybe we should just yield and
add the methods to the different sub-interfaces like List, etc? This
seems to be the least disruptive, but obviously it doesn't greatly
improve the overall design.

Kind regards,

Dave

On Fri, 2021-05-14 at 00:15 +0200, forax at univ-mlv.fr wrote:
> ----- Mail original -----
> > De: "Anthony Vanelverdinghe" <dev at anthonyv.be>
> > À: "Remi Forax" <forax at univ-mlv.fr>
> > Cc: "Stuart Marks" <stuart.marks at oracle.com>, "core-libs-dev"
> > <core-libs-dev at openjdk.java.net>
> > Envoyé: Jeudi 13 Mai 2021 21:18:22
> > Objet: Re: [External] : Re:  ReversibleCollection proposal
> 
> > Hi Rémi
> > 
> > The discussion "new types? or new default methods?" is indeed a
> > valid one. In
> > fact, I think this choice has already been made once in favor of a
> > default
> > method, when adding `List::sort` was chosen over adding
> > `SortedList` (though I
> > imagine that choice was a no-brainer).
> 
> yes, very true, there is no SortedList even if it would be useful to
> know if a list is already sorted, by example, we can add
> binarySearch() on it with no problem of people using it on an
> unsorted list.
> 
> > 
> > In this case I prefer adding new types though, so I wanted to share
> > my take on
> > this.
> > 
> > In the following diagram (see [1] in case it got mangled), I've
> > tried to arrange
> > all relevant Collection types by their defining characteristics:
> > 
> > > - Collection
> > > -----------------------------------------------------------------
> > > ----------------------------------------------|
> > > unordered    ordered                                  
> > > sorted           distinct
> > > distinct & ordered    distinct & sorted |
> > >                                                                  
> > >       Set                                                 |
> > >             Queue = (get|remove)First + addLast      
> > > PriorityQueue
> > >             |
> > >             Stack = (add|get|remove)Last
> > >             |
> > >             Deque = Queue + Stack + addFirst
> > >             LinkedHashSet         SortedSet         |
> > >             List = Deque + (add|get|remove)Indexed    List::sort
> > >             NavigableSet      |
> > > -----------------------------------------------------------------
> > > -----------------------------------------------------------|
> > 
> > As I see it, there are a couple of issues with this:
> > * conceptually, every List is a Deque, but List doesn't extend
> > Deque. If it
> > would, all uses of List (e.g. as a parameter type in APIs) where
> > the indexed
> > access isn't required could be replaced with Deque instead. Or e.g.
> > when you
> > need to take a stack as argument: currently Deque is the
> > recommended parameter
> > type, but that means you can't just pass a List to the method as-
> > is. With RC,
> > you'd be able to use that as parameter type and pass both Deque and
> > List.
> 
> You can use the same argument to have a common super type between Map
> and Collection, it would be very useful.
> 
> Until you think what methods are available on that type, size() and
> isEmpty(), meh, this is useless.
> 
> RC has the same issue, it's stuck in between Collection and List, so
> the cases where you don't want a Collection because it has not enough
> methods you want to use but at the same time you don't want a List
> because it has too many methods are vanishingly small.
> 
> The problem is that adding RC is not source compatible, so you are
> asking to add something in the JDK which serve a corner case but at
> the same time forces people to change their code even if they don't
> use RC.
> It's a loose / loose situation, we will have to maintain a collection
> forever in the JDK that nobody uses but everybody will pay for it.
> 
> [...]
> 
> > 
> > On Wednesday, May 12, 2021 13:22 CEST, forax at univ-mlv.fr wrote:
> > 
> > > First, i think we have overlooked ReversibleMap, if you have a
> > > LinkedHashMap,
> > > the keySet should be a ReversibleSet.
> > 
> > I'm not sure what you meant, but the PR already defines
> > `LinkedHashMap::keySet`
> > as `public ReversibleSet<K> keySet()`.
> 
> LinkedHashMap is perhaps the only implementation which has a keySet
> which is reversible, but there are a lot of other collection
> implementations, Apache collection, Guava, Eclipse, clojure-core, etc
> that may have such kind of implementation too. The same way you want
> RC between Queue and List, you want ReversibleMap between those Map
> implementations.
> 
> > 
> > > 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.
> > 
> > As far as I understand, both options might cause source
> > incompatibilities, but I
> > assume you estimate the actual impact of adding default methods to
> > be (much)
> > smaller?
> 
> Adding a default method may creates source incompatibilities but this
> can be solved by having a name with no collision, that why
> Iterator.forEachRemaining is such a long name by example.
> 
> Adding a common supertype to at least two already existing types
> change the inferred type in methods like Array.asList(), List.of() or
> in Stream so either there is no such problem, which means that nobody
> wants a supertype between Deque and List, or we have a lot of codes
> that now fail to compile. In both case, it means we should not add
> RC.
> 
> > 
> > > - 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.
> > 
> > I think I'm missing something here. I just did an experiment to
> > convince myself
> > that the set of interfaces a class implements isn't hard-wired in
> > its class
> > file. In other words, that any custom List/Deque/SortedSet/...
> > implementation
> > would be seen as implementing RC/RS without having to recompile it
> > (that, or my
> > experiment was flawed somehow, of course). So am I correct that
> > your concerns
> > are only about custom collections that implement Collection
> > directly? If so, if
> > I'd introduce a public method in my library today, I'd have to
> > declare the
> > parameter as Collection in order for custom collections to be able
> > to use it.
> > So in the future, I could either introduce an overloaded the method
> > (one with a
> > Collection parameter & one with a ReversibleCollection), or I could
> > expect
> > clients to do `List::copyOf`... right? I'd appreciate it if you
> > could elaborate
> > on this point, because I don't understand the concern yet.
> 
> Let say Java 18 adds RC, so in my new shiny library, i use it by
> introducing a method
>   void foo(ReversibleCollection c) { ...
> 
> What it means for people that want to use the method foo ? if they
> are using the JDK collection, it all clear, now if they are using an
> ordered Collection from Apache, Guava,  Eclipse, etc, that Collection
> has not yet being retrofitted to implement ReversibleCollection so it
> means that as a user he will not use my shiny method foo until the
> library that provides the implementation is updated.
> 
> As you said, as a user i can also use new ArrayList<>() or
> List.copyOf(), but in that case, why not declaring foo as taking a
> List in the first place, it will make the adoption of my library
> faster.
> So it's a kind of vicious circle, until enough libraries that
> provides a collection API has been updated, as a library developer, i
> will not use ReversibleCollection.
> And given that no library are using ReversibleCollection, collection
> library developers have no incentive to update their library (that
> forces all their users to update their JDK version).
> 
> When you have this kind of relation, it takes a loooong time until
> you reach the point where people will start to using RC.
> 
> > 
> > > - 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.
> > 
> > I believe this is subjective, but to me the new interfaces are like
> > "the missing
> > piece" of the Collections API puzzle. I believe their value is also
> > in the fact
> > that they reconcile List/Deque and LinkedHashSet/SortedSet and are
> > very useful
> > as parameter/return types in APIs.
> 
> Again, for you ReversibleCollection is the missing piece of the
> puzzle, for far more people it's ImmutableList, for me it's an
> interface which is a supertype of Collection that does not allow
> remove and clear because I very rarely use those methods and if there
> is no remove you can make the Iterator far faster. Everybody has its
> fantasy interface he wants to add on the collection API. But i hope
> that t next time we add one, it will be more useful and with a better
> compatibility story than ReversibleCollection, ReversibleSet and
> ReversibleMap. 
> 
> > 
> > Kind regards, Anthony
> 
> regards,
> Rémi
> 
> > 
> > [1]
> > https://gist.github.com/anthonyvdotbe/e2e313693f032e4336e5385334a476db