Wie setzt man Fortsetzungen um?

Lesezeit: 5 Minuten

Benutzeravatar von Kyle Cronin
Kyle Cronin

Ich arbeite an einem in C geschriebenen Scheme-Interpreter. Derzeit verwendet er den C-Laufzeitstapel als eigenen Stapel, was ein kleines Problem bei der Implementierung von Fortsetzungen darstellt. Meine aktuelle Lösung ist das manuelle Kopieren des C-Stacks auf den Heap und das anschließende Zurückkopieren bei Bedarf. Abgesehen davon, dass es sich nicht um Standard-C handelt, ist diese Lösung kaum ideal.

Was ist der einfachste Weg, um Fortsetzungen für Schema in C zu implementieren?

Benutzeravatar von Josh Segall
Josh Segall

Eine gute Zusammenfassung findet sich in Umsetzungsstrategien für erstklassige Fortführungen, ein Artikel von Clinger, Hartheimer und Ost. Ich empfehle, sich insbesondere die Implementierung von Chez Scheme anzusehen.

Das Stapelkopieren ist nicht so komplex und es gibt eine Reihe gut verstandener Techniken, um die Leistung zu verbessern. Die Verwendung von Heap-zugewiesenen Frames ist ebenfalls ziemlich einfach, aber Sie gehen einen Kompromiss ein, indem Sie Overhead für “normale” Situationen erstellen, in denen Sie keine expliziten Fortsetzungen verwenden.

Wenn Sie den Eingabecode in den Continuation Passing Style (CPS) konvertieren, können Sie den Stapel vollständig eliminieren. Obwohl CPS elegant ist, fügt es jedoch einen weiteren Verarbeitungsschritt im Frontend hinzu und erfordert eine zusätzliche Optimierung, um bestimmte Auswirkungen auf die Leistung zu überwinden.

Benutzeravatar von CK Young
CK Jung

Ich erinnere mich, einen Artikel gelesen zu haben, der Ihnen vielleicht helfen könnte: Cheney auf dem MTA 🙂

Einige mir bekannte Implementierungen von Scheme, wie z SISCweisen ihre Aufrufrahmen auf dem Heap zu.

@ollie: Sie müssen das Heben nicht durchführen, wenn sich alle Ihre Aufrufrahmen auf dem Haufen befinden. Es gibt natürlich einen Kompromiss bei der Leistung: die Zeit zum Heben gegenüber dem Overhead, der erforderlich ist, um alle Frames auf dem Heap zuzuweisen. Vielleicht sollte es ein einstellbarer Laufzeitparameter im Interpreter sein. 😛

Benutzeravatar von Joel Borggrén-Franck
Joel Borggren-Franck

Wenn Sie bei Null anfangen, sollten Sie sich unbedingt mit der Transformation des Continuation Passing Style (CPS) befassen.

Gute Quellen sind “LISP in kleinen Stücken” und Marc Feeleys Schema in einer 90-minütigen Präsentation.

  • Queinnecs Buch Lisp In Small Pieces ist erhältlich (zumindest in der französischen Ausgabe von Paracampus)

    – Basile Starynkevitch

    30. Januar 2016 um 12:20 Uhr

Benutzeravatar von soegaard
soegaard

Es scheint, dass Dybvigs These bisher nicht erwähnt wurde. Es ist eine Freude zu lesen. Das Heap-basierte Modell ist am einfachsten zu implementieren, aber das Stack-basierte Modell ist effizienter. Ignorieren Sie das stringbasierte Modell.

R. Kent Dybvig. “Drei Implementierungsmodelle für Schema”.
http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

Sehen Sie sich auch die Implementierungspapiere auf ReadScheme.org an.
https://web.archive.org/http://library.readscheme.org/page8.html

Die Zusammenfassung lautet wie folgt:

Diese Dissertation stellt drei Implementierungsmodelle für die Programmiersprache Scheme vor. Das erste ist ein Heap-basiertes Modell, das bis heute in irgendeiner Form in den meisten Scheme-Implementierungen verwendet wird; das zweite ist ein neues Stack-basiertes Modell, das bei der Ausführung der meisten Programme wesentlich effizienter als das Heap-basierte Modell ist; und das dritte ist ein neues String-basiertes Modell, das für die Verwendung in einer Mehrprozessor-Implementierung von Scheme gedacht ist.

