¿Por qué utilizamos estructuras de datos persistentes en la programación funcional?

La programación funcional emplea estructuras de datos persistentes y objetos inmutables. Mi pregunta es ¿por qué es crucial tener tales estructuras de datos aquí? Quiero entender a bajo nivel ¿qué sucedería si la estructura de datos no es persistente? ¿El programa se bloqueará más a menudo?

Cuando trabaja con objetos de datos inmutables, las funciones tienen la propiedad de que cada vez que las llama con las mismas entradas, producen las mismas salidas. Esto facilita la conceptualización de los cálculos y hacerlos bien. También los hace más fáciles de probar.

Eso es solo un comienzo. Dado que las matemáticas han trabajado durante mucho tiempo con las funciones, existen muchas técnicas de razonamiento que podemos tomar prestadas de las matemáticas y utilizarlas para un razonamiento riguroso sobre los programas. La ventaja más importante desde mi punto de vista es que los sistemas de tipos para programas funcionales están bien desarrollados. Por lo tanto, si comete un error en alguna parte, hay muchas posibilidades de que se muestre como un desajuste de tipo. Por lo tanto, los programas funcionales mecanografiados tienden a ser mucho más confiables que los programas imperativos.

Por el contrario, cuando trabaja con objetos de datos mutables, primero tiene la carga cognitiva de recordar y administrar los múltiples estados que atraviesa el objeto durante un cálculo. Debe tener cuidado de hacer las cosas en el orden correcto, asegurándose de que todas las propiedades que necesita para un paso en particular estén satisfechas en ese punto. Es fácil cometer errores, y los sistemas de tipos no son lo suficientemente potentes como para detectar esos errores.

Las matemáticas nunca funcionaron con objetos de datos mutables. Por lo tanto, no hay técnicas de razonamiento que podamos tomar prestadas de ellos. Existen muchas técnicas propias desarrolladas en informática, especialmente Floyd-Hoare Logic . Sin embargo, estos son más difíciles de dominar que las técnicas matemáticas estándar, la mayoría de los estudiantes no pueden manejarlas, por lo que rara vez se les enseña.

Para obtener una descripción general rápida de cómo difieren los dos paradigmas, puede consultar los primeros folletos de mis notas de clase sobre Principios de lenguajes de programación .

Es más fácil trabajar correctamente con estructuras de datos persistentes que trabajar con estructuras de datos mutables. Esto, yo diría, es la principal ventaja.

Por supuesto, teóricamente hablando, cualquier cosa que hagamos con estructuras de datos persistentes también podemos hacerlo con las mutables, y viceversa. En muchos casos, las estructuras de datos persistentes conllevan costos adicionales, generalmente porque algunas partes de ellas deben copiarse. Estas consideraciones habrían hecho que las estructuras de datos persistentes fueran mucho menos atractivas hace 30 años cuando las supercomputadoras tenían menos memoria que su teléfono móvil. Pero hoy en día los principales cuellos de botella en la producción de software parecen ser el tiempo de desarrollo y los costos de mantenimiento. Por lo tanto, estamos dispuestos a sacrificar algo de eficiencia en la ejecución por la eficiencia en el desarrollo.

¿Por qué es más fácil usar estructuras de datos persistentes? Porque los humanos son realmente malos para rastrear los alias y otros tipos de interacciones inesperadas entre diferentes partes de un programa. Ellos piensan eso automáticamente porque se llaman dos cosas xy y, luego, no tienen nada en común. Después de todo, se necesita esfuerzo para darse cuenta de que "la estrella de la mañana" y "la estrella de la tarde" son realmente lo mismo. Del mismo modo, es muy fácil olvidar que una estructura de datos puede cambiar porque otros hilos están trabajando con ella, o porque llamamos a un método que cambia la estructura de datos, etc. Muchas de estas preocupaciones simplemente no están presentes cuando trabajamos con estructuras de datos persistentes.

Las estructuras de datos persistentes también tienen otras ventajas técnicas. Por lo general, es más fácil optimizarlos. Por ejemplo, siempre puede copiar una estructura de datos persistente en algún otro nodo en su nube si lo desea, no hay que preocuparse por la sincronización.

Agregando a las respuestas de otros, y reforzando un enfoque matemático, la programación funcional también tiene una buena sinergia con Álgebra Relacional y las Conexiones de Galois.

Esto es extremadamente útil en el área de los métodos formales.
Por ejemplo:

• Las pruebas formales en la verificación del programa se simplifican con la Comprobación estática extendida;
• Varias propiedades de Álgebra Relacional son útiles en la resolución de SAT, con herramientas como Alloy;
• Galois Connections permite un enfoque de cálculo para la especificación de software, como se ve en este blog , con una referencia a un artículo , por Shin-Cheng Mu y José Nuno Oliveira.
• Las Conexiones de Galois (y la Programación Funcional) se pueden usar en una forma de Diseño por Contrato, ya que son un concepto más general que Hoare Logic.

Ejemplo

$\{p\} P \{q\}$$[P] \cdot \phi_p \subseteq \phi_q \cdot [P]$

• $[P]$$P$
• $\phi_p$$\phi_q)$$p$$q$

Este enfoque también permite más débil condición previa y más fuerte después de la condición de cálculo, que viene muy bien en una serie de situaciones.

