¿Cómo maneja la programación funcional la situación en la que se hace referencia al mismo objeto desde múltiples lugares?

10

Estoy leyendo y escuchando que las personas (también en este sitio) elogian rutinariamente el paradigma de la programación funcional, haciendo hincapié en lo bueno que es tener todo inmutable. En particular, las personas proponen este enfoque incluso en lenguajes OO tradicionalmente imperativos, como C #, Java o C ++, no solo en lenguajes puramente funcionales como Haskell que fuerzan esto en el programador.

Me resulta difícil de entender, porque encuentro la mutabilidad y los efectos secundarios ... convenientes. Sin embargo, dada la forma en que las personas actualmente condenan los efectos secundarios y consideran que es una buena práctica deshacerse de ellos siempre que sea posible, creo que si quiero ser un programador competente tengo que comenzar mi viaje hacia una mejor comprensión del paradigma ... De ahí mi Q.

Un lugar cuando encuentro problemas con el paradigma funcional es cuando un objeto es referenciado naturalmente desde múltiples lugares. Permítanme describirlo en dos ejemplos.

El primer ejemplo será mi juego C # que intento hacer en mi tiempo libre . Es un juego web por turnos en el que ambos jugadores tienen equipos de 4 monstruos y pueden enviar un monstruo de su equipo al campo de batalla, donde se enfrentará al monstruo enviado por el jugador contrario. Los jugadores también pueden recuperar monstruos del campo de batalla y reemplazarlos con otro monstruo de su equipo (de manera similar a Pokemon).

En esta configuración, se puede hacer referencia natural a un solo monstruo desde al menos 2 lugares: el equipo de un jugador y el campo de batalla, que hace referencia a dos monstruos "activos".

Ahora consideremos la situación cuando un monstruo es golpeado y pierde 20 puntos de vida. Dentro de los paréntesis del paradigma imperativo modifico el healthcampo de este monstruo para reflejar este cambio, y esto es lo que estoy haciendo ahora. Sin embargo, esto hace que la Monsterclase sea mutable y las funciones relacionadas (métodos) impuras, lo que supongo que se considera una mala práctica a partir de ahora.

Aunque me di permiso para tener el código de este juego en un estado menos que ideal para tener alguna esperanza de terminarlo en algún momento del futuro, me gustaría saber y entender cómo debería ser escrito correctamente Por lo tanto: si se trata de un defecto de diseño, ¿cómo solucionarlo?

En el estilo funcional, tal como lo entiendo, en su lugar haría una copia de este Monsterobjeto, manteniéndolo idéntico al anterior excepto por este campo; y el método suffer_hitdevolvería este nuevo objeto en lugar de modificar el antiguo en su lugar. Luego también copiaría el Battlefieldobjeto, manteniendo todos sus campos iguales, excepto este monstruo.

Esto viene con al menos 2 dificultades:

  1. La jerarquía puede ser mucho más profunda que este ejemplo simplificado de solo Battlefield-> Monster. Tendría que hacer esa copia de todos los campos excepto uno y devolver un nuevo objeto en toda esta jerarquía. Este sería un código repetitivo que encuentro molesto, especialmente porque se supone que la programación funcional reduce el repetitivo.
  2. Sin embargo, un problema mucho más grave es que esto llevaría a que los datos no estén sincronizados . El monstruo activo del campo vería reducida su salud; sin embargo, este mismo monstruo, al que hace referencia su jugador controlador Team, no lo haría. Si en cambio adoptara el estilo imperativo, cada modificación de datos sería visible instantáneamente desde todos los demás lugares del código y en casos como este me parece realmente conveniente, pero la forma en que obtengo las cosas es precisamente lo que la gente dice que es mal con el estilo imperativo!
    • Ahora sería posible solucionar este problema haciendo un viaje al Teamdespués de cada ataque. Este es un trabajo extra. Sin embargo, ¿qué pasa si de repente se puede hacer referencia a un monstruo desde incluso más lugares? ¿Qué sucede si vengo con una habilidad que, por ejemplo, permite que un monstruo se enfoque en otro monstruo que no está necesariamente en el campo (en realidad estoy considerando tal habilidad)? ¿ Recordaré seguramente hacer un viaje a los monstruos enfocados inmediatamente después de cada ataque? Esto parece ser una bomba de tiempo que explotará a medida que el código se vuelva más complejo, por lo que creo que no es una solución.

