ABSTRACT

How to organize information is one of the first and most important decisions a software developer faces. This decision affects application development in two fundamental ways, conceptual and structural. The way we conceptualize information profoundly affects the way we think about that information in order to solve problems. For a given application, thinking about the information one way may lead to a natural, easy-to-implement solution, while thinking about the same information another way may lead to an awkward, difficult solution. Consequently, careful decisions about the conceptual organization of information reduce total implementation time and increase both the elegance and extensibility of the resulting software. The act of conceptualizing information is known as data abstraction and results in the formation of abstract data types (ADTs) that capture the way we think about information. An ADT consists of (1) a set of operations (methods) that every implementation of that data type is expected to provide, and (2) a set of legal behaviors that capture how we expect implementation to behave when we invoke its operations. Together, these form a specification for a correct implementation of the ADT. For example, suppose an ADT includes, among others, the operations getSize and removeFirst. A specification might capture the expectation that the return value of getSize after a successful call to the removeFirst method should be one less than the return value of getSize immediately before the remove. It is critically important to notice that an ADT does not specify how the implementation should store the information or what steps it should take to access or modify the information. The ADT constrains the implementation only to the extent that a correct implementation must provide the required operations and exhibit only legal behaviors.