Das Heap-basierte Modell ordnet mehrere wichtige Datenstrukturen in einem Heap zu, einschließlich tatsächlicher Parameterlisten, Bindungsumgebungen und Aufrufrahmen.

Das stapelbasierte Modell ordnet dieselben Strukturen wann immer möglich einem Stapel zu. Dies führt zu weniger Heap-Zuweisung, weniger Speicherreferenzen, kürzeren Befehlssequenzen, weniger Speicherbereinigung und effizienterer Nutzung des Speichers.

Das zeichenkettenbasierte Modell ordnet Versionen dieser Strukturen direkt im Programmtext zu, der als Zeichenkette dargestellt wird. Beim stringbasierten Modell werden Scheme-Programme in eine FFP-Sprache übersetzt, die speziell zur Unterstützung von Scheme entwickelt wurde. Programme in dieser Sprache werden direkt von der FFP-Maschine ausgeführt, einem Computer zur Reduzierung von Zeichenfolgen mit mehreren Prozessoren.

Das Stack-basierte Modell ist von unmittelbarem praktischem Nutzen; Es ist das Modell, das vom Chez Scheme-System des Autors verwendet wird, einer Hochleistungsimplementierung von Scheme. Das zeichenfolgenbasierte Modell wird nützlich sein, um Scheme als High-Level-Alternative zu FFP auf der FFP-Maschine bereitzustellen, sobald die Maschine realisiert ist.

Benutzeravatar von Jay
Jay

Neben den netten Antworten, die Sie bisher bekommen haben, empfehle ich Andrew Appels Compiling with Continuations. Es ist sehr gut geschrieben und obwohl es nicht direkt mit C zu tun hat, ist es eine Quelle wirklich netter Ideen für Compiler-Autoren.

Das Hühner-Wiki hat auch Seiten, die Sie sehr interessant finden werden, wie z Interne Struktur und Kompilierungsprozess (wobei CPS anhand eines tatsächlichen Kompilierungsbeispiels erklärt wird).

  • Ich mag Appels Buch sehr. Ein Bonus ist, dass Sie auf den Quellcode des SML/NJ-Compilers verweisen können, der ein ziemlich gutes lebendiges Beispiel für den Prozess ist, den Appel in dem Buch beschreibt.

    – Nate CK

    19. März 2015 um 1:00 Uhr


Benutzeravatar von Kyle Burton
Kyle Burton

Beispiele, die Sie sich ansehen können, sind: Huhn (eine in C geschriebene Schemaimplementierung, die Fortsetzungen unterstützt); Paul Grahams Auf Lisp – wo er einen CPS-Transformator erstellt, um eine Teilmenge von Fortsetzungen in Common Lisp zu implementieren; und Weblocks – ein auf Fortsetzungen basierendes Web-Framework, das auch eine begrenzte Form von Fortsetzungen in Common Lisp implementiert.

  • Ich mag Appels Buch sehr. Ein Bonus ist, dass Sie auf den Quellcode des SML/NJ-Compilers verweisen können, der ein ziemlich gutes lebendiges Beispiel für den Prozess ist, den Appel in dem Buch beschreibt.

    – Nate CK

    19. März 2015 um 1:00 Uhr


Benutzeravatar von Charles Stewart
Karl Stewart

Fortsetzungen sind nicht das Problem: Sie können diese mit regulären Funktionen höherer Ordnung mit CPS implementieren. Das Problem bei der naiven Stack-Zuweisung ist, dass Tail-Calls niemals optimiert werden, was bedeutet, dass Sie kein Schema sein können.

Der beste derzeitige Ansatz zum Abbilden des Spaghetti-Stapels des Schemas auf den Stapel ist die Verwendung von Trampolinen: im Wesentlichen zusätzliche Infrastruktur, um Nicht-C-ähnliche Aufrufe und Ausgänge von Prozeduren zu handhaben. Sehen Trampolin-Stil (ps).

Es gibt etwas Code Veranschaulichung dieser beiden Ideen.

1410930cookie-checkWie setzt man Fortsetzungen um?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy