Dlaczego Java 8 nie zawiera niezmiennych kolekcji?

Zespół Java wykonał mnóstwo świetnej pracy, usuwając bariery w programowaniu funkcjonalnym w Javie 8. W szczególności zmiany w kolekcjach java.util wykonują świetną robotę, łącząc przekształcenia w bardzo szybko przesyłane strumieniowo operacje. Biorąc pod uwagę, jak dobrą robotę wykonali, dodając pierwszorzędne funkcje i metody funkcjonalne do kolekcji, dlaczego całkowicie nie udało się zapewnić niezmiennych kolekcji, a nawet niezmiennych interfejsów kolekcjonowania?

Bez zmiany żadnego istniejącego kodu zespół Java może w dowolnym momencie dodać niezmienne interfejsy, które są takie same jak zmienne, pomniejszone o metody „set” i sprawić, by istniejące interfejsy rozszerzyły się z nich, w następujący sposób:

                  ImmutableIterable
     ____________/       |
    /                    |
Iterable        ImmutableCollection
   |    _______/    /          \   \___________
   |   /           /            \              \
 Collection  ImmutableList  ImmutableSet  ImmutableMap  ...
    \  \  \_________|______________|__________   |
     \  \___________|____________  |          \  |
      \___________  |            \ |           \ |
                  List            Set           Map ...

Jasne, operacje takie jak List.add () i Map.put () obecnie zwracają wartość logiczną lub poprzednią wartość dla danego klucza, aby wskazać, czy operacja się powiodła, czy nie. Niezmienne kolekcje musiałyby traktować takie metody jak fabryki i zwracać nową kolekcję zawierającą dodany element - co jest niezgodne z obecną sygnaturą. Ale można to obejść, używając innej nazwy metody, takiej jak ImmutableList.append () lub .addAt () i ImmutableMap.putEntry (). Wynikająca z tego gadatliwość byłaby bardziej niż przeważona korzyściami pracy z niezmiennymi kolekcjami, a system typów zapobiegałby błędom wywołania niewłaściwej metody. Z czasem stare metody mogły być przestarzałe.

Zwycięstwa niezmiennych kolekcji:

• Prostota - rozumowanie na temat kodu jest prostsze, gdy podstawowe dane nie ulegają zmianie.
• Dokumentacja - jeśli metoda przyjmuje niezmienny interfejs kolekcji, wiesz, że nie będzie modyfikować tej kolekcji. Jeśli metoda zwraca niezmienną kolekcję, wiesz, że nie możesz jej zmodyfikować.
• Współbieżność - niezmienne kolekcje można bezpiecznie współdzielić między wątkami.

Jako osoba, która próbowała języków, które zakładają niezmienność, bardzo trudno jest wrócić na Dziki Zachód szalonej mutacji. Kolekcje Clojure (abstrakcja sekwencji) mają już wszystko, co zapewniają kolekcje Java 8, oraz niezmienność (choć może zużywa dodatkową pamięć i czas z powodu zsynchronizowanych list połączonych zamiast strumieni). Scala ma zarówno kolekcje zmienne, jak i niezmienne z pełnym zestawem operacji i chociaż operacje te są chętne, wywołanie .iterator daje leniwy widok (i istnieją inne sposoby leniwej ich oceny). Nie rozumiem, jak Java może nadal konkurować bez niezmiennych kolekcji.

Czy ktoś może wskazać mi historię lub dyskusję na ten temat? Z pewnością jest to gdzieś publiczne.

Ponieważ niezmienne kolekcje absolutnie wymagają udostępniania, aby były użyteczne. W przeciwnym razie każda operacja upuszcza gdzieś całą inną listę na stos. Języki całkowicie niezmienne, takie jak Haskell, generują zdumiewające ilości śmieci bez agresywnych optymalizacji i udostępniania. Posiadanie kolekcji, która może być użyta tylko z <50 elementami, nie jest warte umieszczenia w standardowej bibliotece.

Co więcej, niezmienne kolekcje często mają zasadniczo różne implementacje niż ich zmienne odpowiedniki. Rozważmy na przykład ArrayList, że niezmienna niezmienna ArrayListwcale nie byłaby tablicą! Powinien zostać zaimplementowany ze zrównoważonym drzewem o dużym współczynniku rozgałęzienia, Clojure używa 32 IIRC. Sprawienie, by zbiory modyfikowalne były „niezmienne” przez dodanie aktualizacji funkcjonalnej, jest tak samo błędem wydajności, jak przeciek pamięci.

Ponadto udostępnianie nie jest wykonalne w Javie. Java zapewnia zbyt wiele nieograniczonych ograniczeń zmienności i równości referencji, aby udostępnianie było „tylko optymalizacją”. Prawdopodobnie trochę by cię denerwowało, gdybyś mógł zmodyfikować element na liście i zdać sobie sprawę, że właśnie zmodyfikowałeś element w pozostałych 20 wersjach tej listy, którą posiadałeś.

