Abstrakter Datentyp

Abstrakter Datentyp (ADT) ist eine Bezeichnung in der Informatik für Datentypen, um diese unabhängig von einer konkreten Implementierung zu spezifizieren. Sie wurden von Barbara Liskov, Stephen Zilles 1974 und von John Guttag 1977 vorgestellt und einem breiten Publikum durch die "Communications of the ACM" nahe gebracht.

Bei sogenannten primitiven Datentypen, den Basisdatentypen einer Programmiersprache, gibt es oft erhebliche Unterschiede zwischen der Datentypimplementierung in den verschiedenen Sprachen, obwohl sie ähnlich heißen. Mal wird ein ganzzahliger Datentyp (Integer) mit 8-Bit implementiert, mal mit 16, was zur Folge hat, dass der Datentyp unterschiedliche Wertebereiche umfasst.

Definition

Ein Datentyp besteht aus einem Wertebereich, d. h. den Werten, die eine Variable von diesem Datentyp annehmen kann, und einer Menge an Operationen (Funktionen, Methoden oder Prozeduren), die für diesen Datentyp spezifiziert sind. „+“ ist zum Beispiel definiert für numerische Typen, und in einigen Programmiersprachen für einen String-Datentyp. „-“ hingegen ist in der Regel nur definiert für numerische Datentypen. Die Menge der Operationen wird auch das Interface (Schnittstelle) des ADTs genannt.

Bei Abstrakten Datentypen kommen Eigenschaften hinzu, die mit Prädikaten ausgedrückt werden. Diese Eigenschaften müssen für jede konkrete Implementierung vom abstrakten Datentyp gelten. Sie werden auch Axiome genannt und definieren die Semantik, die Bedeutung und Interaktion der Operationen.

Wenn man die Definition eines ADTs mathematisch betrachtet, handelt es sich um die Spezifikation einer Termalgebra durch Signatur, Konstruktor und Axiome.

Beispiel

Ein größeres Beispiel verdeutlicht die Notwendigkeit der Axiome bei ADTs. Wir definieren die ADTs Stack und Queue:

Wertebereich (Basistyp):

STACK (das definieren wir hier)
ELEMENT (ebenfalls ein ADT den wir hier aber nicht definieren 
         wollen, damit arbeitet der Stack)

Operationen (Syntax):

emptyStack: -> STACK (Erzeugt einen leeren Stack)
isStackEmpty: STACK -> Boolean (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)
top: STACK -> ELEMENT (Gibt eine Kopie vom obersten Element zurück)

Jetzt schauen wir uns eine Queue (Warteschlange) an:

Wertebereich (Basistyp):

QUEUE (das definieren wir hier)
ELEMENT

Operationen (Syntax):

emptyQueue: -> QUEUE (Erzeugt eine leere Queue)
isQueueEmpty: QUEUE -> Boolean (Fragt nach, ob die Queue leer ist)
enqueue: ELEMENT × QUEUE -> QUEUE (fügt ein Element unten an)
dequeue: QUEUE -> QUEUE (Entfernt das vorderste Element)
head: QUEUE -> ELEMENT (Gibt das vorderste Element zurück)

Auch bei genauerer Betrachtung kann man keine Unterschiede zwischen den Datentypen (ein Stack arbeitet nach dem Last-in-First-out-Prinzip, eine Queue aber nach dem First-in-First-out-Prinzip) erkennen. Die Namen der Operationen sind Schall und Rauch, sie könnten genauso gut „apfel“ und „birne“ heißen. Die Signaturen sind identisch. Erst mit der Einführung der Axiome wird alles klar:

Axiome (Stack):

 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

Axiome (Queue):

 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))

Eigenschaften abstrakter Datentypen

Anzustrebende Eigenschaften eines gut programmierten ADT und meist auch einer gut spezifierten Datenstruktur sind:

Universalität (implementation independence): Der einmal entworfene und implementierte ADT kann in jedes beliebige Programm einbezogen und dort benutzt werden (z. B. in Form einer Unit).
Präzise Beschreibung (precise specification): Die Schnittstelle zwischen Interface und Implementation muss eindeutig und vollständig sein.
Einfachheit (simplicity): Bei der Anwendung muss man sich nicht um die innere Realisation des ADT kümmern, da der ADT seine Repräsentation und Verwaltung im Speicher selbst übernimmt.
Kapselung (encapsulation): Das Interface soll als eine hermetische Grenze aufgefasst werden. Der Anwender soll sehr genau wissen, was ein ADT tut, aber keinesfalls, wie er es tut.
Geschütztheit (integrity): Der Anwender kann in die interne Struktur der Daten nicht eingreifen. Die Gefahr, Daten ungewollt zu löschen bzw. zu verändern sowie Programmierfehler zu begehen, ist dadurch deutlich herabgesetzt.
Modularität (modularity): Das modulare Prinzip erlaubt übersichtliches und damit sicheres Programmieren und leichten Austausch von Programmteilen. Bei der Fehlersuche können einzelne Module sehr isoliert betrachtet werden. Viele Verbesserungen können über ADTs nachträglich ohne die geringste Änderung in sämtlichen Umgebungs- bzw. Anwendungsprogrammen übernommen werden.

Wird objektorientiert programmiert, können diese Eigenschaften besonders leicht erfüllt werden, weil das objektorientierte Paradigma auf natürliche Weise die Erstellung von ADTs unterstützt. Eine weitere Möglichkeit zur Erstellung von ADTs (auch in Verbindung mit objektorientierter Programmierung) sind generische Typen.

Siehe auch

Literatur

Barbara Liskov, Stephen Zilles: Programming with abstract data types. in SIGPLAN Notices, Vol. 9, No. 4, pp 50–59, 1974
John Guttag: Abstract Data Types and the Development of Data Structures. in Communications of the ACM, Vol. 20, No. 6, pp. 396–404. 1977
J. A. Goguen, J. W. Thatcher, E. W. Wagner: An Initial Algebra Approach to the Specification, Correctness and Implementation of Abstract Data Types. in Current Trends on Programming Methodology, Vol. IV, (Yeh R.T. Ed.), Prentice-Hall Int., 1978
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, pp. 470–522 Dezember 1985
John C. Mitchell, Gordon D. Plotkin: Abstract Data Types Have Existential Type. in ACM Transaction on Programming Languages ans Systems, Vol. 10, No. 3, pp. 470–502. Juli 1988

und für die nicht wissenschaftlich interessierte Öffentlichkeit:

Peter Müller: Introduction to Object-Oriented Programming Using C++. Kapitel zu ADTs in [1]