Wie implementieren Fortsetzungen?

Question

Ich arbeite an einem Scheme-interpreter in C geschrieben.Derzeit verwendet die C-runtime-stack, als seinen eigenen Stapel, der präsentiert ein kleines problem mit der Implementierung von Fortsetzungen.Meine aktuelle Lösung ist das manuelle kopieren der C-stack auf den heap dann kopieren Sie es zurück, wenn nötig.Abgesehen von nicht-standard-C, diese Lösung ist kaum ideal.

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

Answer 1

Ich erinnere mich, einen Artikel Lesen, die möglicherweise für Sie hilfreich sein: Cheney auf der M. T. A. :-)

Einige Implementierungen von Scheme, die ich kenne, wie SISC, reservieren Sie Ihre call-frames auf dem heap.

@Olli:Sie müssen nicht den Hub, wenn Sie alle Ihre call-frames sind auf dem heap.Es gibt einen Kompromiss in performance, natürlich:die Zeit zu hissen, im Vergleich zu den Kosten zu zuordnen, alle frames auf dem heap.Vielleicht sollte es einem tunable-runtime-parameter in der interpreter.:-P

Answer 2

Eine gute Zusammenfassung ist verfügbar im Umsetzung von Strategien für die Erste Klasse Fortsetzungen, ein Artikel von Clinger, Hartheimer und Ost.Ich empfehlen, sich auf Chez Scheme-Implementierung im besonderen.

Stack kopieren ist nicht so Komplex und es gibt eine Reihe von gut verstandenen Techniken zur Verfügung, um die Leistung zu verbessern.Heap-zugewiesenen Rahmen ist auch ziemlich einfach, aber Sie machen einen Kompromiss der Erstellung von overhead-für "normale" situation, wo Sie nicht mit expliziten Fortsetzungen.

Wenn Sie konvertieren die Eingang code continuation passing style (CPS), dann können Sie sofort mit der Beseitigung der Stapel zusammen.Während jedoch die CPS ist elegant, es fügt eine weitere Verarbeitung Schritt in die front-end und erfordert eine zusätzliche Optimierung zu überwinden, bestimmte Auswirkungen auf die Leistung.

Answer 3

Wenn Sie von vorne anfangen, sollte man einen Blick in Continuation Passing Style (CPS) transformation.

Gute Quellen sind unter anderem "LISP" in kleine Stücke" und Marc Feeley Schema in 90 Minuten-Präsentation.

Answer 4

Es scheint Dybvig-thesis unerwähnt so weit.Es ist eine Freude zu Lesen.Die heap-basierten Modell ist am einfachsten zu implementieren, aber die stack-basiert effizienter ist.Ignorieren Sie den string-basierten Modell.

R.Kent Dybvig."Drei Modelle für die Umsetzung Schema".http://www.cs.indiana.edu/~dyb/papers/3imp.pdf

Schauen Sie sich auch die Umsetzung Papiere auf ReadScheme.org.http://library.readscheme.org/page8.html

Die Zusammenfassung ist wie folgt:

Diese dissertation präsentiert drei Modelle für die Umsetzung der Schema Programmiersprache.Die erste ist ein heap-basierten Modell verwendet in einigen form in den meisten Scheme-Implementierungen auf dem neuesten Stand;die zweite ist eine neue stack-basierte Modell, das deutlich mehr ezienter als die heap-basierten Modell bei der Ausführung der meisten Programme;und das Dritte ist ein neues string-basierte Modell für den Gebrauch in einem multiple-Prozessor Umsetzung der Schema.

Die heap-basierten Modell weist einige wichtige Datenstrukturen in eine heap, einschließlich der tatsächlichen parameter-Listen, verbindliche Umgebungen, und rufen Sie frames.

Die stack-basierten Modell teilt die gleichen Strukturen auf einem Stapel wenn es möglich ist.Dies führt zu weniger heap-Zuweisung, die weniger Arbeitsspeicher Referenzen kürzer Befehlsfolgen, weniger Müll-Sammlung, und ezientere Nutzung des Arbeitsspeichers.

Die string-basierte Modell weist Versionen dieser Strukturen Recht in das Programm text, der dargestellt wird als eine Reihe von Symbolen.In der string-basiertes Modell, Scheme-Programme werden übersetzt in eine FFP Sprache speziell auf die Förderung.Programme in diesem Sprache sind direkt ausgeführt, indem die FFP-Maschine, eine Multiprozessor-string-Reduktion computer.

Die stack-basierte Modell von unmittelbarem praktischen nutzen;es ist der Modell des Autors Chez Scheme-system, ein high-performance - Umsetzung der Schema.Die string-basierte Modell wird nützlich sein für die Bereitstellung von Schema als high-level-alternative zu FFP auf die FFP-Maschine sobald die Maschine realisiert.