Wyklucza to również ogromne klasy bardzo istotnych optymalizacji dla efektywnej niezmienności, współdzielenia, fuzji strumieniowej, jak to nazywacie, zmienność psuje ją. (To byłby dobry slogan dla ewangelistów FP)

Zmienna kolekcja nie jest podtypem niezmiennej kolekcji. Zamiast tego zbiory zmienne i niezmienne są rodzeństwem potomków kolekcji czytelnych. Niestety, pojęcia „czytelny”, „tylko do odczytu” i „niezmienny” wydają się rozmywać, mimo że oznaczają trzy różne rzeczy.

• Czytelna podstawowa klasa kolekcji lub typ interfejsu obiecuje, że można czytać elementy, i nie zapewnia żadnych bezpośrednich środków modyfikowania kolekcji, ale nie gwarantuje, że kod odbierający odwołanie nie może rzutować ani manipulować nim w sposób umożliwiający modyfikację.

• Interfejs kolekcji tylko do odczytu nie zawiera żadnych nowych elementów, ale powinien zostać zaimplementowany tylko przez klasę, która obiecuje, że nie ma sposobu na manipulowanie referencją w taki sposób, aby mutować kolekcję lub otrzymać referencję do czegoś to może to zrobić. Nie obiecuje jednak, że kolekcja nie będzie modyfikowana przez coś innego, co ma odniesienie do elementów wewnętrznych. Należy pamiętać, że interfejs kolekcji tylko do odczytu może nie być w stanie zapobiec implementacji przez klasy zmienne, ale może określić, że dowolną implementację lub klasę pochodną z implementacji, która umożliwia mutację, należy uznać za „nielegalną” implementację lub pochodną implementacji .

• Niezmienna kolekcja to taka, która zawsze będzie przechowywać te same dane, o ile istnieje jakiekolwiek odniesienie do niej. Każda implementacja niezmiennego interfejsu, który nie zawsze zwraca te same dane w odpowiedzi na konkretne żądanie, jest zepsuta.

Jest to czasami warto mieć silnie powiązane zmienne i niezmienne typy kolekcji, która zarówno wdrożenia lub wynikają z tego samego „czytelnej” typu i mieć typ czytelny zawierać AsImmutable, AsMutableoraz AsNewMutablemetod. Taki projekt pozwala na wywołanie kodu, który chce utrwalić dane w kolekcji AsImmutable; metoda ta utworzy kopię obronną, jeśli kolekcja jest zmienna, ale pomiń kopię, jeśli jest już niezmienna.

Framework kolekcji Java zapewnia możliwość tworzenia kolekcji tylko do odczytu za pomocą sześciu metod statycznych w klasie java.util.Collections :

• unmodifiableCollection (kolekcja c)
• unmodifiableList (lista list)
• unmodifiableMap (mapa m)
• unmodifiableSet (Set s)
• unmodifiableSortedMap (SortedMap m)
• unmodifiableSortedSet (SortedSet s)

Jak ktoś zauważył w komentarzach do pierwotnego pytania, zwrócone kolekcje mogą nie zostać uznane za niezmienne, ponieważ chociaż kolekcje nie mogą być modyfikowane (żadnych członków nie można dodawać ani usuwać z takiej kolekcji), rzeczywiste obiekty, do których odwołuje się kolekcja można zmodyfikować, jeśli pozwala na to ich typ obiektu.

Problem ten pozostałby jednak bez względu na to, czy kod zwraca pojedynczy obiekt, czy niezmodyfikowaną kolekcję obiektów. Jeśli typ pozwala zmutować jego obiekty, wówczas decyzja została podjęta w projekcie typu i nie widzę, jak zmiana w JCF mogłaby to zmienić. Jeśli niezmienność jest ważna, członkowie kolekcji powinni być typu niezmiennego.

To jest bardzo dobre pytanie. Podoba mi się myśl, że z całego kodu napisanego w Javie i działającego na milionach komputerów na całym świecie, każdego dnia, przez całą dobę, należy zmarnować około połowę całkowitych cykli zegara, robiąc tylko bezpieczne kopie kolekcji, które są zwracane przez funkcje. (I zbieranie śmieci te kolekcje milisekund po ich utworzeniu).

Odsetek programistów Java jest świadomy istnienia unmodifiableCollection()rodziny metod Collectionsklasy, ale nawet wśród nich wielu po prostu się tym nie przejmuje.

I nie mogę ich winić: interfejs, który udaje, że jest do odczytu i zapisu, ale rzuca, UnsupportedOperationExceptionjeśli popełnisz błąd przywołania którejkolwiek z jego metod „zapisu”, jest czymś złym!

Teraz interfejs taki, w Collectionktórym brakuje add(), remove()a clear()metody nie byłyby interfejsem „ImmutableCollection”; byłby to interfejs „UnmodifiableCollection”. W rzeczywistości nigdy nie może istnieć interfejs „ImmutableCollection”, ponieważ niezmienność jest naturą implementacji, a nie cechą interfejsu. Wiem, to nie jest bardzo jasne; pozwól mi wyjaśnić.

