copy-on-write für verschachtelte Strukturen

Gast #4536313
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?
Gast #4536459
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).
Gast #4538539
> 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.

Antwort schreiben

Eine eigene Frage? Dieser Thread ist über 10 Jahre alt. Stell sie in einem eigenen Thread – dort lesen mehr Leute mit, und sie wird öfter und schneller beantwortet.

Neuen Thread starten

Eine Lösung, Ergänzung oder Rückmeldung zu diesem Thread? Dann antworte hier.

Formatierung
  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] – Link zu einem Artikel
  • Verweis auf einen anderen Beitrag: Rechtsklick auf dessen Beitrags-ID (#8078628), „Adresse kopieren“, in den Text einfügen

Mehr zur Formatierung

Längeren Sourcecode als Anhang, nicht in den Text. JPG nur für Fotos und Scans; Zeichnungen und Screenshots als PNG oder GIF. Siehe Bildformate.

Schon registriert? Anmelden

Wird nicht angezeigt. Wir schicken dir einen Link; sobald du damit bestätigst, erscheint dein Beitrag.

Mit dem Abschicken legst du einen kostenlosen Account an und erkennst die Nutzungsbedingungen und die Datenschutzerklärung an.