¿Por qué Java 8 no incluye colecciones inmutables?

130

El equipo de Java ha realizado un gran trabajo eliminando barreras para la programación funcional en Java 8. En particular, los cambios en las colecciones java.util hacen un gran trabajo encadenando transformaciones en operaciones de transmisión muy rápidas. Teniendo en cuenta lo bien que han hecho al agregar funciones de primera clase y métodos funcionales en colecciones, ¿por qué no han podido proporcionar colecciones inmutables o incluso interfaces de colección inmutables?

Sin cambiar ningún código existente, el equipo de Java podría en cualquier momento agregar interfaces inmutables que sean las mismas que las mutables, menos los métodos "establecidos" y hacer que las interfaces existentes se extiendan desde ellos, de esta manera:

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

Claro, operaciones como List.add () y Map.put () actualmente devuelven un valor booleano o anterior para la clave dada para indicar si la operación tuvo éxito o no. Las colecciones inmutables tendrían que tratar tales métodos como fábricas y devolver una nueva colección que contenga el elemento agregado, lo cual es incompatible con la firma actual. Pero eso podría solucionarse utilizando un nombre de método diferente como ImmutableList.append () o .addAt () e ImmutableMap.putEntry (). La verbosidad resultante sería más que compensada por los beneficios de trabajar con colecciones inmutables, y el sistema de tipos evitaría errores al llamar al método incorrecto. Con el tiempo, los viejos métodos podrían quedar en desuso.

Victorias de colecciones inmutables:

  • Simplicidad: el razonamiento sobre el código es más simple cuando los datos subyacentes no cambian.
  • Documentación: si un método toma una interfaz de colección inmutable, sabe que no va a modificar esa colección. Si un método devuelve una colección inmutable, sabe que no puede modificarla.
  • Simultaneidad: las colecciones inmutables se pueden compartir de forma segura entre hilos.

Como alguien que ha probado idiomas que asumen la inmutabilidad, es muy difícil volver al Salvaje Oeste de la mutación desenfrenada. Las colecciones de Clojure (abstracción de secuencia) ya tienen todo lo que proporcionan las colecciones de Java 8, más la inmutabilidad (aunque tal vez usando memoria y tiempo adicionales debido a listas enlazadas sincronizadas en lugar de secuencias). Scala tiene colecciones mutables e inmutables con un conjunto completo de operaciones, y aunque esas operaciones están ansiosas, llamar a .iterator ofrece una visión perezosa (y hay otras formas de evaluarlas perezosamente). No veo cómo Java puede seguir compitiendo sin colecciones inmutables.

¿Alguien puede señalarme la historia o la discusión sobre esto? Seguramente es público en alguna parte.

java history immutability collections GlenPeterson
fuente
99
Relacionado con esto: Ayende blogueó recientemente sobre colecciones y colecciones inmutables en C #, con puntos de referencia. ayende.com/blog/tags/performance - tl; dr - la inmutabilidad es lenta .
Oded
20
con su jerarquía Te puedo dar un ImmutableList y luego cambiarla en usted cuando usted no lo espera, que puede romper un montón de cosas, como es que sólo tienen constcolecciones
trinquete monstruo
18
La inmutabilidad @Oded es lenta, pero también lo es el bloqueo. Así es mantener una historia. La simplicidad / corrección vale la pena la velocidad en muchas situaciones. Con pequeñas colecciones, la velocidad no es un problema. El análisis de Ayende se basa en la suposición de que no necesita historial, bloqueo o simplicidad y que está trabajando con un conjunto de datos de gran tamaño. A veces eso es cierto, pero no es algo que siempre es mejor. Hay compensaciones.
GlenPeterson
55
@GlenPeterson para eso están las copias defensivas Collections.unmodifiable*(). pero no los trates como inmutables cuando no lo son
monstruo de trinquete
13
Eh? Si su función toma un ImmutableListen ese diagrama, ¿las personas pueden pasar un mutable List? No, esa es una violación muy grave de LSP.
Telastyn

Respuestas:

113

