Ist eine Speicherbereinigung erforderlich, um sichere Verschlüsse zu implementieren?

14

Ich habe kürzlich einen Online-Kurs über Programmiersprachen besucht, in dem unter anderem Abschlussarbeiten vorgestellt wurden. Ich schreibe zwei Beispiele auf, die von diesem Kurs inspiriert wurden, um einen Kontext zu geben, bevor ich meine Frage stelle.

Das erste Beispiel ist eine SML-Funktion, die eine Liste der Zahlen von 1 bis x erzeugt, wobei x der Parameter der Funktion ist:

fun countup_from1 (x: int) =
    let
        fun count (from: int) =
            if from = x
            then from :: []
            else from :: count (from + 1)
    in
        count 1
    end

In der SML REPL:

val countup_from1 = fn : int -> int list
- countup_from1 5;
val it = [1,2,3,4,5] : int list

Die countup_from1Funktion verwendet den Helferabschluss count, der die Variable xaus ihrem Kontext erfasst und verwendet .

Wenn ich im zweiten Beispiel eine Funktion aufrufe create_multiplier t, erhalte ich eine Funktion (eigentlich einen Abschluss) zurück, die ihr Argument mit t multipliziert:

fun create_multiplier t = fn x => x * t

In der SML REPL:

- fun create_multiplier t = fn x => x * t;
val create_multiplier = fn : int -> int -> int
- val m = create_multiplier 10;
val m = fn : int -> int
- m 4;
val it = 40 : int
- m 2;
val it = 20 : int

Die Variable mist also an den vom Funktionsaufruf zurückgegebenen Abschluss gebunden, und jetzt kann ich sie nach Belieben verwenden.

Damit der Abschluss während seiner gesamten Lebensdauer ordnungsgemäß funktioniert, müssen wir die Lebensdauer der erfassten Variablen verlängern t(im Beispiel ist es eine Ganzzahl, aber es kann sich um einen beliebigen Wert handeln). Soweit ich weiß, wird dies in SML durch die Garbage Collection ermöglicht: Der Verschluss behält einen Verweis auf den erfassten Wert bei, der später vom Garbage Collector entsorgt wird, wenn der Verschluss zerstört wird.

Meine Frage: Ist die Speicherbereinigung im Allgemeinen der einzig mögliche Mechanismus, um sicherzustellen, dass die Schließungen sicher sind (abrufbar während ihrer gesamten Lebensdauer)?

Oder welche anderen Mechanismen könnten die Gültigkeit von Verschlüssen ohne Garbage Collection sicherstellen: Kopieren Sie die erfassten Werte und speichern Sie sie innerhalb des Verschlusses? Die Lebensdauer des Verschlusses selbst einschränken, sodass er nach Ablauf der erfassten Variablen nicht mehr aufgerufen werden kann?

Was sind die beliebtesten Ansätze?

BEARBEITEN

Ich denke nicht, dass das obige Beispiel erklärt / implementiert werden kann, indem die erfassten Variablen in den Abschluss kopiert werden. Im Allgemeinen können die erfassten Variablen von einem beliebigen Typ sein, z. B. können sie an eine sehr große (unveränderliche) Liste gebunden sein. Daher wäre es in der Implementierung sehr ineffizient, diese Werte zu kopieren.

Der Vollständigkeit halber ist hier ein weiteres Beispiel unter Verwendung von Referenzen (und Nebenwirkungen):

(* Returns a closure containing a counter that is initialized
   to 0 and is incremented by 1 each time the closure is invoked. *)
fun create_counter () =
    let
        (* Create a reference to an integer: allocate the integer
           and let the variable c point to it. *)
        val c = ref 0
    in
        fn () => (c := !c + 1; !c)
    end

(* Create a closure that contains c and increments the value
   referenced by it it each time it is called. *)
val m = create_counter ();

In der SML REPL:

val create_counter = fn : unit -> unit -> int
val m = fn : unit -> int
- m ();
val it = 1 : int
- m ();
val it = 2 : int
- m ();
val it = 3 : int

Variablen können also auch als Referenz erfasst werden und sind nach Abschluss des Funktionsaufrufs, der sie erstellt hat ( create_counter ()), noch aktiv.

