Programación funcional: ¿ideas correctas sobre concurrencia y estado?

21

Los defensores de FP han afirmado que la concurrencia es fácil porque su paradigma evita el estado mutable. No lo entiendo

Imagina que estamos creando un rastreo de mazmorras multijugador (un roguelike) usando FP donde enfatizamos funciones puras y estructuras de datos inmutables. Generamos una mazmorra compuesta de habitaciones, corredores, héroes, monstruos y botín. Nuestro mundo es efectivamente un gráfico objeto de estructuras y sus relaciones. A medida que las cosas cambian, nuestra representación del mundo se modifica para reflejar esos cambios. Nuestro héroe mata una rata, recoge una espada corta, etc.

Para mí, el mundo (realidad actual) lleva esta idea de estado y me falta cómo FP supera esto. A medida que nuestro héroe toma medidas, las funciones modifican el estado del mundo. Parece que cada decisión (IA o humana) debe basarse en el estado del mundo tal como está en el presente. ¿Dónde permitiríamos la concurrencia? No podemos tener múltiples procesos que modifiquen simultáneamente el estado del mundo para que un proceso no base sus resultados en algún estado vencido. Me parece que todo el control debe ocurrir dentro de un solo ciclo de control para que siempre estemos procesando el estado actual representado por nuestro gráfico actual de objetos del mundo.

Claramente, hay situaciones perfectamente adecuadas para la concurrencia (es decir, cuando se procesan tareas aisladas cuyos estados son independientes entre sí).

No puedo ver cómo la concurrencia es útil en mi ejemplo y ese puede ser el problema. Puedo estar tergiversando el reclamo de alguna manera.

¿Alguien puede representar mejor este reclamo?

Mario T. Lanza
fuente
1
Te refieres al estado compartido; el estado compartido siempre será lo que es y siempre requerirá alguna forma de sincronización, la forma más frecuente entre las personas con FP pura es STM, que le permite tratar la memoria compartida como memoria local al tener una capa de abstracción sobre ella que hace que el acceso sea transaccional de manera competitiva Las condiciones se manejan automáticamente. Otra técnica para la memoria compartida es pasar mensajes donde, en lugar de tener memoria compartida, tienes memoria local y conocimiento de otros actores para pedir su memoria local
Jimmy Hoffa
1
Entonces ... ¿se pregunta cómo la facilidad de concurrencia de estado compartido ayuda a administrar el estado en una aplicación de subproceso único? Por otro lado, su ejemplo se presta claramente a la concurrencia conceptual (un hilo para cada entidad controlada por IA) ya sea que se implemente o no de esa manera. Estoy confundido con lo que estás preguntando aquí.
CA McCann
1
en una palabra, Zippers
jk.
2
Cada objeto tendría su propia visión del mundo. Habrá eventual consistencia . Probablemente también es cómo funcionan las cosas en nuestro "mundo real" con el colapso de la función de onda .
herzmeister
1
Puede encontrar interesantes los " retrojuegos
user802500

Respuestas:

15

Trataré de insinuar la respuesta. Esta no es una respuesta, solo una ilustración introductoria. La respuesta de @ jk apunta a lo real, las cremalleras.

Imagina que tienes una estructura de árbol inmutable. Desea alterar un nodo insertando un hijo. Como resultado, obtienes un árbol completamente nuevo.

Pero la mayor parte del árbol nuevo es exactamente igual al árbol viejo. Una implementación inteligente reutilizaría la mayoría de los fragmentos de árbol, enrutando punteros alrededor del nodo alterado:

De Wikipedia

El libro de Okasaki está lleno de ejemplos como este.

Así que supongo que podría alterar razonablemente pequeñas partes de su mundo de juego en cada movimiento (recoger una moneda), y solo cambiar realmente pequeñas partes de la estructura de datos de su mundo (la celda donde se recogió la moneda). Las partes que solo pertenecen a estados pasados ​​se recolectarán a tiempo.

Esto probablemente toma alguna consideración en el diseño de la estructura mundial del juego de datos de una manera apropiada. Lamentablemente, no soy un experto en estos asuntos. Definitivamente debe ser algo más que una matriz NxM que se usaría como una estructura de datos mutable. Probablemente debería consistir en piezas más pequeñas (corredores? Celdas individuales?) Que se apuntan entre sí, como lo hacen los nodos de los árboles.

