Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s that have similar behavior; or for certain data type
Data type
In computer programming, a data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of...
s of one or more programming languages that have similar semantics
Semantics
Semantics is the study of meaning. It focuses on the relation between signifiers, such as words, phrases, signs and symbols, and what they stand for, their denotata....
. An abstract data type is defined indirectly, only by the operations that may be performed on it and by mathematical constraints on the effects (and possibly cost
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
) of those operations.
For example, an abstract stack data structure could be defined by three operations: push, that inserts some data item onto the structure, pop, that extracts an item from it (with the constraint that each pop always returns the most recently pushed item that has not been popped yet), and peek, that allows data on top of the structure to be examined without removal. When analyzing the efficiency
Analysis of algorithms
To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
of algorithms that use stacks, one may also specify that all operations take the same time no matter how many items have been pushed into the stack, and that the stack uses a constant amount of storage for each element.
Abstract data types are purely theoretical entities, used (among other things) to simplify the description of abstract algorithms, to classify and evaluate data structures, and to formally describe the type system
Type system
A type system associates a type with each computed value. By examining the flow of these values, a type system attempts to ensure or prove that no type errors can occur...
s of programming languages. However, an ADT may be implemented
Implementation
Implementation is the realization of an application, or execution of a plan, idea, model, design, specification, standard, algorithm, or policy.-Computer Science:...
In computer programming, a data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of...
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s, in many ways and in many programming languages; or described in a formal specification language. ADTs are often implemented as modules
Modular programming
Modular programming is a software design technique that increases the extent to which software is composed of separate, interchangeable components called modules by breaking down program functions into modules, each of which accomplishes one function and contains everything necessary to accomplish...
In the field of computer science, an interface is a tool and concept that refers to a point of interaction between components, and is applicable at the level of both hardware and software...
declares procedures that correspond to the ADT operations, sometimes with comments
Comment (computer programming)
In computer programming, a comment is a programming language construct used to embed programmer-readable annotations in the source code of a computer program. Those annotations are potentially significant to programmers but typically ignorable to compilers and interpreters. Comments are usually...
In computer science, information hiding is the principle of segregation of the design decisions in a computer program that are most likely to change, thus protecting other parts of the program from extensive modification if the design decision is changed...
strategy allows the implementation of the module to be changed without disturbing the client
Client (computing)
A client is an application or system that accesses a service made available by a server. The server is often on another computer system, in which case the client accesses the service by way of a network....
programs.
The term abstract data type can also be regarded as a generalised approach of a number of algebraic structures, such as lattices, groups, and rings. This can be treated as part of subject area of Artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
. The notion of abstract data types is related to the concept of data abstraction, important in object-oriented programming
Object-oriented programming language
This is a list of object-oriented programming programming languages.-Languages with object-oriented features:*ABAP*Ada 95*AmigaE*BETA*Blue*Boo*C++*C#*COBOL*Cobra*ColdFusion*Common Lisp*COOL*CorbaScript*Clarion*CLU*Curl*D*Dylan*E*Eiffel...
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
.
Defining an abstract data type (ADT)
An Abstract Data type is defined as a mathematical model of the data objects that make up a data type as well as the functions that operate on these objects
There are no standard conventions for defining them. A broad division may be drawn between "imperative" and "functional" definition styles.
In computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state...
languages, an abstract data structure is conceived as an entity that is mutable — meaning that it may be in different states at different times. Some operations may change the state of the ADT; therefore, the order in which operations are evaluated is important, and the same operation on the same entities may have different effects if executed at different times — just like the instructions of a computer, or the commands and procedures of an imperative language. To underscore this view, it is customary to say that the operations are executed or applied, rather than evaluated. The imperative style is often used when describing abstract algorithms. This is described by Donald E. Knuth and can be referenced from here The Art of Computer Programming
The Art of Computer Programming
The Art of Computer Programming is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis....
.
Abstract variable
Imperative ADT definitions often depend on the concept of an abstract variable, which may be regarded as the simplest non-trivial ADT. An abstract variable V is a mutable entity that admits two operations:
store(V,x) where x is a value of unspecified nature; and
fetch(V), that yields a value;
with the constraint that
fetch(V) always returns the value x used in the most recent store(V,x) operation on the same variable V.
As in so many programming languages, the operation store(V,x) is often written V ← x (or some similar notation), and fetch(V) is implied whenever a variable V is used in a context where a value is required. Thus, for example, V ← V + 1 is commonly understood to be a shorthand for store(V,fetch(V) + 1).
In this definition, it is implicitly assumed that storing a value into a variable U has no effect on the state of a distinct variable V. To make this assumption explicit, one could add the constraint that
if U and V are distinct variables, the sequence { store(U,x); store(V,y) } is equivalent to { store(V,y); store(U,x) }.
More generally, ADT definitions often assume that any operation that changes the state of one ADT instance has no effect on the state of any other instance (including other instances of the same ADT) — unless the ADT axioms imply that the two instances are connected (aliased
Aliasing (computing)
In computing, aliasing describes a situation in which a data location in memory can be accessed through different symbolic names in the program. Thus, modifying the data through one name implicitly modifies the values associated to all aliased names, which may not be expected by the programmer...
) in that sense. For example, when extending the definition of abstract variable to include abstract records
Record (computer science)
In computer science, a record is an instance of a product of primitive data types called a tuple. In C it is the compound data in a struct. Records are among the simplest data structures. A record is a value that contains other values, typically in fixed number and sequence and typically indexed...
, the operation that selects a field from a record variable R must yield a variable V that is aliased to that part of R.
The definition of an abstract variable V may also restrict the stored values x to members of a specific set X, called the range or type of V. As in programming languages, such restrictions may simplify the description and analysis of algorithms
Analysis of algorithms
To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
, and improve their readability.
Note that this definition does not imply anything about the result of evaluating fetch(V) when V is un-initialized, that is, before performing any store operation on V. An algorithm that does so is usually considered invalid, because its effect is not defined. (However, there are some important algorithms whose efficiency strongly depends on the assumption that such a fetch is legal, and returns some arbitrary value in the variable's range.)
Instance creation
Some algorithms need to create new instances of some ADT (such as new variables, or new stacks). To describe such algorithms, one usually includes in the ADT definition a create operation that yields an instance of the ADT, usually with axioms equivalent to
the result of create is distinct from any instance S in use by the algorithm.
This axiom may be strengthened to exclude also partial aliasing with other instances. On the other hand, this axiom still allows implementations of create to yield a previously created instance that has become inaccessible to the program.
Preconditions, postconditions, and invariants
In imperative-style definitions, the axioms are often expressed by preconditions, that specify when an operation may be executed; postconditions, that relate the states of the ADT before and after the execution of each operation; and invariants, that specify properties of the ADT that are not changed by the operations.
Example: abstract stack (imperative)
As another example, an imperative definition of an abstract stack could specify that the state of a stack S can be modified only by the operations
push(S,x), where x is some value of unspecified nature; and
pop(S), that yields a value as a result;
with the constraint that
For any value x and any abstract variable V, the sequence of operations { push(S,x); V ← pop(S) } is equivalent to { V ← x };
Since the assignment { V ← x }, by definition, cannot change the state of S, this condition implies that { V ← pop(S) } restores S to the state it had before the { push(S,x) }. From this condition and from the properties of abstract variables, it follows, for example, that the sequence
{ push(S,x); push(S,y); U ← pop(S); push(S,z); V ← pop(S); W ← pop(S); }
where x,y, and z are any values, and U, V, W are pairwise distinct variables, is equivalent to
{ U ← y; V ← z; W ← x }
Here it is implicitly assumed that operations on a stack instance do not modify the state of any other ADT instance, including other stacks; that is,
For any values x,y, and any distinct stacks S and T, the sequence { push(S,x); push(T,y) } is equivalent to { push(T,y); push(S,x) }.
A stack ADT definition usually includes also a Boolean-valued function empty(S) and a create operation that returns a stack instance, with axioms equivalent to
create ≠ S for any stack S (a newly created stack is distinct from all previous stacks)
empty(create) (a newly created stack is empty)
notempty(push(S,x)) (pushing something into a stack makes it non-empty)
Single-instance style
Sometimes an ADT is defined as if only one instance of it existed during the execution of the algorithm, and all operations were applied to that instance, which is not explicitly notated. For example, the abstract stack above could have been defined with operations push(x) and pop, that operate on "the" only existing stack. ADT definitions in this style can be easily rewritten to admit multiple coexisting instances of the ADT, by adding an explicit instance parameter (like S in the previous example) to every operation that uses or modifies the implicit instance.
On the other hand, some ADTs cannot be meaningfully defined without assuming multiple instances. This is the case when a single operation takes two distinct instances of the ADT as parameters. For an example, consider augmenting the definition of the stack ADT with an operation compare(S,T) that checks whether the stacks S and T contain the same items in the same order.
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
, is to consider each state of the structure as a separate entity. In this view, any operation that modifies the ADT is modeled as a mathematical function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
that takes the old state as an argument, and returns the new state as part of the result. Unlike the "imperative" operations, these functions have no side effect
Side effect (computer science)
In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world...
s. Therefore, the order in which they are evaluated is immaterial, and the same operation applied to the same arguments (including the same input states) will always return the same results (and output states).
In the functional view, in particular, there is no way (or need) to define an "abstract variable" with the semantics of imperative variables (namely, with fetch and store operations). Instead of storing values into variables, one passes them as arguments to functions.
Example: abstract stack (functional)
For example, a complete functional-style definition of a stack ADT could use the three operations:
push: takes a stack state and an arbitrary value, returns a stack state;
top: takes a stack state, returns a value;
pop: takes a stack state, returns a stack state;
with the following axioms:
top(push(s,x)) = x (pushing an item onto a stack leaves it at the top)
pop(push(s,x)) = s (pop undoes the effect of push)
In a functional-style definition there is no need for a create operation. Indeed, there is no notion of "stack instance". The stack states can be thought of as being potential states of a single stack structure, and two stack states that contain the same values in the same order are considered to be identical states. This view actually mirrors the behavior of some concrete implementations, such as linked list
Linked list
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
s with hash cons.
Instead of create, a functional definition of a stack ADT may assume the existence of a special stack state, the empty stack, designated by a special symbol like Λ or ""; or define a bottom operation that takes no aguments and returns this special stack state. Note that the axioms imply that
push(Λ,x) ≠ Λ
In a functional definition of a stack one does not need an empty predicate: instead, one can test whether a stack is empty by testing whether it is equal to Λ.
Note that these axioms do not define the effect of top(s) or pop(s), unless s is a stack state returned by a push. Since push leaves the stack non-empty, those two operations are undefined (hence invalid) when s = Λ. On the other hand, the axioms (and the lack of side effects) imply that push(s,x) = push(t,y) if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
x = y and s = t.
As in some other branches of mathematics, it is customary to assume also that the stack states are only those whose existence can be proved from the axioms in a finite number of steps. In the stack ADT example above, this rule means that every stack is a finite sequence of values, that becomes the empty stack (Λ) after a finite number of pops. By themselves, the axioms above do not exclude the existence of infinite stacks (that can be poped forever, each time yielding a different state) or circular stacks (that return to the same state after a finite number of pops). In particular, they do not exclude states s such that pop(s) = s or push(s,x) = s for some x. However, since one cannot obtain such stack states with the given operations, they are assumed "not to exist".
In computer science, abstraction is the process by which data and programs are defined with a representation similar to its pictorial meaning as rooted in the more complex realm of human life and language with their higher need of summarization and categorization , while hiding away the...
provides a promise that any implementation of the ADT has certain properties and abilities; knowing these is all that is required to make use of an ADT object. The user does not need any technical knowledge of how the implementation works to use the ADT. In this way, the implementation may be complex but will be encapsulated in a simple interface when it is actually used.
Localization of change
Code that uses an ADT object will not need to be edited if the implementation of the ADT is changed. Since any changes to the implementation must still comply with the interface, and since code using an ADT may only refer to properties and abilities specified in the interface, changes may be made to the implementation without requiring any changes in code where the ADT is used.
Flexibility
Different implementations of an ADT, having all the same properties and abilities, are equivalent and may be used somewhat interchangeably in code that uses the ADT. This gives a great deal of flexibility when using ADT objects in different situations. For example, different implementations of an ADT may be more efficient in different situations; it is possible to use each in the situation where they are preferable, thus increasing overall efficiency.
Typical operations
Some operations that are often specified for ADTs (possibly under other names) are
compare(s,t), that tests whether two structures are equivalent in some sense;
A hash function is any algorithm or subroutine that maps large data sets to smaller data sets, called keys. For example, a single integer can serve as an index to an array...
from the instance's state;
print(s) or show(s), that produces a human-readable representation of the structure's state.
In imperative-style ADT definitions, one often finds also
create, that yields a new instance of the ADT;
initialize(s), that prepares a newly-created instance s for further operations, or resets it to some "initial state";
copy(s,t), that puts instance s in a state equivalent to that of t;
clone(t), that performs s ← new, copy(s,t), and returns s;
free(s) or destroy(s), that reclaims the memory and other resources used by s;
The free operation is not normally relevant or meaningful, since ADTs are theoretical entities that do not "use memory". However, it may be necessary when one needs to analyze the storage used by an algorithm that uses the ADT. In that case one needs additional axioms that specify how much memory each ADT instance uses, as a function of its state, and how much of it is returned to the pool by free.
Examples
Some common ADTs, which have proved useful in a great variety of applications, are
Each of these ADTs may be defined in many ways and variants, not necessarily equivalent. For example, a stack ADT may or may not have a count operation that tells how many items have been pushed and not yet popped. This choice makes a difference not only for its clients but also for the implementation.
In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....
for each abstract operation. The ADT instances are represented by some concrete data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
that is manipulated by those procedures, according to the ADT's specifications.
Usually there are many ways to implement the same ADT, using several different concrete data structures. Thus, for example, an abstract stack can be implemented by a linked list
Linked list
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
or by an array.
An ADT implementation is often packaged as one or more modules, whose interface contains only the signature (number and types of the parameters and results) of the operations. The implementation of the module — namely, the bodies of the procedures and the concrete data structure used — can then be hidden from most clients of the module. This makes it possible to change the implementation without affecting the clients.
When implementing an ADT, each instance (in imperative-style definitions) or each state (in functional-style definitions) is usually represented by a handle
Handle (computing)
In computer programming, a handle is a particular kind of smart pointer. Handles are used when application software references blocks of memory or objects managed by another system, such as a database or an operating system....
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
and Java, support a form of abstract data types. When a class is used as a type, it is a abstract type that refers to a hidden representation. In this model an ADT is typically implemented as class
Class (computer science)
In object-oriented programming, a class is a construct that is used as a blueprint to create instances of itself – referred to as class instances, class objects, instance objects or simply objects. A class defines constituent members which enable these class instances to have state and behavior...
In computer science, an object is any entity that can be manipulated by the commands of a programming language, such as a value, variable, function, or data structure...
of that class. The module's interface typically declares the constructors as ordinary procedures, and most of the other ADT operations as methods
Method (computer science)
In object-oriented programming, a method is a subroutine associated with a class. Methods define the behavior to be exhibited by instances of the associated class at program run time...
of that class. However, such an approach does not easily encapsulate multiple representational variants found in an ADT. It also can undermine the extensibility of object-oriented programs.
In a pure object-oriented program that uses interfaces as types, types refer to behaviors not representations.
Example: implementation of the stack ADT
As an example, here is an implementation of the stack ADT above in the C programming language.
Imperative-style interface
An imperative-style interface might be:
typedef struct stack_Rep stack_Rep; /* Type: instance representation (an opaque record). */
typedef stack_Rep *stack_T; /* Type: handle to a stack instance (an opaque pointer). */
typedef void *stack_Item; /* Type: value that can be stored in stack (arbitrary address). */
stack_T stack_create(void); /* Create new stack instance, initially empty. */
void stack_push(stack_T s, stack_Item e); /* Add an item at the top of the stack. */
stack_Item stack_pop(stack_T s); /* Remove the top item from the stack and return it . */
int stack_empty(stack_T ts); /* Check whether stack is empty. */
This implementation could be used in the following manner:
include /* Include the stack interface. */
stack_T t = stack_create; /* Create a stack instance. */
int foo = 17; /* An arbitrary datum. */
t = stack_push(t, &foo); /* Push the address of 'foo' onto the stack. */
…
void *e = stack_pop(t); /* Get the top item and delete it from the stack. */
if (stack_empty(t)) { … } /* Do something if stack is empty. */
…
This interface can be implemented in many ways. The implementation may be arbitrarily inefficient, since the formal definition of the ADT, above, does not specify how much space the stack may use, nor how long each operation should take. It also does not specify whether the stack state t continues to exist after a call s ← pop(t).
In practice the formal definition should specify that the space is proportional to the number of items pushed and not yet popped; and that every one of the operations above must finish in a constant amount of time, independently of that number. To comply with these additional specifications, the implementation could use a linked list, or an array (with dynamic resizing) together with two integers (an item count and the array size)
Functional-style interface
Functional-style ADT definitions are more appropriate for functional programming languages, and vice-versa. However, one can provide a functional style interface even in an imperative language like C. For example:
typedef struct stack_Rep stack_Rep; /* Type: stack state representation (an opaque record). */
typedef stack_Rep *stack_T; /* Type: handle to a stack state (an opaque pointer). */
typedef void *stack_Item; /* Type: item (arbitrary address). */
stack_T stack_empty(void); /* Returns the empty stack state. */
stack_T stack_push(stack_T s, stack_Item x); /* Adds x at the top of s, returns the resulting state. */
stack_Item stack_top(stack_T s); /* Returns the item currently at the top of s. */
stack_T stack_pop(stack_T s); /* Remove the top item from s, returns the resulting state. */
The main problem is that C lacks garbage collection, and this makes this style of programming impractical; moreover, memory allocation routines in C are slower than allocation in a typical garbage collector, thus the performance impact of so many allocations is even greater.
ADT libraries
Many modern programming languages,such as C++ and Java, come with standard libraries that implement several common ADTs, such as those listed above.
Built-in abstract data types
The specification of some programming languages is intentionally vague about the representation of certain built-in data types, defining only the operations that can be done on them. Therefore, those types can be viewed as "built-in ADTs". Examples are the arrays in many scripting languages, such as Awk, Lua, and Perl
Perl
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
, which can be regarded as an implementation of the Map or Table ADT.
In mathematics, an initial algebra is an initial object in the category of F-algebras for a given endofunctor F. The initiality provides a general framework for induction and recursion....
In generic programming, a concept is a description of supported operations on a type, including syntax and semantics. In this way, concepts are related to abstract base classes but concepts do not require a subtype relationship.-Languages using:...
In computer science and software engineering, formal methods are a particular kind of mathematically-based techniques for the specification, development and verification of software and hardware systems...
A functional specification in systems engineering and software development is the documentation that describes the requested behavior of an engineering system...
Substitutability is a principle in object-oriented programming. It states that, in a computer program, if S is a subtype of T, then objects of type T may be replaced with objects of type S without altering any of the desirable properties of that program...
Object-oriented programming is a programming paradigm using "objects" – data structures consisting of data fields and methods together with their interactions – to design applications and computer programs. Programming techniques may include features such as data abstraction,...
A type system associates a type with each computed value. By examining the flow of these values, a type system attempts to ensure or prove that no type errors can occur...
In mathematics, logic and computer science, type theory is any of several formal systems that can serve as alternatives to naive set theory, or the study of such formalisms in general...
In computer programming, particularly functional programming and type theory, an algebraic data type is a datatype each of whose values is data from other datatypes wrapped in one of the constructors of the datatype. Any wrapped datum is an argument to the constructor...
In functional programming, a generalized algebraic data type is a generalization of the algebraic data types of Haskell and ML, applying to parametric types.With this extension, the parameters of the return type of a data constructor can be freely chosen when declaring...
