Optimising the memory management of higher order functional programs [Elektronische Ressource] / [RWTH Aachen, Fachgruppe Informatik]. Vorgelegt von Markus Mohnen

Sujets

• Informatik

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 1997
• Nombre de lectures: 7
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Optimising the Memory Management of
Higher–Order Functional Programs
Von der Mathematisch–Naturwissenschaftlichen Fakult¨ at der
Rheinisch–Westf¨ alischen Technischen Hochschule Aachen zur Erlangung des
akademischen Grades eines Doktors der Naturwissenschaften genehmigte
Dissertation
vorgelegt von
Diplom–Informatiker Markus Mohnen
aus Erkelenz
Referent: Universit¨ atsprofessor Dr. rer. nat. K. Indermark
Korreferent: Prof. dr. ir. M. J. Plasmeijer
Tag der mundlic¨ hen Prufung:¨ 24.11.1997
D 82 (Diss. RWTH Aachen)
Markus Mohnen
Lehrstuhl fur¨ Informatik II
Email: [e-mail]
Aachener Informatik–Bericht 97–13
Herausgeber: Fachgruppe Informatik
Ahornstr. 55
RWTH Aachen
52056 Aachen
GERMANY
Druck: L¨ onnies & Schmitz Druckerei
Warmweiherstr. 22
52066 Aachen
GERMANY
ISSN 0935–3232
Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 The Benefits of Escape Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Correctness of Program . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Contributions of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Part I Analysis 7
2. The Language F . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Denotational Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Denotational Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3. Escaping as Denotational Property . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.1 Augmented Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2ted Denotational Semantics . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 Augmentation is Well–Behaved . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4tation is a Conservative Extension . . . . . . . . . . . . . . . . . . . . 29
3.5 Escaping as (Augmented) Denotational Property . . . . . . . . . . . . . . . . 32
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4. The Abstract Interpretation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.1 Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2 Interpretation of Selectors and Constructors . . . . . . . . . . . . . . . . . . . 41
4.3 In of (Partial) Applications . . . . . . . . . . . . . . . . . . . . . . 45
4.4 The Complete Abstract Interpretation . . . . . . . . . . . . . . . . . . . . . . 45
4.5 Efficient Computation of E . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
4.5.1 The Size of a Program . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.5.2 The Na¨ıve Fixpoint Computation . . . . . . . . . . . . . . . . . . . . . 49
4.5.3 Additivity of E . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.5.4 Structurally Recursive Functions . . . . . . . . . . . . . . . . . . . . . 53
4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5. Denotational Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
ii Contents
5.1 Relating Abstract and Concrete Domains . . . . . . . . . . . . . . . . . . . . 54
5.2 Denotational Safeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5.3 Void Abstract Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Part II Optimisations 63
6. The Semantics G: Modelling Eager Graph Reduction Denotationally . . . . . . . . 63
6.1 Heap Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.2 The Graph Domain G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6.3 Graph Expression Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.4 Fixpoints in Quasi Ordered Sets . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.5 Graph Program Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.6 Soundness of G wrt. M . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.7 Escaping as Graph Property . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7. Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.1 Compile–Time Garbage Collection . . . . . . . . . . . . . . . . . . . . . . . . 96
7.1.1 Program Annotations . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
7.1.2 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
7.1.3 Using the Abstract Interpretation E for Finding Annotations . . . . . 103
7.1.4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
7.2 Avoiding Heap Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
7.2.1 Further Improvement: Analysing the Call Structure . . . . . . . . . . 116
7.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Part III Extensions 118
8. Extensions of F . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
8.1 Syntactic Sugar: Pattern–Matching, Local Definitions, ... . . . . . . . . . . . 118
8.2 Constructors with Functional Arguments . . . . . . . . . . . . . . . . . . . . 118
8.3 Parametric Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
8.4 Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
8.5 Lazy Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
8.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
9. Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
9.1 Escape Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
9.1.1 Goldberg & Park’s Escape Analysis . . . . . . . . . . . . . . . . . . . 122
9.1.2 Hughes’ Inheritance Analysis . . . . . . . . . . . . . . . . . . . . . . . 125
9.1.3 Jones & Le M´etayer’s Transmission Analysis . . . . . . . . . . . . . . 125
9.1.4 The Analysis by Inoue, Seki, and Yagi . . . . . . . . . . . . . . . . . . 125
Contents iii
9.2 Flow Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
9.3 Compile–Time Garbage Collection . . . . . . . . . . . . . . . . . . . . . . . . 125
9.4 Uniqueness Type System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
9.5 Region Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
9.6 Deforestation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
9.6.1 Short Cut Deforestation . . . . . . . . . . . . . . . . . . . . . . . . . . 128
10. Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
10.1 Lazy Semantics on Quasi Ordered Sets . . . . . . . . . . . . . . . . . . . . . . 130
10.2 Costtics Based on Denotational Graph Semantics . . . . . . . . . . . . 131
10.3 Compile–Time Garbage Collection for Lazy Functional Languages . . . . . . 131
10.4 for Java . . . . . . . . . . . . . . . . . . . 132
Appendix 133
A. Universal Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
B. Symbols and Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
C. Source Code for C Version of qs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
Basic Notations
B Boolean values{0,1}
N Natural numbers{0,1,2,...}
P(A) Set of all subsets of A
P (A) Set of all finite subsets of Afin
A B Disjoint union of sets A and B
i ihA | i∈ Ii Family of sets A with index set I (see Appendix A)
f : A B Partial function
Dom(f) Domain of partial function f
f ∪ g Union of functions f and g with Dom(f)∩ Dom(g) =∅:

f(a) if a∈ Dom(f)
(f ∪ g)(a) :=
g(a) if a∈ Dom(g)
id Identity function
undef Function with empty domain, i.e. Dom(undef) =∅
f[a/b] Function g resulting from modification of f at a:

0b if a = a0g(a ) := 0f(a ) otherwise
f[a /b ,... ,a ,b ] Short form of f[a /b ]... [a /b ]1 1 n n 1 1 n n
[a /b ,... ,a ,b ] Short form of undef[a /b ,... ,a ,b ]1 1 n n 1 1 n n
[A ×···× A → B] Set of all functions f : A ×···× A → B1 n 1 n
(a) Selection of the i–th component a of vector a = (a ,... ,a )i i 1 n
hA, ≤i Partially ordered set (pos) (see Appendix A)
hA , ≤ i×hA , ≤ i Product of pos (see Appendix A)1 1 2 2
[hA , ≤i→hA , ≤ i] Function space of pos (see Appendix A)1 2 2
1. Introduction
In traditional programming languages like Pascal, C, or Ada recursive dynamic data struc-
tures like lists or trees are available by explicit access to t