Strutture dati puramente funzionali con copy-on-write?

Question

Voglio avere il vantaggio di strutture dati funzionali (più versioni di dati che possono condividere la struttura) ma essere in grado di modificarlo in uno stile imperativo.

Cosa sto pensando (e un possibile utilizzo): un gioco RPG in cui è memorizzata la cronologia di un gioco intero (ad esempio, per consentire di viaggiare indietro nel tempo). Usando copy-on-write, potrei semplicemente clonare la struttura tenendo lo stato del gioco e modificarlo introducendo un nuovo turno - ma ho accesso ai turni precedenti (non necessariamente tutti, forse solo le istantanee selezionate dello stato del gioco), senza il pena di dover copiare tutto ogni volta.

---

Diciamo che foo è una mappa.

bar = foo.clone() 

Nulla di struttura foo s'(ad esempio, l'albero) viene ancora copiato. Tuttavia, da oggi viene considerato come una copia e nessuna modifica è consentita per propagare indietro a "pippo".

baz = bar[someKey] 
baz.modifyInSomeWay() 

Ora

• un nuovo oggetto viene creato, che è una copia modificata di baz.
• bar viene sostituito con una nuova mappa, con nuovo baz (possibilmente mantenendo una parte della struttura di foo).
• foo non è interessato.

Ma se poi facciamo ...

baz.modifyAgain() 

... baz può essere solo modificata, perché abbiamo una versione recente di esso. bar non ha bisogno di essere cambiato.

Tutto questo richiede contenente alcune informazioni sulla versione foo e bar, aumentandola su foo.clone(), e passarlo a baz in qualche modo (rendendolo un oggetto proxy?).

Inoltre, qualsiasi parte della struttura che è stata clonata diventa una "parte della cronologia" e non può più essere modificata, che potrebbe essere applicata in fase di esecuzione.

---

Questo assomiglia prototipi di JavaScript un po ', ma mi è più in quanto consente per le modifiche per propagarsi verso l'alto. Penso che sarebbe qualcosa di simile a un sistema di controllo della versione.

• È stato fatto e in quale misura?
• È una buona idea? Se no, c'è un modo per salvarlo?
• Come potrebbe essere implementato? Stavo pensando di costruirlo sopra un linguaggio GC di alto livello, come Python.

Answer 1

Functional ("persistent") data structures sono in genere in modo ricorsivo costruiti fuori dei nodi immutabili (ad esempio, la lista concatenata in cui sono condivisi suffissi comuni, albero di ricerca o heap in cui solo le parti della struttura ad albero che si trovano sul percorso dalla radice alla aggiornata oggetto deve copiare).

Tutto ciò che è necessario copiare l'intero set per ogni modifica è errato. In questi casi, si tende a sovrapporre le piccole "diff" che vengono controllate (impiegando più tempo) con la ricorsione alle versioni precedenti. Ogni tanto, quando le differenze diventano troppo grandi, si può fare una copia/ricostruzione profonda (quindi il costo ammortizzato non è così male).

Le strutture di dati persistenti possono avere un sovraccarico significativo, ma se si dispone di un'allocazione molto efficiente di oggetti di piccole dimensioni (JVM GC si qualifica), possono essere molto pratici - nel migliore dei casi, altrettanto veloce quanto l'equivalente mutabile, dando solo persistenza al costo della memoria utilizzata - che può essere molto meno di una copia completa su ogni aggiornamento.

A seconda della lingua, probabilmente troverai la sintassi che desideri ottenere senza l'overloading dell'operatore per l'assegnazione. I lvalue (riferimenti mutabili) in C++ richiedono sicuramente una semantica non persistente.

Answer 2

Sembra tremendamente convoluto e soggetto a errori rispetto alla semplice struttura dei dati immutabile e quindi utilizza un wrapper che contiene un riferimento ad esso e espone un'interfaccia imperativa che funziona aggiornando la versione avvolta.

ad es. in Scala

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

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

Certo, significa che devi fare due versioni dell'interfaccia, ma la semantica è molto più sicura.

Answer 3

1. È stato fatto e in quale misura?

Sì, vedere ad esempio qt5 implicit sharing.

2. È una buona idea? Se no, c'è un modo per salvarlo?

Sì, è una buona idea. Una delle alternative proposte è quella di utilizzare una struttura dati completamente immutabile (racchiusa in un'interfaccia imperativa), ma il problema è che anche se un oggetto è l'unico a puntare a un dato, un'operazione di modifica creerà una copia dei dati (non c'è aggiornamento sul posto), questo è inefficiente. Usando l'approccio copy on write, una copia viene eseguita solo nella prima modifica, le modifiche successive alterano i dati copiati in posizione (se non è stato creato un altro riferimento agli stessi dati, fuori rotta).

3. Come può essere implementato? Stavo pensando di costruirlo sopra un linguaggio GC di alto livello, come Python.

Un modo è utilizzare il conteggio dei riferimenti, come in qt (vedere la descrizione here). Per implementarlo sarà necessario l'overloading dell'operatore di assegnazione o una chiamata al metodo esplicita (come bar = foo.clone(), ma potrebbe essere fragile, cosa succede se qualcuno dimentica di chiamare clone e basta fare bar = foo?), Quindi il conteggio può essere mantenuto.

Altra possibilità di creare un oggetto proxy, come hai detto tu. Si veda ad esempio uno pycow (un'implementazione python).