Essentials of Compilation
An Incremental Approach in Racket
by Siek
ISBN: 9780262373289 | Copyright 2023
Instructor Requests
A hands-on approach to understanding and building compilers.
Compilers are notoriously some of the most 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. Essentials of Compilation guides the reader in constructing their own compiler for a small but powerful programming language, adding complex language features as the book progresses. Jeremy Siek 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
•Learn-by-doing approach suitable for students and professionals
•Proven in the classroom
•Extensive ancillary resources include source code and solutions
| Expand/Collapse All | |
|---|---|
| Cover (pg. Cover) | |
| Contents (pg. vii) | |
| Preface (pg. xi) | |
| 1. Preliminaries (pg. 1) | |
| 1.1 Abstract Syntax Trees (pg. 1) | |
| 1.2 Grammars (pg. 3) | |
| 1.3 Pattern Matching (pg. 4) | |
| 1.4 Recursive Functions (pg. 6) | |
| 1.5 Interpreters (pg. 6) | |
| 1.6 Example Compiler: A Partial Evaluator (pg. 9) | |
| 2. Integers and Variables (pg. 13) | |
| 2.1 The LVar Language (pg. 13) | |
| 2.2 The x86Int Assembly Language (pg. 16) | |
| 2.3 Planning the Trip to x86 (pg. 22) | |
| 2.4 Uniquify Variables (pg. 25) | |
| 2.5 Remove Complex Operands (pg. 27) | |
| 2.6 Explicate Control (pg. 28) | |
| 2.7 Select Instructions (pg. 30) | |
| 2.8 Assign Homes (pg. 31) | |
| 2.9 Patch Instructions (pg. 32) | |
| 2.10 Generate Prelude and Conclusion (pg. 33) | |
| 2.11 Challenge: Partial Evaluator for LVar (pg. 33) | |
| 3. Register Allocation (pg. 35) | |
| 3.1 Registers and Calling Conventions (pg. 36) | |
| 3.2 Liveness Analysis (pg. 38) | |
| 3.3 Build the Interference Graph (pg. 42) | |
| 3.4 Graph Coloring via Sudoku (pg. 44) | |
| 3.5 Patch Instructions (pg. 49) | |
| 3.6 Prelude and Conclusion (pg. 50) | |
| 3.7 Challenge: Move Biasing (pg. 52) | |
| 3.8 Further Reading (pg. 55) | |
| 4. Booleans and Conditionals (pg. 57) | |
| 4.1 The LIf Language (pg. 58) | |
| 4.2 Type Checking LIf Programs (pg. 59) | |
| 4.3 The CIf Intermediate Language (pg. 64) | |
| 4.4 The x86If Language (pg. 64) | |
| 4.5 Shrink the LIf Language (pg. 66) | |
| 4.6 Uniquify Variables (pg. 67) | |
| 4.7 Remove Complex Operands (pg. 67) | |
| 4.8 Explicate Control (pg. 68) | |
| 4.9 Select Instructions (pg. 74) | |
| 4.10 Register Allocation (pg. 75) | |
| 4.11 Patch Instructions (pg. 77) | |
| 4.12 Challenge: Optimize Blocks and Remove Jumps (pg. 77) | |
| 4.13 Further Reading (pg. 81) | |
| 5. Loops and Dataflow Analysis (pg. 83) | |
| 5.1 The LWhile Language (pg. 84) | |
| 5.2 Cyclic Control Flow and Dataflow Analysis (pg. 85) | |
| 5.3 Mutable Variables and Remove Complex Operands (pg. 89) | |
| 5.4 Uncover get! (pg. 91) | |
| 5.5 Remove Complex Operands (pg. 92) | |
| 5.6 Explicate Control and C⟲ (pg. 93) | |
| 5.7 Select Instructions (pg. 94) | |
| 5.8 Register Allocation (pg. 95) | |
| 6. Tuples and Garbage Collection (pg. 97) | |
| 6.1 The LTup Language (pg. 97) | |
| 6.2 Garbage Collection (pg. 100) | |
| 6.3 Expose Allocation (pg. 108) | |
| 6.4 Remove Complex Operands (pg. 109) | |
| 6.5 Explicate Control and the CTup Language (pg. 110) | |
| 6.6 Select Instructions and the x86Global Language (pg. 110) | |
| 6.7 Register Allocation (pg. 115) | |
| 6.8 Prelude and Conclusion (pg. 115) | |
| 6.9 Challenge: Simple Structures (pg. 117) | |
| 6.10 Challenge: Arrays (pg. 119) | |
| 6.11 Uncover get! (pg. 123) | |
| 6.12 Challenge: Generational Collection (pg. 124) | |
| 6.13 Further Reading (pg. 125) | |
| 7. Functions (pg. 127) | |
| 7.1 The LFun Language (pg. 127) | |
| 7.2 Functions in x86 (pg. 132) | |
| 7.3 Shrink LFun (pg. 135) | |
| 7.4 Reveal Functions and the LFunRef Language (pg. 135) | |
| 7.5 Limit Functions (pg. 135) | |
| 7.6 Remove Complex Operands (pg. 136) | |
| 7.7 Explicate Control and the CFun Language (pg. 136) | |
| 7.8 Select Instructions and the x86Defcallq* Language (pg. 138) | |
| 7.9 Register Allocation (pg. 140) | |
| 7.10 Patch Instructions (pg. 141) | |
| 7.11 Prelude and Conclusion (pg. 141) | |
| 7.12 An Example Translation (pg. 143) | |
| 8. Lexically Scoped Functions (pg. 145) | |
| 8.1 The Lλ Language (pg. 147) | |
| 8.2 Assignment and Lexically Scoped Functions (pg. 150) | |
| 8.3 Assignment Conversion (pg. 150) | |
| 8.4 Closure Conversion (pg. 152) | |
| 8.5 An Example Translation (pg. 154) | |
| 8.6 Expose Allocation (pg. 155) | |
| 8.7 Explicate Control and CClos (pg. 155) | |
| 8.8 Select Instructions (pg. 155) | |
| 8.9 Challenge: Optimize Closures (pg. 158) | |
| 8.10 Further Reading (pg. 160) | |
| 9. Dynamic Typing (pg. 161) | |
| 9.1 The LDyn Language (pg. 161) | |
| 9.2 Representation of Tagged Values (pg. 166) | |
| 9.3 The LAny Language (pg. 166) | |
| 9.4 Cast Insertion: Compiling LDyn to LAny (pg. 172) | |
| 9.5 Reveal Casts (pg. 173) | |
| 9.6 Remove Complex Operands (pg. 174) | |
| 9.7 Explicate Control and CAny (pg. 174) | |
| 9.8 Select Instructions (pg. 174) | |
| 9.9 Register Allocation for LAny (pg. 177) | |
| 10. Gradual Typing (pg. 179) | |
| 10.1 Type Checking L? (pg. 179) | |
| 10.2 Interpreting LCast (pg. 187) | |
| 10.3 Cast Insertion (pg. 188) | |
| 10.4 Lower Casts (pg. 191) | |
| 10.5 Differentiate Proxies (pg. 192) | |
| 10.6 Reveal Casts (pg. 194) | |
| 10.7 Closure Conversion (pg. 195) | |
| 10.8 Select Instructions (pg. 195) | |
| 10.9 Further Reading (pg. 196) | |
| 11. Generics (pg. 199) | |
| 11.1 Compiling Generics (pg. 206) | |
| 11.2 Resolve Instantiation (pg. 207) | |
| 11.3 Erase Generic Types (pg. 207) | |
| A. Appendix (pg. 211) | |
| A.1 Interpreters (pg. 211) | |
| A.2 Utility Functions (pg. 211) | |
| A.3 x86 Instruction Set Quick Reference (pg. 212) | |
| References (pg. 215) | |
| Index (pg. 223) | |
| Instructors Only | |
|---|---|
|
You must have an instructor account and submit a request to access instructor materials for this book.
|
|
eTextbook
Go paperless today! Available online anytime, nothing to download or install.
Features
|