9000
fuente
3
+1: Por señalar el libro de Okasaki. No lo he leído pero está en mi lista de tareas. Creo que lo que representaste es la solución correcta. Como alternativa, puede considerar los tipos de unicidad (Clean, en.wikipedia.org/wiki/Uniqueness_type ): utilizando este tipo de tipos puede actualizar de forma destructiva los objetos de datos mientras conserva la transparencia referencial.
Giorgio
¿Existe algún beneficio para las relaciones que se definirán mediante referencia indirecta mediante claves o identificadores? Es decir, estaba pensando que menos toques reales de una estructura a otra necesitarían menos enmiendas a la estructura mundial cuando se produce un cambio. ¿O esta técnica no se usa realmente en FP?
Mario T. Lanza
9

La respuesta de 9000 es la mitad de la respuesta, las estructuras de datos persistentes le permiten reutilizar partes sin cambios.

Es posible que ya esté pensando "oye, ¿y si quiero cambiar la raíz del árbol?" tal como está con el ejemplo dado que ahora significa cambiar todos los nodos. Aquí es donde las cremalleras vienen al rescate. Permiten cambiar el elemento en un foco en O (1), y el foco se puede mover a cualquier parte de la estructura.

El otro punto con las cremalleras es que existe una Cremallera para casi cualquier tipo de datos que desee

jk.
fuente
Me temo que me llevará algún tiempo profundizar en las "cremalleras", ya que estoy al margen de cualquiera que solo explore FP. No tengo experiencia con Haskell.
Mario T. Lanza
Intentaré agregar un ejemplo más tarde hoy
jk.
4

Los programas de estilo funcional crean muchas oportunidades como esa para usar la concurrencia. Cada vez que transforma, filtra o agrega una colección, y todo es puro o inmutable, existe la oportunidad de acelerar la operación por concurrencia.

Por ejemplo, suponga que realiza decisiones de IA de forma independiente y sin ningún orden en particular. No se turnan, todos toman una decisión simultáneamente y luego el mundo avanza. El código podría verse así:

func MakeMonsterDecision curWorldState monster =
    ...
    ...
    return monsterDecision

func NextWorldState curWorldState =
    ...
    let monsterMakeDecisionForCurrentState = MakeMonsterDecision curWorldState
    let monsterDecisions = List.map monsterMakeDecisionForCurrentState activeMonsters
    ...
    return newWorldState

Tienes una función para calcular lo que hará un monstruo dado un estado mundial, y aplicarlo a cada monstruo como parte de la computación del próximo estado mundial. Esto es algo natural en un lenguaje funcional, y el compilador es libre de realizar el paso 'aplicarlo a cada monstruo' en paralelo.

En un lenguaje imperativo, es más probable que iteres sobre cada monstruo, aplicando sus efectos al mundo. Es más fácil hacerlo de esa manera, porque no desea lidiar con la clonación o el alias complicado. El compilador no puede realizar los cálculos de monstruos en paralelo en ese caso, porque las primeras decisiones de monstruos afectan las decisiones de monstruos posteriores.

Craig Gidney
fuente
Eso ayuda bastante. Puedo ver cómo en un juego sería muy beneficioso que los monstruos decidieran simultáneamente qué hacer a continuación.
Mario T. Lanza
4

Escuchar algunas charlas de Rich Hickey, esta en particular, alivió mi confusión. En uno indicó que está bien que los procesos concurrentes no tengan el estado más actual. Necesitaba escuchar eso. Lo que tenía problemas para digerir era que los programas en realidad estarían de acuerdo con basar las decisiones en instantáneas del mundo que desde entonces han sido reemplazadas por otras más nuevas. Seguía preguntándome cómo el FP concurrente resolvió el problema de basar las decisiones en el estado anterior.

En una aplicación bancaria nunca desearíamos basar una decisión en una instantánea del estado que desde entonces ha sido reemplazada por una nueva (se produjo un retiro).

Esa concurrencia es fácil porque el paradigma de FP evita el estado mutable es una afirmación técnica que no intenta decir nada sobre los méritos lógicos de basar las decisiones en un estado potencialmente antiguo. FP todavía en última instancia modela el cambio de estado. No hay forma de evitar esto.

