Abstract data type

An Abstract Data Type ( ADT ) is a group of data together with the definition of all permitted operations that access them.

description

Since access is only possible via the specified operations, the data is encapsulated from the outside .

An ADT describes what the operations do (semantics), but not yet how they should do it (implementation). The concept of the ADT can also be specified differently and an ADT can be noted in different ways, for example using pseudocode or a mathematical description. However, more modern programming languages ​​specifically support the creation of ADTs.

Object-oriented programming languages support the creation of ADTs through their class concept, since data and operations are linked here, the data can be protected and the permitted operations can be specified. Some modular programming languages such as Ada or Modula-2 also specifically support the creation of ADTs. Usually it is possible to define an ADT by defining the data and the signatures of the operations, while the semantics are described as comment text.

example

Java supports ADTs through classes, abstract classes and interfaces . Only data and signatures of the operations are defined in an interface, a defined class implements the interface first. In general, a class defines the data and the operations permitted on it.

Specifications

An abstract data type can be indicated by different specifications. A specification consists of a signature and semantics that define the meaning and interaction of the operations.

From a mathematical point of view, it is the specification of a term algebra through signature , generator and axioms. This results in the first type of specification, the mathematical-axiomatic.

Another possibility is the mathematical-algebraic specification, which differs from the axiomatic specification only in the specification of the semantics. The meaning of the content of the operations is defined by mathematical means, matrices, vectors, sequences, etc.

In addition, there are special forms, such as the informal method of specification - by specifying an interface of a programming language, for example as a Java interface or the implementation of the data type in a functional programming language such as Haskell  - which is initially contradicting the attempt to make the data type independent of a To make implementation. The implementation in a functional programming language, however, serves as a specification for ADTs, which are ultimately implemented in procedural or object-oriented languages. The advantage of this specification is that it can be tested immediately whether the specification makes sense, which is not easily possible with the other options, especially the axiomatic ones.

example

In the following, the ADTs stack storage ( stack , works according to the last-in-first-out principle) and queue ( queue , works according to the first-in-first-out principle) are defined in the four specifications mentioned.

signature

Mathematical-axiomatic and -algebraic method

STACK (wird hier definiert)
ELEMENT (ein hier nicht definierter ADT, mit dem der Stack arbeitet)
BOOL

emptyStack: → STACK (erzeugt einen leeren Stack)
isStackEmpty: STACK → BOOL (fragt nach, ob der Stack leer ist)
push: ELEMENT × STACK → STACK (packt ein Element oben auf den Stack)
pop: STACK → STACK (entfernt das oberste Element und gibt den neuen Stack zurück)
top: STACK → ELEMENT (gibt das oberste Element zurück, ohne es zu entfernen)

QUEUE
ELEMENT
BOOL

emptyQueue: → QUEUE
isQueueEmpty: QUEUE → BOOL
enqueue: ELEMENT × QUEUE → QUEUE (fügt ein Element hinten an)
dequeue: QUEUE → QUEUE (entfernt das vorderste Element)
head: QUEUE → ELEMENT (gibt das vorderste Element zurück, ohne es zu entfernen)

Informal method (Java)

public interface IStack<E> {

    public boolean isStackEmpty();
    public IStack<E> push(E elem);
    public IStack<E> pop();
    public E top();
}

public interface IQueue<E> {

    public boolean isQueueEmpty();
    public IQueue<E> enqueue(E elem);
    public IQueue<E> dequeue();
    public E head();
}

Specification by a functional programming language (Haskell)

data Stack e = E | S e (Stack e)
isStackEmpty :: Stack a → Bool
push :: e → Stack e → Stack e
pop :: Stack e → Stack e
top :: Stack e → e

data Queue e = E | Q (Queue e) e
isQueueEmpty :: Queue e → Bool
enqueue :: e → Queue e → Queue e
dequeue :: Queue e → Queue e
head :: Queue e → e

semantics

Even with a closer look at the (identical) signatures, no differences between the data types can be seen. Only when the semantics are defined do differences arise.