Porque las colecciones inmutables absolutamente requieren compartir para ser utilizables. De lo contrario, cada operación suelta una lista completamente diferente en el montón en alguna parte. Los lenguajes que son completamente inmutables, como Haskell, generan cantidades asombrosas de basura sin optimizaciones agresivas y compartidos. Tener una colección que solo se puede usar con <50 elementos no vale la pena poner en la biblioteca estándar.

Además, las colecciones inmutables a menudo tienen implementaciones fundamentalmente diferentes que sus contrapartes mutables. Considere, por ejemplo ArrayList, ¡un inmutable eficiente ArrayListno sería una matriz en absoluto! Debe implementarse con un árbol equilibrado con un gran factor de ramificación, Clojure utiliza 32 IIRC. Hacer que las colecciones mutables sean "inmutables" simplemente agregando una actualización funcional es un error de rendimiento tanto como una pérdida de memoria.

Además, compartir no es viable en Java. Java proporciona demasiados ganchos sin restricciones a la mutabilidad y la igualdad de referencia para que compartir sea "solo una optimización". Probablemente te molestaría un poco si pudieras modificar un elemento en una lista, y darte cuenta de que acabas de modificar un elemento en las otras 20 versiones de esa lista que tenías.

Esto también descarta grandes clases de optimizaciones muy vitales para la inmutabilidad eficiente, el intercambio, la fusión de flujo, lo que sea, la mutabilidad lo rompe. (Eso sería un buen eslogan para los evangelistas de FP)

jozefg
fuente
21
Mi ejemplo hablaba de interfaces inmutables . Java podría proporcionar un conjunto completo de implementaciones mutables e inmutables de esas interfaces que harían las compensaciones necesarias. Depende del programador elegir mutable o inmutable según corresponda. Los programadores deben saber cuándo usar una lista vs.conjunto ahora. Por lo general, no necesita la versión mutable hasta que tenga un problema de rendimiento, y puede que solo sea necesario como generador. En cualquier caso, tener la interfaz inmutable sería una victoria por sí solo.
GlenPeterson
44
Leí su respuesta nuevamente y creo que está diciendo que Java tiene una suposición fundamental de mutabilidad (por ejemplo, Java Beans) y que las colecciones son solo la punta del iceberg y tallar esa punta no resolverá el problema subyacente. Un punto valido. ¡Podría aceptar esta respuesta y acelerar mi adopción de Scala! :-)
GlenPeterson
8
No estoy seguro de que las colecciones inmutables requieran la capacidad de compartir partes comunes para ser útiles. El tipo inmutable más común en Java, una colección inmutable de caracteres, se usa para permitir compartir, pero ya no lo hace. La clave que lo hace útil es la capacidad de copiar rápidamente datos de a Stringen a StringBuffer, manipularlos y luego copiar los datos en un nuevo inmutable String. Usar un patrón de este tipo con conjuntos y listas podría ser tan bueno como usar tipos inmutables diseñados para facilitar la producción de instancias ligeramente cambiadas, pero aún podría ser mejor ...
supercat
3
Es completamente posible hacer una colección inmutable en Java utilizando el uso compartido. Los elementos almacenados en la colección son referencias y sus referentes pueden estar mutados, ¿y qué? Tal comportamiento ya rompe las colecciones existentes, como HashMap y TreeSet, pero se implementan en Java. Y si varias colecciones contienen referencias al mismo objeto, se espera que la modificación del objeto provoque un cambio visible cuando se vea desde todas las colecciones.
Solomonoff's Secret
44
jozefg, es totalmente posible implementar colecciones inmutables eficientes en JVM con intercambio estructural. Scala y Clojure los tienen como parte de su biblioteca estándar, ambas implementaciones se basan en HAMT (Hash Array Mapped Trie) de Phil Bagwell. Su declaración con respecto a Clojure implementando estructuras de datos inmutables con árboles BALANCEADOS es completamente errónea.
sesm
78

