Abstract Data Types (ADT): Defining ‘What’ not ‘How’

Abstract Data Types (ADT) are high-level abstractions characterized by a set of objects and related operations. ADTs do not define implementation guidance and therefore afford programmers much freedom while still adhering to general design requirements.

ADTs are fundamental underpinnings of Computer Science and direct the development of many modern programming language features. This article will introduce the ADT as a concept, illustrate how ADTs manipulate encapsulated data, and direct development via focusing on high-level outcomes rather than the nitty-gritty details of implementation.

Highlights

• Defining an ADT by considering their characteristics
• Understanding the algebraic form through which an ADT is defined
• Common ADTs such as Queue, List, Stack, and Tree
• Implementing ADTs as Data Structures
• Custom implementation of a Queue in Python
• Comparing ADTs to Objects

Introduction

ADTs are among the most foundational concepts of computer science and have a wide range of applications. They describe the what of a program’s functionality and leave the how of it all up to developers. In seeking the definition of an abstract data type we can consider each part of the term as follows:

• Abstract: Conceptual rather than concrete
• Data: Information formatted for use by a computer
• Type: A category of objects with shared characteristics

The terms Data and Type are immediately recognized as related as their use as Data Type is common among all programming languages. This term is used to describe integers, booleans, floating-point values, and similar built-in features of most modern programming languages. Given this; let us borrow the following definition of abstract data type (Dale, 1996):

A class of objects whose logical behavior is defined by a set of values and a set of operations.

Abstract data types are almost poetically simplistic but can be difficult to grasp without some contrast to other concepts. In this article, we’ll consider the common characteristics of ADTs, how they are defined, implemented, and some examples of a custom implementation. Through this process, the underlying concepts of ADTs should become clearer.

Characteristics of ADTs

ADTs are contrasted by Data Types (DT) such as Integers, Booleans, and Chars. These structures are characterized by their representation of values without operations. A key feature in defining ADTs is their abstraction of operational details from users and developers.

• Encapsulates a Data Type and set of operations to manipulate the Type
• Operations are only defined by inputs and outputs
• Operation details are hidden from the user through encapsulation
• Theoretical in nature
• Define what is getting done not how it is getting done
• Allows internal implementation details to change without

An ADT may provide a complex implementation of a basic function of which a developer would be allowed access to the function without necessitating an awareness of its underlying logic.

ADT Operation Types

Abstract Data Types define necessary operations for implementation. These operations fall into three primary categories—and several less common ones. These categories may be referred to by several names depending on context, language, or the mood of a developer on a particular day. Such categories include the following (Nell, 2010):

• Constructors – Initializes an instance of an ADT
• Transformers – Changes the state of an ADT (a.k.a. mutator)
• Observers – Allows read-only access to ADT values without changing ADT State. a.k.a. accessors.
• Destructor – Clears the State of an ADT before freeing of memory space
• Iterator – Allows the processing of ADT components in a one-by-one fashion.

These are by no means an exhaustive list of possible operation types for ADTs. These are, however, quite common. It is also worth noting that ADT operators can fall into multiple categories. For example, an operator that merges two existing lists would be both a constructor and an observer (Thalmann, 1979.)

ADT Creation

With all this talk of ADTs, one might begin to wonder how to create one. Perhaps the best way to discern between ADTs, Data Structures, Objects, and varying implementations is to consider the syntax by which they are created.

The abstraction of ADTs is clearest when examining the syntax—often expressed in algebraic form. Consider the following logical definition of a Queue ADT using algebraic syntax that describes the Signature and the Axioms (Dale, 1996):

Queue<Item>

Signature:
    isEmpty : Queue -> bool
    frontOf : Queue -> Item
    empty   :       -> Queue
    add     : Queue -> Queue
    pop     : Queue x  Elem -> Queue

Axioms:
    isEmpty(empty) = true
    isEmpty(enq(q, x)) = false
    frontOf(enq(q, x)) =
        if isEmpty(q) the x
        else frontOf(q);
    pop(add(q, x)) = 
        if isEmpty(q) empty
        else add(pop(q), x);

The conceptual nature of ADTs is clear here—no common programming language can do anything with this other than throw a syntax error. Between the name, signature, and axioms, however—a developer can implement a language-specific Data Structure in accord with the Queue ADT expressed above.

ADT Examples

Abstract Data Types can be difficult to grasp initially because—well, they’re so abstract. They come in many forms intended for many purposes and some ADT implementation may differ ever-so-slightly that one can hardly discern them as separate Data Structure types.

To make the collective ADT waters even muddier—there are sub-categories of ADTs such as AGDTs where specific application contrasts them from broader concepts (Thalmann, 1979.) Some common ADTs that are implanted in the standard libraries of many modern programming languages include the following:

• List
• Stack
• Queue
• DeQue
• Set
• Graph

These are by no means an exhaustive list and ADT types and implementations can easily number into the dozens, if not hundreds—being separated only by slight nuances. To get a better feel for how an ADT becomes a Data Structure through implementation, let’s consider how we might go about implementing the Queue ADT outlined above in conceptual algebraic form.

