Estructuras de datos puramente funcionales con copy-on-write?

Question

Quiero tener la ventaja de las estructuras de datos funcionales (múltiples versiones de datos que pueden compartir estructura) pero ser capaz de modificarlo en un estilo imperativo.

Lo que estoy pensando (y un posible uso): un juego de rol en el que se almacena el historial completo del juego (por ejemplo, para permitir viajar en el tiempo). Usando copy-on-write, podría simplemente clonar la estructura que contiene el estado del juego y modificarlo introduciendo un nuevo turno, pero tener acceso a los turnos anteriores (no necesariamente todos, tal vez solo instantáneas seleccionadas del estado del juego), sin el pena de tener que copiar todo todo el tiempo.

---

Digamos foo es un mapa.

bar = foo.clone() 

Nada de la estructura foo 's (por ejemplo, árbol) es copiado todavía. Sin embargo, a partir de ahora bar se trata como una copia y no se permiten cambios para propagar de nuevo a `foo '.

baz = bar[someKey] 
baz.modifyInSomeWay() 

Ahora

• un nuevo objeto se crea, que es una copia modificada de baz.
• bar se reemplaza con un nuevo mapa, con el nuevo baz (posiblemente conservando parte de la estructura de foo).
• foo no se ve afectado.

Pero si luego hacemos ...

baz.modifyAgain() 

... baz puede ser sólo modificada, porque tenemos una versión reciente de la misma. bar no necesita ser cambiado.

Todo esto requiere mantener una cierta información sobre la versión de foo y bar, aumentarla en foo.clone(), y pasándolo a baz alguna manera (por lo que es un objeto proxy?).

Además, cualquier parte de la estructura que ha sido clonada se convierte en una 'parte de la historia' y ya no se puede cambiar, lo que podría aplicarse en tiempo de ejecución.

---

Esto se asemeja a prototipos de JavaScript un poco, pero lo que es más, ya que permite que los cambios para propagar hacia arriba. Creo que sería algo así como un sistema de control de versiones.

• ¿Se ha hecho esto y en qué medida?
• ¿Es esta una buena idea? Si no, ¿hay alguna manera de salvarlo?
• ¿Cómo podría implementarse? Estaba pensando en construirlo sobre algún lenguaje GC-ed de alto nivel, como Python.

Answer 1

Functional ("persistent") data structures son normalmente de forma recursiva construyeron subir de nodos inmutables (por ejemplo, lista enlazada, donde se comparten sufijos comunes, árbol de búsqueda o montón, donde sólo las partes de la estructura de árbol que están en el camino de la raíz a la actualización el artículo necesita copiarse).

Cualquier cosa donde se deba copiar todo el conjunto para cada modificación es incorrecta. En esos casos, tiende a superponer pequeñas "diffs" que se controlan (tomando tiempo extra) con recurrencia a versiones anteriores. De vez en cuando, cuando los diferenciales son demasiado grandes, puede hacer una copia/reconstrucción profunda (para que el costo amortizado no sea tan malo).

Las estructuras de datos persistentes pueden tener una sobrecarga significativa, pero si tiene una asignación muy eficiente de objetos pequeños (JVM GC califica), pueden ser muy prácticas; en el mejor de los casos, igual de rápidas que el equivalente mutable, dando solo persistencia a costa de la memoria utilizada, que puede ser mucho menos que una copia completa en cada actualización.

Dependiendo de su idioma, probablemente encontrará la sintaxis que desea lograr sin la sobrecarga del operador para la asignación. Los valores L (referencias mutables) en C++ definitivamente requieren una semántica no persistente.

Answer 2

Esto suena terriblemente intrincado y propenso a errores en comparación con tener una estructura de datos completamente inmutable y luego utilizar un contenedor que contiene una referencia y expone una interfaz imperativa que funciona mediante la actualización de la versión envuelta.

p. Ej. en Scala

class ImmutableData{ 
    def doStuff(blah : Blah) : ImmutableData = implementation 
} 

class MutableData(var wrapped : ImmutableData){ 
    def doStuff(blah : Blah) : Unit = { wrapped = wrapped.doStuff(blah); } 
} 

Claro que significa que tiene que hacer dos versiones de la interfaz, pero la semántica es una cuerdo mucho.

Answer 3

1. ¿Se ha hecho esto y en qué medida?

Sí, ver por ejemplo qt5 implicit sharing.

2. ¿Es esta una buena idea? Si no, ¿hay alguna manera de salvarlo?

Sí, es una buena idea. Una de las alternativas propuestas es utilizar una estructura de datos totalmente inmutables (envuelta en una interfaz imperativa), pero el problema es que incluso si un objeto es el único que apunta a un dato, una operación de modificación creará una copia de los datos. (no hay una actualización en su lugar), esto es ineficiente. Usando el enfoque de copiar al escribir, una copia se hace solo en la primera modificación, las modificaciones posteriores alteran los datos copiados en su lugar (si no se creó otra referencia a los mismos datos, fuera del curso).

3. ¿Cómo podría implementarse? Estaba pensando en construirlo sobre algún lenguaje GC-ed de alto nivel, como Python.

Una forma es utilizar el recuento de referencias, como en qt (ver una descripción here). Para su implementación se requiere ya sea la sobrecarga de operadores de asignación o una llamada de método explícito (como bar = foo.clone(), pero puede ser frágil, lo que pasa si alguien se olvide de llamar clone y sólo hacer bar = foo?), Por lo que el conteo se puede mantener.

Otra posibilidad en Tho crear un objeto proxy, como usted ha dicho. Ver por ejemplo un pycow (una implementación de python).