1 Introduction 1
1.1 Literate Programs 2
1.2 Programming Style 8
1.3 Efficiency 11
Further Reading 12
Exercises 13
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
3 Atoms 33
3.1 Interface 33
3.2 Implementation 34
Further Reading 42
4 Exceptions and Assertions 45
4.1 Interface 47
.4.2 Implementation 53
4.3 Assertions 59
Further Reading 63
Exercises 64
5 Memory Management 67
5.1 Interface 69
5.2 Production Implementation 73
5.3 Checking Implementation 76
Further Reading 85
Exercises 86
6 More Memory Management 89
6.1 Interface 90
6.2 Implementation 92
Further Reading 98
Exercises 100
7 Lists 103
7.1 Interface 103
7.2 Implementation 108
Further Reading 113
Exercises 114
8 Tables 115
8.1 Interface 115
8.2 Example: Word Frequencies 118
8.3 Implementation 12 5
Further Reading 132
Exercises 133
9 Sets 137
9.1 Interface 138
9.2 Example: Cross-Reference Listings 140
9.3 Implementation 148
9.3.1 Member Operations 150
9.3.2 Set Operations 154
Further Reading 158
Exercises 158
10 Dynamic Arrays
10.1 Interfaces 162
10.2 Implementation 165
Further Reading 169
Exercises 169
11 Sequences 171
11.1 Interface 171
11.2 Implementation 174
Further Reading 180
Exercises 180
12 Rings 183
12.1 Interface 183
12.2 Implementation 187
Further Reading 196
Exercises 197
13 Bit Vectors 199
13.1 Interface 199
13.2 Implementation 202
13.2.1 Member Operations 204
13.2.2 Comparisons 209
13.2.3 Set Operations 211
Further Reading 213
Exercises 21314 Formatting 215
14.1 Interface 216
14.1.1 Formatting Functions 216
14.1.2 Conversion Functions 219
14.2 Implementation 224
14.2.1 Formatting Functions 225
14.2.2 Conversion Functions 232
Further Reading 238
Exercises 239
15 Low-LevelStrings 241
15.1 Interface 243
15.2 Example: Printing Identifiers 249
15.3 Implementation 251
15.3.1 String Operations 252
15.3.2 Analyzing Strings 258
15.3.3 Conversion Functions 263
Further Reading 264
Exercises 265
16 High-LevelStrings 269
16.1 Interface 269
16.2 Implementation 276
16.2.1 String Operations 281
16.2.2 Memory Management 285
16.2.3 Analyzing Strings 288
16.2.4 Conversion Functions 293
Further Reading 293
Exercises 294
17 Extended-Precision Arithmetic 297
17.1 Interface 297
17.2 Implementation 303
17.2.1 Addition and Subtraction 305
17.2.2 Multiplication 307
17.2.3 Division and Comparison 309
17.2.4 Shifting 315
17.2.5 String Conversions 319
Further Reading 321
Exercises 322
18 Arbitrary-Precision Arithmetic 323
18.1 Interface 323
18.2 Example: A Calculator 327
18.3 Implementation 334
18.3.1 Negation and Multiplication 337
18.3.2 Addition and Subtraction 338
18.3.3 Division 342
18.3.4 Exponentiation 343
18.3.5 Comparisons 346
18.3.6 Convenience Functions 347
18.3.7 Shifting 349
18.3.8 String and Integer Conversions 350
Further Reading 353
Exercises 354
19 Multiple-Precision Arithmetic 357
19.1 Interface 358
19.2 Example: Another Calculator 365
19.3 Implementation 373
19.3.1 Conversions 377
19.3.2 Unsigned Arithmetic 380
19.3.3 Signed Arithmetic 383
19.3.4 Convenience Functions 388
19.3.5 Comparisons and Logical Operations 395
19.3.6 String Conversions 399
Further Reading 402
Exercises 402
20 Threads 405
20.1 Interfaces 408
20.1.1 Threads 409
20.1.2 General Semaphores 413
20.1.3 Synchronous Communication Channels 417
20.2 Examples 418
20.2.1 Sorting Concurrently 418
20.2.2 Critical Regions 423
20.2.3 Generating Primes 426
20.3 Implementations 431
20.3.1 Synchronous Communication Channels 431
20.3.2 Threads 434
20.3.3 Thread Creation and Context-Switching 446
20.3.4 Preemption 454
20.3.5 General Semaphores 457
20.3.6 Context-Switching on the MIPS and ALPHA 459
Further Reading 463
Exercises 465
Interface Summary 469
Bibliography 497
Index 505