Mario T. Lanza
fuente
0

Los defensores de FP han afirmado que la concurrencia es fácil porque su paradigma evita el estado mutable. No lo entiendo

Quería hablar sobre esta pregunta general como alguien que es un neófito funcional pero que ha estado a la altura de mis ojos en los efectos secundarios a lo largo de los años y me gustaría mitigarlos, por todo tipo de razones, incluso más fácil (o específicamente "más seguro, menos concurrencia "). Cuando miro a mis compañeros funcionales y lo que están haciendo, la hierba parece un poco más verde y huele mejor, al menos en este sentido.

Algoritmos seriales

Dicho esto, sobre su ejemplo específico, si su problema es de naturaleza serial y B no se puede ejecutar hasta que A esté terminado, conceptualmente no puede ejecutar A y B en paralelo sin importar qué. Debe encontrar una manera de romper la dependencia del orden, como en su respuesta, basándose en hacer movimientos paralelos utilizando el estado del juego anterior, o usar una estructura de datos que permita modificar partes de ella de forma independiente para eliminar la dependencia del orden como se propone en las otras respuestas o algo por el estilo. Pero definitivamente hay una serie de problemas de diseño conceptual como este en los que no se puede simplemente multiprocesar todo tan fácilmente porque las cosas son inmutables. Algunas cosas serán de naturaleza serial hasta que encuentres una forma inteligente de romper la dependencia del orden, si eso es posible.

Simultaneidad más fácil

Dicho esto, hay muchos casos en los que no somos capaces de poner en paralelo los programas que implican efectos secundarios en los lugares que podrían mejorar potencialmente el rendimiento significativamente simplemente debido a la posibilidad de que podría no ser seguro para subprocesos. Uno de los casos en los que la eliminación del estado mutable (o más específicamente, los efectos secundarios externos) ayuda mucho, según veo, es que convierte "puede o no ser seguro para subprocesos" en "definitivamente seguro para subprocesos" .

Para hacer esa afirmación un poco más concreta, considere que le doy una tarea para implementar una función de clasificación en C que acepta un comparador y lo usa para ordenar una matriz de elementos. Está destinado a ser bastante generalizado, pero supondré fácilmente que se utilizará contra entradas de tal escala (millones de elementos o más) que sin duda será beneficioso utilizar siempre una implementación multiproceso. ¿Puedes multiprocesar tu función de clasificación?

El problema es que no puede porque los comparadores a los que llama su función de clasificación puedencausar efectos secundarios a menos que sepa cómo se implementan (o al menos se documentan) para todos los casos posibles, lo cual es imposible sin desgeneralizar la función. Un comparador podría hacer algo desagradable como modificar una variable global dentro de una manera no atómica. Es posible que el 99.9999% de los comparadores no hagan esto, pero aún no podemos multiprocesar esta función generalizada simplemente debido al 0.00001% de los casos que pueden causar efectos secundarios. Como resultado, es posible que deba ofrecer una función de clasificación de subprocesos múltiples y de subprocesos múltiples y transferir la responsabilidad a los programadores que la utilizan para decidir cuál usar en función de la seguridad de los subprocesos. Y las personas aún pueden usar la versión de subproceso único y perder oportunidades de subprocesos múltiples porque también pueden no estar seguros de si el comparador es seguro para subprocesos,

Hay una gran cantidad de capacidad intelectual que puede estar involucrada en la racionalización de la seguridad de las cosas sin tirar cerraduras a todas partes que pueden desaparecer si solo tuviéramos garantías firmes de que las funciones no causarán efectos secundarios por ahora y el futuro. Y hay miedo: miedo práctico, porque cualquiera que haya tenido que depurar una condición de carrera demasiadas veces probablemente dudaría en hacer múltiples subprocesos cualquier cosa de la que no pueda estar 110% seguro de que es seguro para subprocesos y permanecerá como tal. Incluso para los más paranoicos (de los cuales probablemente estoy al menos en el límite), la función pura proporciona esa sensación de alivio y confianza que podemos llamar con seguridad en paralelo.