Una idea para una mejor solución proviene de mi segundo ejemplo, cuando llego al mismo problema. En la academia nos dijeron que escribiéramos un intérprete de un lenguaje de nuestro propio diseño en Haskell. (Así es como me vi obligado a comenzar a entender qué es FP). El problema apareció cuando estaba implementando cierres. Una vez más, se puede hacer referencia al mismo ámbito desde varios lugares: a través de la variable que contiene este ámbito y como el ámbito principal de cualquier ámbito anidado. Obviamente, si se realiza un cambio en este alcance a través de cualquiera de las referencias que lo apuntan, este cambio también debe ser visible a través de todas las demás referencias.

La solución con la que vine fue asignar a cada ámbito una ID y mantener un diccionario central de todos los ámbitos de la Statemónada. Ahora las variables solo contendrían la ID del ámbito al que estaban vinculadas, en lugar del ámbito en sí, y los ámbitos anidados también contendrían la ID de su ámbito principal.

Supongo que podría intentarse el mismo enfoque en mi juego de lucha de monstruos ... Los campos y los equipos no hacen referencia a los monstruos; en su lugar, tienen identificaciones de monstruos que se guardan en un diccionario central de monstruos.

Sin embargo, una vez más puedo ver un problema con este enfoque que me impide aceptarlo sin dudarlo como la solución al problema:

Una vez más es una fuente de código repetitivo. Hace que las líneas simples sean necesariamente 3 líneas: lo que antes era una modificación en el lugar de una línea de un solo campo ahora requiere (a) Recuperar el objeto del diccionario central (b) Realizar el cambio (c) Guardar el nuevo objeto al diccionario central. Además, mantener identificadores de objetos y diccionarios centrales en lugar de tener referencias aumenta la complejidad. Dado que FP se anuncia para reducir la complejidad y el código repetitivo, esto sugiere que lo estoy haciendo mal.

También iba a escribir sobre un segundo problema que parece mucho más grave: este enfoque introduce pérdidas de memoria . Los objetos inalcanzables normalmente serán basura recolectada. Sin embargo, los objetos contenidos en un diccionario central no se pueden recolectar basura, incluso si ningún objeto accesible hace referencia a esta ID en particular. Y si bien la programación teóricamente cuidadosa puede evitar pérdidas de memoria (podríamos tener cuidado de eliminar manualmente cada objeto del diccionario central una vez que ya no sea necesario), esto es propenso a errores y se anuncia FP para aumentar la corrección de los programas, por lo que una vez más, esto puede No sea la forma correcta.

Sin embargo, descubrí a tiempo que parece ser un problema resuelto. Java proporciona WeakHashMapque podría usarse para resolver este problema. C # proporciona una instalación similar ConditionalWeakTable, aunque, según los documentos, debe ser utilizada por los compiladores. Y en Haskell tenemos System.Mem.Weak .

¿Almacenar tales diccionarios es la solución funcional correcta para este problema o hay uno más simple que no puedo ver? Me imagino que el número de dichos diccionarios puede crecer fácilmente y de forma negativa; así que si se supone que estos diccionarios también son inmutables, esto puede significar una gran cantidad de paso de parámetros o, en idiomas que lo admitan, cálculos monádicos, ya que los diccionarios se mantendrían en mónadas (pero una vez más, estoy leyendo eso en términos puramente funcionales los idiomas con el menor código posible deberían ser monádicos, mientras que esta solución de diccionario colocaría casi todo el código dentro de la Statemónada; lo que una vez más me hace dudar si esta es la solución correcta).

Después de considerarlo, creo que agregaría una pregunta más: ¿Qué estamos ganando al construir tales diccionarios? Lo que está mal con la programación imperativa es, según muchos expertos, que los cambios en algunos objetos se propagan a otras piezas de código. Para resolver este problema, se supone que los objetos son inmutables, precisamente por esta razón, si entiendo correctamente, que los cambios realizados en ellos no deberían ser visibles en otro lugar. Pero ahora estoy preocupado por otras piezas de código que funcionan con datos obsoletos, así que invento diccionarios centrales para que ... una vez más, los cambios en algunas piezas de código se propaguen a otras piezas de código. ¿No volvemos, por lo tanto, al estilo imperativo con todos sus supuestos inconvenientes, pero con una complejidad adicional?

gaazkam
fuente
66
Para darle a esto una cierta perspectiva, los programas funcionales inmutables están destinados principalmente a situaciones de procesamiento de datos que involucran concurrencia. En otras palabras, programas que procesan datos de entrada a través de un conjunto de ecuaciones o procesos que producen un resultado de salida. La inmutabilidad ayuda en este escenario por varias razones: se garantiza que los valores que leen múltiples subprocesos no cambien durante su vida útil, lo que simplifica enormemente la capacidad de procesar los datos de una manera libre de bloqueo y la razón sobre cómo funciona el algoritmo.
Robert Harvey
8
El pequeño secreto sucio sobre la inmutabilidad funcional y la programación de juegos es que esas dos cosas son incompatibles entre sí. Básicamente, está tratando de modelar un sistema dinámico y en constante cambio utilizando una estructura de datos estática e inamovible.
Robert Harvey
2
No tome la mutabilidad frente a la inmutabilidad como un dogma religioso. Hay situaciones en las que cada una es mejor que la otra, la inmutabilidad no siempre es mejor, por ejemplo, escribir un kit de herramientas GUI con tipos de datos inmutables será una pesadilla absoluta.
cuál es el
1
Esta pregunta específica de C # y sus respuestas cubren el tema de repetitivo, principalmente como resultado de la necesidad de crear clones ligeramente modificados (actualizados) de un objeto inmutable existente.
rwong
2
Una idea clave es que un monstruo en este juego se considera una entidad. Además, el resultado de cada batalla (que consiste en el número de secuencia de batalla, las identificaciones de entidad de los monstruos, los estados de los monstruos antes y después de la batalla) se considera un estado en un determinado punto de tiempo (o paso de tiempo). Por lo tanto, los jugadores ( Team) pueden recuperar el resultado de la batalla y, por lo tanto, los estados de los monstruos mediante una tupla (número de batalla, ID de entidad de monstruo).
rwong

Respuestas:

19

¿Cómo maneja la programación funcional un objeto referenciado desde múltiples lugares? ¡Te invita a volver a visitar tu modelo!

Para explicar ... veamos cómo a veces se escriben los juegos en red, con una copia central "dorada" del estado del juego y un conjunto de eventos de clientes entrantes que actualizan ese estado, y luego se transmiten a los otros clientes .

Puede leer sobre la diversión que tuvo el equipo de Factorio al lograr que esto se comportara bien en algunas situaciones; Aquí hay una breve descripción de su modelo:

La forma básica en que funciona nuestro modo multijugador es que todos los clientes simulan el estado del juego y solo reciben y envían la entrada del jugador (llamada Acciones de entrada). La principal responsabilidad del servidor es representar las acciones de entrada y asegurarse de que todos los clientes ejecuten las mismas acciones en la misma marca.

Dado que el servidor necesita arbitrar cuando se ejecutan acciones, una acción del jugador mueve algo como esto: Acción del jugador -> Cliente del juego -> Red -> Servidor -> Red-> Cliente del juego. Esto significa que cada acción del jugador solo se ejecuta una vez que realiza un viaje de ida y vuelta a través de la red. Esto haría que el juego se sintiera realmente lento, por eso la ocultación de latencia fue un mecanismo agregado en el juego casi desde la introducción del modo multijugador. La ocultación de latencia funciona simulando la entrada del jugador, sin considerar las acciones de otros jugadores y sin considerar el arbitraje del servidor.

