Abstrakter Datentyp
aus Wikipedia, der freien Enzyklopädie
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 und 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. Beispielsweise wird ein ganzzahliger Datentyp (Integer) mal mit 8 Bit implementiert und mal mit 16, was zur Folge hat, dass der Datentyp unterschiedliche Wertebereiche umfasst.
Inhaltsverzeichnis |
[Bearbeiten] Definition
Ein Datentyp besteht aus einem Wertebereich, d. h. den Werten, die eine Variable dieses Datentyps 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 die Schnittstelle des ADTs genannt.
Ein abstrakter Datentyp kann durch unterschiedliche Spezifikationen angegeben werden. Eine Spezifikation besteht aus einer Signatur und einer Semantik, die Bedeutung und Interaktion der Operationen festlegt.
Mathematisch betrachtet handelt es sich um die Spezifikation einer Termalgebra durch Signatur, Erzeuger und Axiome. Daraus ergibt sich die erste Art der Spezifikation, die mathematisch-axiomatische.
Eine weitere Möglichkeit ist die mathematisch-algebraische Spezifikation, die sich nur in der Angabe der Semantik von der axiomatischen unterscheidet. Die inhaltliche Bedeutung der Operationen wird hierbei durch mathematische Mittel, Matrizen, Vektoren, Folgen, etc. definiert.
Daneben existieren Sonderformen, wie die informelle Methode der Spezifikation – durch Angabe einer Schnittstelle einer Programmiersprache, bspw. als Java-Schnittstellen oder die Implementierung des Datentyps in einer funktionalen Programmiersprache wie Haskell – was im ersten Moment widersprüchlich zu dem Bestreben steht, den Datentyp unabhängig von einer Implementierung zu machen. Die Implementierung in einer funktionalen Programmiersprache dient allerdings als Spezifikation für ADTs, die schließlich in prozeduralen oder objektorientierten Sprachen implementiert werden. Der Vorteil dieser Spezifikation ist, dass gleich getestet werden kann, ob die Spezifikation sinnvoll ist, was bei den anderen Möglichkeiten, besonders der axiomatischen, nicht ohne weiteres möglich ist.
[Bearbeiten] Beispiel
Im Folgenden werden die ADTs Stapelspeicher (Stack, arbeitet nach dem Last-in-First-out-Prinzip) und Warteschlange (Queue, arbeitet nach dem First-in-First-out-Prinzip) in den angesprochenen vier Spezifikationen definiert.
[Bearbeiten] Signatur
[Bearbeiten] Mathematisch-axiomatische und -algebraische Methode
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 unten an) dequeue: QUEUE -> QUEUE (entfernt das vorderste Element) head: QUEUE -> ELEMENT (gibt das vorderste Element zurück, ohne es zu entfernen)
[Bearbeiten] Informelle Methode (Java)
public interface IStack<E> {
// Konstruktor in der konkreten Klasse
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();
}
[Bearbeiten] Spezifikation durch eine funktionale Programmiersprache (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
[Bearbeiten] Semantik
Auch bei genauerer Betrachtung der (identischen) Signaturen sind keine Unterschiede zwischen den Datentypen zu erkennen. Erst mit der Definition der Semantik ergeben sich Unterschiede.
[Bearbeiten] Mathematisch-axiomatische Methode
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))
[Bearbeiten] Mathematisch-algebraische Methode
SETS ELEMENT = E (Menge der Elemente);STACK = S =
FUNCTIONS emptyStack =
isStackEmpty(S) =
push(S,x) =
, falls
, falls
top(S) =
, falls
, falls
pop(S) =
=
, falls
SETS ELEMENT = E (Menge der Elemente);enqueue(Q,x) =
, falls
[Bearbeiten] Informelle Methode (Java)
Semantik: durch Angabe von Voraussetzung und Effekt/Ergebnis der Methode (Beim objektorientierten Programmieren entfällt meist die Notwendigkeit, als Voraussetzung die Existenz der Datenstruktur anzugeben, da die Methode an ein Objekt gebunden ist, was schon existiert.)
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.
// 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();
}
[Bearbeiten] Spezifikation durch eine funktionale Programmiersprache (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)
[Bearbeiten] 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 Implementierung und Anwendung muss eindeutig und vollständig sein.
- Einfachheit (simplicity): Bei der Anwendung interessiert die innere Realisierung des ADT nicht, der ADT übernimmt seine Repräsentation und Verwaltung im Speicher selbst.
- Kapselung (encapsulation): Die Schnittstelle 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.
[Bearbeiten] 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
- Peter Müller: Introduction to Object-Oriented Programming Using C++. Kapitel zu ADTs online.
- Jorge Martinez: Ordered Algebraic Structures. [1], Springer, 2002
