Probleme beim Implementieren von Abschlüssen in nicht funktionalen Einstellungen

18

In Programmiersprachen sind Verschlüsse ein beliebtes und oft gewünschtes Merkmal. Wikipedia sagt (Hervorhebung von mir):

In der Informatik ist ein Closure (...) eine Funktion zusammen mit einer Referenzierungsumgebung für die nicht lokalen Variablen dieser Funktion. Ein Closure ermöglicht es einer Funktion, auf Variablen außerhalb ihres unmittelbaren lexikalischen Bereichs zuzugreifen.

Ein Closure ist also im Wesentlichen ein (anonymer?) Funktionswert, der Variablen außerhalb seines eigenen Gültigkeitsbereichs verwenden kann. Nach meiner Erfahrung bedeutet dies, dass auf Variablen zugegriffen werden kann, die sich an ihrem Definitionspunkt im Gültigkeitsbereich befinden.

In der Praxis scheint sich das Konzept jedoch zumindest außerhalb der funktionalen Programmierung zu unterscheiden. Verschiedene Sprachen implementieren unterschiedliche Semantiken, es scheint sogar Meinungsverschiedenheiten zu geben. Viele Programmierer scheinen nicht zu wissen, was Abschlüsse sind, und betrachten sie nur als anonyme Funktionen.

Auch bei der Umsetzung von Schließungen scheinen große Hürden zu bestehen. Am bemerkenswertesten ist, dass Java 7 sie enthalten sollte, aber die Funktion wurde auf eine zukünftige Version zurückgesetzt.

Warum sind Verschlüsse so schwer zu verstehen und zu realisieren? Dies ist eine zu weit gefasste und vage Frage, daher möchte ich mich auf diese miteinander verbundenen Fragen konzentrieren:

  • Gibt es Probleme beim Ausdruck von Abschlüssen in gemeinsamen semantischen Formalismen (kleine Schritte, große Schritte, ...)?
  • Sind vorhandene Typsysteme nicht für Verschlüsse geeignet und können nicht einfach erweitert werden?
  • Ist es problematisch, Verschlüsse an eine herkömmliche stapelbasierte Verfahrensübersetzung anzupassen?

Beachten Sie, dass sich die Frage hauptsächlich auf prozedurale, objektorientierte und Skriptsprachen im Allgemeinen bezieht. Soweit ich weiß, haben funktionale Sprachen keine Probleme.

Raphael
quelle
Gute Frage. In Scala wurden Closures implementiert, und Martin Odersky hat den Java 1.5-Compiler geschrieben. Daher ist nicht klar, warum sie nicht in Java 7 enthalten sind. (Ich werde versuchen, später eine bessere Antwort zu schreiben.)
Dave Clarke
4
In unreinen funktionalen Sprachen wie Lisp und ML sind Abschlüsse in Ordnung, daher kann es keinen inhärenten semantischen Grund dafür geben, dass sie problematisch sind.
Gilles 'SO - hör auf böse zu sein'
Ich habe den Artikel hinzugefügt, weil ich mich nur schwer vorstellen konnte, wie eine Semantik mit kleinen Schritten für Verschlüsse aussehen könnte. Es kann sehr gut sein, dass Verschlüsse an sich kein Problem sind, aber es ist schwierig, sie in eine Sprache zu integrieren, die nicht für sie entwickelt wurde.
Raphael
1
Werfen Sie einen Blick auf pdfs.semanticscholar.org/73a2/… - Lua-Autoren haben es sehr geschickt gemacht und diskutieren auch allgemeine Probleme bei der Implementierung von Schließungen
Bulat

Antworten:

10

Darf ich Sie auf die Wikipedia-Seite des Funarg-Problems weiterleiten ? Zumindest haben die Compiler-Leute so auf das Problem der Closure-Implementierung verwiesen.

Ein Closure ist also im Wesentlichen ein (anonymer?) Funktionswert, der Variablen außerhalb seines eigenen Gültigkeitsbereichs verwenden kann. Nach meiner Erfahrung bedeutet dies, dass auf Variablen zugegriffen werden kann, die sich an ihrem Definitionspunkt im Gültigkeitsbereich befinden.