En Factorio tenemos el estado del juego, este es el estado completo del mapa, jugador, derechos, todo. Se simula determinísticamente en todos los clientes en función de las acciones recibidas del servidor. Esto es sagrado y si alguna vez es diferente del servidor o cualquier otro cliente, se produce una desincronización.

En la parte superior del estado del juego tenemos el estado de latencia. Contiene un pequeño subconjunto del estado principal. El estado de latencia no es sagrado y solo representa cómo pensamos que se verá el estado del juego en el futuro según las acciones de entrada que realizó el jugador.

La clave es que el estado de cada objeto es inmutable en el tic específico en la línea de tiempo . Todo en el estado global multijugador debe finalmente converger en una realidad determinista.

Y, esa podría ser la clave de su pregunta. El estado de cada entidad es inmutable para un tic determinado, y realiza un seguimiento de los eventos de transición que producen nuevas instancias a lo largo del tiempo.

Si lo piensa, la cola de eventos entrantes del servidor debe tener acceso a un directorio central de entidades, solo para que pueda aplicar sus eventos.

Al final, sus métodos simples de mutadores de una línea que no desea complicar son solo simples porque realmente no está modelando el tiempo con precisión. Después de todo, si la salud puede cambiar en el medio del ciclo de procesamiento, las entidades anteriores en este tic verán un valor antiguo y las posteriores verán un valor cambiado. Gestionar esto con cuidado significa al menos diferenciar los estados actuales (inmutables) y siguientes (en construcción), ¡que en realidad son solo dos ticks en la gran línea de tiempo de ticks!

Entonces, como una guía amplia, considere dividir el estado de un monstruo en varios objetos pequeños que se relacionan, por ejemplo, con la ubicación / velocidad / física, salud / daño, activos. Construya un evento para describir cada mutación que pueda ocurrir, y ejecute su ciclo principal como:

  1. procesar entradas y generar eventos correspondientes
  2. generar eventos internos (por ejemplo, debido a colisiones de objetos, etc.)
  3. aplique eventos a los monstruos inmutables actuales, para generar nuevos monstruos para el próximo tic, principalmente copiando el estado antiguo sin cambios donde sea posible, pero creando nuevos objetos de estado donde sea necesario.
  4. renderizar y repetir para el próximo tic.

O algo así. Me parece pensar "¿cómo haría que esto se distribuya?" Es un buen ejercicio mental, en general, para refinar mi comprensión cuando estoy confundido acerca de dónde viven las cosas y cómo deberían evolucionar.

Gracias a una nota de @ AaronM.Eshbach, destacando que este es un dominio de problema similar al de Abastecimiento de eventos y el patrón CQRS , donde está modelando cambios de estado en un sistema distribuido como una serie de eventos inmutables a lo largo del tiempo . En este caso, lo más probable es que intentemos limpiar una aplicación de base de datos compleja, segregando (como su nombre lo indica) el manejo del comando del mutador del sistema de consulta / vista. Más complejo, por supuesto, pero más flexible.

SusanW
fuente
2
Para una referencia adicional, vea Event Sourcing y CQRS . Este es un dominio de problema similar: el modelado cambia al estado en un sistema distribuido como una serie de eventos inmutables a lo largo del tiempo.
Aaron M. Eshbach
@ AaronM.Eshbach ese es el! ¿Te importa si incluyo tu comentario / citas en la respuesta? Hace que suene más autoritario. ¡Gracias!
SusanW
Por supuesto que no, por favor hazlo.
Aaron M. Eshbach
3

Todavía estás a medias en el campamento imperativo. En lugar de pensar en un solo objeto a la vez, piense en su juego en términos de un historial de jugadas o eventos

p1 - send m1 to battlefield
p2 - send m2 to battlefield
m1 - attacks m2 (2 dam)
m2 - attacks m1 (10 dam)
p1 - retreats m1

etc.

Puede calcular el estado del juego en cualquier punto dado encadenando las acciones para producir un objeto de estado inmutable. Cada jugada es una función que toma un objeto de estado y devuelve un nuevo objeto de estado

Ewan
fuente