[External] : Re: ReversibleCollection proposal

[dfranken.jdk at gmail.com]

Dear mr. Forax,

I understand your point of view. You don't like to have separate
standalone interfaces for things that seem to belong in a hierarchy, is
that correct? Now that I thought about it, I agree.

So if a reversable/ordered set is a specialized form of a reversable
collection where reversable collection is a specialized form of a
collection, it makes sense to add it into the hierarchy.

Are you proposing to just add methods to the root Collection interface,
because it already has methods which may or may not be implemented or
throw Exceptions by its implementations? Or were you just pointing out
that's just how it works now? That the capabilities a certain
collection has, like unmodifiability or not allowing null elements, are
not exposed through a proper interface but through what it returns for
certain methods?

But we could also view "having (possibly duplicate) items in a
sequence" as a capability and that is defined by an actual interface,
List.

I do fear that if we add methods to the Collection interface, users
might not expect them to throw exceptions. E.g. if we add getFirst(),
users may just expect it to return the element that iterator().next()
or .stream().findFirst().orElseThrow() would return instead of an
UnsupportedOperationException. And while HashSet does not have a
defined order, it would in practice always return the same element.

So while I accept that some hidden capabilities are surfaced only
through return values of certain methods, I think an interface is still
a better choice here. However, if we go that route, I also agree on the
fact that we might need to explore defining proper interfaces for the
other capabilities at some point.

Kind regards,

Dave

