9.7 Data Abstraction

Data abstraction involves the conception and use of a data structure as:

• an interface, which is implementation-neutral and contains function declarations;

• an implementation, which contains function definitions; and

• an application, which is also implementation-neutral and contains invocations to functions in the implementation; the application is sometimes called the main program or client code.

The underlying implementation can change without disrupting the client code as long as the contractual signature of each function declaration in the interface remains unchanged. In this way, the implementation is hidden from the application. A data type developed this way is called an abstract data type (ADT). Consider a list abstract data type. One possible representation for the list used in the implementation might be an array or vector. Another possible representation might be a linked list. (Note that Church Numerals are a representation of numbers in λ-calculus; see Programming Exercise 5.2.2.) A goal of a type system is to support the definition of abstract data types that have the properties and behavior of primitive types. One advantage of using an ADT is that the application is independent of the representation of the data structure used in the implementation. In turn, any implementation of the interface can be substituted without requiring modifications to the client application. In Section 9.8, we demonstrate a variety of possible representations for an environment ADT, all of which satisfy the requirements for the interface of the abstract data type and, therefore, maintain the integrity of the independence between the representation and the application.