Abstract data type

In the theory of imperative programming 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. This is analogous to 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, similar to the imperative style often used when describing abstract algorithms. (See The Art of Computer Programming by Donald Knuth for more details).

Imperative-style definitions of ADT 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;
• 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.

Fetching before storing can be disallowed, defined to have a certain result, or (less desirably), leave the behavior unspecified.

As in 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 names are always distinct: 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 of the same ADT, unless the ADT axioms define certain instances as connected (see aliased) in a specific way. The most common such connections include:

• Aliasing, in which two or more names refer to the exact same data object.
• Composition, in which an ADT is defined to contain instances of (the same or other) ADTs.
• Reference, in which an ADT is defined to refer to instance of (the same or other) ADTs.

For example, when extending the definition of an abstract variable to include abstract records, operations upon a field F of a record variable R, clearly involve F, which is distinct from, but also a part of, R.

The definition of an ADT may restrict the stored value(s) for its instances, to members of a specific set X called the range of those variables. For example, an ADT for an aggregate such as a Stack or Queue, may constrain all items in the queue to be integers, or at least to all be of a single type (see homogeneity). As in programming languages, such restrictions may simplify the description and analysis of algorithms, and improve its 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 may be considered invalid, either (a) because the ADT prohibits such an operation, or (b) simply because its effect is not defined by the ADT. 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.)

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 already in use by the algorithm.

This axiom may be strengthened to exclude also partial aliasing with other instances. For practical use, such as axiom may still allow implementations of create() to yield a previously created instance that has become inaccessible to the program; however, defining that such an instance even is "the same" is difficult, especially in the abstract (though even a re-used block of memory is only "the same object" in certain senses).

As another example, an imperative-style 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;
• 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) }.

An abstract stack 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 prior stack S (a newly created stack is distinct from all previous stacks);
• empty(create()) (a newly created stack is empty);
• not empty(push(S, x)) (pushing something into a stack makes it non-empty).

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 abstract stack with an operation compare(S, T) that checks whether the stacks S and T contain the same items in the same order.

Another way to define an ADT, closer to the spirit of functional programming, is to consider each state of the structure as a separate entity. In this view, any operation that modifies the ADT is modelled as a mathematical function 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 effects. 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.

For example, a complete functional-style definition of an abstract stack 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.

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 lists with hash cons.

Instead of create(), a functional-style definition of an abstract stack 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 arguments and returns this special stack state. Note that the axioms imply that

• push(Λ, x) ≠ Λ.

In a functional-style 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 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 abstract stack 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 popped 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".

Aside from the behavior in terms of axioms, it is also possible to include, in the definition of an ADT operation, their algorithmic complexity. Alexander Stepanov, designer of the C++ Standard Template Library, included complexity guarantees in the STL specification, arguing:

The reason for introducing the notion of abstract data types was to allow interchangeable software modules. You cannot have interchangeable modules unless these modules share similar complexity behavior. If I replace one module with another module with the same functional behavior but with different complexity tradeoffs, the user of this code will be unpleasantly surprised. I could tell him anything I like about data abstraction, and he still would not want to use the code. Complexity assertions have to be part of the interface.

— Alexander Stepanov[5]

Abstraction 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.

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 object 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.

Different implementations of the 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 the 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.

As an example, here is an implementation of the abstract stack above in the C programming language.

An imperative-style interface might be:

typedef struct stack_Rep stack_Rep;       // type: stack instance representation (opaque record)
typedef stack_Rep* stack_T;               // type: handle to a stack instance (opaque pointer)
typedef void* stack_Item;                 // type: value stored in stack instance (arbitrary address)

stack_T stack_create(void);               // creates a new empty stack instance
void stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack
stack_Item stack_pop(stack_T s);          // removes the top item from the stack and returns it
bool stack_empty(stack_T s);              // checks whether stack is empty

This interface could be used in the following manner:

#include <stack.h>          // includes the stack interface

stack_T s = stack_create(); // creates a new empty stack instance
int x = 17;
stack_push(s, &x);          // adds the address of x at the top of the stack
void* y = stack_pop(s);     // removes the address of x from the stack and returns it
if (stack_empty(s)) { }     // does 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 s continues to exist after a call x ← pop(s).

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 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 (opaque record)
typedef stack_Rep* stack_T;                  // type: handle to a stack state (opaque pointer)
typedef void* stack_Item;                    // type: value of a stack state (arbitrary address)

stack_T stack_empty(void);                   // returns the empty stack state
stack_T stack_push(stack_T s, stack_Item x); // adds an item at the top of the stack state and returns the resulting stack state
stack_T stack_pop(stack_T s);                // removes the top item from the stack state and returns the resulting stack state
stack_Item stack_top(stack_T s);             // returns the top item of the stack state

Many modern programming languages, such as C++ and Java, come with standard libraries that implement several common ADTs, such as those listed above.

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, which can be regarded as an implementation of the abstract list.