Topic: abstract data type

topics > computer science > programming > object-oriented programming > Group: type inheritance

data type
program design
program module
program proving
requirement specification

abstract functions
abstraction in programming language
automatic selection of algorithm for abstract data type
data type as a set of operations
decomposition of a system into levels
program module as encapsulation
generic operations and polymorphism
information hiding
interface type
object-oriented classes
object-oriented data types
object-oriented templates and containers
opaque and partially-opaque data types
representation data type
requirement specification by function
separate a module's interface specification from its implementation
software components
type parameter
types of object-oriented classes
user-defined data type


An abstract data type is an abstract specification of a data type. An implementation of an abstract data type is a concrete representation with matching attributes. An abstract data type specifies the names for operations and their semantic properties. Abstract data types are useful for program proofs.

(Topic: information hiding) is the use of interfaces to hide an implementation from its users. This is almost the same as an abstract data type. The main difference is that an interface usually has a concrete representation and normally does not specify the semantic properties of an operation.

In practice, abstract data types are difficult to use. They make lots of educational sense but the variability needed in real programs may be too high. Individual programs may depend only ony a few properties of abstract data type. Maybe an abstract data type is like a program cluster, i.e., a grab bag of features. A better design would be to split apart the abstract data type into all of its properties. These properties could then be attached to individual objects. The problem here is that semantic constraints are often interrelated. This would require sets of requirements mapping to sets of objects; too complicated.

The goal behind all this is to program in abstractions instead of programming in concrete implementations. Ideally the use of abstract data types would occur at all levels, i.e., the implementation of an abstraction would also be abstract. You then need a set of axioms to put the abstractions on a firm foundation. But these axioms define an abstract machine in which the abstractions are implemented. Now the original abstract data type is an implementation instead of an abstraction. Maybe this goal is unattainable. (cbb 1/90)

Subtopic: mathematical abstraction up

Quote: reason about programs in terms of mathematical domains; e.g., 'string of integers' for a stack or queue, not its concrete representation [»harmDE5_1991]
Quote: consistent and complete algebraic specification of abstract data types; e.g., a symbol table [»guttJV6_1977]
Quote: an abstract data type is an algebra fully specified by its axioms; independent of implementation or environment [»silbA2_1980]
Quote: the complex numbers is an abstraction that is represented by a variety of different sets

Subtopic: data abstraction up

Quote: data abstraction leads to programs as a collection of types, composing modules instead of individual procedures [»guttJV_2002]
Quote: data type abstraction allows one variable to be substituted for another without making the program illegal or meaningless [»parnDL3_1976]
Quote: data abstraction allows abbreviation, code sharing, and reuse; like subroutines [»parnDL3_1976]
Quote: with user-defined data types, programs are shorter; easier to write, understand, prove correct, modify [»parnDL3_1976]
Quote: a data representation is correct if every procedure models the intended abstract operation and initialization models the abstract, initial value [»hoarCA_1972a]

Subtopic: abstract data type up

Quote: an abstract data type is a class of objects defined by a representation-independent specification of its behavioral characteristics [»guttJV_2002]
Quote: a fixed set of type abstractions is not sufficient, need application-domain-specific types [»guttJV_2002]
Quote: decomposition creates structure while abstraction suppresses detail; data abstraction decomposes a system into domain-specific types that remain relevant over the lifetime of a program
Quote: program verification sees types as behavioral invariants that instances of the type must satisfy [»wegnP10_1986]
Quote: objects should be known via formally specified operations rather than by implementation; i.e., by abstract data type [»meyeB9_1990]
Quote: software elements should be implementations of well-understood specifications, not as arbitrary executable texts [»meyeB10_1992]
Quote: the object-oriented abstract type is a bigger building block than a module interface, procedure, statement, or instruction [»nelsG_1991]

Subtopic: abstract state up

Quote: Javari guarantees that a read-only reference cannot be used to reassign any field in the object's protected, abstract state [»tschMS10_2005]

Subtopic: abstraction up

Quote: a data type is a concrete representation of an idea or concept; e.g., 'float' [»stroB_1991]
Quote: primary goal of programming language is to program in abstractions instead of hardware facilities [»wirtN3_1976]
Quote: an abstract data type captures the essence of an object while a trait is a property
Quote: user-defined data types are abstractions; e.g., structured programming, stepwise refinement, and information hiding
Quote: software is not fractal; high-level design is qualitatively different from low-level design; e.g., system architecture, abstract data type, and implementation [»guttJV_2002]

Subtopic: interface of virtual methods up

Quote: an abstract type is an interface defined by pure virtual functions and no data members; most operations are virtual function calls [»stroB_1991]
Quote: single dispatching encourages the definition of abstract data types; multiple dispatching does not [»taivA9_1996]
Quote: abstract data types are important; provide access to a type's values through constants and functions; no access to implementation; like a primitive type [»brucKB3_1996]
Quote: encapsulation and interface inheritance are useful features of object-oriented programming [»oustJK3_1998]
Quote: Sketchpad includes general functions that are independent of type; e.g., expand an instance of a subpicture; powerful [»suthIE5_1963]
Quote: a 'file' class is any object or value with a given set of attributes; e.g., 'reset' defined [»maclBJ12_1983]
Quote: all enumerated and subrange types have standard set of accessing functions such as 'first' and 'pred' [»veneT3_1978]