Answer 5

Neben der schönen Antworten, die Sie schon so weit gekommen, ich empfehle Andrew Appel Kompilieren mit Fortsetzungen.Es ist sehr gut geschrieben und während die nicht am direkten Umgang mit C, ist es eine Quelle der wirklich schöne Ideen für compiler Schriftsteller.

Das Huhn Wiki auch Seiten, die Sie finden sehr interessant, wie interne Struktur und Kompilierung (dem CPS erklärt sich mit einem aktuellen Beispiel-Zusammenstellung).

Answer 6

Beispiele, die man sich anschauen kann sind: Huhn (eine Scheme-Implementierung, in C geschrieben, dass die Unterstützung Fortsetzungen);Paul Graham Auf Lisp - dort, wo er erzeugt einen CPS Transformator zu implementieren, die eine Teilmenge von Fortsetzungen in Common Lisp;und Weblocks - Fortsetzung basierte web-framework, das implementiert auch eine begrenzte form von Fortsetzungen in Common Lisp.

Answer 7

Fortsetzungen sind nicht das problem:implementieren Sie diese mit regelmäßigen höherer Ordnung Funktionen, die mit CPS.Das Problem mit naiv-stack-Zuweisung ist, dass der Schwanz Aufrufe sind nie optimiert, was bedeutet, dass Sie nicht in das Schema.

Die beste derzeitige Konzept-mapping Schema spaghetti-stack auf dem Stapel ist mit Trampolinen:im wesentlichen zusätzlichen Infrastruktur zur Handhabung von nicht-C-wie Anrufe und verlässt Verfahren.Finden Trampolined Stil (ps).

Es gibt code illustrieren diese beiden Ideen.

Answer 8

Der traditionelle Weg ist zu verwenden setjmp und longjmp, allerdings gibt es Einschränkungen.

Hier ist eine einigermaßen gute Erklärung

Answer 9

Fortsetzungen bestehen im wesentlichen aus den gespeicherten Status der Stapel-und CPU-Register auf den Punkt der context-switches.Zumindest müssen Sie nicht kopieren Sie den gesamten Stapel auf den heap beim Wechsel konnten Sie nur umleiten der stack-pointer.

Fortsetzungen sind trivial implementiert unter Verwendung von Fasern. http://en.wikipedia.org/wiki/Fiber_%28computer_science%29 .Die einzigen Dinge, müssen Sie vorsichtig Kapselung sind für die übergabe von Parametern und Rückgabewerten.

In Windows Fasern werden mit dem CreateFiber/SwitchToFiber Familie fordert.in Posix-kompatiblen Systemen kann es getan werden mit makecontext/swapcontext.

boost::coroutine ist eine funktionierende Implementierung von Coroutinen in C++, dienen als Bezugspunkt für die Umsetzung.

Answer 10

Verwenden Sie einen expliziten stack statt.

Answer 11

Patrick ist richtig, nur so können Sie wirklich, dies zu tun, ist die Verwendung eines expliziten stapeln in Ihrem Dolmetscher, und hissen die entsprechende segment der stack in den heap, wenn Sie brauchen, um zu konvertieren, um eine Fortsetzung.

Dies ist im Grunde das gleiche wie das, was benötigt wird, um Unterstützung Verschlüsse in Sprachen, die Sie unterstützen (Verschlüsse und Fortsetzungen etwas verwandt).

Answer 12

Als soegaard darauf hingewiesen, dass der wichtigste Bezugsrahmen bleibt diese ein

Die Idee ist, eine Fortsetzung ist ein Verschluss hält seine Bewertung-Steuerung-stack.Die Steuerung-stack ist erforderlich, um weiterhin die Auswertung von dem moment die Fortsetzung wurde erstellt mit call/cc.

Oft Berufung auf die Fortsetzung macht lange Zeit der Ausführung und füllt den Speicher mit dupliziert stapeln.Ich schrieb diese dummen code, um zu beweisen, dass, im mit-System, es macht die Regelung crash,

Der code, der die Summe der ersten 1000 zahlen 1+2+3+...+1000.

(call-with-current-continuation 
 (lambda (break)
   ((lambda (s) (s s 1000 break))
    (lambda (s n cc)
      (if (= 0 n)
          (cc 0)
          (+ n
             ;; non-tail-recursive,
             ;; the stack grows at each recursive call
             (call-with-current-continuation
              (lambda (__)
                (s s (- n 1) __)))))))))

Wenn Sie den Schalter von 1000 auf 100 000 der code wird verbringen 2 Sekunden, und wenn Sie wachsen, wird die eingegebene Nummer wird es Abstürzen.