1 Introduction 1
1.1 Decomposition and Abstraction 2
1.2 Abstraction 4
1.2.1 Abstraction by Parameterization 7
1.2.2 Abstraction by Specification 8
1.2.3 Kinds of Abstractions 10
1.3 The Remainder of the Book 12
Exercises 13
2 Understanding Objects in Java 15
2.1 Program Structure 15
2.2 Packages 17
2.3 Objects and Variables 18
2.3.1 Mutability 21
2.3.2 Method Call Semantics 22
2.4 Type Checking 24
2.4.1 Type Hierarchy 24
2.4.2 Conversions and Overloading 27
2.5 Dispatching 29
2.6 Types 30
2.6.1 Primitive Object Types 30
2.6.2 Vectors 31
2.7 Stream Input/Output 32
2.8 Java Applications 33
Exercises 35
3 Procedural Abstraction 39
3.1 The Benefits of Abstraction 40
3.2 Specifications 42
3.3 Specifications of Procedural Abstractions 43
3.4 Implementing Procedures 47
3.5 Designing Procedural Abstractions 50
3.6 Summary 55
Exercises 56
4 Exceptions 57
4.1 Specifications 59
4.2 The Java Exception Mechanism 61
4.2.1 Exception Types 61
4.2.2 Defining Exception Types 62
4.2.3 Throwing Exceptions 64
4.2.4 Handling Exceptions 65
4.2.5 Coping with Unchecked Exceptions 66
4.3 Programming with Exceptions 67
4.3.1 Reflecting and Masking 67
4.4 Design Issues 68
4.4.1 When to Use Exceptions 70
4.4.2 Checked versus Unchecked Exceptions 70
4.5 Defensive Programming 72
4.6 Summary 74
Exercises 75
5 Data Abstraction 77
5.1 Specifications for Data Abstractions 79
5.1.1 Specification of IntSet 80
5.1.2 The Poly Abstraction 83
5.2 Using Data Abstractions 85
5.3 Implementing Data Abstractions 86
5.3.1 Implementing Data Abstractions in Java 87
5.3.2 Implementation of IntSet 87
5.3.3 Implementation of Poly 89
5.3.4 Records 90
5.4 Additional Methods 94
5.5 Aids to Understanding Implementations 99
5.5.1 The Abstraction Function 99
5.5.2 The Representation Invariant 102
5.5.3 Implementing the Abstraction Function and Rep Invariant 105
5.5.4 Discussion 107
5.6 Properties of Data Abstraction Implementations 108
5.6.1 Benevolent Side Effects 108
5.6.2 Exposing the Rep 111
5.7 Reasoning about Data Abstractions 112
5.7.1 Preserving the Rep Invariant 113
5.7.2 Reasoning about Operations 114
5.7.3 Reasoning at the Abstract Level 115
5.8 Design Issues 116
5.8.1 Mutability 116
5.8.2 Operation Categories 117
5.8.3 Adequacy 118
5.9 Locality and Modifiability 120
5.10 Summary 121
Exercises 121
6 Iteration Abstraction 125
6.1 Iteration in Java 128
6.2 Specifying Iterators 130
6.3 Using Iterators 132
6.4 Implementing Iterators 134
6.5 Rep Invariants and Abstraction Functions for Generators 137
6.6 Ordered Lists 138
6.7 Design Issues 143
6.8 Summary 144
Exercises 144
7 Type Hierarchy 147
7.1 Assignment and Dispatching 149
7.1.1 Assignment 149
7.1.2 Dispatching 150
7.2 Defining a Type Hierarchy 152
7.3 Defining Hierarchies in Java 152
7.4 A Simple Example 154
7.5 Exception Types 161
7.6 Abstract Classes 161
7.7 Interfaces 166
7.8 Multiple Implementations 167
7.8.1 Lists 168
7.8.2 Polynomials 171
7.9 The Meaning of Subtypes 174
7.9.1 The Methods Rule 176
7.9.2 The Properties Rule 179
7.9.3 Equality 182
7.10 Discussion of Type Hierarchy 183
7.11 Summary 184
Exercises 186
8 Polymorphic Abstractions 189
8.1 Polymorphic Data Abstractions 190
8.2 Using Polymorphic Data Abstractions 193
8.3 Equality Revisited 193
8.4 Additional Methods 195
8.5 More Flexibility 198
8.6 Polymorphic Procedures 202
8.7 Summary 202
Exercises 204
9 Specifications 207
9.1 Specifications and Specificand Sets 207
9.2 Some Criteria for Specifications 208
9.2.1 Restrictiveness 208
9.2.2 Generality 211
9.2.3 Clarity 212
9.3 Why Specifications? 215
9.4 Summary 217
Exercises 219
10 Testing and Debugging 221
10.1 Testing 222
10.1.1 Black-Box Testing 223
10.1.2 Glass-Box Testing 227
10.2 Testing Procedures 230
10.3 Testing Iterators 231
10.4 Testing Data Abstractions 232
10.5 Testing Polymorphic Abstractions 235
10.6 Testing a Type Hierarchy 235
10.7 Unit and Integration Testing 237
10.8 Tools for Testing 239
10.9 Debugging 242
10.10 Defensive Programming 249
10.11 Summary 251
Exercises 252
11 Requirements Analysis 255
11.1 The Software Life Cycle 255
11.2 Requirements Analysis Overview 259
11.3 The Stock Tracker 264
11.4 Summary 269
Exercises 270
12 Requirements Specifications 271
12.1 Data Models 272
12.1.1 Subsets 273
12.1.2 Relations 274
12.1.3 Textual Information 278
12.2 Requirements Specifications 282
12.3 Requirements Specification for Stock Tracker 286
12.3.1 The Data Model 286
12.3.2 Stock Tracker Specification 289
12.4 Requirements Specification for a Search Engine 291
12.5 Summary 298
Exercises 298
13 Design 301
13.1 An Overview of the Design Process 301
13.2 The Design Notebook 304
13.2.1 The Introductory Section 304
13.2.2 The Abstraction Sections 308
13.3 The Structure of Interactive Programs 310
13.4 Starting the Design 315
13.5 Discussion of the Method 323
13.6 Continuing the Design 324
13.7 The Query Abstraction 326
13.8 The WordTable Abstraction 332
13.9 Finishing Up 333
13.10 Interaction between FP and UI 334
13.11 Module Dependency Diagrams versus DataModels 336
13.12 Review and Discussion 338
13.12.1 Inventing Helpers 339
13.12.2 Specifying Helpers 340
13.12.3 Continuing the Design 341
13.12.4 The Design Notebook 342
13.13 Top-Down Design 343
13.14 Summary 344
Exercises 345
14 Between Design and Implementation 347
14.1 Evaluating a Design 347
14.1.1 Correctness and Performance 348
14.1.2 Structure 353
14.2 Ordering the Program Development Process 360
14.3 Summary 366
Exercises 367
15 Design Patterns 369
15.1 Hiding Object Creation 371
15.2 Neat Hacks 375
15.2.1 Flyweights 375
15.2.2 Singletons 378
15.2.3 The State Pattern 382
15.3 The Bridge Pattern 385
15.4 Procedures Should Be Objects Too 386
15.5 Composites 390
15.5.1 Traversing the Tree 393
15.6 The Power of Indirection 399
15.7 Publish/Subscribe 402
15.7.1 Abstracting Control 403
15.8 Summary 406
Exercises 407
Glossary 409
Index 427