@online{a-model-for-adtsMcPherson2017,
    author={Jack McPherson},
    date={2017-01-14},
    title={A Model For ADTs},
    url={https://jmcph4.github.io/2017/01/14/a-model-for-adts.html},
    urldate={2020-05-16},
}

A Model For ADTs

For the past month or so I have concerned myself with the study of Abstract Data Types (ADTs), particularly the precise, abstract mathematical definition of them. This post reflects the current culmination of my efforts.

Introduction

Abstract Data Types (ADTs) are mathematical objects somewhat congruent to algebraic structures in pure mathematics. We have a set of operations we can perform on a given ADT and a set of values it may take.

For the purposes of my analysis, an axiom I have adopted is that no ADT can be perfectly implemented in any computer programming language. This is due to the inherent nature of real computers: i.e., they are error-prone. ADTs, like any mathematical objects, do not suffer from "errors" (imagine taking the logarithm of a negative number and the universe raising an exception).

Despite this seemingly pessimistic outlook, we can implement ADTs effectively and quite closely to their mathematical definitions. Firstly, we require some way to understand and reason about ADTs in general. We require a specification.

Specification of ADTs

Above, I claimed that the formal mathematical definition of an ADT is a set of operations and a set of possible values, this is not as pragmatic as I would like. It is at this point that I started to devise a strategy for specifying ADTs in a more useful sense. We define the following characteristics of any general ADT:

• Operations

• Unary

• Binary

• Access

• Size

• Equality^✝

• Membership

These are charactertistics of all ADTs, not merely specific ones. Examples of such specifications are available as a Gist.

Hierarchy of ADTs

It is well known that some ADTs are special cases of other, more general, ADTs. For instance, a binary tree is an ADT that is a special case of the (more general) tree ADT (also referred to as a \(k\)-ary tree with \(k=2\)). This becomes quite evident when specifying ADTs, as one finds themselves repeating themselves more and more. This is the motivation behind my ADT graph (not the ADT called a graph, but a graph of ADTs).

Let us define a directed graph, \(G\), whose vertices are ADTs. An edge in \(G\) from a vertex \(u\) to a vertex \(v\) denotes that the ADT represented by \(v\) is a special case of the ADT represented by \(u\).

In some sense, the "most important" ADTs in \(G\) are those \(v\in G\) such that \(deg^{+}(v)=0\), as these are the ADTs which are the most general and thus all other ADTs can be derived. We will call the set of all such ADTs the set of base ADTs. In the current model, this set is: $$\{List, Hypergraph, Stack, Queue, Multimap, Multiset\}$$

Conclusion

The description of the model I have given here is by no means complete. For example, the ADT graph does not have every ADT in existence in it (nor can it, in practice). Despite this incompleteness, I hope that I have provided sufficient description to enable the model to be well-understood and useful. Of course, I am open to change and growth of the model.

^✝By "equality", I mean mathematical equality. In a concrete implementation, this is actually closer to isomorphism, as in computer programming, two things are "equal" when they are in fact the same thing.