Interfejs List -> metoda Add -> Barbara

Ostatnio ktoś zapytał na listach dyskusyjnych OpenJDK o dodanie ImmutableList do hierarchii kolekcji Javowych:
https://github.com/openjdk/jdk/pull/1026#issuecomment-722531896

At the risk of a can of worms, or at least of raising something that has
long since been discussed and rejected...

This discussion of unmodifiable lists brings me back to the thought that
there would be good client-side reasons for inserting an UnmodifiableList
interface as a parent of LIst, not least because all our unmodifiable
variants from the Collections.unmodifiableList proxy onward fail the Liskov
substitution test for actually "being contract-fulfilling Lists".

Is this something that has been considered and rejected? (If so, is it easy
to point me at the discussion, as I expect I'd find it fascinating). Is it
worth considering, might it have some merit, or merely horrible
unforeseen-by-me consequences to the implementation?

Odpowiedzi są takie:

Why does List.of() in Java not return a typed immutable list?
https://stackoverflow.com/a/57926310

It's not that nobody cares; it's that this is a problem of considerable subtlety.

The original reason there isn't a family of "immutable" collection interfaces is because of a concern about interface proliferation. There could potentially be interfaces not only for immutability, but synchronized and runtime type-checked collections, and also collections that can have elements set but not added or removed (e.g., Arrays.asList) or collections from which elements can be removed but not added (e.g., Map.keySet).

But it could also be argued that immutability is so important that it should be special-cased, and that there be support in the type hierarchy for it even if there isn't support for all those other characteristics. Fair enough.

The initial suggestion is to have an ImmutableList interface extend List, as

ImmutableList <: List <: Collection

(Where <: means "is a subtype of".)

This can certainly be done, but then ImmutableList would inherit all of the methods from List, including all the mutator methods. Something would have to be done with them; a sub-interface can't "disinherit" methods from a super-interface. The best that could be done is to specify that these methods throw an exception, provide default implementations that do so, and perhaps mark the methods as deprecated so that programmers get a warning at compile time.

This works, but it doesn't help much. An implementation of such an interface cannot be guaranteed to be immutable at all. A malicious or buggy implementation could override the mutator methods, or it could simply add more methods that mutate the state. Any programs that used ImmutableList couldn't make any assumptions that the list was, in fact, immutable.

A variation on this is to make ImmutableList be a class instead of an interface, to define its mutator methods to throw exceptions, to make them final, and to provide no public constructors, in order to restrict implementations. In fact, this is exactly what Guava's ImmutableList has done. If you trust the Guava developers (I think they're pretty reputable) then if you have a Guava ImmutableList instance, you're assured that it is in fact immutable. For example, you could store it in a field with the knowledge that it won't change out from under you unexpectedly. But this also means that you can't add another ImmutableList implementation, at least not without modifying Guava.

A problem that isn't solved by this approach is the "scrubbing" of immutability by upcasting. A lot of existing APIs define methods with parameters of type Collection or Iterable. If you were to pass an ImmutableList to such a method, it would lose the type information indicating that the list is immutable. To benefit from this, you'd have to add immutable-flavored overloads everywhere. Or, you could add instanceof checks everywhere. Both are pretty messy.