On Mon, 2021-05-10 at 12:22 +0200, forax at univ-mlv.fr wrote:
> ----- Mail original -----
> > De: "dfranken jdk" <dfranken.jdk at gmail.com>
> > À: "Remi Forax" <forax at univ-mlv.fr>, "Stuart Marks"
> > <stuart.marks at oracle.com>
> > Cc: "core-libs-dev" <core-libs-dev at openjdk.java.net>
> > Envoyé: Dimanche 9 Mai 2021 12:13:58
> > Objet: Re: [External] : Re: ReversibleCollection proposal
> 
> > When I thought about Collection's role in the hierarchy, it seemed
> > to
> > me that 'Collection' is an interface for describing how elements
> > are
> > stored in a cardboard box (we can and and remove them) and that we
> > might need a different, yet related, interface to describe how to
> > retrieve the items from the box. This way we are not tied to the
> > Collection hierarchy and we could have one Set implementation which
> > is
> > ordered and another Set implementation which is not and they would
> > both
> > still implement Collection, but only one would implement the
> > interface.
> 
> So you want to model ReversibleSet as Set + Reversible,
> Reversible being an interface with a small number of method specific
> to the fact that the implementation is reversible. 
> 
> This does not work well for two reasons,
> - there is no syntax to represent the union of types in Java,
>    Set & Reversible set = ...
>   is not a valid syntax. You can use a type variable with several
> bounds instead but it does work nicely with the rest of the language
> (overidding, overloading, etc).
> 
> - having public methods that takes an interface with few methods is a
> common design error.
>   Let suppose you have a method foo that only prints the elements of
> a collection, in that case you may want to type the first parameter
> as Iterable or Collection.
>   But requirements change an now you want to prints the elements
> sorted, oops, you have to change the signature of the public method
> which may be something not possible
>   depending how many "clients" this method has.
>   Providing interfaces with a small number of access methods will
> lead to this kind of issue. 
> 
> > 
> > Imagine an interface like 'java.lang.OrderedEnumerable` if you will
> > with methods such as 'first(), last(), etc', then each
> > implementation
> > would be free to choose to implement the interface or not. I also
> > thought about 'OrderedIterable', but there would be too much
> > confusion
> > with 'Iterable', but I think these are related too. Retrieving
> > items is
> > an iteration problem, not a storage problem.
> 
> The problem is that is you multiply the number of interfaces to
> access the elements, you add the dilemma of choice in the mix.
> The first iteration of the Scala Collection were like this, too many
> interfaces, at least for my taste. 
> 
> > 
> > While I would love to see the Collection hierarchy redesigned to
> > also
> > allow for ImmutableCollection which for instance would not have an
> > `add(T e)` method, I don't think we can simply do something like
> > that
> > without breaking too many things.
> 
> Dear Santa, i want an interface BuilderCollection that only allows
> add() but no remove()/clear(), because if you can not remove
> elements, then all the iterators can implement the snapshot at the
> beginning semantics,
> so no ConcurrentModificationException anymore. For me, being able to
> snapshot/freeze a collection is better than an ImmutableCollection,
> because it can be immutable when you want. 
> 
> Anyway, it's not gonna to happen, there is so many ways to slice an
> onion and each have pros and cons and providing all the possible
> interfaces is a good.way to make something simple complex.
> 
> > 
> > So in short, separating retrieval aspects from storage aspects with
> > a
> > different interface might be the way to go.
> > 
> > Kind regards,
> > 
> > Dave Franken
> > 
> 
> regards,
> Rémi
> 
> > On Wed, 2021-05-05 at 12:41 +0200, forax at univ-mlv.fr wrote:
> > > ----- 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 5 Mai 2021 02:00:03
> > > > Objet: Re: [External] : Re: ReversibleCollection proposal
> > > 
> > > > On 5/1/21 5:57 AM, forax at univ-mlv.fr wrote:
> > > > > I suppose the performance issue comes from the fact that
> > > > > traversing a
> > > > > LinkedHahSet is slow because it's a linked list ?
> > > > > 
> > > > > You can replace a LinkedHashSet by a List + Set, the List
> > > > > keeps
> > > > > the values in
> > > > > order, the Set avoids duplicates.
> > > > > 
> > > > > Using a Stream, it becomes
> > > > >    Stream.of(getItemsFromSomeplace(),
> > > > > getItemsFromAnotherPlace(),
> > > > >    getItemsFromSomeplaceElse())
> > > > >     .flatMap(List::stream)
> > > > >     .distinct()              // use a Set internally
> > > > >     .collect(toList());
> > > > 
> > > > The problem with any example is that simplifying assumptions
> > > > are
> > > > necessary for
> > > > showing the example, but those assumptions enable it to be
> > > > easily
> > > > picked apart.
> > > > Of
> > > > course, the example isn't just a particular example; it is a
> > > > *template* for a
> > > > whole
> > > > space of possible examples. Consider the possibility that the
> > > > items
> > > > processing
> > > > client needs to do some intermediate processing on the first
> > > > group
> > > > of items
> > > > before
> > > > adding the other groups. This might not be possible to do using
> > > > streams. Use
> > > > your
> > > > imagination.
> > > > 
> > > > > I think there are maybe some scenarios where
> > > > > ReversibleCollection
> > > > > can be useful,
> > > > > but they are rare, to the point where when there is a good
> > > > > scenario for it
> > > > > people will not recognize it because ReversibleCollection
> > > > > will
> > > > > not be part of
> > > > > their muscle memory.
> > > > 
> > > > 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.
> > > 
> > > > 
> > > > > There is a real value to add methods like
> > > > > descendingSet/descendingList()/getFirst/getLast on existing
> > > > > collections, but we
> > > > > don't need a new interface (or two) for that.
> > > > 
> > > > It depends on what you mean by "need". Sure, we could get away
> > > > without this;
> > > > after
> > > > all, we've survived the past twenty years without it, so we
> > > > could
> > > > probably
> > > > survive
> > > > the next twenty years as well.
> > > > 
> > > > It would indeed be useful to add various methods to List,
> > > > Deque,
> > > > SortedSet, and
> > > > LinkedHashSet to provide a full set of methods on all of them.
> > > > And
> > > > it would also
> > > > be
> > > > nice to have those methods be similar to one another. An
> > > > interface
> > > > helps with
> > > > that,
> > > > but I agree, that's not really the reason to have an interface
> > > > though.
> > > > 
> > > > The reversed-view concept could also be added individually to
> > > > the
> > > > different
> > > > places.
> > > > A reverse-ordered List is a List, a reverse-ordered Deque is a
> > > > Deque, a
> > > > reverse-ordered SortedSet is a SortedSet, and a reverse-ordered
> > > > LinkedHashSet is
> > > > a
> > > > ... ? And what is the type of the keySet of a LinkedHashMap,
> > > > that
> > > > enables one to
> > > > (say) get the last element?
> > > 
> > > see below
> > > 
> > > > 
> > > > After working with a system like this for a while, it begins to
> > > > emerge that
> > > > there is
> > > > an abstraction missing from the collections framework,
> > > > something
> > > > like an
> > > > "ordered
> > > > collection". People have been missing this for quite a long
> > > > time.
> > > > The most
> > > > recent
> > > > example (which this proposal builds on) is Tagir's proposal
> > > > from a
> > > > year ago. And
> > > > it's been asked about several times before that.
> > > > ReversibleCollection fills in
> > > > that
> > > > missing abstraction.
> > > 
> > > 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.
> > > 
> > > > 
> > > > s'marks
> > > 
> > > Rémi