Usos de estructuras de datos persistentes en lenguajes no funcionales.

Los lenguajes que son puramente funcionales o casi puramente funcionales se benefician de las estructuras de datos persistentes porque son inmutables y encajan bien con el estilo sin estado de la programación funcional.

Pero de vez en cuando vemos bibliotecas de estructuras de datos persistentes para lenguajes (basados ​​en estado, OOP) como Java. Un reclamo a menudo escuchado a favor de las estructuras de datos persistentes es que, debido a que son inmutables, son seguras para subprocesos .

Sin embargo, la razón por la que las estructuras de datos persistentes son seguras para subprocesos es que si un subproceso "agregara" un elemento a una colección persistente, la operación devuelve una nueva colección como la original pero con el elemento agregado. Por lo tanto, otros hilos ven la colección original. Las dos colecciones comparten mucho estado interno, por supuesto, es por eso que estas estructuras persistentes son eficientes.

Pero dado que diferentes subprocesos ven diferentes estados de datos, parece que las estructuras de datos persistentes no son en sí mismas suficientes para manejar escenarios en los que un subproceso realiza un cambio que es visible para otros subprocesos. Para esto, parece que debemos usar dispositivos como átomos, referencias, memoria transaccional de software o incluso bloqueos clásicos y mecanismos de sincronización.

¿Por qué, entonces, se promociona la inmutabilidad de los PDS como algo beneficioso para la "seguridad del hilo"? ¿Hay ejemplos reales en los que los PDS ayudan en la sincronización o en la resolución de problemas de concurrencia? ¿O los PDS son simplemente una forma de proporcionar una interfaz sin estado a un objeto en apoyo de un estilo de programación funcional?

Las estructuras de datos persistentes / inmutables no resuelven los problemas de concurrencia por sí solos, pero hacen que resolverlos sea mucho más fácil.

Considere un hilo T1 que pasa un conjunto S a otro hilo T2. Si S es mutable, T1 tiene un problema: pierde el control de lo que sucede con S. Thread T2 puede modificarlo, por lo que T1 no puede confiar en absoluto en el contenido de S. Y viceversa: T2 no puede estar seguro de que T1 no modifica S mientras T2 opera en él.

Una solución es agregar algún tipo de contrato a la comunicación de T1 y T2 para que solo uno de los hilos pueda modificar S. Esto es propenso a errores y afecta tanto el diseño como la implementación.

Otra solución es que T1 o T2 clonen la estructura de datos (o ambos, si no están coordinados). Sin embargo, si S no es persistente, esta es una operación costosa de O (n) .

Si tiene una estructura de datos persistente, está libre de esta carga. Puede pasar una estructura a otro hilo y no tiene que preocuparse por lo que hace con él. Ambos hilos tienen acceso a la versión original y pueden realizar operaciones arbitrarias en él, no influye en lo que ve el otro hilo.

Ver también: estructura de datos persistente vs inmutable .

¿Por qué, entonces, se promociona la inmutabilidad de los PDS como algo beneficioso para la "seguridad del hilo"? ¿Hay ejemplos reales en los que los PDS ayudan en la sincronización o en la resolución de problemas de concurrencia?

El principal beneficio de un PDS en ese caso es que puede modificar una porción de datos sin hacer que todo sea único (sin copiar todo en profundidad, por así decirlo). Eso tiene muchos beneficios potenciales además de permitirle escribir funciones baratas sin efectos secundarios: copia de instancias y datos pegados, sistemas triviales de deshacer, funciones triviales de reproducción en juegos, edición trivial no destructiva, seguridad trivial de excepciones, etc. etc. etc.

Uno puede imaginar una estructura de datos que sería persistente pero mutable. Por ejemplo, podría tomar una lista vinculada, representada por un puntero al primer nodo, y una operación de antecedente que devolvería una nueva lista, que consta de un nuevo nodo principal más la lista anterior. Como todavía tiene la referencia al encabezado anterior, puede acceder y modificar esta lista, que mientras tanto también se ha incrustado dentro de la nueva lista. Si bien es posible, este paradigma no ofrece los beneficios de estructuras de datos persistentes e inmutables, por ejemplo, no es seguro para subprocesos de forma predeterminada. Sin embargo, puede tener sus usos siempre que el desarrollador sepa lo que está haciendo, por ejemplo, para la eficiencia del espacio. También tenga en cuenta que si bien la estructura puede ser mutable a nivel de lenguaje, ya que nada impide que el código la modifique,

