Rein funktionale Datenstrukturen mit Copy-on-Write?

Question

Ich möchte den Vorteil von funktionalen Datenstrukturen (mehrere Versionen von Daten, die Struktur teilen können) haben, aber in der Lage sein, es in einem imperativen Stil zu ändern.

Was ich denke (und eine mögliche Verwendung): ein RPG-Spiel, in dem ganze Spielhistorie gespeichert ist (zum Beispiel, um eine Reise in die Vergangenheit zu ermöglichen). Mit Copy-on-Write könnte ich einfach die Struktur, die den Spielstatus hält, klonen und sie modifizieren, indem ich eine neue Runde einführe - aber habe Zugriff auf die früheren Runden (nicht notwendigerweise alle, vielleicht nur ausgewählte Schnappschüsse des Spielstatus), ohne die Strafe, jedes Mal alles kopieren zu müssen.

---

Sagen wir foo ist eine Karte.

bar = foo.clone() 

Nichts von foo ‚s-Struktur (zB Baum) wird noch kopiert. von jetzt an bar wird als Kopie behandelt und keine Änderungen dürfen zurück zu `foo 'propagieren. Jetzt

baz = bar[someKey] 
baz.modifyInSomeWay() 

• ein neues Objekt erstellt wird, das ist eine modifizierte Kopie von baz.
• bar ist mit einer neuen Karte ersetzt, das Halten neue baz (möglicherweise einige foo ‚s Struktur beibehalten).
• foo ist nicht betroffen.

Aber wenn wir dann tun ...

baz.modifyAgain() 

... baz kann nur geändert werden, weil wir eine neue Version davon haben. bar muss nicht geändert werden.

All dies erfordert hält einige Versionsinformationen über foo und bar, es auf foo.clone() erhöht und es baz irgendwie vorbei (indem sie es ein Proxy-Objekt?).

Auch jeder Teil der Struktur, der geklont wurde, wird zu einem "Teil der Historie" und kann nicht mehr geändert werden, was zur Laufzeit erzwungen werden könnte.

---

Dies ähnelt Prototypen ein bisschen des JavaScript, aber ich, dass es mehr als es nach oben für Änderungen fortzupflanzen ermöglicht. Ich denke, es wäre so etwas wie ein Versionskontrollsystem.

• Wurde dies getan, und in welchem ​​Umfang?
• Ist das eine gute Idee? Wenn nicht, gibt es eine Möglichkeit, es zu speichern?
• Wie könnte es implementiert werden? Ich dachte darüber nach, es auf einer höheren GC-ed-Sprache wie Python aufzubauen.

Answer 1

Functional ("persistent") data structures werden typischerweise rekursiv aus unveränderlichen Knoten (zB einzeln verknüpfte Liste in den gemeinsamen Suffixe wird geteilt, Suchbaum oder Heap aufgebaut, wo nur die Teile der Baumstruktur, die von der Wurzel zu dem aktualisierte auf dem Weg ist, Artikel muss kopiert werden).

Alles, wo der gesamte Satz für jede Änderung kopiert werden muss, ist schlecht. In diesen Fällen neigen Sie dazu, kleine "diffs" zu überlagern, die mit Rekursion zu früheren Versionen überprüft werden (was zusätzliche Zeit in Anspruch nimmt). Hin und wieder, wenn die Diffs zu groß werden, könntest du eine tiefe Kopie/Wiederherstellung machen (also sind die amortisierten Kosten nicht so schlecht).

Persistente Datenstrukturen können einen erheblichen Mehraufwand verursachen, aber wenn Sie sehr effizient kleine Objekte zuweisen (JVM GC qualifiziert), können sie sehr praktisch sein - im besten Fall genauso schnell wie das änderbare Äquivalent, das nur Persistenz ergibt auf Kosten des verwendeten Speichers - was bei jedem Update viel weniger als eine vollständige Kopie sein kann.

Abhängig von Ihrer Sprache werden Sie wahrscheinlich die gewünschte Syntax finden, ohne dass der Operator für die Zuweisung überlastet wird. L-Werte (veränderbare Referenzen) in C++ erfordern definitiv nicht persistente Semantik.

Answer 2

Das klingt furchtbar verschlungen und fehleranfällig im Vergleich zu einer völlig unveränderlichen Datenstruktur und dann mit einem Wrapper, der einen Verweis darauf enthält und eine imperative Schnittstelle darstellt, die durch Aktualisieren der verpackten Version funktioniert.

z.B. in Scala

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

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

Sicher, es bedeutet, dass Sie zwei Versionen der Schnittstelle machen, aber die Semantik ist viel vernünftigere.

Answer 3

1. Ist das in welchem ​​Umfang geschehen?

Ja, siehe zum Beispiel qt5 implicit sharing.

2. Ist das eine gute Idee? Wenn nicht, gibt es eine Möglichkeit, es zu speichern?

Ja, es ist eine gute Idee. Eine der vorgeschlagenen Alternativen besteht darin, eine vollständig unveränderbare Datenstruktur zu verwenden (in eine imperative Schnittstelle eingeschlossen), aber das Problem besteht darin, dass selbst wenn ein Objekt auf Daten verweist, eine Modifikationsoperation eine Kopie der Daten erzeugt (Es gibt kein Update), das ist ineffizient. Beim Kopiervorgang wird eine Kopie nur in der ersten Änderung erstellt, bei nachfolgenden Änderungen werden die kopierten Daten geändert (wenn nicht ein anderer Verweis auf die gleichen Daten erstellt wurde).

3. Wie könnte es implementiert werden? Ich dachte darüber nach, es auf einer höheren GC-ed-Sprache wie Python aufzubauen.

Ein Weg ist, Referenzzählung, wie in Qt zu verwenden (siehe eine Beschreibung here). Um es zu implementieren, erfordert entweder Zuweisungsoperator Überladung oder einen expliziten Methodenaufruf (wie bar = foo.clone(), aber es kann fragil sein, was passiert, wenn jemand vergisst, clone aufrufen und tun Sie einfach bar = foo?), So dass die Zählung beibehalten werden kann.

Andere Möglichkeit, ein Proxy-Objekt zu erstellen, wie Sie sagten. Siehe zum Beispiel eine pycow (eine Python-Implementierung).