Una colección mutable no es un subtipo de una colección inmutable. En cambio, las colecciones mutables e inmutables son descendientes hermanos de colecciones legibles. Desafortunadamente, los conceptos de "legible", "solo lectura" e "inmutable" parecen confundirse, aunque significan tres cosas diferentes.

  • Una clase base de colección legible o un tipo de interfaz promete que se pueden leer elementos, y no proporciona ningún medio directo para modificar la colección, pero no garantiza que el código que recibe la referencia no pueda emitirla o manipularla de manera que permita la modificación.

  • Una interfaz de colección de solo lectura no incluye ningún miembro nuevo, pero solo debe ser implementada por una clase que prometa que no hay forma de manipular una referencia a ella de manera que mute la colección ni reciba una referencia a algo eso podría hacerlo. Sin embargo, no promete que la colección no será modificada por otra cosa que tenga una referencia a las partes internas. Tenga en cuenta que una interfaz de colección de solo lectura puede no ser capaz de evitar la implementación por clases mutables, pero puede especificar que cualquier implementación, o clase derivada de una implementación, que permita la mutación se considerará una implementación "ilegítima" o derivada de una implementación .

  • Una colección inmutable es aquella que siempre tendrá los mismos datos mientras exista alguna referencia a ella. Cualquier implementación de una interfaz inmutable que no siempre devuelve los mismos datos en respuesta a una solicitud particular está interrumpida.

A veces es útil tener tipos fuertemente asociados-mutables e inmutables de recogida que tanto implementar o derivarse del mismo tipo "legible", y tener el tipo legible incluir AsImmutable, AsMutabley AsNewMutablemétodos. Tal diseño puede permitir que el código que desea persistir los datos en una colección llame AsImmutable; ese método hará una copia defensiva si la colección es mutable, pero omita la copia si ya es inmutable.

Super gato
fuente
1
Gran respuesta. Las colecciones inmutables pueden brindarle una garantía bastante sólida relacionada con la seguridad de los hilos y cómo puede razonar sobre ellas a medida que pasa el tiempo. Una colección legible / de solo lectura no. De hecho, para honrar el principio de sustitución de Liskov, solo lectura e inmutable probablemente debería ser un tipo base abstracto con un método final y miembros privados para garantizar que ninguna clase derivada pueda destruir la garantía otorgada por el tipo. O deben ser del tipo completamente concreto que envuelva una colección (solo lectura) o siempre tome una copia defensiva (inmutable). Así es como lo hace ImmutableList de guayaba.
Laurent Bourgault-Roy
1
@ LaurentBourgault-Roy: Hay ventajas tanto para los tipos inmutables sellados como para los heredables. Si uno no quiere permitir que una clase derivada ilegítima rompa sus invariantes, los tipos sellados pueden ofrecer protección contra eso, mientras que las clases heredables no ofrecen ninguno. Por otro lado, puede ser posible que el código que sabe algo sobre los datos que contiene los almacene mucho más compacto que un tipo que no sabe nada al respecto. Considere, por ejemplo, un tipo ReadableIndexedIntSequence que encapsula una secuencia de int, con métodos getLength()y getItemAt(int).
supercat
1
@ LaurentBourgault-Roy: dado un ReadableIndexedIntSequence, uno podría producir una instancia de un tipo inmutable respaldado por una matriz copiando todos los elementos en una matriz, pero supongamos que una implementación particular simplemente devuelve 16777216 para la longitud y ((long)index*index)>>24para cada elemento. Esa sería una secuencia legítima inmutable de enteros, pero copiarla en una matriz sería una gran pérdida de tiempo y memoria.
supercat
1
Yo estoy totalmente de acuerdo. Mi solución le brinda la corrección (hasta cierto punto), pero para obtener rendimiento con un conjunto de datos grande, debe tener una estructura y un diseño persistentes para la inmutabilidad desde el principio. Para una colección pequeña, puede salirse con la suya de vez en cuando. Recuerdo que Scala hizo un análisis de varios programas y descubrió que algo así como el 90% de las listas instanciadas tenían 10 o menos elementos.
Laurent Bourgault-Roy
1
@ LaurentBourgault-Roy: La pregunta fundamental es si se confía en las personas para que no produzcan implementaciones rotas o clases derivadas. Si lo hace, y si las interfaces / clases base proporcionan métodos asMutable / asImmutable, es posible mejorar el rendimiento en muchos órdenes de magnitud [por ejemplo, compare el costo de llamar asImmutablea una instancia de la secuencia definida anteriormente versus el costo de construcción una copia inmutable respaldada por matriz]. Yo diría que tener interfaces definidas para tales propósitos es probablemente mejor que tratar de usar enfoques ad-hoc; En mi humilde opinión, la razón más grande ...
supercat
15