Subtopic: set of operations up

Quote: with abstract data types, each object is defined by its structure and available operations; these operations ensure semantic integrity [»brodML1_1981]
Quote: an abstract data type is a class of objects defined by the operations available on those objects [»liskB4_1974]
Quote: programming by abstract data types: decide on types and define a full set of operations for each type [»stroB5_1989]

Subtopic: set of modes up

Quote: an abstract data type is a class of modes that specifies the permissible operands for its operators; can use any member of the mode class [»parnDL3_1976]
Quote: a programming language should be able to group modes into abstract types almost arbitrarily

Subtopic: representation invariant and abstraction function up

Quote: the representation invariant of an abstract type defines its valid representations as the values of a data structure [»guttJV_2002]
Quote: the abstraction function of an abstract type maps abstract values to values of its data structure [»guttJV_2002]

Subtopic: operations and representation up

Quote: an object implements an abstract data type with a private, mutable state and public operations on the state [»taivA4_1993]
Quote: an abstract data type is a representation type and a set of operations [»johnRI3_1976]
Quote: to use an abstract type as part of a concrete type, separate the abstract object into two parts: a handle providing the user interface and a representation holding the object's state [»stroB_1991]
Quote: abstract data as matrix of constructors and observations of abstract state; e.g. cons and head [»cookWR5_1990]
Quote: abstract data type as observations on tightly coupled representations (from constructors) [»cookWR5_1990]

Subtopic: separate representation up

Quote: algebraic specification allows multiple implementations of an abstract data type [»guttJV6_1977]
Quote: language should define the essential semantics of a construct with multiple, equivalent, implementations [»shawM3_1980]
Quote: Russell is representation independent, i.e., different value spaces exhibit the same behavior [»demeA3_1979]
Quote: specification types for abstract data types, representation types for implementing them [»boomHJ9_1976]
Quote: spec-types have different representations but the same set of operators; operators are generic [»parnDL3_1976]
Quote: an abstract specification of a problem is valid for a class of implementations; e.g., anything with mutually exclusive resource states [»brinP9_1978]
Quote: want to deal with a program's desired behavior instead of how it is implemented [»cheaTE_1976]
Quote: define generic, abstract data types with type parameters and hidden, representation types [»harmDE5_1991]
Quote: restrict data structures to a module; all other modules must call access programs [»parnDL3_1985]

Subtopic: symbolic execution up

Quote: test software by symbolically executing its algebraic sepecification [»guttJV6_1977]

Subtopic: maintenance up

Quote: an abstract class is easier to evolve than an interface; can not add methods to a public interface [»blocJ_2001]

Subtopic: examples up

Quote: Liskov got the idea for abstract data type in 1972; access the private data of an object via public operations; could be implemented in Simula 67 [»liskB_1996]
Quote: Cobol's data division provides physical and logical descriptions of files [»sammJE_1969, OK]
Quote: SUIT can dynamically change the display style of a bounded value object; demonstrates abstract data types [»pausR10_1992]
Quote: each SUIT object is an abstract data type with optional, multiple display styles [»pausR10_1992]
Quote: Amoeba objects are abstract data types managed by server processes
Quote: PODUS dynamically updates procedures; program must be written top-down with abstract data types [»segaME3_1993]
Quote: the Larch Shared Language specifies traits; i.e., operators, their properties, and their constraints; may be an abstract data type [»guttJV9_1985]

Subtopic: problems with abstract data type up

Quote: recursive procedural abstraction for interoperability vs. data abstraction for optimization [»cookWR5_1990]
Quote: abstract data type is difficult to extend; many changes to representation [»cookWR5_1990]
Quote: object oriented programming is objects and inheritance; abstract data types are too restrictive [»taivA4_1993]
Quote: use concrete types for efficiency and abstract types for flexibility; neither are useful for inheritance [»stroB_1991]
Quote: algebraic specification requires formal training in computer science; may limit its use

Related Topics up

Group: data type   (34 topics, 730 quotes)
Group: program design   (13 topics, 454 quotes)
Group: program module   (10 topics, 336 quotes)
Group: program proving   (10 topics, 311 quotes)
Group: requirement specification   (11 topics, 307 quotes)

Topic: abstract functions (11 items)
Topic: abstraction (62 items)
Topic: abstraction in programming language (47 items)
Topic: automatic selection of algorithm for abstract data type (7 items)
Topic: constraints (35 items)
Topic: data type as a set of operations (38 items)
Topic: decomposition of a system into levels (49 items)
Topic: program module as encapsulation (28 items)
Topic: generic operations and polymorphism (67 items)
Topic: information hiding (50 items)
Topic: interface type (50 items)
Topic: object-oriented classes (67 items)
Topic: object-oriented data types (29 items)
Topic: object-oriented templates and containers (27 items)
Topic: opaque and partially-opaque data types (14 items)
Topic: representation data type (21 items)
Topic: requirement specification by function (20 items)
Topic: separate a module's interface specification from its implementation (86 items)
Topic: software components (11 items)
Topic: type parameter (34 items)
Topic: types of object-oriented classes (18 items)
Topic: user-defined data type
(13 items)

Updated barberCB 12/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.