Giorgio
quelle
2
Alle Variablen, die geschlossen sind, sollten vor Garbage Collection geschützt werden, und alle Variablen, die nicht geschlossen sind, sollten für die Garbage Collection in Frage kommen. Daraus folgt, dass jeder Mechanismus, der zuverlässig nachverfolgen kann, ob eine Variable geschlossen ist oder nicht, auch den Speicher, den die Variable belegt, zuverlässig wiederherstellen kann.
Robert Harvey
3
@btilly: Refcounting ist nur eine von vielen Implementierungsstrategien für einen Garbage Collector. Es ist eigentlich egal, wie der GC zum Zweck dieser Frage implementiert wird.
Jörg W Mittag
3
@btilly: Was bedeutet "echte" Garbage Collection? Refcounting ist nur eine andere Möglichkeit, GC zu implementieren. Die Nachverfolgung ist populärer, wahrscheinlich wegen der Schwierigkeiten beim Sammeln von Zyklen mit der Nachzählung. (Normalerweise haben Sie ohnehin einen separaten Ablaufverfolgungs-GC. Warum sollten Sie sich also die Mühe machen, zwei GCs zu implementieren, wenn Sie mit einem auskommen können?) Es gibt jedoch auch andere Möglichkeiten, mit Zyklen umzugehen. 1) Verbiete es ihnen einfach. 2) Ignoriere sie einfach. (Wenn Sie eine Implementierung für schnelle einmalige Skripte durchführen, warum nicht?) 3) Versuchen Sie, diese explizit zu erkennen. (Es stellt sich heraus, dass die Verfügbarkeit des Nachzählers das beschleunigen kann.)
Jörg W Mittag
1
Es kommt darauf an, warum Sie Schließungen überhaupt wünschen. Wenn Sie beispielsweise eine vollständige Lambda-Kalkül-Semantik implementieren möchten, benötigen Sie auf jeden Fall GC, Punkt. Es gibt keinen anderen Weg. Wenn Sie etwas möchten, das in der Ferne Closures ähnelt, aber nicht der genauen Semantik von Closures folgt (wie in C ++, Delphi, was auch immer), tun Sie, was Sie wollen, verwenden Sie die Regionsanalyse und verwenden Sie die vollständig manuelle Speicherverwaltung.
SK-logic
2
@Mason Wheeler: Closures sind nur Werte. Im Allgemeinen kann nicht vorhergesagt werden, wie sie zur Laufzeit verschoben werden. In diesem Sinne sind sie nichts Besonderes. Dasselbe gilt für eine Zeichenfolge, eine Liste usw.
Giorgio

Antworten:

14

Interessant ist in diesem Punkt die Programmiersprache Rust.

Rust ist eine Systemsprache mit optionalem GC und wurde von Anfang an mit Closures entwickelt .

Als die anderen Variablen kommen Rostverschlüsse in verschiedenen Geschmacksrichtungen vor. Stapel Verschlüsse , die häufigsten sind für One-Shot - Nutzung. Sie leben auf dem Stapel und können sich auf alles beziehen. Eigene Closures übernehmen das Eigentum an den erfassten Variablen. Ich denke, sie leben auf dem sogenannten "Austauschhaufen", der ein globaler Haufen ist. Ihre Lebensdauer hängt davon ab, wem sie gehören. Verwaltete Abschlüsse befinden sich auf dem aufgabenlokalen Heap und werden vom GC der Aufgabe verfolgt. Ich bin mir jedoch nicht sicher, welche Einschränkungen sie bei der Erfassung haben.

3 Umdrehungen
quelle
1
Sehr interessanter Link und Verweis auf die Rust-Sprache. Vielen Dank. +1.
Giorgio
1
Ich habe viel nachgedacht, bevor ich eine Antwort angenommen habe, weil ich finde, dass Masons Antwort auch sehr informativ ist. Ich habe mich für diese entschieden, weil sie sowohl informativ ist als auch eine weniger bekannte Sprache mit einer originellen Herangehensweise an Verschlüsse zitiert.
Giorgio
Dank dafür. Ich bin sehr begeistert von dieser jungen Sprache und teile gerne mein Interesse. Ich wusste nicht, ob sichere Verschlüsse ohne GC möglich sind, bevor ich von Rust hörte.
Barjak
9

Wenn Sie mit einem GC anfangen, werden Sie leider Opfer des XY-Syndroms:

  • Verschlüsse erfordern mehr als die Variablen, über die sie geschlossen wurden, solange der Verschluss dies tut (aus Sicherheitsgründen).
  • Mit dem GC können wir die Lebensdauer dieser Variablen lang genug verlängern
  • XY-Syndrom: Gibt es andere Mechanismen, um die Lebensdauer zu verlängern?

