Table of Contents

Preface xi
Organization xiii
Instructional Use xiv
How to Get the Software xvi
Acknowledgments xvii
Chapter 1: Introduction 1
1.1 Literate Programs 2
1.2 Programming Style 8
1.3 Efficiency 11
Further Reading 12
Exercises 13
Chapter 2: Interfaces and Implementations 15
2.1 Interfaces 15
2.2 Implementations 18
2.3 Abstract Data Types 21
2.4 Client Responsibilities 24
2.5 Efficiency 30
Further Reading 30
Exercises 31
Chapter 3: Atoms 33
3.1 Interface 33
3.2 Implementation 34
Further Reading 42
Exercises 42
Chapter 4: Exceptions and Assertions 45
4.1 Interface 47
4.2 Implementation 53
4.3 Assertions 59
Further Reading 63
Exercises 64
Chapter 5: Memory Management 67
5.1 Interface 69
5.2 Production Implementation 73
5.3 Checking Implementation 76
Further Reading 85
Exercises 86
Chapter 6: More Memory Management 89
6.1 Interface 90
6.2 Implementation 92
Further Reading 98
Exercises 100
Chapter 7: Lists 103
7.1 Interface 103
7.2 Implementation 108
Further Reading 113
Exercises 114
Chapter 8: Tables 115
8.1 Interface 115
8.2 Example: Word Frequencies 118
8.3 Implementation 125
Further Reading 132
Exercises 133
Chapter 9: Sets 137
9.1 Interface 138
9.2 Example: Cross-Reference Listings 140
9.3 Implementation 148
Further Reading 158
Exercises 158
Chapter 10: Dynamic Arrays 161
10.1 Interfaces 162
10.2 Implementation 165
Further Reading 169
Exercises 169
Chapter 11: Sequences 171
11.1 Interface 171
11.2 Implementation 174
Further Reading 180
Exercises 180
Chapter 12: Rings 183
12.1 Interface 183
12.2 Implementation 187
Further Reading 196
Exercises 197
Chapter 13: Bit Vectors 199
13.1 Interface 199
13.2 Implementation 202
Further Reading 213
Exercises 213
Chapter 14: Formatting 215
14.1 Interface 216
14.2 Implementation 224
Further Reading 238
Exercises 239
Chapter 15: Low-Level Strings 241
15.1 Interface 243
15.2 Example: Printing Identifiers 249
15.3 Implementation 251
Further Reading 264
Exercises 265
Chapter 16: High-Level Strings 269
16.1 Interface 269
16.2 Implementation 276
Further Reading 293
Exercises 294
Chapter 17. Extended-Precision Arithmetic 297
17.1 Interface 297
17.2 Implementation 303
Further Reading 321
Exercises 322
Chapter 18: Arbitrary-Precision Arithmetic 323
18.1 Interface 323
18.2 Example: A Calculator 327
18.3 Implementation 334
Further Reading 353
Exercises 354
Chapter 19: Multiple-Precision Arithmetic 357
19.1 Interface 358
19.2 Example: Another Calculator 365
19.3 Implementation 373
Further Reading 402
Exercises 402
Chapter 20: Threads 405
20.1 Interfaces 408
20.2 Examples 418
20.3 Implementations 431
Further Reading 463
Exercises 465
Appendix: Interface Summary 469
Bibliography 497
Index 505

About the Author

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