Obwohl diese Definition sinnvoll ist, hilft sie nicht, das Problem der Implementierung erstklassiger Funktionen in einer traditionellen Sprache auf Laufzeitstapelbasis zu beschreiben. Wenn es um Implementierungsprobleme geht, können erstklassige Funktionen grob in zwei Klassen unterteilt werden:

  • Lokale Variablen in den Funktionen werden nach der Rückkehr der Funktion nie mehr verwendet.
  • Lokale Variablen können nach der Rückkehr der Funktion verwendet werden.

Der erste Fall (downwards funargs) ist nicht so schwer zu implementieren und kann auch in älteren prozeduralen Sprachen wie Algol, C und Pascal gefunden werden. C umgeht das Problem, da es keine verschachtelten Funktionen zulässt, aber Algol und Pascal die erforderliche Buchhaltung durchführen, damit innere Funktionen auf die Stapelvariablen der äußeren Funktion verweisen können.

Der zweite Fall (Aufwärts-Funargs) erfordert andererseits, dass Aktivierungsdatensätze außerhalb des Stapels im Heap gespeichert werden. Dies bedeutet, dass es sehr leicht ist, Speicherressourcen zu verlieren, wenn die Sprachlaufzeit keinen Garbage Collector enthält. Während heute fast alles Müll ist, ist das Erfordernis einer Müllabfuhr immer noch eine bedeutende Designentscheidung, und dies war vor einiger Zeit noch wichtiger.


Wenn ich mich richtig erinnere, war das Hauptproblem für das spezielle Java-Beispiel nicht, dass man Closures implementieren konnte, sondern wie man sie in einer Weise in die Sprache einführte, die mit vorhandenen Features (wie anonymen inneren Klassen) und nicht redundant war das hat nicht mit vorhandenen Features gekollidiert (wie geprüften Ausnahmen - ein Problem, das nicht trivial zu lösen ist und an das die meisten Leute zuerst nicht denken).

Ich kann mir auch andere Dinge vorstellen, die die Implementierung erstklassiger Funktionen weniger trivial machen, z. B. die Entscheidung, was mit "magischen" Variablen wie dieser , self oder super zu tun ist , und die Interaktion mit vorhandenen Kontrollflussoperatoren wie break und return (Wollen wir nicht-lokale Rückgaben zulassen oder nicht?). Letztendlich scheint die jüngste Beliebtheit von erstklassigen Funktionen darauf hinzudeuten, dass Sprachen, in denen dies nicht der Fall ist, dies meist aus historischen Gründen oder aufgrund einer wichtigen Entwurfsentscheidung zu einem frühen Zeitpunkt tun.