(Note that the JDK's List.copyOf sidesteps this problem. Even though there are no immutable types, it checks the implementation before making a copy, and avoids making copies unnecessarily. Thus, callers can use List.copyOf to make defensive copies with impunity.)

As an alternative, one might argue that we don't want ImmutableList to be a sub-interface of List, we want it to be a super-interface:

List <: ImmutableList

This way, instead of ImmutableList having to specify that all those mutator methods throw exceptions, they wouldn't be present in the interface at all. This is nice, except that this model is completely wrong. Since ArrayList is a List, that means ArrayList is also an ImmutableList, which is clearly nonsensical. The problem is that "immutable" implies a restriction on subtypes, which can't be done in an inheritance hierarchy. Instead, it would need to be renamed to allow capabilities to be added as one goes down the hierarchy, for example,

List <: ReadableList

which is more accurate. However, ReadableList is altogether a different thing from an ImmutableList.

Finally, there are a bunch of semantic issues that we haven't considered. One concerns immutability vs. unmodifiability. Java has APIs that support unmodifiability, for example:

List<String> alist = new ArrayList<>(...);
??? ulist = Collections.unmodifiableList(alist);
What should the type of ulist be? It's not immutable, since it will change if somebody changes the backing list alist. Now consider:

???<String[]> arlist = List.of(new String[] { ... }, new String[] { ... });
What should the type be? It's certainly not immutable, as it contains arrays, and arrays are always mutable. Thus it's not at all clear that it would be reasonable to say that List.of returns something immutable.

Java Collections API Design FAQ
https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/doc-files/coll-designfaq.html#a1

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.

Scala ma hierarchię, w której zależności są poprawne, jednak powoduje to skomplikowaną hierarchię (coś za coś). Mamy np:

• typ scala.collection.Iterable
• typ scala.collection.immutable.Iterable dziedziczący po scala.collection.Iterable
• typ scala.collection.mutable.Iterable dziedziczący po scala.collection.Iterable
• typ scala.collection.Seq (czyli readable sequence) dziedziczący po scala.collection.Iterable
• typ scala.collection.immutable.Seq dziedziczący po scala.collection.Seq
• typ scala.collection.mutable.Seq dziedziczący po scala.collection.Seq
• typ scala.collection.Set (czyli readable set) dziedziczący po scala.collection.Iterable
• typ scala.collection.immutable.Set dziedziczący po scala.collection.Set
• typ scala.collectiom.mutable.Set dziedziczący po scala.collection.Set
• itp itd

Mimo rozbudowanej hierarchii kolekcji w Scali i tak mnóstwo niezmienników nie jest zakodowanych w typach, więc jak ktoś chce się czepiać to na pewno szybko znajdzie powód żeby się czepiać i niby argumentować dalsze rozbudowywanie hierarchii typów.

Jednym z "rozwiązań" jest sklejanie typów, w Javie da się to zrobić dla metod argumentów generyków, ale nie pomoże to przy podawaniu typu zmiennej lokalnej, bo nie da się podać kilku interfejsów. Można dziedziczyć, ale wtedy wracamy do punktu wyjścia.

Jeżeli byłoby to możliwe i miało jakąś sensowną składnię do aliasów, to wtedy zaczynamy rozwiązywać właściwy problem. Programistę interesuje, jakie operacje udostępnia mu dana kolekcja, a nie, gdzie w hierarchii dziedziczenia się ona znajduje. Dlatego robimy interfejsy Resizable, Removable, Addable i jakie nam tam trzeba, nie łączymy ich żadną hierarchią podtypu/nadtypu, a tylko w argumencie funkcji podajemy, że przekazany typ ma mieć to i tamto.

Afish napisał(a):

Jednym z "rozwiązań" jest sklejanie typów
(...)
Dlatego robimy interfejsy Resizable, Removable, Addable i jakie nam tam trzeba, nie łączymy ich żadną hierarchią podtypu/nadtypu, a tylko w argumencie funkcji podajemy, że przekazany typ ma mieć to i tamto.

W ten prosty sposób dochodzimy do wniosku że polimorfizm z języków obiektowych jak Java/C# jest niedoskonały i lepszym rozwiązaniem jest polimorfizm ad-hoc jak TypeClassy w Haskellu lub Traity w Rust

KamilAdam napisał(a):

W ten prosty sposób dochodzimy do wniosku że polimorfizm z języków obiektowych jak Java/C# jest niedoskonały i lepszym rozwiązaniem jest polimorfizm ad-hoc jak TypeClassy w Haskellu lub Traity w Rust

Ja bym raczej powiedział, że próbujemy używać dziedziczenia tam, gdzie ono nie pasuje. Można nawet dojść do wniosku, że jeżeli zrobimy interfejs bazowy jakichś kolekcji (powiedzmy z metodą Contains, ale bez Add czy Remove czy czegoś innego do modyfikacji), to już potem nie możemy zrobić podinterfejsu z metodą Add, bo psujemy zasadę historii. Nie jestem przekonany, że takie rygorystyczne trzymanie się zasady Liskov jest pożądane, ale na pewno trzeba umieć odpowiedzieć na to pytanie (i odpowiednio uargumentować) przy tworzeniu tych wszystkich interfejsów do kolekcji, jeżeli chcemy to zrobić "dobrze".

Afish napisał(a):

Jednym z "rozwiązań" jest sklejanie typów, w Javie da się to zrobić dla metod argumentów generyków, ale nie pomoże to przy podawaniu typu zmiennej lokalnej, bo nie da się podać kilku interfejsów. Można dziedziczyć, ale wtedy wracamy do punktu wyjścia.

Jeżeli byłoby to możliwe i miało jakąś sensowną składnię do aliasów, to wtedy zaczynamy rozwiązywać właściwy problem.

Nadchodząca Scala 3 to ma: http://dotty.epfl.ch/docs/reference/new-types/intersection-types.html

trait Resettable {
  def reset(): Unit
}
trait Growable[T] {
  def add(t: T): Unit
}
def f(x: Resettable & Growable[String]) = {
  x.reset()
  x.add("first")
}

Takie coś wymazywane jest chyba do pierwszego typu z przecięcia, a więc w bajtkodzie zostaje:

def f(x: Resettable) = {
  x.reset()
  x.asInstanceOf[Growable[String]].add("first")
}

Aliasy też można zrobić, a'la:

type ResettableAndGrowable[T] = Resettable & Growable[T]

Co do Haskella i Rusta to nie wiem (albo nie pamiętam) jak tam aliasy typów działają.

Przykład w Dotty 0.27 (czyli prototypie nadchodzącej Scali 3):

trait Resettable {
  def reset(): Unit
}
trait Growable[T] {
  def add(t: T): Unit
}

type ResettableAndGrowable[T] = Resettable & Growable[T]

def f(x: ResettableAndGrowable[String]) = {
  x.reset()
  x.add("first")
}

@main def main = {
  class MyResettableAndGrowable extends Growable[String] with Resettable {
    override def add(t: String): Unit = println(s"added $t")
    override def reset(): Unit = println("reset")
  }
  val x: ResettableAndGrowable[String] = new MyResettableAndGrowable
  f(x)
}

https://scastie.scala-lang.org/XUeVeCR3Soq9NjyHSwB6Ng

No i @Wibowit podał ładny przykład. W javie też da się zrobić takie Resettable & Growable[T] jako parametr metody, ale do zmiennej lokalnej już nie da się przypisać bez posiadania konkretnej klasy, a tu wygląda okej. I teraz jak mamy takie podejście, to biblioteka standardowa może iść w stronę tuzina interfejsów skupiających się na zachowaniu, bez mieszania ich w jakąś relację nadtypu i podtypu, do tego dorzucić trochę aliasów dla najpopularniejszych kombinacji i w teorii gotowe.

Oczywiście pozostaje jeszcze trochę kwestii do ogarnięcia. Czy type ResettableAndGrowable[T] = Resettable & Growable[T] i type ResettableAndGrowable2[T] = Resettable & Growable[T] są tym samym — jeżeli tak, to efektywnie mamy "dziedziczenie" na poziomie strukturalnym, ale wtedy tracimy trochę bezpieczeństwa typów (bo zrobimy type Pesel = String z ewentualną opcją rozbudowy w przyszłości przez zastąpienie aliasu pełnowymiarową klasą, ale wtedy ktoś może przekazać dowolny literał znakowy jako pesel (w sensie literał bez jawnego konstruowania typu pesel, a nie, że o dowolnej treści, to drugie póki co ignoruję)). No i oczywiście problem diamentu czy jakieś wyzwania techniczne (bo erasure itp).

Afish napisał(a):

Oczywiście pozostaje jeszcze trochę kwestii do ogarnięcia. Czy type ResettableAndGrowable[T] = Resettable & Growable[T] i type ResettableAndGrowable2[T] = Resettable & Growable[T] są tym samym — jeżeli tak, to efektywnie mamy "dziedziczenie" na poziomie strukturalnym, ale wtedy tracimy trochę bezpieczeństwa typów (bo zrobimy type Pesel = String z ewentualną opcją rozbudowy w przyszłości przez zastąpienie aliasu pełnowymiarową klasą, ale wtedy ktoś może przekazać dowolny literał znakowy jako pesel (w sensie literał bez jawnego konstruowania typu pesel, a nie, że o dowolnej treści, to drugie póki co ignoruję)). No i oczywiście problem diamentu czy jakieś wyzwania techniczne (bo erasure itp).

Zwykłe aliasy są tym samym, zarówno w czasie kompilacji jak i czasie wykonania. Oprócz tego w Scali 3 będą Opaque Type Aliases http://dotty.epfl.ch/docs/reference/other-new-features/opaques.html czyli aliasy, które nie są tym samym (co docelowy typ) w czasie kompilacji, ale dalej są tym samym w czasie wykonania. Oba rodzaje aliasów są wymazywane do docelowego typu w czasie kompilacji (więc mają zerowy koszt wydajnościowy), więc refleksja i pattern matching się sypią (analogicznie do generyków - zresztą pattern matching stosuje się zwykle do wypakowywania danych, a nie ich rzutowania). Jednak opaque type aliases przydają się i tak do sterowania ograniczeniami typów, metodami rozszerzającymi, wszelkiego rodzaju implicitami, itp