9 - Abstract data types

Summary

Most programming languages allow programmer defined data structures (e.g. array … of …) and when there is a rich choice available (array, record, set, pointer, etc.) there is no doubt that very neat, expressive data models can be built. However there is one major drawback. That is that the syntax used for accessing each type of structure is distinctive and fixed. This has two effects. Firstly, if for example, a list structure is altered from an array implementation to a record-with-pointer implementation then every reference to the list in the program must be changed. The distinctive array reference syntax (a[i]) has to be changed to record/pointer reference syntax (p↑. field). Secondly the program becomes more machine-oriented and less problem-oriented because of the intrusion of programming details.

The way of avoiding the problems mentioned above is to think of a data structure not just as a storage area but as a collection of distinctive operations on certain data. This almost establishes the informal definition of an abstract data type (ADT)

ADT = Data Structure + Distinctive Operations

We have been using one abstract data type (the list) without naming it as such. Its distinctive operations are head and tail, ‘concatenate’ (∥) and ‘creation from elements’ (〈e₁, e₂, …, e_n〉). We have also introduced realisations or implementations of the abstract data type list in various languages – see Chapter 6. In fact in Section 6.3, Templates for FORTRAN, the implementation of LIST as a module shows the clear intention to treat the data space and the operations as an indivisible unit.