Fully-parameterized, first-class modules with hygienic macros [Elektronische Ressource] / vorgelegt von Josef Martin Gasbichler

Martin Gasbichler

Sujets

• Informatik

Informations

• Publié par: eberhard_karls_universitat_tubingen
• Publié le: 01 janvier 2006
• Nombre de lectures: 12
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Fully-parameterized, First-class Modules with
Hygienic Macros
Dissertation
der Fakultat fur Informations- und Kognitionswissenschaften
der Eberhard-Karls-Universitat Tubingen
zur Erlangung des Grades eines
Doktors der Naturwissenschaften
(Dr. rer. nat.)
vorgelegt von
Dipl.-Inform. Josef Martin Gasbichler
aus Biberach/Ri
Tubingen
2006Tag der mun dlichen Quali kation: 15. 02. 2006
Dekan: Prof. Dr. Michael Diehl
1. Berichterstatter: Prof. Dr. Herbert Klaeren
2. Berichte Prof. Dr. Peter Thiemann
(Universitat Freiburg)Abstract
It is possible to de ne a formal semantics for con guration, elaboration, linking, and evaluation of
fully-parameterized rst-class modules with hygienic macros, independent compilation, and code
sharing. Thisdissertationde nessuchasemanticsmakinguseofexplicitsubstitutiontoformalize
hygienic expansion and linking. In the module system, interfaces de ne the static semantics of
modules and include the de nitions of exported macros. This enables full parameterization and
independent compilation of modules even in the presence of macros. Thus modules are truly
exchangeable components of the program. The basis for the module system is an operational
semanticsforhygienicmacroexpansion—computationalmacrosaswellasrewriting-basedmacros.
The macro semantics provides deep insight into the nature of hygienic macro expansion through
the use of explicit substitutions instead of conventional renaming techniques. The semantics
also includes the formal description of Macro Scheme, the meta-language used for evaluating
computational macros.
Zusammenfassung
Es ist moglic h, eine formale Semantik anzugeben, welche die Phasen Kon guration, syntak-
tische Analyse mit Makroexpansion, Linken und Auswertung fur ein vollparametrisiertes Mo-
dulsystem mit Modulen als Werten erster Klasse, unabhangi ger Ubersetzung und Code-Sharing
beschreibt. Diese Dissertation beschreibt eine solche Semantik. Dabei formalisieren explizite
Substitutionen die hygienische Makroexpansion und das Linken. Im Modulsystem beschreiben
SchnittstellendiestatischeSemantikvonModulenundenthaltendieDenitionenderexportierten
Makros. Dies ermoglicht volle Parametrisierung und unabhangige Ubersetzung sogar in Kombi-
nation mit Makros. Module sind damit echte austauschbare Komponenten eines Programms. Die
Grundlage fur das Modulsystem bildet eine operationelle Semantik fur hygienische Makroexpan-
sion die berechnende Makros ebenso beschreibt wie regelbasierte Makros. Durch die Verwendung
expliziter Substitutionen anstelle konventioneller Umbenennung gibt die Semantik fur Makro-
expansion tiefe Einblicke in das Wesen hygienischer Makroexpansion. Die Semantik beschreibt
au erdem Makro Scheme, die Metasprache f ur die berechnenden Makros.Contents
1 Introduction 1
1.1 Combining Modules and Macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Representation of Identi ers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Explicit Substitutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Structure of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Fully-Parameterized Module Systems 7
2.1 Fully-Parameterized Module Systems and Scheme . . . . . . . . . . . . . . . . . . . 7
2.2 The Programmer’s Point of View . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Phase Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5 The Missing Link Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.6 Transformation with Code Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7 Con guration Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.8 Semantics of the Con guration Language . . . . . . . . . . . . . . . . . . . . . . . 21
3 A Semantics for Hygienic Macros 25
3.1 Hygienic Macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 The Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29v
n,$%3.3 The Calculus. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31v
3.4 Parsing Scheme Without Macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.5 The Core Macro Expander. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.5.1 Time Complexity of the Macro Expander . . . . . . . . . . . . . . . . . . . 53
3.6 Computational Macro Transformers . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.6.1 The Semantics of Macro Scheme . . . . . . . . . . . . . . . . . . . . . . . . 57
3.6.2 Additional Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.6.3 Expanding Macro Applications Using es-transformer . . . . . . . . . . . 66
3.7 Parsing Scheme with Macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.8 Parsing and Macro Expansion for Macro Scheme . . . . . . . . . . . . . . . . . . . 75
3.8.1 Scoping Issues Between Object And Meta-Language . . . . . . . . . . . . . 76
3.9 Semantics of syntax-rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.9.1 Macro Expansion for syntax-rules . . . . . . . . . . . . . . . . . . . . . . 81
3.9.2 Elimination for Forms. . . . . . . . . . . . . . . . . . . . . . 83
3.9.3 Eion Rules for Patterns . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.9.4 Parsing syntax-rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.10 Future Work Towards Full Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.11 Comparison with the Work of Bove and Arbilla . . . . . . . . . . . . . . . . . . . . 94
4 Semantics for Modules 97
4.1 Identi er Representation and Linking for Modules . . . . . . . . . . . . . . . . . . 97
Module4.2 The Calculus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104n
4.2.1 Abstract Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
iii CONTENTS
4.2.2 Evaluation of Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.2.3 Eval of Module Expressions . . . . . . . . . . . . . . . . . . . . . . . 110
4.3 Parsing and Importing for Modules and Interfaces . . . . . . . . . . . . . . . . . . 113
4.4 Macro Expansion for Interfaces and Modules . . . . . . . . . . . . . . . . . . . . . 120
4.5 Independent Compilation and Code Sharing . . . . . . . . . . . . . . . . . . . . . . 125
4.6 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5 Implementation 129
5.1 Con guration Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5.1.1 The Backend for Scheme 48 . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.1.2 The PLT Backend . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.1.3 Con guration Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
5.2 Implementation of the Rewriting Systems . . . . . . . . . . . . . . . . . . . . . . . 131
Module5.2.1 Rewriting System for and Macro Scheme . . . . . . . . . . . . . . . 135n
5.2.2 A Short Review of Using PLT redex . . . . . . . . . . . . . . . . . . . . . . 135
5.3 Direct Implementation of the Macro Expander . . . . . . . . . . . . . . . . . . . . 136
5.3.1 Implementation of Macro Scheme . . . . . . . . . . . . . . . . . . . . . . . . 138
A5.4 Generation of LT X Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139E
6 Related Work 143
6.1 First-Class Macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
6.2 Fully-Parameterized Module Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 144
6.3 Macro Expansion Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
6.4 Module Systems with Macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
6.5 Meta-Languages for Macros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
7 Conclusions 149
7.1 Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
7.2 Insights Gained from the Macro Expansion Semantics . . . . . . . . . . . . . . . . 149
7.3 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
7.4 Closing Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
A Notation 153List of Figures
2.1 Overview of phases and entities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 The con guration language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Semantics of the con guration language . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Partial order among denition clauses . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.1 The language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
n3.2 Abstract syntax of . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Elimination of$% . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.4 Concrete Syntax based on s-expressions . . . . . . . . . . . . . . . . . . . . . . . . 39
3.5 Mixture of abstract and concrete syntax . . . . . . . . . . . . . . . . . . . . . . . . 40
3.6 Parsing r