ADT Implementations

An ADT is a concept that does not reveal the inner workings or make demands about how these workings are implemented. For example, a Queue is an ADT in concept only though the Java Queue is considered a Data Structure—a.k.a. an implementation of an ADT.

Early computer languages only provided built-in data types. The constructs, such as an int, char, and double allowed developers to create routines that generated desired output by utilizing these features. In many cases, these routines involved an excess of syntax and complex logical flow.

ADTs brought developers the ability to define their own data structures based on what was deemed convenient to their use case. This helped reduce syntax, increase extensibility, and provide a framework for the development of modern software engineering practices such as SOLID.

Custom Queue ADT Implementation

Queue objects can also provide removal access for the last object similar to Stacks. Through such usage, a Queue is considered a First-In-First-Out (FIFO) design. Other variations of the Queue include such ADTs as the Double-Ended Queue (DeQue) where items can be removed from the beginning or end of the contained collection. Let’s take a look at how the Queue ADT from above would be implemented in Python.

from typing import Any, NoReturn


class Queue:

    def __init__(self):
        self._items = []

    def add(self, item: Any) -> NoReturn:
        """Adds an item to the back of the queue"""
        self._items.append(item)

    def pop(self) -> Any:
        """Removes the first item of the queue"""
        return self._items.pop(0)

    def isEmpty(self) -> bool:
        """Checks if any items are in the queue"""
        return len(self._items) == 0

    def __str__(self):
        return str(self._items)


if __name__ == '__main__':

    # Create a new Queue object
    q = Queue()

    # Have some items
    people = ['bob', 'alice', 'pat']

    # View starting queue
    print("Initial Queue:", q)

    # Add everyone to the queue
    for person in people:

        print("\tAdding:", person)
        q.add(person)

    # View full queue
    print("Filled Queue:", q)

    # Remove People, one-by-one
    while not q.isEmpty():

        next_person = q.pop()

        print("\tNext Person:", next_person)

    # Print resulting queue
    print("Final Queue:", q)


# Results
Initial Queue: []
    Adding: bob
    Adding: alice
    Adding: pat
Filled Queue: ['bob', 'alice', 'pat']
    Next Person: bob
    Next Person: alice
    Next Person: pat
Final Queue: []

Note: This code is available for download via GitHub

Here we add each person to our list, view the list, then proceed to remove each person again—this is where the Queue is notably different from a Stack. The first person added to our Queue object (Bob) is now the first person removed. This illustrates the First-In-First-Out characteristic of our Queue as opposed to a Last-in-First-Out characteristic of Stacks.

The Python standard library includes a Queue module that provides a robust, thread-safe (appropriate for multithreading) Queue class. This ADT implementation is much more robust than the basic example shown here. Check out the documentation for a better idea of how a Queue is used out in the wild.

Note: We are only implementing the isEmpty(), pop(), and add() aspects here for brevity. The __init__ and __str__ are Python-specific details outside of the scope of our ADT.

ADTs vs. Objects

ADTs are not objects—this is an important point to understand. Both concepts are data abstractions but there are notable differences. The separation of these terms is often argued as being purely semantic reflected by the synonymous use of each in many textbooks.

Generally; ADTs are suited for defining Types where conceptually simple but computationally complex calculations are required and objects are used for more complex concepts are needed with less efficient computation (Cook, 2009.)

In Java, interfaces are generally used to construct ADTs while classes are used to construct Objects. This is not strictly enforced but the abstraction common to interfaces dually represents the conceptual intent of ADTs. The interchangeability of these terms in many textbooks reflects—if nothing else—the nuance by which their separation is defined.

Final Thoughts

Abstract Data Types (ADTs) are high-level concepts that encapsulate a Type or Class and dictate a set of operations or procedures through which data can be manipulated. The ability to define the what of implementation and not the how allows designers to focus on the big picture rather than be distracted by lower-level details.

ADTs can be a bit heady in definition but in practice, they are almost beautiful in the simplicity through which they direct such immense expression. The Queue, Stack, List, and Tree are found throughout the world of Computer Science and Software Engineering as countless different implementations—yet all find form from the same ADTs.

References

1. Dale, Nell, and Chip Weems. Programming and Problem Solving with C++: Brief Edition. 6th ed., Jones & Bartlett Learning, 2010.
2. Thalmann, D Magnenat-Thalmann, N. Design and implementation of abstract graphical data types,” COMPSAC 79. Proceedings. Computer Software and The IEEE Computer Society’s Third International Applications Conference, 1979., 1979, pp. 519-524, doi: 10.1109/CMPSAC.1979.762551.
3. Cook, William R. “On Understanding Data Abstraction, Revisited.” Proceeding of the 24th ACM SIGPLAN Conference on Object-Oriented Programming Systems Languages and Applications – OOPSLA 09, 2009. doi:10.1145/1640089.1640133.
4. Dale, Nell, and Henry Walker. Abstract Data Types: Specifications, Implementations, and Applications. D.C. Heath & Company, 1996.