Dynamic compilation for functional programs [Elektronische Ressource] / vorgelegt von Martin Grabmüller

Sujets

• Informatik

Informations

• Publié par: technische_universitat_berlin
• Publié le: 01 janvier 2009
• Nombre de lectures: 21
• Langue: Deutsch

Extrait

Dynamic Compilation for Functional Programs
vorgelegt von Diplom-Informatiker
Martin Grabmuller
aus Munc hen
von der Fakult at IV { Elektrotechnik und Informatik
der Technischen Universit at Berlin
zur Erlangung des akademischen Grades
Doktor der Ingenieurwissenschaften
{ Dr.-Ing. {
genehmigte Dissertation
Promotionsausschuss:
Vorsitzender: Prof. Dr.-Ing. Sebastian M oller
Berichter: Prof. Dr. Peter Pepper
Berichter: Prof. Dr. Sabine Glesner
Tag der wissenschaftlichen Aussprache: 21. April 2009
Berlin 2009
D 832Zusammenfassung
Diese Arbeit behandelt die dynamische, zur Laufzeit statt ndende Ubersetzung und
Optimierung funktionaler Programme. Ziel der Optimierung ist die erhohte Laufzeit-
e zient der Programme, die durch die compilergesteuerte Eliminierung von Abstrak-
tionen der Programmiersprache erreicht wird.
Bei der Implementierung objekt-orientierter Programmiersprachen werden bereits seit
mehreren Jahrzehnten Compiler-Techniken zur Laufzeit eingesetzt, um objekt-orien-
tierte Programme e zient ausf uhren zu konnen. Spatestens seit der Einfuhrung der
Programmiersprache Java und ihres auf einer abstrakten Maschine basierenden Aus-
fuhrungsmodells hat sich die Praktikabilitat dieser Implementierungstechnik gezeigt.
Viele Eigenschaften moderner Programmiersprachen konnten erst durch den Einsatz
dynamischer Transformationstechniken e zient realisiert werden, wie zum Beispiel
das dynamische Nachladen von Programmteilen (auch ub er Netzwerke), Re ection
sowie verschiedene Sicherheitslosungen (z.B. Sandboxing).
Ziel dieser Arbeit ist zu zeigen, dass rein funktionale Programmiersprachen auf ahn-
liche Weise e zient implementiert werden k onnen, und sogar Vorteile gegenub er den
allgemein eingesetzten objekt-orientierten Sprachen bieten, was die E zienz, Sicher-
heit und Korrektheit von Programmen angeht.
Um dieses Ziel zu erreichen, werden in dieser Arbeit Implementierungstechniken
entworfen bzw. aus bestehenden Losungen weiterentwickelt, welche die dynamis-
che Kompilierung und Optimierung funktionaler Programme erlauben: zum einen
prasentieren wir eine Programmzwischendarstellung (getypte dynamische Continua-
tion-Passing-Style-Darstellung), welche sich zur dynamischen Kompilierung und Op-
timierung eignet. Basierend auf dieser Darstellung haben wir eine Erweiterung zur
verzogerten und selektiven Codeerzeugung von Programmteilen entwickelt. Der wich-
tigste Beitrag dieser Arbeit ist die dynamische Spezialisierung zur Eliminierung poly-
morpher Funktionen und Datenstrukturen, welche die E zienz funktionaler Pro-
gramme deutlich steigern kann. Die prasentierten Ergebnisse experimenteller Messun-
gen eines prototypischen Ausfuhrungssystems belegen, dass funktionale Programme
e zient dynamisch kompiliert werden k onnen.
34Summary
This thesis is about dynamic translation and optimization of functional programs.
The goal of the optimization is increased run-time e ciency, which is obtained by
compiler-directed elimination of programming language abstractions.
Object-oriented programming languages have been implemented for several decades
using run-time compilation techniques. With the introduction of the Java program-
ming language and its virtual machine-based execution model, the practicability of
this implementation method for real-world applications has been proved. Many as-
pects of modern programming languages, such as dynamic loading and linking of
code (even across networks), re ection and security solutions (e.g., sandboxing) can
be realized e ciently only by using dynamic transformation techniques.
The goal of this work is to show that functional programming languages can be e -
ciently implemented in a similar way, and that these languages even o er advantages
when compared to more common object-oriented languages. E ciency, security and
correctness of programs is easier to ensure in the functional setting.
Towards this goal, we design and develop implementation techniques to enable dy-
namic compilation and optimization of functional programming languages: we de-
scribe an intermediate representation for functional programs (typed dynamic con-
tinuation-passing style), which is well suited for dynamic compilation. Based on this
representation, we have developed an extension for incremental and selective code
generation. The main contribution of this work shows how dynamic specialization
of polymorphic functions and data structures can increase the run-time e ciency of
functional programs considerably. We present the results of experimental measure-
ments for a prototypical implementation, which prove that functional programs can
e ciently be dynamically compiled.
56Contents
1 Introduction 11
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.1 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.1.2 Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.3 Outline of this Dissertation . . . . . . . . . . . . . . . . . . . . . . . 14
2 Background 15
2.1 Functional Programming . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Dynamic Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.1 Virtual Machines . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.2 History of Dynamic Compilation . . . . . . . . . . . . . . . . 19
2.2.3 Dynamic Compilation Techniques . . . . . . . . . . . . . . . . 20
2.2.4 Dy and Functional Programming . . . . . . 22
2.2.5 Dynamic in Other Languages . . . . . . . . . . . 24
2.2.6 Formal Treatment of Dynamic Optimization . . . . . . . . . . 26
2.2.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 Analysis and Transformation . . . . . . . . . . . . . . . . . . . . . . . 28
2.4 Typed Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.1 Use of Type Systems . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.2 Continuation-passing Style . . . . . . . . . . . . . . . . . . . . 30
2.4.3 Closure Conversion . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4.4 Data Representation . . . . . . . . . . . . . . . . . . . . . . . 32
3 Dynamic Compilation of Functional Programs 35
3.1 Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 Compilation Process . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4 Typed Dynamic Continuation-passing Style 39
4.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2 Running Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.3 Source Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.3.2 Overloaded Numeric Literals and Primitive Operators . . . . . 45
78 CONTENTS
4.3.3 Static Semantics . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3.4 Dynamic Semantics . . . . . . . . . . . . . . . . . . . . . . . . 48
4.4 Continuation Language . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.4.1 Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.4.2 Static Semantics . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.4.3 Dynamic Semantics . . . . . . . . . . . . . . . . . . . . . . . . 53
4.5 CPS Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.6 Closure Conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.6.1 Type checking Closure-converted Terms . . . . . . . . . . . . 59
4.6.2 Closure Conversion Algorithm . . . . . . . . . . . . . . . . . . 61
4.6.3 Notes on Closure Conversion . . . . . . . . . . . . . . . . . . . 62
4.7 Generation of Machine Code . . . . . . . . . . . . . . . . . . . . . . . 65
5 Incremental Compilation 69
5.1 Language Extension . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.2 Code Generation for Delay Expressions . . . . . . . . . . . . . . . . . 70
5.3 Placing of Delay Expressions . . . . . . . . . . . . . . . . . . . . . . . 72
5.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6 Run-time Monomorphization 75
6.1 Specialization of Polymorphic Functions . . . . . . . . . . . . . . . . 76
6.1.1 Polymorphic Functions . . . . . . . . . . . . . . . . . . . . . . 76
6.1.2 P Recursion . . . . . . . . . . . . . . . . . . . . . . 81
6.1.3 Type Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.2 Data Type Specialization . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.2.1 Type-directed Representation Selection . . . . . . . . . . . . . 85
6.2.2 Data Layout Algorithm . . . . . . . . . . . . . . . . . . . . . . 87
7 Implementation 89
7.1 Implementation Outline . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.1.1 Front End . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.1.2 Conversion and Optimization . . . . . . . . . . . . . . . . . . 90
7.1.3 Code Generation . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.1.4 Run-time System . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.2 Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
8 Experimental Results 95
8.1 Test Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8.2 Bench