Java Collections Framework proporciona la capacidad de crear una versión de solo lectura de una colección mediante seis métodos estáticos en la clase java.util.Collections :

Como alguien ha señalado en los comentarios a la pregunta original, las colecciones devueltas pueden no considerarse inmutables porque a pesar de que las colecciones no se pueden modificar (no se pueden agregar ni eliminar miembros de dicha colección), los objetos reales a los que hace referencia la colección puede modificarse si su tipo de objeto lo permite.

Sin embargo, este problema se mantendría independientemente de si el código devuelve un solo objeto o una colección de objetos no modificable. Si el tipo permite que sus objetos sean mutados, entonces esa decisión se tomó en el diseño del tipo y no veo cómo un cambio en el JCF podría alterar eso. Si la inmutabilidad es importante, los miembros de una colección deben ser de un tipo inmutable.

Arkanon
fuente
44
El diseño de las colecciones no modificables se habría mejorado enormemente si los contenedores incluían una indicación de si la cosa que se estaba envolviendo ya era inmutable, y si existían immutableListmétodos de fábrica que devolverían un contenedor de solo lectura alrededor de una copia de un documento entregado. lista a menos que la lista pasada ya sea inmutable . Sería fácil crear tipos definidos por el usuario como ese, pero por un problema: no habría forma de que el joesCollections.immutableListmétodo reconozca que no debería necesitar copiar el objeto devuelto por fredsCollections.immutableList.
supercat
8

Esta es una muy buena pregunta. Disfruto entreteniendo la idea de que de todo el código escrito en Java y que se ejecuta en millones de computadoras en todo el mundo, todos los días, durante todo el día, aproximadamente la mitad del ciclo total del reloj debe desperdiciarse haciendo nada más que hacer copias de seguridad de las colecciones que están siendo devuelto por funciones. (Y recolectar basura estas colecciones milisegundos después de su creación).

Un porcentaje de los programadores de Java son conscientes de la existencia de la unmodifiableCollection()familia de métodos de la Collectionsclase, pero incluso entre ellos, muchos simplemente no se molestan con eso.

Y no puedo culparlos: ¡una interfaz que pretende ser de lectura-escritura pero arrojará una UnsupportedOperationExceptionsi cometes el error de invocar cualquiera de sus métodos de 'escritura' es algo muy malo!

Ahora, una interfaz como la Collectionque faltaría add(), remove()y los clear()métodos no serían una interfaz "ImmutableCollection"; sería una interfaz "UnmodifiableCollection". De hecho, nunca podría haber una interfaz "ImmutableCollection", porque la inmutabilidad es una naturaleza de una implementación, no una característica de una interfaz. Lo sé, eso no está muy claro; Dejame explicar.

Supongamos que alguien le entrega una interfaz de colección de solo lectura; ¿Es seguro pasarlo a otro hilo? Si supiera con certeza que representa una colección verdaderamente inmutable, entonces la respuesta sería "sí"; desafortunadamente, dado que es una interfaz, no sabes cómo se implementa, por lo que la respuesta tiene que ser un no : por lo que sabes, puede ser una vista inmodificable (para ti) de una colección que de hecho es mutable, (como con lo que obtienes Collections.unmodifiableCollection()), por lo que intentar leerlo mientras otro hilo está modificando resultaría en la lectura de datos corruptos.

