Essentials of Compilation: An Incremental Approach in Python

Description

A hands-on approach to understanding and building compilers using the programming language Python. Compilers are notoriously difficult programs to teach and understand. Most books about compilers dedicate one chapter to each progressive stage, a structure that hides how language features motivate design choices. By contrast, this innovative textbook provides an incremental approach that allows students to write every single line of code themselves. Jeremy Siek guides the reader in constructing their own compiler in the powerful object-oriented programming language Python, adding complex language features as the book progresses. Essentials of Compilation explains the essential concepts, algorithms, and data structures that underlie modern compilers and lays the groundwork for future study of advanced topics. Already in wide use by students and professionals alike, this rigorous but accessible book invites readers to learn by doing. • Deconstructs the challenge of compiler construction into bite-sized pieces • Enhances learning by connecting language features to compiler design choices • Develops understanding of how programs are mapped onto computer hardware • Classroom-tested, hands-on approach suitable for students and professionals • Extensive ancillary resources include source code and solutions Preface 1 Preliminaries 1.1 Abstract Syntax Trees 1.2 Grammars 1.3 Pattern Matching 1.4 Recursive Functions 1.5 Interpreters 1.6 Example Compiler: A Partial Evaluator 2 Integers and Variables 2.1 The LVar Language 2.1.1 Extensible Interpreters via Method Overriding 2.1.2 Definitional Interpreter for LVar 2.2 The x86Int Assembly Language 2.3 Planning the Trip to x86 2.4 Remove Complex Operands 2.5 Select Instructions 2.6 Assign Homes 2.7 Patch Instructions 2.8 Generate Prelude and Conclusion 2.9 Challenge: Partial Evaluator for LVar 3 Parsing 3.1 Lexical Analysis and Regular Expressions 3.2 Grammars and Parse Trees 3.3 Ambiguous Grammars 3.4 From Parse Trees to Abstract Syntax Trees 3.5 Earley's Algorithm 3.6 The LALR(1) Algorithm 3.7 Further Reading 4 Register Allocation 4.1 Registers and Calling Conventions 4.2 Liveness Analysis 4.3 Build the Interference Graph 4.4 Graph Coloring via Sudoku 4.5 Patch Instructions 4.6 Generate Prelude and Conclusion 4.7 Challenge: Move Biasing 4.8 Further Reading 5 Booleans and Conditionals 5.1 The LIf Language 5.2 Type Checking LIf Programs 5.3 The CIf Intermediate Language 5.4 The x86If Language 5.5 Shrink the LIf Language 5.6 Remove Complex Operands 5.7 Explicate Control 5.8 Select Instructions 5.9 Register Allocation 5.9.1 Liveness Analysis 5.9.2 Build the Interference Graph 5.10 Patch Instructions 5.11 Generate Prelude and Conclusion 5.12 Challenge: Optimize Blocks and Remove Jumps 5.12.1 Optimize Blocks 5.12.2 Remove Jumps 5.13 Further Reading 6 Loops and Dataflow Analysis 6.1 The LWhile Language 6.2 Cyclic Control Flow and Dataflow Analysis 6.3 Remove Complex Operands 6.4 Explicate Control 6.5 Register Allocation 7 Tuples and Garbage Collection 7.1 The LTup Language 7.2 Garbage Collection 7.2.1 Two-Space Copying Collector 7.2.2 Graph Copying via Cheney's Algorithm 7.2.3 Data Representation 7.2.4 Implementation of the Garbage Collector 7.3 Expose Allocation 7.4 Remove Complex Operands 7.5 Explicate Control and the CTup Language 7.6 Select Instructions and the x86Global Language 7.7 Register Allocation 7.8 Generate Prelude and Conclusion 7.9 Challenge: Arrays 7.9.1 Data Representation 7.9.2 Overload Resolution 7.9.3 Bounds Checking 7.9.4 Expose Allocation 7.9.5 Remove Complex Operands 7.9.6 Explicate Control 7.9.7 Select Instructions 7.10 Further Reading 8 Functions 8.1 The LFun Language 8.2 Functions in x86 8.2.1 Calling Conventions 8.2.2 Efficient Tail Calls 8.3 Shrink LFun 8.4 Reveal Functions and the LFunRef Language 8.5 Limit Functions 8.6 Remove Complex Operands 8.7 Explicate Control and the CFun Language 8.8 Select Instructions and the x86Defcallq* Language 8.9 Register Allocation 8.9.1 Liveness Analysis 8.9.2 Build Interference Graph 8.9.3 Allocate Registers 8.10 Patch Instructions 8.11 Generate Prelude and Conclusion 8.12 An Example Translation 9 Lexically Scoped Functions 9.1 The L Language 9.2 Assignment and Lexically Scoped Functions 9.3 Uniquify Variables 9.4 Assignment Conversion 9.5 Closure Conversion 9.5.1 An Example Translation 9.6 Expose Allocation 9.7 Explicate Control and CClos 9.8 Select Instructions 9.9 Challenge: Optimize Closures 9.10 Further Reading 10 Dynamic Typing 10.1 The LDyn Language 10.2 Representation of Tagged Values 10.3 The LAny Language 10.4 Cast Insertion: Compiling LDyn to LAny 10.5 Reveal Casts 10.6 Assignment Conversion 10.7 Closure Conversion 10.8 Remove Complex Operands 10.9 Explicate Control and CAny 10.10 Select Instructions 10.11 Register Allocation for LAny 11 Gradual Typing 11.1 Type Checking L? 11.2 Interpreting LCast 11.3 Overload Resolution 11.4 Cast Insertion 11.5 Lower Casts 11.6 Differentiate Proxies 11.7 Reveal Casts 11.8 Closure Conversion 11.9 Select Instructions 11.10 Further Reading 12 Generics 12.1 Compiling Generics 12.2 Resolve Instantiation 12.3 Erase Generic Types A Appendix A.1 x86 Instruction Set Quick Reference References Index