Beachten Sie jedoch, dass die Idee , die Lebensdauer einer Variablen zu verlängern , für einen Abschluss nicht erforderlich ist . es ist nur vom GC überbracht worden; Die ursprüngliche Sicherheitserklärung besagt, dass nur die Variablen für geschlossene Fenster so lange gültig sein sollten wie der Verschluss (und selbst wenn dies wackelig ist, können wir sagen, dass sie bis nach dem letzten Aufruf des Verschlusses gültig sein sollten).

Es gibt im Wesentlichen zwei Ansätze , die ich sehen kann (und die möglicherweise kombiniert werden könnten):

  1. Verlängern Sie die Lebensdauer von Closed-Over-Variablen (wie zum Beispiel bei einem GC)
  2. Beschränken Sie die Lebensdauer des Verschlusses

Letzteres ist nur ein symmetrischer Ansatz. Es wird nicht oft verwendet, aber wenn Sie wie Rust ein region-aware Type-System haben, dann ist es sicherlich möglich.

Matthieu M.
quelle
7

Garbage Collection wird für sichere Abschlüsse beim Erfassen von Variablen nach Wert nicht benötigt. Ein prominentes Beispiel ist C ++. C ++ hat keine Standard-Garbage Collection. Lambdas in C ++ 11 sind Abschlüsse (sie erfassen lokale Variablen aus dem umgebenden Bereich). Jede von einem Lambda erfasste Variable kann angegeben werden, um nach Wert oder Referenz erfasst zu werden. Wenn es als Referenz erfasst wird, kann man sagen, dass es nicht sicher ist. Wenn eine Variable jedoch nach Wert erfasst wird, ist dies sicher, da die erfasste Kopie und die ursprüngliche Variable voneinander getrennt sind und eine unabhängige Lebensdauer haben.

In dem von Ihnen angegebenen SML-Beispiel ist es einfach zu erklären: Variablen werden nach Wert erfasst. Es ist nicht erforderlich, die Lebensdauer einer Variablen zu verlängern, da Sie ihren Wert einfach in den Abschluss kopieren können. Dies ist möglich, weil in ML keine Variablen zugewiesen werden können. Es gibt also keinen Unterschied zwischen einer Kopie und vielen unabhängigen Kopien. Obwohl SML über eine Garbage Collection verfügt, hat dies nichts mit der Erfassung von Variablen durch Closures zu tun.

Garbage Collection wird auch nicht für sichere Abschlüsse beim Erfassen von Variablen nach Referenz (Art von) benötigt. Ein Beispiel ist die Apple Blocks-Erweiterung für die Sprachen C, C ++, Objective-C und Objective-C ++. In C und C ++ gibt es keine Standard-Garbage Collection. Blockiert standardmäßig die Erfassung von Variablen nach Wert. Wenn jedoch eine lokale Variable mit deklariert wird __block, dann sie Blöcke erfassen scheinbar „by reference“, und sie sind sicher -. Sie auch nach dem Umfang verwendet werden können , dass der Block in wurde definiert Was hier passiert , ist , dass __blockVariablen ist eigentlich ein Spezielle Struktur darunter, und wenn Blöcke kopiert werden (Blöcke müssen kopiert werden, um sie überhaupt außerhalb des Gültigkeitsbereichs zu verwenden), verschieben sie die Struktur für die__block Variable in den Haufen, und der Block verwaltet seinen Speicher, glaube ich durch Referenzzählung.

user102008
quelle
4
"Speicherbereinigung wird für Schließungen nicht benötigt.": Die Frage ist, ob sie benötigt wird, damit die Sprache sichere Schließungen erzwingen kann. Ich weiß, dass ich sichere Closures in C ++ schreiben kann, aber die Sprache erzwingt sie nicht. Informationen zu Abschlüssen, die die Lebensdauer erfasster Variablen verlängern, finden Sie in der Bearbeitung meiner Frage.
Giorgio
1
Ich nehme an, die Frage könnte umformuliert werden: für sichere Verschlüsse .
Matthieu M.
1
Der Titel enthält den Begriff "sichere Verschlüsse". Glaubst du, ich könnte ihn besser formulieren?
Giorgio
1
Können Sie bitte den zweiten Absatz korrigieren? In SML verlängern Closures die Lebensdauer von Daten, auf die von erfassten Variablen verwiesen wird. Es ist auch richtig, dass Sie keine Variablen zuweisen können (ihre Bindung ändern), aber Sie haben veränderbare Daten (durch ref). Also, OK, man kann diskutieren, ob die Implementierung von Schließungen mit Garbage Collection zusammenhängt oder nicht, aber die obigen Aussagen sollten korrigiert werden.
Giorgio
1
@ Giorgio: Wie wäre es jetzt? Inwiefern ist meine Aussage, dass Verschlüsse die Lebensdauer einer erfassten Variablen nicht verlängern müssen, falsch? Wenn Sie von veränderlichen Daten sprechen, sprechen Sie von Referenztypen ( refs, Arrays usw.), die auf eine Struktur verweisen. Aber der Wert ist die Referenz selbst, nicht das, worauf er zeigt. Wenn Sie var a = ref 1eine Kopie haben und diese erstellen var b = aund verwenden b, bedeutet dies, dass Sie sie noch verwenden a? Sie haben Zugriff auf dieselbe Struktur, auf die von a? Ja. So funktionieren diese Typen in SML und haben nichts mit Closures zu tun
user102008
6

Eine Speicherbereinigung ist nicht erforderlich, um Sperren zu implementieren. Im Jahr 2008 hat die Delphi-Sprache, bei der es sich nicht um Müll handelt, eine Implementierung von Closures hinzugefügt. Das funktioniert so:

Der Compiler erstellt ein Funktionsobjekt unter der Haube, das eine Schnittstelle implementiert, die einen Abschluss darstellt. Alle übergeordneten lokalen Variablen werden von lokalen Variablen für die einschließende Prozedur in Felder auf dem Funktionsobjekt geändert. Dies stellt sicher, dass der Zustand so lange erhalten bleibt, wie der Funktor ist.

Die Einschränkung bei diesem System besteht darin, dass alle Parameter, die als Referenz auf die einschließende Funktion übergeben werden, sowie der Ergebniswert der Funktion nicht vom Funktor erfasst werden können, da es sich nicht um Gebietsschemas handelt, deren Gültigkeitsbereich auf den der einschließenden Funktion beschränkt ist.

Auf den Funktor wird durch die Closure-Referenz verwiesen, wobei syntaktischer Zucker verwendet wird, damit er für den Entwickler wie ein Funktionszeiger anstelle eines Interfaces aussieht. Es verwendet Delphis Referenzzählsystem für Schnittstellen, um sicherzustellen, dass das Funktionsobjekt (und der gesamte Zustand, den es enthält) so lange "am Leben" bleibt, wie es benötigt, und wird dann freigegeben, wenn der Refcount auf 0 fällt.

Mason Wheeler
quelle
1
Ah, es ist also nur möglich, lokale Variablen zu erfassen, nicht die Argumente! Dies scheint ein vernünftiger und kluger Kompromiss zu sein! +1
Giorgio
1
@ Giorgio: Es kann Argumente erfassen, nur keine, die var- Parameter sind.
Mason Wheeler
2
Sie verlieren auch die Fähigkeit, zwei Abschlüsse zu haben, die über einen gemeinsam genutzten privaten Status kommunizieren. Sie werden das in den grundlegenden Anwendungsfällen nicht antreffen, aber es schränkt Ihre Fähigkeit ein, komplexe Dinge zu tun. Immer noch ein gutes Beispiel dafür, was möglich ist!
btilly
3
@btilly: Tatsächlich ist es vollkommen legal, wenn Sie zwei Verschlüsse in dieselbe umschließende Funktion einfügen. Am Ende haben sie dasselbe Funktionsobjekt gemeinsam. Wenn sie denselben Status ändern, werden die Änderungen in einem davon in dem anderen widergespiegelt.
Mason Wheeler
2
@MasonWheeler: "Nein. Die Garbage Collection ist nicht deterministisch. Es gibt keine Garantie dafür, dass ein bestimmtes Objekt jemals gesammelt wird, geschweige denn, wenn es auftritt. Die Referenzzählung ist jedoch deterministisch: Der Compiler garantiert, dass das Objekt vorhanden ist wird sofort freigegeben, nachdem die Zählung auf 0 gefallen ist. " Wenn ich jedes Mal einen Cent hätte, wenn ich hörte, dass sich dieser Mythos verewigte. OCaml hat eine deterministische GC. C ++ - Thread-Safe shared_ptrist nicht deterministisch, da Destruktoren versuchen, auf Null zu dekrementieren.
Jon Harrop