Compiling with Continuations

This book shows how continuation-passing style is used as an intermediate representation to perform optimizations and program transformations. Continuations can be used to compile most programming languages. The method is illustrated in a compiler for the programming language Standard ML. Prior knowledge of ML, however, is not necessary, as the author carefully explains each concept as it arises. This is the first book to show how concepts from the theory of programming languages can be applied to the production of practical optimizing compilers for modern languages like ML. All the details of compiling are covered, including the interface to a runtime system and garbage collector. Contents Acknowledgments 1 Overview 1.1 Continuation-passing style 1.2 Advantages of CPS 1.3 What is ML 1.4 Compiler organization 2 Continuation-passing style 2.1 The CPS datatype 2.2 Functions that escape 2.3 Scope rules 2.4 Closure conversion 2.5 Spilling 3 Semantics of the CPS 4 ML-specific optimizations 4.1 Data representation 4.2 Pattern matching 4.3 Equality 4.4 Unboxed updates 4.5 The mini-ML sublanguage 4.6 Exception declarations 4.7 The lambda language 4.8 The module system 5 Conversion into CPS 5.1 Variables and constants 5.2 Records and selection 5.3 Primitive arithmetic operators 5.4 Function calls 5.5 Mutually recursive functions 5.6 Data constructors 5.7 Case statements 5.8 Exception handling 5.9 Call with current continuation 6 Optimization of the CPS 6.1 Constant folding and ??-contraction 6.2 Eta reduction and uncurrying 6.3 Cascading optimizations 6.4 Implementation 7 Beta expansion 7.1 When to do in-line expansion 7.2 Estimating the savings 7.3 Runaway expansion 8 Hoisting 8.1 Merging FIX de???nitions 8.2 Rules for hoisting 8.3 Hoisting optimizations 9 Common subexpressions 10 Closure conversion 10.1 A simple example 10.2 A bigger example 10.3 Closure-passing style 10.4 The closure-conversion algorithm 10.5 Closure representation 10.6 Callee-save registers 10.7 Callee-save continuation closures 10.8 Stack allocation of closures 10.9 Lifting function de???nitions to top level 11 Register spilling 11.1 Rearranging the expression 11.2 The spilling algorithm 12 Space complexity 12.1 Axioms for analyzing space 12.2 Preserving space complexity 12.3 Closure representations 12.4 When to initiate garbage collection 13 The abstract machine 13.1 Compilation units 13.2 Interface with the garbage collector 13.3 Position-independent code 13.4 Special-purpose registers 13.5 Pseudo-operations 13.6 Instructions of the continuation machine 13.7 Register assignment 13.8 Branch prediction 13.9 Generation of abstract-machine instructions 13.10 Integer arithmetic 13.11 Unboxed ???oating-point values 14 Machine-code generation 14.1 Translation for the VAX 14.1.1 Span-dependent instructions 14.2 Translation for the MC68020 14.3 Translation for the MIPS and SPARC 14.3.1 PC-relative addressing 14.3.2 Instruction scheduling 14.3.3 Anti-aliasing 14.3.4 Alternating temporaries 14.4 An example 15 Performance evaluation 15.1 Hardware 15.2 Measurements of individual optimizations 15.3 Tuning the parameters 15.4 More about caches 15.5 Compile time 15.6 Comparison with other compilers 15.7 Conclusions 16 The runtime system 16.1 E???ciency of garbage collection 16.2 Breadth-???rst copying 16.3 Generational garbage collection 16.4 Runtime data formats 16.5 Big bags of pages 16.6 Asynchronous interrupts 17 Parallel programming 17.1 Coroutines and semaphores 17.2 Better programming models 17.3 Multiple processors 17.4 Multiprocessor garbage collection 18 Future directions 18.1 Control dependencies 18.2 Type information 18.3 Loop optimizations 18.4 Garbage collection 18.5 Static single-assignment form 18.6 State threading A Introduction to ML A.1 Expressions A.2 Patterns A.3 Declarations A.4 Some examples B Semantics of the CPS C Obtaining Standard ML of New Jersey D Readings Bibliography Index The control and data flow of a program can be represented using continuations, a concept from denotational semantics that has practical application in real compilers. This book shows how continuation-passing style is used as an intermediate representation on which to perform optimisations and program transformations. Continuations can be used to compile most programming languages. The method is illustrated in a compiler for the programming language Standard ML. However, prior knowledge of ML is not necessary, as the author carefully explains each concept as it arises. This is the first book to show how concepts from the theory of programming languages can be applied to the producton of practical optimising compilers for modern languages like ML. This book will be essential reading for compiler writers in both industry and academe, as well as for students and researchers in programming language theory