Entonces, lo que esencialmente ha descrito es un conjunto de interfaces de colección no "inmutables", sino "no modificables". Es importante comprender que "No modificable" simplemente significa que quien tiene una referencia a dicha interfaz no puede modificar la colección subyacente, y se evita simplemente porque la interfaz carece de métodos de modificación, no porque la colección subyacente sea necesariamente inmutable. La colección subyacente bien podría ser mutable; no tienes conocimiento ni control sobre eso.

¡Para tener colecciones inmutables, tendrían que ser clases , no interfaces!

Estas clases de colección inmutable tendrían que ser finales, de modo que cuando se le dé una referencia a dicha colección, usted sabe con certeza que se comportará como una colección inmutable, sin importar lo que usted, o cualquier otra persona que tenga una referencia, pueda hacer con eso.

Entonces, para tener un conjunto completo de colecciones en Java, (o cualquier otro lenguaje imperativo declarativo), necesitaríamos lo siguiente:

  1. Un conjunto de interfaces de colección no modificables .

  2. Un conjunto de interfaces de colección mutable , que amplía las no modificables.

  3. Un conjunto de clases de colección mutable que implementan las interfaces mutables y, por extensión, también las interfaces no modificables.

  4. Un conjunto de clases de colección inmutables , que implementan las interfaces no modificables, pero que se pasan principalmente como clases, para garantizar la inmutabilidad.

He implementado todo lo anterior por diversión, y los estoy usando en proyectos, y funcionan de maravilla.

La razón por la cual no son parte del tiempo de ejecución de Java es probablemente porque se pensó que esto sería demasiado / demasiado complejo / demasiado difícil de entender.

Personalmente, creo que lo que describí anteriormente no es suficiente; Una cosa más que parece ser necesaria es un conjunto de interfaces y clases mutables para la inmutabilidad estructural . (Lo que simplemente puede llamarse "rígido" porque el prefijo "StructurallyImmutable" es demasiado largo).

Mike Nakis
fuente
Buenos puntos. Dos detalles: 1. Las colecciones inmutables requieren ciertas firmas de métodos, específicamente (usando una Lista como ejemplo): List<T> add(T t)- todos los métodos "mutadores" deben devolver una nueva colección que refleje el cambio. 2. Para bien o para mal, las interfaces a menudo representan un contrato además de una firma. Serializable es una de esas interfaces. Del mismo modo, Comparable requiere que implemente correctamente su compareTo()método para que funcione correctamente e idealmente sea compatible con equals()y hashCode().
GlenPeterson
Oh, ni siquiera tenía en mente la inmutabilidad mutación por copia. Lo que escribí anteriormente se refiere a colecciones inmutables simples y simples que realmente no tienen métodos como add(). Pero supongo que si se agregaran métodos mutantes a las clases inmutables, entonces tendrían que devolver también clases inmutables. Entonces, si hay un problema al acecho allí, no lo veo.
Mike Nakis
¿Su implementación está disponible públicamente? Debería haber preguntado esto hace meses. De todos modos, el mío es: github.com/GlenKPeterson/UncleJim
GlenPeterson
44
Suppose someone hands you such a read-only collection interface; is it safe to pass it to another thread?Supongamos que alguien le pasa una instancia de una interfaz de colección mutable. ¿Es seguro invocar algún método? No sabe que la implementación no se repite para siempre, arroja una excepción o ignora por completo el contrato de la interfaz. ¿Por qué tener un doble estándar específicamente para colecciones inmutables?
Doval
1
En mi humilde opinión, su razonamiento contra interfaces mutables es incorrecto. Puede escribir una implementación mutable de interfaces inmutables, y luego se rompe. Seguro. Pero es tu culpa, ya que estás violando el contrato. Solo deja de hacer eso. No es diferente de romper una SortedSetsubclasificación del conjunto con una implementación no conforme. O al pasar un inconsistente Comparable. Casi cualquier cosa se puede romper si quieres. Supongo que eso es lo que @Doval quería decir con "doble rasero".
maaartinus
2

