Introduction

Every time we decide to represent a certain set of quantities in a particular way, we are defining a new data type: the data type whose values are those representations and whose operations are the procedures that manipulate those entities. Data abstraction divides a data type into two pieces: an interface and an implementation.

• The interface tells us what the data of the type represents, what the operations on the data are, and what properties these operations may be relied on to have.
• The implementation provides a specific representation of the data and code for the operations that make use of that data representation.

Abstract Data Type

• A data type that is abstract in this way is said to be an abstract data type. The rest of the program, the client of the data type, manipulates the new data only through the operations specified in the interface. Thus if we wish to change the representation of the data, all we must do is change the implementation of the operations in the interface.
• When the client manipulates the values of the data type only through the procedures in the interface, we say that the client code is representation-independent, because then the code does not rely on the representation of the values in the data type.
• The most important part of an implementation is the specification of how the data is represented. We use the notation [v] for “the representation of data v.”

Example: Datatype of Natural Numbers

Interface

Of course, not just any set of procedures will be acceptable as an implementation of this interface. A set of procedures will be acceptable as implementations of zero, is-zero?, successor, and predecessor. This set of procedures is the interface specification for natural numbers. This specification does not dictate how these natural numbers are to be represented. It requires only that these procedures conspire to produce the specified behavior.

Constructors

Most interfaces will contain some constructors that build elements of the data type.

• (zero) ⇒ [0]
• (successor [n]) ⇒ [n+1]
• (predecessor [n+1]) ⇒ [n]

Observers

Most interfaces will contain some observers that extract information from values of the data type.

• (is-zero? [n]) ⇒ #t if [n] is a representation of 0, #f otherwise.

Client Code