Program development in Java : abstraction, specification, and object-oriented design

Written by a world-renowned expert on programming methodology, and the winner of the 2008 Turing Award, 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. Preface, xv Acknowledgments, xix . 1 Introduction 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 Abstraction, 10 1.3 The Remainder of the Book, 12 . 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 Mothod 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 vs 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 Specifications of IntSet, 80 5.1.2 The Poly Abstraction, 83 5.2 Using Data Abstractions, 86 5.3 Implementing Data Abstractions, 86 5.3.1 Implementing Data A bstractions 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.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 Exerciese, 186 . 8 Polymorphic Abstractions, 189 8.1 Polymorphic Data Abstractions, 190 8.2 Using Polymorphic Data Abdstractions, 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, 232 13.6 Continuing the Design, 234 13.7 The Query Abstraction, 326 13.8 The WorldTable 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, 403 15.7.1 Abstracting Control, 403 15.8 Summary, 406 Exercises, 407 Glossary, 409 Index, 427 Of all the books that have sought to explain object-oriented, component-based development, this one is unique in its clarity. MIT Professor Barbara Liskov presents a start-to-finish methodology for constructing reliable, understandable, easy-to-maintain Java software.Developers will learn exactly how to decompose a programming problem into its key elements, and then build an optimal program from independent modules -- crucial for success in large-scale, team development projects. Liskov masterfully introduces key concepts of abstraction, specification, and object-oriented design in the context of small programs; then scales the techniques up to enterprise-class development, where they work equally well. The book includes detailed coverage of developing and writing accurate specifications; optimizing tradeoffs between simplicity and performance; and making code easier to evaluate, debug, and test. In the second half of the book, Liskov focuses on modular development of large-scale programs: discovering useful abstractions, program design, analysis, implementation, testing, and the value of design patterns. All examples are based on Java (though the concepts are equally applicable to any object-based language). This book is about efficient and effective programming practice. A component-based and object-oriented software engineering needs an approach involving abstraction, specification, and object-oriented design. The approach, which shows how to decompose a programming problem into parts and then how to build a desired program from independent modules, is critical for larger programs worked on by teams. The book illustrates particular techniques with implementations in Java (a brief introduction to Java is included for those not already familiar with the language). Beginning with smaller programs, to make sure the basic methodology is understood, the book then shows how to apply the same techniques for high-quality programming-in-the-large. (Publisher's copy) Liskov (engineering, Massachusetts Institute of Technology) and Guttag (computer science and engineering, also at MIT) present a component- based methodology for software program development. The book focuses on modular program construction: how to get the modules right and how to organize a program as a collection of modules. It explains the key types of abstractions, demonstrates how to develop specifications that define these abstractions, and illustrates how to implement them using numerous examples. An introduction to key Java concepts is included. Annotation copyrighted by Book News, Inc., Portland, OR 1. Introduction -- 2. Understanding Objects In Java -- 3. Procedural Abstraction -- 4. Exceptions -- 5. Data Abstraction -- 6. Iteration Abstraction -- 7. Type Hierarchy -- 8. Polymorphic Abstractions -- 9. Specifications -- 10. Testing And Debugging -- 11. Requirements Analysis -- 12. Requirements Specifications -- 13. Design -- 14. Between Design And Implementation -- 15. Design Patterns. Barbara Liskov With John Guttag.