Program Development in Java

Written by a world-renowned expert on programming methodology, this book shows how to build production-quality programs--programs that are reliable, easy to maintain, and quick to modify. Its emphasis is on modular program construction: how to get the modules right and how to organize a program as a collection of modules. The book presents a methodology effective for either an individual programmer, who may be writing a small program or a single module in a larger one; or a software engineer, who may be part of a team developing a complex program comprised of many modules. Both audiences will acquire a solid foundation for object-oriented program design and component-based software development from this methodology.

Because each module in a program corresponds to an abstraction, such as a collection of documents or a routine to search the collection for documents of interest, the book first explains the kinds of abstractions most useful to programmers: procedures; iteration abstractions; and, most critically, data abstractions. Indeed, the author treats data abstraction as the central paradigm in object-oriented program design and implementation. The author also shows, with numerous examples, how to develop informal specifications that define these abstractions--specifications that describe what the modules do--and then discusses how to implement the modules so that they do what they are supposed to do with acceptable performance.

Other topics discussed include:

• Encapsulation and the need for an implementation to provide the behavior defined by the specification
• Tradeoffs between simplicity and performance
• Techniques to help readers of code understand and reason about it, focusing on such properties as rep invariants and abstraction functions
• Type hierarchy and its use in defining families of related data abstractions
• Debugging, testing, and requirements analysis
• Program design as a top-down, iterative process, and design patterns

The Java programming language is used for the book's examples. However, the techniques presented are language independent, and an introduction to key Java concepts is included for programmers who may not be familiar with the language.

Contents

Preface xv

Acknowledgments xix

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 Data Models 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