Quiero entender a un nivel bajo, ¿qué sucedería si la estructura de datos no es persistente?

Veamos un generador de números pseudoaleatorios con un gran espacio de estado (como " Mersenne twister " con un estado de 2450 bytes) como una estructura de datos. Realmente no queremos usar ningún número aleatorio más de una vez, por lo que parece haber pocas razones para implementar esto como una estructura de datos persistente inmutable. Ahora preguntémonos qué podría salir mal en el siguiente código:

mt_gen = CreateMersenneTwisterPRNGen(seed)
integral = MonteCarloIntegral_Bulk(mt_gen) + MonteCarloIntegral_Boundary(mt_gen)

La mayoría de los lenguajes de programación no especifican el orden en el que MonteCarloIntegral_Bulky MonteCarloIntegral_Boundaryserán evaluados. Si ambos toman una referencia a un mt_gen mutable como argumento, el resultado de este cálculo puede depender de la plataforma. Peor aún, puede haber plataformas en las que el resultado no sea reproducible en absoluto entre diferentes ejecuciones.

Se puede diseñar una estructura de datos mutable eficiente para mt_gen de modo que cualquier entrelazado de la ejecución de MonteCarloIntegral_Bulky MonteCarloIntegral_Boundarydé un resultado "correcto", pero un entrelazado diferente en general dará lugar a un resultado "correcto" diferente. Esta no reproducibilidad hace que la función correspondiente sea "impura" y también conduce a otros problemas.

La no reproducibilidad puede evitarse imponiendo un orden de ejecución secuencial fijo. Pero en ese caso, el código podría organizarse de tal manera que solo una única referencia a mt_gen esté disponible en un momento dado. En un lenguaje de programación funcional mecanografiado, los tipos de unicidad podrían usarse para hacer cumplir esta restricción, permitiendo así actualizaciones seguras mutables también en el contexto de lenguajes de programación funcional puros. Todo esto puede sonar agradable y elegante, pero al menos en teoría las simulaciones de Monte Carlo son vergonzosamente paralelas, y nuestra "solución" acaba de destruir esta propiedad. Este no es solo un problema teórico, sino un problema práctico muy real. Sin embargo, tenemos que modificar (la funcionalidad que ofrece) nuestro generador de números pseudoaleatorios y la secuencia de números aleatorios que produce, y ningún lenguaje de programación puede hacer esto automáticamente por nosotros. (Por supuesto, podemos usar una biblioteca de números pseudoaleatoria diferente que ya ofrece la funcionalidad requerida).

En un nivel bajo, las estructuras de datos mutables conducen fácilmente a la no reproducibilidad (y, por lo tanto, a la impureza), si el orden de ejecución no es secuencial y fijo. Una estrategia imperativa típica para tratar estos problemas es tener fases secuenciales con un orden de ejecución fijo, durante el cual se cambian las estructuras de datos mutables, y fases paralelas con un orden de ejecución arbitrario, durante el cual todas las estructuras de datos mutables compartidas permanecen constantes.

Andrej Bauer planteó la cuestión del alias para estructuras de datos mutables. Curiosamente, diferentes lenguajes imperativos como Fortran y C tienen diferentes supuestos sobre el alias permitido de argumentos de función, y la mayoría de los programadores desconocen que su lenguaje tiene un modelo de alias.

La inmutabilidad y la semántica del valor pueden estar ligeramente sobrevaloradas. Lo que es más importante es que el sistema de tipos y el marco lógico (como el modelo de máquina abstracto, el modelo de alias, el modelo de concurrencia o el modelo de administración de memoria) de su lenguaje de programación ofrece suficiente soporte para trabajar de manera "segura" con datos "eficientes" estructuras La introducción de la "semántica de movimiento" a C ++ 11 podría parecer un gran paso atrás en términos de pureza y "seguridad" desde un punto de vista teórico, pero en la práctica es todo lo contrario. El sistema de tipos y el marco lógico del lenguaje se han ampliado para eliminar grandes partes del peligro asociado a la nueva semántica. (E incluso si quedan bordes ásperos, esto no significa que esto no pueda mejorarse con un "mejor"

Uday Reddy planteó la cuestión de que las matemáticas nunca funcionaron con objetos de datos mutables, y que los sistemas de tipos para programas funcionales están bien desarrollados para objetos de datos inmutables. Esto me recordó la explicación de Jean-Yves Girard de que las matemáticas no están acostumbradas a trabajar con objetos cambiables, cuando trata de motivar la lógica lineal.

Uno podría preguntarse cómo ampliar el sistema de tipos y el marco lógico de los lenguajes de programación funcionales para permitir trabajar de manera "segura" con estructuras de datos no persistentes "eficientes" mutables. Un problema aquí podría ser que la lógica clásica y las álgebras booleanas podrían no ser el mejor marco lógico para trabajar con estructuras de datos mutables. ¿Quizás la lógica lineal y los monoides conmutativos podrían ser más adecuados para esa tarea? ¿Quizás debería leer lo que Philip Wadler tiene que decir sobre lógica lineal como sistema de tipos para lenguajes de programación funcionales? Pero incluso si la lógica lineal no fuera capaz de resolver este problema, esto no significa que el sistema de tipos y el marco lógico de un lenguaje de programación funcional no puedan extenderse para permitir "seguro" y "eficiente"