After the invention of the concept of abstract data types, related work was dominated for some time by the development of theoretical foundations using algebra, category theory, or logic. This emphasis delayed the dissemination of this useful concept into the world of the practicing software engineer. This book tries to bridge the worlds of algebraic specification of abstract data types and implementation of abstract data types using Modula-2.

The concepts and development techniques offered in the book are called OOD-A, for object-oriented design using abstract data types. The presentation of OOD-A is divided into two parts.

The first part (six chapters) serves as an introduction to and explanation of abstract data types, specification of abstract data types using OBJ, and stepwise manual transformation of such specifications into Modula-2 modules. The second part, which contains the remaining nine chapters, describes the application of OOD-A to a small but nontrivial problem: creating an index of words in a textfile.

The first chapter gives a survey of the OOD-A approach. Following the OOD-A approach, a software system is seen as a set of structured documents to be developed, which all represent views of the system. In addition, Mitchell briefly compares OOD-A with Grady Booch’s OOD. In contrast to OOD, where the emphasis is on single objects and their implementation, OOD-A focuses on finding, describing, and implementing abstract types of objects.

Chapter 2 introduces abstract data types, which are represented by equational non-parameterized specifications using the language OBJ. Finding and describing a set of suitable abstract data types is addressed in chapter 3. A set of heuristic development rules is given, which is called case analysis. These rules allow one to derive details of an equational specification from a problem analysis. Some guidelines deal with the question of how to avoid redundant or overlapping cases and find a complete set of cases.

Chapter 4 describes how to map an abstract data type specification onto an implementation using Modula-2. The author describes a number of ways to transform an equational specification into a procedure formulated using an imperative programming language.

A particular problem inherent to Modula-2 is creating new objects of opaque types. The OOD-A approach uses opaque types to support encapsulation. Chapter 5 is devoted to basic storage management strategies addressing this problem. The approach given here is to mimic the way a compiler handles non-opaque types.

The explanation of OOD-A concludes with chapter 6, which addresses the problem of choosing good names for identifiers in specifications and programs. This chapter presents useful ideas about inventing names in a uniform and consistent way. For example, the proposed guidelines contain rules on when to choose verbs or nouns for procedure names.

The second part describes in detail the application of OOD-A to the index problem. Chapter 7 gives a short introduction, while chapter 8 discusses the decisions made at the strategic level about names, layout, and so on.

Chapter 9 describes how the architecture of the index system is structured in terms of abstract data types by giving a number of data type configurations of increasing detail and complexity. The abstract data types identified in chapter 9 are specified in chapter 10 using OBJ and case analysis.

Chapter 11 covers transforming the abstract data type architecture into an architecture composed of Modula-2 modules for solving the index problem. Various kinds of relations between abstract data type specifications and modules are discussed. No one-to-one mapping between them exists, due to error handling, finite resources, and other peculiarities of imperative languages in general and Modula-2 in particular. While chapter 11 deals with the transformation at the architecture level, chapter 12 covers the derivation of modules’ interface definitions from the signature of a related abstract data type specification.

Chapter 13 describes the implementation of the modules’ bodies. The equations of the abstract data type specifications serve in some cases as a guide for choosing an appropriate algorithm. While this approach is not advised in every case, the case analysis for finding the equations is also helpful in devising a skeleton for the algorithms.

How the final implementation detail is found is given in chapter 14. The missing algorithmic details, namely connections between modules and connections of the modules to the chosen environment, are described.

Chapter 15 gives an extension of the worked example by considering another version of the index program. Mitchell considers porting to a different environment and improving the performance of an internal sorting routine.

The book concludes with an appendix, a bibliography, and an adequate index. The appendix explains some alternative and more general guidelines for managing storage of opaque types. The good bibliography discusses basic papers and books on the various fields of software design covered.

Overall, the book is well written and meets its target of presenting a basic approach to designing a software system based on abstract data types. All ideas, techniques, and design decisions presented are discussed and justified at length. It serves as a good introduction to the topic.

The material has a few minor weaknesses. One is that the concept of views is briefly introduced in Part 1 and then extensively described in Part 2 only in conjunction with the example. A more elaborate and abstract description of the concept would have been appropriate. Also, the first part does not give a full description of OOD-A. The emphasis is on single specifications and related modules. Only in Part 2 does the architectural dimension of OOD-A become apparent. The discussion in Part 2, however, centers on the index system. Thus, a general and comprehensive discussion of architectural aspects of systems developed using OOD-A is missing. This information can only be obtained implicitly by abstracting from the index system in Part 2.

The discussion also fails to include two more elaborate aspects of software design: the use of parametrized abstract data types and object-oriented programming languages. Even beginners would have found a discussion of parametrized abstract data types and their use in software development and reuse helpful. In larger systems, more than one kind of list, table, or the like will appear as a software component, and the use of parametrized abstract data types to cope with architectural complexity is inevitable. Implementing parametrized abstract data types in a language like Modula-2 in a type-safe way is difficult, however. A second edition of the book is said to be in preparation using Ada as an implementation language. This change might overcome this weakness. With regard to object-oriented programming, the author simply says on page 4 that this area is outside the scope of the book, which is not appropriate.

Despite these minor weaknesses, I recommend the book, since it provides a useful set of development rules and techniques to build well-structured software systems. It also helps the reader to start working with equational specifications in a practical way, thus paving the way for introducing a sound mathematical approach to software engineering into practical work.