copy-on-write für verschachtelte Strukturen

[Rüdiger (Gast)]

Ich versuche gerade, das copy-on-write-Konzept für eine einfache 
Skriptsprache umzusetzen.

Die Idee dahinter ist ja, wenn ich z.B. ein großes Array habe
 A=[1...1000000]
und nun B als Kopie von A erzeuge:
 B=A
dann wird in B zunächst nur eine Referenz zu A gespeichert.
Erst wenn ich B modifiziere, z.B.
 B[42]=999
dann erstellt B eine "echte" Kopie von A und ändert dort Element #42.

Ich stehe nun auf dem Schlauch, wie das bei verschachtelten Strukturen 
(ähnlich JSON Objekten) funktioniert. Sagen wir, ich habe eine Struktur
 S={x: 42}
Nun setze ich
 S.x=S
Das Ergebnis sollte dann sein:
 S={x: {x: 42}}
Tatsächlich würde das copy-on-write-Konzept aber nahelegen, folgendes 
Ergebnis zu erzeugen:
 S={x: S}
Dies ist eine unbrauchbare endlose Rekursion.
Woran kann der Interpreter erkennen, dass er in diesem Fall für S.x eine 
echte Kopie von S erstellen muss? S enthält nach S={x:42} seine eigenen 
Daten, keine Referenz, und muss daher eigentlich keine Kopie erzeugen, 
wenn eins seiner Elemente überschrieben wird.

Von daher sehe ich kein direktes Kriterium, wonach der Interpreter 
entscheiden kann, dass er im Schritt S.x=S eine neue Kopie erstellen 
muss.

Ist das Problem verständlich?

[The D. (thedaz)]

Bin jetzt kein Experte aber meine Vermutung: Du müsstest S als Referenz 
vom Inhalt von S sprachlich unterscheiden können. Wie sonst würdest du 
bei einer Operation wie S=S vermeiden, daß Objekt zu versauen?

[Rüdiger (Gast)]

Erst einmal, sprachlich wird nicht zwischen der Referenz und dem 
Inhalt von S unterschieden. Die Wirkung ist immer, als ob der Inhalt 
benutzt wird. Nur der Interpreter optimiert das, indem er z.B. für "T=S" 
statt einer Kopie des Inhalts sich in T zunächst nur eine Referenz zu S 
merkt. Erst wenn T modifiziert wird, erstellt er eine Kopie von S und 
vergisst die Referenz.

Dein Beispiel "S=S" ist ähnlich meinem (umständlichen) Beispiel aus dem 
vorherigen Post ein Level einfacher. Entsprechend copy-on-write würde 
der Interpreter für den Befehl "S=S" S als eine Referenz auf sich selbst 
erstellen. Auch hier müsste erkannt werden, dass eine ungewollt 
rekursive Struktur entsteht, und dass stattdessen direkt eine Kopie 
erstellt werden muss (bzw. dass diese Anweisung komplett wegoptimiert 
wird, weil sie keine Auswirkung hat).

[Noch einer (Gast)]

> dass eine ungewollt rekursive Struktur entsteht

So ziemlich alle Programmiersprachen erzeugen da eine rekursive 
Struktur. Dein Problem existiert auch unabhängig vom copy-on-write.

Die Anhänger der reinen funktionalen Programmierung haben da eine 
Lösung. Sie erlauben nur eine Initialisierung, keine nachträgliche 
Zuweisung.