Załóżmy, że ktoś przekazuje ci taki interfejs kolekcji tylko do odczytu; czy bezpiecznie jest przekazać go do innego wątku? Gdybyście na pewno wiedzieli, że jest to kolekcja niezmienna, odpowiedź brzmiałaby „tak”; niestety, ponieważ jest to interfejs, nie wiesz, w jaki sposób jest on implementowany, więc odpowiedź musi brzmieć „ nie” : dla wszystkich wiesz, może to być niezmodyfikowany (dla ciebie) widok kolekcji, która w rzeczywistości jest modyfikowalna, (jak to, co dostajesz Collections.unmodifiableCollection()), więc próba odczytania z niego, gdy inny wątek jest modyfikowany, spowoduje odczyt uszkodzonych danych.

Tak więc, co zasadniczo opisałeś, to zestaw nie „niezmiennych”, ale „niemodyfikowalnych” interfejsów kolekcji. Ważne jest, aby zrozumieć, że „niemodyfikowalny” oznacza po prostu, że ktokolwiek, kto ma odniesienie do takiego interfejsu, nie może modyfikować podstawowej kolekcji, a im zapobiega się po prostu dlatego, że interfejs nie ma żadnych metod modyfikacji, a nie dlatego, że podstawowa kolekcja jest koniecznie niezmienna. Podstawowa kolekcja może równie dobrze być zmienna; nie macie o tym żadnej wiedzy i kontroli.

Aby mieć niezmienne kolekcje, musiałyby to być klasy , a nie interfejsy!

Te niezmienne klasy kolekcjonerskie musiałyby być ostateczne, więc gdy otrzymasz odniesienie do takiej kolekcji, wiesz na pewno, że będzie się ona zachowywać jak niezmienna kolekcja bez względu na to, co Ty, lub ktokolwiek, kto ma do niej odniesienie, mógłbyś zrób to.

Tak więc, aby mieć pełny zestaw kolekcji w Javie (lub innym deklaratywnym języku imperatywnym), potrzebowalibyśmy:

1. Zestaw niemodyfikowalnych interfejsów kolekcji .

2. Zestaw modyfikowalnych zbiórki interfejsów , rozszerzającego żadnych modyfikacji z nich.

3. Zestaw modyfikowalnych zbiórki klas realizujących zmienny interfejsy, a co za tym idzie również modyfikowalnych interfejsów.

4. Zbiór niezmiennych klas kolekcji , implementujących niemodyfikowalne interfejsy, ale przeważnie przekazywany jako klasy, aby zagwarantować niezmienność.

Wszystkie powyższe zaimplementowałem dla zabawy i używam ich w projektach, które działają jak urok.

Powodem, dla którego nie są częścią środowiska wykonawczego java, jest prawdopodobnie dlatego, że sądzono, że byłoby to zbyt duże / zbyt złożone / zbyt trudne do zrozumienia.

Osobiście uważam, że to, co opisałem powyżej, nie wystarczy; jeszcze jedna rzecz, która wydaje się potrzebna, to zestaw zmiennych interfejsów i klas dla niezmienności strukturalnej . (Które można po prostu nazwać „Sztywnym”, ponieważ prefiks „StructurallyImmutable” jest zbyt cholernie długi).

Niezmienne kolekcje mogą być głęboko rekurencyjne w porównaniu do siebie nawzajem i nie mogą być nieracjonalnie nieefektywne, jeśli równość obiektów jest realizowana przez secureHash. Nazywa się to lasem merkle. Może być dla każdej kolekcji lub w jej części, jak (samoczynnie równoważące się binarne) drzewo AVL dla posortowanej mapy.

O ile wszystkie obiekty java w tych kolekcjach nie mają unikatowego identyfikatora lub łańcucha bitów do haszowania, kolekcja nie ma nic do haszowania, by móc się jednoznacznie nazwać.

Przykład: Na moim laptopie 4x1.6 GHz mogę uruchomić 200 k sha256s na sekundę najmniejszego rozmiaru, który mieści się w 1 cyklu mieszania (do 55 bajtów), w porównaniu do 500 K operacji HashMap lub 3 mln operacji w tablicy mieszającej długich. Nowe zbiory o wartości 200 K / log (collectionSize) na sekundę są wystarczająco szybkie dla niektórych rzeczy, w których ważna jest integralność danych i anonimowa globalna skalowalność.

Występ. Kolekcje z natury mogą być bardzo duże. Kopiowanie 1000 elementów do nowej struktury z 1001 elementami zamiast wstawiania jednego elementu jest po prostu okropne.

Konkurencja. Jeśli masz uruchomionych kilka wątków, mogą chcieć pobrać bieżącą wersję kolekcji, a nie wersję przekazaną 12 godzin temu, gdy wątek się rozpoczął.

Przechowywanie. Dzięki niezmiennym obiektom w wielowątkowym środowisku możesz uzyskać dziesiątki kopii tego samego obiektu w różnych punktach jego cyklu życia. Nie ma znaczenia dla obiektu kalendarza lub daty, ale gdy będzie to zbiór 10 000 widżetów, zabije cię.