Y ese es uno de los casos principales donde lo veo tan beneficioso si puede obtener una garantía sólida de que tales funciones son seguras para subprocesos que obtiene con lenguajes funcionales puros. El otro es que los lenguajes funcionales a menudo promueven la creación de funciones libres de efectos secundarios en primer lugar. Por ejemplo, podrían proporcionarle estructuras de datos persistentes donde es razonablemente bastante eficiente ingresar una estructura de datos masiva y luego generar una nueva con solo una pequeña parte de ella modificada del original sin tocar el original. Aquellos que trabajan sin tales estructuras de datos pueden querer modificarlos directamente y perder algo de seguridad de subprocesos en el camino.

Efectos secundarios

Dicho esto, no estoy de acuerdo con una parte con el debido respeto a mis amigos funcionales (que creo que son súper geniales):

[...] porque su paradigma evita el estado mutable.

No es necesariamente la inmutabilidad lo que hace que la concurrencia sea tan práctica como la veo. Son funciones que evitan causar efectos secundarios. Si una función ingresa una matriz para ordenar, la copia y luego muta la copia para ordenar su contenido y genera la copia, sigue siendo tan segura como una que trabaja con algún tipo de matriz inmutable, incluso si está pasando la misma entrada matriz de múltiples hilos. Así que creo que todavía hay un lugar para los tipos mutables en la creación de código muy amigable con la concurrencia, por así decirlo, aunque hay muchos beneficios adicionales para los tipos inmutables, incluidas las estructuras de datos persistentes que utilizo no tanto por sus propiedades inmutables sino para elimine el gasto de tener que copiar todo en profundidad para crear funciones libres de efectos secundarios.

Y a menudo hay gastos generales para hacer que las funciones estén libres de efectos secundarios en forma de barajar y copiar algunos datos adicionales, tal vez un nivel adicional de indirección, y posiblemente algo de GC en partes de una estructura de datos persistente, pero miro a uno de mis amigos que tiene una máquina de 32 núcleos y creo que el intercambio probablemente valga la pena si podemos hacer más cosas con confianza en paralelo.


fuente
1
"Estado mutable" siempre significa el estado en el nivel de aplicación, no el nivel de procedimiento. Eliminar punteros y pasar parámetros como valores de copia es una de las técnicas integradas en FP. Pero cualquier función útil tiene que mutar el estado en algún nivel: ¡el punto de la programación funcional es asegurar que el estado mutable que pertenece al llamante no ingrese al procedimiento, y las mutaciones no salgan del procedimiento excepto por los valores de retorno! Pero hay pocos programas que pueden hacer mucho trabajo sin mutar el estado en absoluto, y los errores siempre vuelven a aparecer en la interfaz.
Steve
1
Para ser sincero, la mayoría de los lenguajes modernos permiten utilizar un estilo funcional de programación (con un poco de disciplina) y, por supuesto, hay lenguajes dedicados a patrones funcionales. Pero es un patrón menos eficiente desde el punto de vista computacional, y se exagera popularmente como una solución a todos los males, como lo era la orientación a objetos en los años 90. La mayoría de los programas no están sujetos a cálculos intensivos de CPU que se beneficiarían de la paralelización, y de los que sí lo están, a menudo se debe a la dificultad de razonar, diseñar e implementar el programa de una manera susceptible de ejecución paralela.
Steve
1
La mayoría de los programas que se ocupan del estado mutable, lo hacen porque tienen que hacerlo por una razón u otra. Y la mayoría de los programas no son incorrectos porque usan el estado compartido o lo actualizan de manera anómala; generalmente es porque reciben basura inesperada como entrada (que determina una salida de basura) o porque operan incorrectamente en sus entradas (incorrectamente en el sentido del propósito para ser alcanzado). Los patrones funcionales hacen poco para abordar esto.
Steve
1
@ Steve, al menos podría estar de acuerdo con usted, ya que estoy en el lado de solo explorar formas de hacer las cosas de una manera más segura desde los lenguajes como C o C ++, y realmente no creo que necesitemos ser completos soplado puro funcional para hacerlo. Pero encuentro que al menos algunos de los conceptos en FP son útiles. Acabo de terminar de escribir una respuesta sobre cómo encontrar PDS útil aquí, y la ventaja más grande que encuentro sobre el PDS en realidad no es multi-hilos de seguridad, pero cosas como de instancias, la edición no destructiva, la seguridad excepción, deshacer simples, etc: