David R. Hanson is a Professor of Computer Science at Princeton University with more than 20 years of research experience in programming languages. He has conducted research in conjunction with Bell Laboratories and is the co-author of lcc, a production quality, research compiler for the C language that is popular with the Unix community. lcc is presented and analyzed in the book A Retargetable C Compiler: Design and Implementation, by Christopher Fraser and David Hanson (c) 1995, Addison-Wesley. 0201498413AB04062001

• Preface xiOrganization xiiiInstructional Use xivHow to Get the Software xviAcknowledgments xviiChapter 1: Introduction 11.1 Literate Programs 21.2 Programming Style 81.3 Efficiency 11Further Reading 12Exercises 13Chapter 2: Interfaces and Implementations 152.1 Interfaces 152.2 Implementations 182.3 Abstract Data Types 212.4 Client Responsibilities 242.5 Efficiency 30Further Reading 30Exercises 31Chapter 3: Atoms 333.1 Interface 333.2 Implementation 34Further Reading 42Exercises 42Chapter 4: Exceptions and Assertions 454.1 Interface 474.2 Implementation 534.3 Assertions 59Further Reading 63Exercises 64Chapter 5: Memory Management 675.1 Interface 695.2 Production Implementation 735.3 Checking Implementation 76Further Reading 85Exercises 86Chapter 6: More Memory Management 896.1 Interface 906.2 Implementation 92Further Reading 98Exercises 100Chapter 7: Lists 1037.1 Interface 1037.2 Implementation 108Further Reading 113Exercises 114Chapter 8: Tables 1158.1 Interface 1158.2 Example: Word Frequencies 1188.3 Implementation 125Further Reading 132Exercises 133Chapter 9: Sets 1379.1 Interface 1389.2 Example: Cross-Reference Listings 1409.3 Implementation 148Further Reading 158Exercises 158Chapter 10: Dynamic Arrays 16110.1 Interfaces 16210.2 Implementation 165Further Reading 169Exercises 169Chapter 11: Sequences 17111.1 Interface 17111.2 Implementation 174Further Reading 180Exercises 180Chapter 12: Rings 18312.1 Interface 18312.2 Implementation 187Further Reading 196Exercises 197Chapter 13: Bit Vectors 19913.1 Interface 19913.2 Implementation 202Further Reading 213Exercises 213Chapter 14: Formatting 21514.1 Interface 21614.2 Implementation 224Further Reading 238Exercises 239Chapter 15: Low-Level Strings 24115.1 Interface 24315.2 Example: Printing Identifiers 24915.3 Implementation 251Further Reading 264Exercises 265Chapter 16: High-Level Strings 26916.1 Interface 26916.2 Implementation 276Further Reading 293Exercises 294Chapter 17. Extended-Precision Arithmetic 29717.1 Interface 29717.2 Implementation 303Further Reading 321Exercises 322Chapter 18: Arbitrary-Precision Arithmetic 32318.1 Interface 32318.2 Example: A Calculator 32718.3 Implementation 334Further Reading 353Exercises 354Chapter 19: Multiple-Precision Arithmetic 35719.1 Interface 35819.2 Example: Another Calculator 36519.3 Implementation 373Further Reading 402Exercises 402Chapter 20: Threads 40520.1 Interfaces 40820.2 Examples 41820.3 Implementations 431Further Reading 463Exercises 465Appendix: Interface Summary 469Bibliography 497Index 505

David R. Hanson is a Professor of Computer Science at Princeton University with more than 20 years of research experience in programming languages. He has conducted research in conjunction with Bell Laboratories and is the co-author of lcc, a production quality, research compiler for the C language that is popular with the Unix community. lcc is presented and analyzed in the book A Retargetable C Compiler: Design and Implementation, by Christopher Fraser and David Hanson (c) 1995, Addison-Wesley. 0201498413AB04062001

• Preface xiOrganization xiiiInstructional Use xivHow to Get the Software xviAcknowledgments xviiChapter 1: Introduction 11.1 Literate Programs 21.2 Programming Style 81.3 Efficiency 11Further Reading 12Exercises 13Chapter 2: Interfaces and Implementations 152.1 Interfaces 152.2 Implementations 182.3 Abstract Data Types 212.4 Client Responsibilities 242.5 Efficiency 30Further Reading 30Exercises 31Chapter 3: Atoms 333.1 Interface 333.2 Implementation 34Further Reading 42Exercises 42Chapter 4: Exceptions and Assertions 454.1 Interface 474.2 Implementation 534.3 Assertions 59Further Reading 63Exercises 64Chapter 5: Memory Management 675.1 Interface 695.2 Production Implementation 735.3 Checking Implementation 76Further Reading 85Exercises 86Chapter 6: More Memory Management 896.1 Interface 906.2 Implementation 92Further Reading 98Exercises 100Chapter 7: Lists 1037.1 Interface 1037.2 Implementation 108Further Reading 113Exercises 114Chapter 8: Tables 1158.1 Interface 1158.2 Example: Word Frequencies 1188.3 Implementation 125Further Reading 132Exercises 133Chapter 9: Sets 1379.1 Interface 1389.2 Example: Cross-Reference Listings 1409.3 Implementation 148Further Reading 158Exercises 158Chapter 10: Dynamic Arrays 16110.1 Interfaces 16210.2 Implementation 165Further Reading 169Exercises 169Chapter 11: Sequences 17111.1 Interface 17111.2 Implementation 174Further Reading 180Exercises 180Chapter 12: Rings 18312.1 Interface 18312.2 Implementation 187Further Reading 196Exercises 197Chapter 13: Bit Vectors 19913.1 Interface 19913.2 Implementation 202Further Reading 213Exercises 213Chapter 14: Formatting 21514.1 Interface 21614.2 Implementation 224Further Reading 238Exercises 239Chapter 15: Low-Level Strings 24115.1 Interface 24315.2 Example: Printing Identifiers 24915.3 Implementation 251Further Reading 264Exercises 265Chapter 16: High-Level Strings 26916.1 Interface 26916.2 Implementation 276Further Reading 293Exercises 294Chapter 17. Extended-Precision Arithmetic 29717.1 Interface 29717.2 Implementation 303Further Reading 321Exercises 322Chapter 18: Arbitrary-Precision Arithmetic 32318.1 Interface 32318.2 Example: A Calculator 32718.3 Implementation 334Further Reading 353Exercises 354Chapter 19: Multiple-Precision Arithmetic 35719.1 Interface 35819.2 Example: Another Calculator 36519.3 Implementation 373Further Reading 402Exercises 402Chapter 20: Threads 40520.1 Interfaces 40820.2 Examples 41820.3 Implementations 431Further Reading 463Exercises 465Appendix: Interface Summary 469Bibliography 497Index 505