Tan larga historia corta, sin inmutabilidad (impuesta por el lenguaje o por convención), la persistencia de las estructuras de datos pierde algunos de sus beneficios (seguridad de subprocesos) pero no otros (eficiencia de espacio para algunos escenarios).

En cuanto a los ejemplos de lenguajes no funcionales, Java String.substring()utiliza lo que yo llamaría una estructura de datos persistente. La cadena está representada por una matriz de caracteres más las compensaciones de inicio y fin del rango de la matriz que realmente se utiliza. Cuando se crea una subcadena, el nuevo objeto reutiliza la misma matriz de caracteres, solo con desplazamientos iniciales y finales modificados. Como Stringes inmutable, es (con respecto a la substring()operación, no a otros) una estructura de datos persistente inmutable.

La inmutabilidad de las estructuras de datos es la parte relevante para la seguridad de subprocesos. Su persistencia (reutilización de fragmentos existentes cuando se crea una nueva estructura) es relevante para la eficiencia cuando se trabaja con tales colecciones. Como son inmutables, una operación como agregar un elemento no modifica la estructura existente, pero devuelve una nueva, con el elemento adicional agregado. Si cada vez que se copiara toda la estructura, comenzando con una colección vacía y agregando 1000 elementos uno por uno para terminar con una colección de 1000 elementos, crearía objetos temporales con 0 + 1 + 2 + ... + 999 = 500000 elementos en total, lo que sería un gran desperdicio. Con estructuras de datos persistentes, esto se puede evitar ya que la colección de 1 elemento se reutiliza en la de 2 elementos, que se reutiliza en la de 3 elementos, y así sucesivamente.

Es cierto que soy parcial al aplicar dichos conceptos en C ++ por el lenguaje y su naturaleza, así como mi dominio e incluso la forma en que usamos el lenguaje. Pero dadas estas cosas, creo que los diseños inmutables son el aspecto menos interesante cuando se trata de cosechar una gran parte de los beneficios asociados con la programación funcional, como la seguridad de los hilos, la facilidad de razonamiento sobre el sistema, encontrar más reutilización para las funciones (y descubrir que podemos combinarlos en cualquier orden sin sorpresas desagradables), etc.

Tome este ejemplo simplista de C ++ (es cierto que no está optimizado para simplificar para evitar avergonzarme frente a los expertos en procesamiento de imágenes):

// Inputs an image and outputs a new one with the specified size.
Image resized_image(const Image& src, int new_w, int new_h)
{
     Image dst(new_w, new_h);
     for (int y=0; y < new_h; ++y)
     {
         for (int x=0; x < new_w; ++x)
              dst[y][x] = src.sample(x / (float)new_w, y / (float)new_h);
     }
     return dst;
}

Si bien la implementación de esa función muta el estado local (y temporal) en forma de dos variables de contador y una imagen local temporal para la salida, no tiene efectos secundarios externos. Introduce una imagen y genera una nueva. Podemos multiprocesarlo al contenido de nuestros corazones. Es fácil razonar, fácil de probar a fondo. Es una excepción segura ya que si algo arroja, la nueva imagen se descarta automáticamente y no tenemos que preocuparnos por revertir los efectos secundarios externos (no hay imágenes externas que se modifiquen fuera del alcance de la función, por así decirlo).

Veo poco que ganar, y potencialmente mucho que perder, al hacer Imageinmutable en el contexto anterior, en C ++, excepto para hacer que la función anterior sea más difícil de implementar y posiblemente un poco menos eficiente.

Pureza

Por lo tanto, las funciones puras (sin efectos secundarios externos ) son muy interesantes para mí, y enfatizo la importancia de favorecerlas a menudo a los miembros del equipo incluso en C ++. Pero los diseños inmutables, aplicados en general con ausencia de contexto y matices, no son tan interesantes para mí ya que, dada la naturaleza imperativa del lenguaje, a menudo es útil y práctico poder mutar algunos objetos temporales locales en el proceso de manera eficiente (ambos para desarrolladores y hardware) implementando una función pura.

Copia barata de estructuras fuertes

La segunda propiedad más útil que encuentro es la capacidad de copiar a bajo costo las estructuras de datos realmente pesadas cuando el costo de hacerlo, como a menudo se incurriría para hacer funciones puras dada su estricta naturaleza de entrada / salida, no sería trivial. Estas no serían estructuras pequeñas que puedan caber en la pila. Serían estructuras grandes y fuertes, como la totalidad Scenede un videojuego.

En ese caso, la sobrecarga de copia podría evitar oportunidades para un paralelismo efectivo, porque podría ser difícil paralelizar la física y renderizar de manera efectiva sin bloquearse y bloquearse si la física está mutando la escena que el renderizador está tratando de dibujar simultáneamente, mientras que al mismo tiempo tiene una física profunda copiar toda la escena del juego solo para generar un fotograma con la física aplicada podría ser igualmente ineficaz. Sin embargo, si el sistema de física era 'puro' en el sentido de que simplemente ingresaba una escena y emitía una nueva con la física aplicada, y tal pureza no tenía el costo de una copia astronómica en lo alto, podría operar en paralelo con seguridad. Renderizador sin que uno espere en el otro.

Entonces, la capacidad de copiar de manera económica los datos realmente pesados ​​del estado de su aplicación y generar nuevas versiones modificadas con un costo mínimo para el procesamiento y el uso de la memoria realmente puede abrir nuevas puertas para la pureza y el paralelismo efectivo, y allí encuentro muchas lecciones que aprender de cómo se implementan las estructuras de datos persistentes. Pero cualquier cosa que creamos usando tales lecciones no tiene que ser completamente persistente, u ofrecer interfaces inmutables (podría usar copia en escritura, por ejemplo, o un "constructor / transitorio"), para lograr esta capacidad de ser muy barata. para copiar y modificar solo secciones de la copia sin duplicar el uso de la memoria y el acceso a la memoria en nuestra búsqueda de paralelismo y pureza en nuestras funciones / sistemas / canalización.

Inmutabilidad

Finalmente, existe la inmutabilidad que considero la menos interesante de estas tres, pero puede imponerse, con un puño de hierro, cuando ciertos diseños de objetos no están destinados a ser utilizados como temporales locales para una función pura, y en su lugar en un contexto más amplio, un valor tipo de "pureza a nivel de objeto", ya que en todos los métodos ya no causan efectos secundarios externos (ya no mutan las variables miembro fuera del alcance local inmediato del método).

Y aunque considero que es el menos interesante de estos tres en lenguajes como C ++, sin duda puede simplificar las pruebas y la seguridad de los subprocesos y el razonamiento de objetos no triviales. Trabajar con la garantía de que a un objeto no se le puede dar ninguna combinación de estado única fuera de su constructor, por ejemplo, y que podemos pasarlo libremente, incluso por referencia / puntero sin depender de la constidad y la lectura, puede ser una carga. solo iteradores y controladores y tal, al tiempo que garantiza (bueno, al menos tanto como podamos dentro del lenguaje) que sus contenidos originales no serán mutados.

Pero considero que esta es la propiedad menos interesante porque la mayoría de los objetos que veo son tan beneficiosos como el uso temporal, en forma mutable, para implementar una función pura (o incluso un concepto más amplio, como un "sistema puro" que podría ser un objeto o una serie de funciona con el efecto final de simplemente ingresar algo y generar algo nuevo sin tocar nada más, y creo que la inmutabilidad llevada a las extremidades en un lenguaje fundamentalmente imperativo es un objetivo bastante contraproducente. Lo aplicaría con moderación para las partes de la base de código donde realmente ayuda más.

Finalmente:

[...] parecería que las estructuras de datos persistentes no son en sí mismas suficientes para manejar escenarios en los que un hilo realiza un cambio que es visible para otros hilos. Para esto, parece que debemos usar dispositivos como átomos, referencias, memoria transaccional de software o incluso bloqueos clásicos y mecanismos de sincronización.

Naturalmente, si su diseño requiere modificaciones (en el sentido del diseño del usuario final) para que sean visibles para múltiples hilos simultáneamente a medida que ocurren, volveremos a la sincronización o al menos al tablero de dibujo para encontrar algunas formas sofisticadas de lidiar con esto ( He visto algunos ejemplos muy elaborados utilizados por expertos que se ocupan de este tipo de problemas en la programación funcional).

Pero descubrí que, una vez que obtienes ese tipo de copia y la capacidad de generar versiones parcialmente modificadas de estructuras pesadas muy baratas, como obtendrías con estructuras de datos persistentes como ejemplo, a menudo abre muchas puertas y oportunidades que podrías No había pensado antes en paralelizar el código que puede ejecutarse de manera completamente independiente el uno del otro en un estricto tipo de canalización paralela de E / S. Incluso si algunas partes del algoritmo tienen que ser de naturaleza en serie, puede diferir ese procesamiento a un solo hilo, pero descubrir que apoyarse en estos conceptos ha abierto las puertas para paralelizar fácilmente y sin preocupaciones, el 90% del trabajo pesado, por ejemplo