Implementierung Funktionaler Programmiersprachen: Codegenerierung, Speicherverwaltung Und Testsysteme Für Sprachen Mit Verzögerter Auswertung

ISBN-13: 9783824420377 / Niemiecki / Miękka / 1993 / 252 str.

Michael Gloger

Opis

2.1 MS -Eine einfache funktionale Sprache Zur Beschreibung der Ubersetzung funktionaler Sprachen wird in diesem Ab schnitt eine einfache Sprache definiert, die als gemeinsamer Kern der meisten modernen funktionalen Sprachen angesehen werden kann. Diese Sprache enthalt keine Listen-oder Mengenabstraktionen und nur sehr eingeschrankte Moglich keiten des Pattern-Matching. Sie ist jedoch machtig genug, um die im folgenden behandelten wesentlichen Probleme der Codegenerierung aufzeigen zu konnen. Wir wollen diese Sprache Mini-SAMPAE oder kurz MS nennen, da sie eine Un termenge der in SAMPAE zulassigen Programme definiert. Die Syntax von MS ist in den Abbildungen 2.1, 2.2 und 2.3 zusammengefasst. Ein MS-Programm besteht aus einem einzigen Modul, das eine Liste von Definitionen und einen Ausdruck enthalt. Der Wert dieses Ausdrucks ist das Ergebnis des Programms bei der Ausfuhrung. In der globalen Definitionsliste konnen Typen und Funktionen definiert werden. Die Typen der definierten Funktionen konnen in MS nicht spezifiziert werden. Typdefinitionen dienen lediglich dazu, neue Datenkonstruktoren zu definieren. Es wird davon ausge gangen, dass eine fruhere Ubersetzungsphase, der Typ checker, das Programm auf Typkorrektheit uberpruft und fur jedes syntaktische Konstrukt einen Typ berechnet hat, der wahrend der Codegenerierungsphase erfragt werden kann."

Spis treści

1 Projektgeschichte und Überblick.- 1.1 Das SAMP?E Projekt.- 1.2 Die funktionale Sprache SAMP?E.- 1.3 Die SAMP?E Programmierumgebung.- 1.4 Die Ausführung von SAMP?E Programmen.- 1.5 Übersetzer-Architektur und Maschinenmodelle.- 1.6 Aufbau dieser Arbeit.- 2 Einführung.- 2.1 MS — Eine einfache funktionale Sprache.- 2.2 Verzögerte Auswertung und Striktheitsanalyse.- 2.3 Eigenschaften moderner RISC Rechner.- 2.4 Prinzipielle Techniken der MS Implementierung.- 2.4.1 Polymorphismus.- 2.4.2 Automatische Speicherverwaltung und Struktur von Speicherzellen.- 2.4.3 Verzögerte Auswertung.- 2.4.4 Funktionen höherer Ordnung.- 3 Übersetzung von Sprachen mit verzögerter Auswertung.- 3.1 Phaseneinteilung des Übersetzers.- 3.2 Die abstrakte Registermaschine RM.- 3.3 Die abstrakte Syntax von MS.- 3.4 Suspensionsanalyse.- 3.5 RM-Übersetzer.- 3.5.1 RM-Codegeneratoren — die Basis der Übersetzerspezifikation.- 3.5.2 Codegenerator-Kombinatoren.- 3.5.3 Signatur der Übersetzerfunktionen.- 3.5.4 Übersetzen der globalen Definitionen.- 3.5.5 Übersetzen von Ausdrücken.- 3.5.6 Codegenerierung für verzögerte Ausdrücke.- 3.6 Optimierung der Repräsentation verzögerter Ausdrücke.- 3.6.1 Motivation.- 3.6.2 Die optimale Repräsentation von Suspensionen.- 3.6.3 Komplexität des Optimierungsproblems Optimale Suspensions-Repräsentation.- 3.6.4 Eine Näherungslösung des Optimierungsproblems.- 3.6.5 Suspensionsanalyse für Multisuspensionen.- 3.6.6 Anpassung des Übersetzers.- 3.6 Generierung von Objektcode am Beispiel des SPARC-Prozessors.- 3.6.1 Aktivieren des Garbage-Collectors und Optimierung von Speicherallokierungen.- 3.6.2 Verminderung der Anzahl der gleichzeitig lebendigen virtuellen Register.- 3.6.3 Registerzuteilung.- 4 Speicherverwaltung.- 4.1 Speicherfreigabe für Multisuspensionen.- 4.1.1 Einzelheiten des Two-Space-Copy-Collectors.- 4.1.2 Problematik der Speicherfreigabe für Multisuspensionen.- 4.1.3 Effiziente Speicherfreigabe für Multisuspensionen.- 4.2 Generationenbasierte Speicherbereinigung.- 4.2.1 Gründe und Voraussetzungen für die Anwendung generationsbasierter Techniken.- 4.2.2 Speicherallokierungsverhalten bei Sprachen mit verzögerter Auswertung.- 4.2.3 Ein einfacher generationsbasierter Garbage-Collector für Sprachen mit verzögerter Auswertung.- 4.2.4 Evaluierung der Garbage-Collector-Algorithmen.- 5 Testen bei verzögerter Auswertung.- 5.1 Einführung in die Problematik und Diskussion bisheriger Techniken.- 5.2 Das Boxmodell.- 5.3 Implementierung des Testsystems.- 6 Zusammenfassung und Ausblick.- 6.1 Codegenerierung.- 6.2 Speicherverwaltung.- 6.3 Testen.- A Die funktionale Sprache SAMP?E.- A.1 Lexikalische Konventionen.- A.2 Operatoren.- A.3 Ausdrücke.- A.4 Definition von Werten.- A.5 Module.- A.6 Typen.- A.6.1 Basistypen.- A.6.2 Vordefinierte strukturierte Typen.- A.6.3 Typsynonyme.- A.6.4 Summentypen.- A.7 Iterator-Ausdrücke.- B Standard SAMP?E-Funktionen.- C Befehle des SPARC-Prozessors.