hugomg
quelle
1
Kennen Sie Sprachen, die zwischen Aufwärts- und Abwärtsfällen unterscheiden? In .NET-Sprachen kann eine generische Methode, die eine Abwärtsfunktion erwartet, eine Struktur des generischen Typs zusammen mit einem Delegaten empfangen, der eine solche Struktur wie eine Byref (in C # ein " refParameter") empfängt . Wenn der Aufrufer alle relevanten Variablen in der Struktur gekapselt hat, ist der Delegat möglicherweise vollständig statisch, sodass keine Heap-Zuweisung erforderlich ist. Compiler bieten keine hilfreiche Syntaxhilfe für solche Konstrukte, aber das Framework könnte sie unterstützen.
Superkatze
2
@supercat: Rust verfügt über mehrere Schließungstypen , mit denen Sie beim Kompilieren erzwingen können, ob eine innere Funktion den Heap verwenden muss. Dies bedeutet jedoch nicht, dass eine Implementierung nicht versuchen kann, Heap-Zuweisungen zu vermeiden, ohne Sie zu zwingen, sich um all diese zusätzlichen Typen zu kümmern. Ein Compiler kann versuchen, die Funktionslebensdauern abzuleiten, oder er kann Laufzeitprüfungen verwenden, um Variablen nur dann träge auf dem Heap zu speichern, wenn dies unbedingt erforderlich ist ( Details finden Sie im Abschnitt "Lexikalischer Gültigkeitsbereich" des
Dokuments
5

Wir können uns ansehen, wie Closures in C # implementiert sind. Der Umfang der Transformationen, die der C # -Compiler durchführt, macht deutlich, dass die Implementierung von Closures ziemlich aufwändig ist. Möglicherweise gibt es einfachere Möglichkeiten, Closures zu implementieren, aber ich denke, das C # -Compiler-Team würde sich dessen bewusst sein.

Betrachten Sie das folgende Pseudo-C # (ich habe ein bisschen C # -spezifisches Material herausgeschnitten):

int x = 1;
function f = function() { x++; };
for (int i = 1; i < 10; i++) {
    f();
}
print x; // Should print 9

Der Compiler wandelt das in so etwas um:

class FunctionStuff {
   int x;
   void theFunction() {
       x++;
   }
}

FunctionStuff theClosureObject = new FunctionStuff();
theClosureObject.x = 1;
for (int i = 1; i < 10; i++) {
    theClosureObject.theFunction();
}
print theClosureObject.x; // Should print 9

(In Wirklichkeit wird die Variable f weiterhin erstellt, wobei f ein 'Delegat' (= Funktionszeiger) ist, dieser Delegat jedoch weiterhin dem theClosureObject-Objekt zugeordnet ist. Ich habe diesen Teil aus Gründen der Klarheit für diejenigen weggelassen, die nicht vertraut sind mit C #)

Diese Transformation ist ziemlich umfangreich und kompliziert: Berücksichtigen Sie Closures in Closures und das Zusammenspiel von Closures mit den übrigen Funktionen der C # -Sprache. Ich kann mir vorstellen, dass das Feature für Java zurückgedrängt wurde, da Java 7 bereits viele neue Features enthält.

Alex ten Brink
quelle
Ich kann sehen, wohin das führt. Wenn mehrere Abschlüsse und der Hauptbereich auf dieselbe Variable zugreifen, wird dies unübersichtlich.
Raphael
Um ehrlich zu sein, liegt dies eher daran, dass das vorhandene OO-Framework für die Implementierung von Closures verwendet wird, als dass ein echtes Problem damit vorliegt. Andere Sprachen ordnen die Variablen einfach in einer separaten, methodenlosen Struktur zu und lassen sie dann von mehreren Closures gemeinsam nutzen, wenn sie dies möchten.
Umarmung
@Raphael: Wie stehst du zu Verschlüssen in Verschlüssen? Warten Sie, lassen Sie mich das hinzufügen.
Alex ten Brink
5

Um einen Teil Ihrer Frage zu beantworten. Der von Morrisett und Harper beschriebene Formalismus behandelt die Groß- und Kleinschrittsemantik polymorpher Sprachen höherer Ordnung, die Abschlüsse enthalten. Es gibt Artikel davor, die die Art der Semantik liefern, nach der Sie suchen. Schauen Sie sich zum Beispiel die SECD-Maschine an . Das Hinzufügen von veränderlichen Referenzen oder veränderlichen Einheimischen zu dieser Semantik ist unkompliziert. Ich sehe keine technischen Probleme bei der Bereitstellung einer solchen Semantik.

Dave Clarke
quelle
Vielen Dank für den Hinweis! Es scheint kein leichtes Lesen zu sein, aber das ist wahrscheinlich von einer Semantik-Arbeit zu erwarten.
Raphael
1
@Raphael: Es gibt wahrscheinlich einfachere. Ich werde versuchen, etwas zu finden und mich bei Ihnen zu melden. In jedem Fall enthält Abbildung 8 die Semantik, nach der Sie suchen.
Dave Clarke
Vielleicht können Sie einen groben Überblick bzw. Die zentralen Ideen in Ihrer Antwort?
Raphael
2
@ Raffael. Vielleicht könnte ich Sie auf meine Vorlesungsunterlagen verweisen, die ich für einen Programmiersprachenkurs verwende, der Ihnen eine kurze Einführung bietet. Bitte
Uday Reddy
1
Dieser Link erscheint entweder tot oder hinter unsichtbarer Authentifizierung. ( cs.cmu.edu/afs/cs/user/rwh/public/www/home/papers/gcpoly/tr.pdf ). Ich bekomme 403 verboten.
Ben Fletcher