Mathematical-axiomatic method

 x: ELEMENT
 s: STACK
 isStackEmpty(emptyStack()) = TRUE
 isStackEmpty(push(x,s)) = FALSE
 pop(emptyStack()) = ERROR
 pop(push(x,s)) = s
 top(emptyStack()) = ERROR
 top(push(x,s)) = x
 push(top(s),pop(s)) = s, falls s nicht leer

 x: ELEMENT
 q: QUEUE
 isQueueEmpty(emptyQueue()) = TRUE
 isQueueEmpty(enqueue(x,q)) = FALSE
 head(emptyQueue()) = ERROR
 head(enqueue(x,q)) = IF isQueueEmpty(q) THEN x ELSE head(q)
 dequeue(emptyQueue()) = ERROR
 dequeue(enqueue(x,q)) = IF isQueueEmpty(q) THEN q ELSE enqueue(x, dequeue(q))

Mathematical-algebraic method

SETS ELEMENT = E (Menge der Elemente)  ${\displaystyle x\in E}$
     STACK = S =  ${\displaystyle \lbrace \langle \rangle \rbrace \cup \lbrace \langle x_{1}{,}...{,}x_{n}\rangle |x_{i}\in E\land \ n\in \mathbb {N} \land n\geq 1\rbrace }$
FUNCTIONS
    emptyStack      =  ${\displaystyle \langle \rangle }$
    isStackEmpty(S) =  ${\displaystyle (S==\langle \rangle )}$
    push(S,x)       =  ${\displaystyle \langle x\rangle }$, falls  ${\displaystyle (S==\langle \rangle )}$
                    =  ${\displaystyle \langle x_{1}{,}...{,}x_{n}{,}x\rangle }$, falls  ${\displaystyle (S==\langle x_{1}{,}...{,}x_{n}\rangle )}$
    top(S)          =  ${\displaystyle \perp }$, falls  ${\displaystyle (S==\langle \rangle )}$
                    =  ${\displaystyle x_{n}\,}$, falls  ${\displaystyle (S==\langle x_{1}{,}...{,}x_{n}\rangle ,n\geq 1)}$
    pop(S)          =  ${\displaystyle \perp }$, falls  ${\displaystyle (S==\langle \rangle )}$
                    =  ${\displaystyle \langle \rangle }$, falls  ${\displaystyle (S==\langle x\rangle )}$
                    =  ${\displaystyle \langle x_{1}{,}...{,}x_{n-1}\rangle }$, falls  ${\displaystyle (S==\langle x_{1}{,}...{,}x_{n}\rangle ,n\geq 2)}$

SETS ELEMENT = E (Menge der Elemente)  ${\displaystyle x\in E}$
     QUEUE = Q =  ${\displaystyle \lbrace \langle \rangle \rbrace \cup \lbrace \langle x_{1}{,}...{,}x_{n}\rangle |x_{i}\in E\land \ n\in \mathbb {N} \land n\geq 1\rbrace }$
FUNCTIONS
    emptyQueue      =  ${\displaystyle \langle \rangle }$
    isQueueEmpty(Q) =  ${\displaystyle (Q==\langle \rangle )}$
    enqueue(Q,x)    =  ${\displaystyle \langle x\rangle }$, falls  ${\displaystyle (Q==\langle \rangle )}$
                    =  ${\displaystyle \langle x{,}x_{1}{,}...{,}x_{n}\rangle }$, falls  ${\displaystyle (Q==\langle x_{1}{,}...{,}x_{n}\rangle )}$
    head(Q)         =  ${\displaystyle \perp }$, falls  ${\displaystyle (Q==\langle \rangle )}$
                    =  ${\displaystyle x_{n}\,}$, falls  ${\displaystyle (Q==\langle x_{1}{,}...{,}x_{n}\rangle ,n\geq 1)}$
    dequeue(Q)      =  ${\displaystyle \perp }$, falls  ${\displaystyle (Q==\langle \rangle )}$
                    =  ${\displaystyle \langle \rangle }$, falls  ${\displaystyle (Q==\langle x\rangle )}$
                    =  ${\displaystyle \langle x_{1}{,}...{,}x_{n-1}\rangle }$, falls  ${\displaystyle (Q==\langle x_{1}{,}...{,}x_{n}\rangle ,n\geq 2)}$

Informal method (Java)

Semantics: by specifying the prerequisite and effect / result of the method (with object-oriented programming there is usually no need to state the existence of the data structure as a prerequisite, since the method is linked to an object that already exists).

public interface IStack<E> {
    // Konstruktor in der konkreten Klasse