Las colecciones inmutables pueden ser profundamente recursivas, en comparación entre sí, y no ineficaces si la igualdad de objetos es mediante secureHash. Esto se llama un bosque de merkle. Puede ser por colección o dentro de partes de ellos, como un árbol AVL (binario de equilibrio automático) para un mapa ordenado.

A menos que todos los objetos java en estas colecciones tengan una identificación única o alguna cadena de bits para hacer hash, la colección no tiene nada que hacer para nombrar a sí misma.

Ejemplo: en mi computadora portátil 4x1.6ghz, puedo ejecutar 200K sha256s por segundo del tamaño más pequeño que cabe en 1 ciclo de hash (hasta 55 bytes), en comparación con 500K HashMap ops o 3M ops en una tabla hash de largos. 200K / log (collectionSize) nuevas colecciones por segundo es lo suficientemente rápido para algunas cosas donde la integridad de los datos y la escalabilidad anónima global son importantes.

Ben Rayfield
fuente
-3

Actuación. Las colecciones por su naturaleza pueden ser muy grandes. Copiar 1000 elementos en una nueva estructura con 1001 elementos en lugar de insertar un solo elemento es simplemente horrible.

Concurrencia. Si tiene varios subprocesos en ejecución, es posible que deseen obtener la versión actual de la colección y no la versión que se aprobó hace 12 horas cuando comenzó el subproceso.

Almacenamiento. Con objetos inmutables en un entorno de subprocesos múltiples, puede terminar con docenas de copias del "mismo" objeto en diferentes puntos de su ciclo de vida. No importa para un objeto Calendario o Fecha, pero cuando se trata de una colección de 10,000 widgets, esto te matará.

James Anderson
fuente
12
Las colecciones inmutables solo requieren copia si no se puede compartir debido a la mutabilidad generalizada como lo ha hecho Java. La concurrencia es generalmente más fácil con colecciones inmutables porque no requieren bloqueo; y para la visibilidad, siempre puede tener una referencia mutable a una colección inmutable (común en OCaml). Al compartir, las actualizaciones pueden ser esencialmente gratuitas. Puede hacer asignaciones logarítmicamente más que con una estructura mutable, pero en la actualización, muchos subobjetos caducados pueden liberarse de inmediato o reutilizarse, por lo que no necesariamente tiene una sobrecarga de memoria más alta.
Jon Purdy
44
Problemas de pareja Las colecciones en Clojure y Scala son inmutables, pero admiten copias livianas. Agregar el elemento 1001 significa copiar menos de 33 elementos, además de hacer algunos punteros nuevos. Si comparte una colección mutable entre hilos, tiene todo tipo de problemas de sincronización cuando la cambia. Operaciones como "remove ()" son una pesadilla. Además, las colecciones inmutables se pueden construir de forma mutable, y luego copiarse una vez en una versión inmutable segura para compartir a través de subprocesos.
GlenPeterson
44
Usar la concurrencia como argumento contra la inmutabilidad es inusual. Duplicados también.
Tom Hawtin - tackline
44
Un poco molesto por los votos negativos aquí. El OP preguntó por qué no implementaron colecciones inmutables y proporcioné una respuesta considerada a la pregunta. Presumiblemente, la única respuesta aceptable entre los conscientes de la moda es "porque cometieron un error". De hecho, tengo algo de experiencia con esto teniendo que refactorizar grandes porciones de código utilizando la clase BigDecimal, que de otro modo sería excelente, simplemente debido a un rendimiento pobre debido a la inmutabilidad 512 veces mayor que el uso de un doble más un poco de desorden para arreglar los decimales.
James Anderson
3
@JamesAnderson: Mis problemas con su respuesta: "Rendimiento": podría decir que las colecciones inmutables de la vida real siempre implementan alguna forma de compartir y reutilizar para evitar exactamente el problema que describe. "Concurrencia": el argumento se reduce a "Si desea mutabilidad, entonces un objeto inmutable no funciona". Quiero decir que si hay una noción de "última versión de la misma cosa", entonces algo tiene que mutar, ya sea la cosa misma o algo que la posea. Y en "Almacenamiento", parece decir que a veces no se desea la mutabilidad.
jhominal