Table of contents
Preface
1 Introduction
1.1 Partial evaluation = program specialization 1
1.2 Why do partial evaluation? 5
1.3 Computation in one stage or more 7
1.4 Partial evaluation and compilation 11
1.5 Automatic program generation 13
1.6 Critical assessment 15
1.7 Overview of the book 17
Part I: Fundamental Concepts in Programming Languages
2 Functions, Types, and Expressions
2.1 Functions 23
2.2 Types in programming languages 26
2.3 Recursive data types 32
2.4 Summary 36
2.5 Exercises 37
3 Programming Languages and Interpreters
3.1 Interpreters, compilers, and running times 38
3.2 The untyped lambda calculus: syntax and semantics 43
3.3 Three mini-languages 50
3.4 Compiling compilers 58
3.5 The central problems of compilation 60
3.6 Summary 61
3.7 Exercises 62
Part II: Principles of Partial Evaluation
4 Partial Evaluation for a Flow Chart Language
4.1 Introduction 68
4.2 What is partial evaluation? 69
4.3 Partial evaluation and compilation 73
4.4 Program specialization techniques 76
4.5 Algorithms used in mix 85
4.6 The second Futamura projection: compiler generation 86
4.7 Generating a compiler generator: mix^3 91
4.8 The tricks under the carpet 91
4.9 The granularity of binding-time analysis 94
4.10 Overview of mix performance 97
4.11 Summary and a more abstract perspective 98
4.12 Exercises 99
5 Partial Evaluation for a First-Order Functional Language
5.1 From flow charts to functions 101
5.2 Binding-time analysis by abstract interpretation 106
5.3 Adding annotations 110
5.4 Specialization algorithm for Scheme0 113
5.5 Call unfolding on the fly 118
5.6 Implementation 122
5.7 Using type rules for binding-time checking 123
5.8 Constructing the generating extension 125
5.9 Exercises 125
6 Efficiency, Speedup, and Optimality
6.1 Defining and measuring speedup 127
6.2 Flow chart mix gives linear speedup 130
6.3 Speedup analysis 132
6.4 Optimality of mix 138
6.5 Hierarchies of meta-languages 139
6.6 Exercises 141
7 Online, Offline, and Self-application
7.1 Decision making as a prephase? 145
7.2 Online and offline expression reduction 145
7.3 BTA and the taming of self-application 153
7.4 A recipe for self-application 157
7.5 Exercises 159
Part III: Partial Evaluation for Stronger Languages
8 Partial Evaluation for the Lambda Calculus 163
8.1 The lambda calculus and self-interpretation 164
8.2 Partial evaluation using a two-level lambda calculus 166
8.3 Congruence and consistency of annotations 169
8.4 Binding-time analysis 172
8.5 Simplicity versus power in Lambdamix 173
8.6 Binding-time analysis by type inference 175
8.7 BTA by solving constraints 175
8.8 Correctness of Lambdamix 183
8.9 Exercises 190
9 Partial Evaluation for Prolog (by Torben Mogensen)
9.1 An example 195
9.2 The structure of Logimix 196
9.3 Conclusion 200
9.4 Exercises 202
10 Aspects of Similix: A Partial Evaluator for a Subset of Scheme
10.1 An overview of Similix 204
10.2 Specialization with respect to functional values 210
10.3 Avoiding duplication 215
10.4 Call unfolding on the fly 217
10.5 Continuation-based reduction 218
10.6 Handling partially static structures 223
10.7 The Similix implementation 225
10.8 Exercises 225
11 Partial Evaluation for the C Language (by Lars Ole Andersen)
11.1 Introduction 229
11.2 Specialization of control flow 232
11.3 Function specialization 234
11.4 Data structures and their binding-time separation 239
11.5 Partial evaluation for C by two-level execution 245
11.6 Separation of the binding times 253
11.7 Self-application, types, and double encoding 256
11.8 C-mix: a partial evaluator for C programs 256
11.9 Towards partial evaluation for full Ansi C 258
11.10 Exercises 259
Part IV: Partial Evaluation in Practice
12 Binding-Time Improvements
12.1 A case study: Knuth, Morris, Pratt string matching 264
12.2 Bounded static variation 266
12.3 Conversion into continuation passing style 270
12.4 Eta conversion 273
12.5 Improvements derived from `free theorems' 274
12.6 Exercises 274
13 Applications of Partial Evaluation
13.1 Types of problems susceptible to partial evaluation 277
13.2 When can partial evaluation be of benefit? 285
13.3 Exercises 293
Part V: Advanced Topics
14 Termination of Partial Evaluation 297
14.1 Termination of online partial evaluators 297
14.2 Termination of offline partial evaluators 298
14.3 Binding-time analysis ensuring termination 301
14.4 Safety of BTA algorithm 305
14.5 Exercises 307
15 Program Analysis
15.1 Abstract interpretation 309
15.2 Closure analysis 314
15.3 Higher-order binding-time analysis 319
15.4 Projections and partially static data 323
15.5 Projection-based binding-time analysis 328
15.6 Describing the dynamic data 332
15.7 Summary 333
15.8 Exercises 333
16 Larger Perspectives
16.1 Relations to recursive function theory 335
16.2 Types for interpreters, compilers, and partial evaluators 337
16.3 Some research problems 346
17 Program Transformation
17.1 A language with pattern matching 347
17.2 Fold/unfold transformations 350
17.3 Partial evaluation by fold/unfold 355
17.4 Supercompilation and deforestation 358
17.5 Exercises 364
18 Guide to the Literature
18.1 A brief historical overview 366
18.2 Partial evaluation literature by subject language 368
18.3 Principles and techniques 370
18.4 Applications 372
18.5 Other topics related to partial evaluation 374
A The Self-Applicable Scheme0 Specializer
A.1 Using the Scheme0 specializer 376
A.2 Data structures in the Scheme0 specializer 378
A.3 The components of the Scheme0 specializer 380
Bibliography 389
Index 406
Back to book homepage.