    // Ergebnis: true, wenn der Stack leer ist, false andernfalls
    public boolean isStackEmpty();

    // Effekt: Der Stack enthält das Element elem als oberstes Element.
    // Ergebnis: Der Stack nach dem Einfügen des Elements elem.
    public IStack<E> push(E elem);

    // Voraussetzung: Der Stack ist nicht leer.
    // Effekt: Das oberste Element wird vom Stack gelöscht.
    // Ergebnis: Der Stack nach dem Löschen.
    public IStack<E> pop();

    // Voraussetzung: Der Stack ist nicht leer.
    // Ergebnis: Das oberste Element.
    public E top();
}
public interface IQueue<E> {
    public boolean isQueueEmpty();
    public IQueue<E> enqueue(E elem);
    public IQueue<E> dequeue();
    public E head();
}

Specification by a functional programming language (Haskell)

emptyStack = E
isStackEmpty E = True
isStackEmpty (S x xs) = False
push e xs = S e xs
pop (S x xs) = xs
top (S x xs) = x

emptyQueue = E
isQueueEmpty E = True
isQueueEmpty (Q xs x) = False
enqueue e xs = Q xs e
dequeue E = E
dequeue (Q (E) x) = E
dequeue (Q (Q ys y) x) = enqueue x (dequeue (Q ys y))
head E = error "Queue ist leer."
head (Q (E) x) = x
head (Q (Q ys y) x) = head (Q ys y)

Desired properties

The desired properties of a well-programmed ADT and usually a well-specified data structure are:

• Universality (implementation independence): Once the ADT has been designed and implemented, it can be included and used in any program (e.g. in the form of a unit ).
• Precise specification: The interface between implementation and application must be clear and complete.
• Simplicity : In the application, the inner realization of the ADT is of no interest, the ADT takes over its representation and administration in the memory itself.
• Encapsulation : The interface should be seen as a hermetic boundary. The user should know exactly what an ADT is doing, but not how he is doing it.
• Protection (integrity): The user cannot intervene in the internal structure of the data. This significantly reduces the risk of unintentionally deleting or changing data and of making programming errors.
• Modularity : The modular principle allows clear and therefore safe programming and easy exchange of program parts. Individual modules can be viewed in isolation when troubleshooting . Many improvements can be subsequently adopted via ADTs in all environment or application programs without the slightest change.

If programming is object-oriented , these properties can be fulfilled particularly easily because the object-oriented paradigm naturally supports the creation of ADTs. Another possibility for creating ADTs (also in connection with object-oriented programming) are generic types .

literature

• Barbara Liskov , Stephen Zilles: Programming with abstract data types . In: SIGPLAN Notices , Vol. 9, No. 4, 1974, pp. 50-59
• John Guttag : Abstract Data Types and the Development of Data Structures . In: Communications of the ACM , Vol. 20, 1977, No. 6, pp. 396-404.
• JA Goguen, JW Thatcher, EW Wagner: An Initial Algebra Approach to the Specification, Correctness and Implementation of Abstract Data Types . In: RT Yeh (Ed.): Current Trends on Programming Methodology , Vol. IV, 1978, Prentice-Hall Int.
• Hartmut Ehrig, Bernd Mahr: Fundamentals of Algebraic Specification 1 - Equations and Initial Semantics . Springer-Verlag, 1985
• Luca Cardelli, Peter Wegner: On Understanding Types, Data Abstraction, and Polymorphism . In: Computing Surveys , Vol. 17, No. 4, December 1985, pp. 470-522
• John C. Mitchell, Gordon D. Plotkin: Abstract Data Types Have Existential Type . In: ACM Transaction on Programming Languages ​​ans Systems , Vol. 10, No. 3, July 1988, pp. 470-502.
• Peter Müller: Introduction to Object-Oriented Programming Using C ++ . Chapter on ADT
• Jorge Martinez: Ordered algebraic structures: proceedings of the Gainesville conference sponsored by the University of Florida 28th February-3rd Marchf, 200 . Kluwer Academic Publishers, Dordrecht; Boston 2002, ISBN 978-1-4020-0752-1 ( limited preview in Google Book Search [accessed July 5, 2010]).
• Rolke, Sennholz: Basic and advanced course in computer science . Cornelsen, Düsseldorf 1992, ISBN 3-464-57312-5 .