Abstract Data Types: The Other ADTs

Abstract Data Types are a crucial construct in everyday programming. They effectively constitute all types which values might have. For the sake of brevity, I will refer to Abstract Data Types in this article as ADTs, though not to be confused with Algebraic Data Types, covered in another article).

Note: While the concepts in this article apply to all programming languages, the specific examples are drawn from the C programming language.

ADTs can simply be described as “all the things that describe a type”. For instance,

int’s ADT specifies which values are valid for an int (whole numbers in the range of INT_MIN to INT_MAX) and the operations that are defined for an int (for example, incrementing, decrementing, adding with another int, etc). Important to note is that some things about ints are not part of int’s ADT. For instance, the fact that ints are usually represented as bit strings has nothing to do with the int ADT. Neither has the fact that ints can be used as pointers (since that is a language bug/feature rather than a property of the type).

In general, the set of values which are valid for an ADT are called the domain, and the “things you can do” with an ADT are called the ADT’s operations, or sometimes, API (Application Programming Interface). The ADT does not include how values are stored, nor the specific steps by which operations do their jobs. This is why they are referred to as abstract: the concerns of how these details work is hidden (or abstracted) from the developer.

In C, there are four primitive (sometimes called atomic) data types: char, int, float, and double. All other data types are built from these. As an example, a bool is implemented as an int (where 1 has the value true and 0 has the value false). However, because bool has an ADT, a developer needn’t ever know this. In order to use a bool, you only need to know that the domain is {true, false} and the API is composed of 5 operations: ! (negate), && (logical AND), || (logical OR), == (logical equality), and != (logical inequality / XOR). Note that = (assignment) is not included in the list of operations: This is because assignment does not actually operate on bools, only on variables of type bool. Consider true = false: This statement does not compile because true, while a valid bool value, is not an assignable variable. Therefore, = is not part of bool’s API.

According to a very good article by MIT, operations on an ADT can be classified as either Creators, Produces, Observers, or Mutators.

• Creators instantiate the ADT, such as the literals 0 (for int) or 'c' (for char).
• Producers generate new ADT instances from existing ones (eg, int’s +, which takes two ints and produces a third).
• Observers take instances of the ADT and return a different type (eg, double’s floor observes a double but returns an int).
• Mutators change ADT instances without altering their identity. Atomic ADTs do not have mutators, but data structures (covered in the next article) do. For example, an array’s dereference-and-assign operation (eg, arr[3] = 5) changes an element of the array without replacing the array itself, so we say it mutates the array.

Some languages have type qualifiers which modify a type’s ADT, such as unsigned. An unsigned int has a domain of 0 to UINT_MAX, as opposed to an int’s domain of INT_MIN to INT_MAX. The same API applies, but the implementation of the operations might be different, as might the domain.