Abstract data type

In computer science, an abstract data type (ADT) is a mathematical model for data types where a data type is defined by its behavior (semantics) from the point of view of a user of the data.

Description

Abstract data types can be categorized in terms of:

• Possible values
• Possible operations on data of this type
• The behavior of these operations

Data structures

This contrasts with data structures, which are concrete representations of data, and are the point of view of an implementer, not a user.

Formal definition

Formally, an ADT may be defined as a "class of objects whose logical behavior is defined by a set of values and a set of operations"; this is analogous to an algebraic structure in mathematics.

Behavior

What is meant by "behavior" varies by author, with the two main types of formal specifications for behavior being axiomatic (algebraic) specification and an abstract model; these correspond to axiomatic semantics and operational semantics of an abstract machine, respectively.

Some authors also include the computational complexity ("cost"), both in terms of time (for computing operations) and space (for representing values).

In practice many common data types are not ADTs, as the abstraction is not perfect, and users must be aware of issues like arithmetic overflow that are due to the representation.

For example, integers are often implemented as fixed width (32-bit or 64-bit binary numbers), and thus experience integer overflow if the maximum value is exceeded.

Theoretical concept

ADTs are a theoretical concept in computer science, used in the design and analysis of algorithms, data structures, and software systems, and do not correspond to specific features of computer languages.

Mainstream computer languages do not directly support formally specified ADTs.

ADTs were first proposed by Barbara Liskov and Stephen N. Zilles in 1974, as part of the development of the CLU language.

ADT-like features

Various language features correspond to certain aspects of ADTs, and are easily confused with ADTs proper; these include:

• Abstract types
• Data type
• Opaque data types
• Protocols
• Design by contract

See also

• Abstraction (software engineering)
• Abstraction principle (computer programming)
• Abstraction inversion for an anti-pattern of one danger in abstraction
• Algorithm for an abstract description of a computational procedure
• Bracket abstraction for making a term into a function of a variable
• Computer science
• Concept (generic programming)
• Data (computing)
• Data modeling for structuring data independent of the processes that use it
• Data structure
• Data type
• Design by contract
• Formal methods
• Functional specification
• Generalized algebraic data type
• Greenspun's Tenth Rule for an aphorism about an (the?) optimum point in the space of abstractions
• Higher-order function for abstraction where functions produce or consume other functions
• Information hiding (or "encapsulation") for abstractions that hide implementation details
• Initial algebra
• Joseph Goguen
• Lambda abstraction for making a term into a function of some variable
• Liskov substitution principle
• List of abstractions (computer science)
• Mathematical model
• Refinement (computing) for the opposite of abstraction in computing
• Type theory
• Walls and Mirrors

External links

• Abstract data type @ Wikipedia