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, 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.

Inhaltsverzeichnis 1 Definition 2 Beispiel 2.1 Signatur 2.1.1 Mathematisch-axiomatische/-algebraische Methode 2.1.2 Informelle Methode (Java) 2.1.3 Spezifikation durch eine Funktionale Programmiersprache (Haskell) 2.2 Semantik 2.2.1 Mathematisch-axiomatische Methode 2.2.2 Mathematisch-algebraische Methode 2.2.3 Informelle Methode (Java) 2.2.4 Spezifikation durch eine funktionale Programmiersprache (Haskell) 3 Eigenschaften abstrakter Datentypen 4 Siehe auch 5 Literatur

[Bearbeiten] 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.

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.

Wenn man die Definition eines ADTs 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-Interfaces oder die Implementation des Datentyps in einer funktionalen Programmiersprache wie Haskell – was im ersten Moment widersprüchlich zu dem Bestreben steht, den Datentyp unabhängig von einer Implementation zu machen. Die Implementation 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.

Kurzdefinition: Ein abstrakter Datentyp ist eine implementationsunabhängige Spezifikation einer Datenstruktur, mit den darauf zulässigen Operationen.

[Bearbeiten] Beispiel

Wir definieren die ADTs Stack und Queue in allen vier angesprochenen Spezifikationen:

[Bearbeiten] Signatur

[Bearbeiten] Mathematisch-axiomatische/-algebraische Methode

Wertebereich (Basistyp):

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

Operationen (Syntax):

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 obersten Element zurück, ohne es zu entfernen)

Jetzt schauen wir uns eine Queue (Warteschlange) an:

Wertebereich (Basistyp):

QUEUE (das definieren wir hier)
ELEMENT
BOOL

Operationen (Syntax):

emptyQueue: -> QUEUE (Erzeugt eine leere Queue)
isQueueEmpty: QUEUE -> BOOL (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)

[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> {
    (Konstruktor in der konkreten Klasse)
    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

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 Definition der Semantik:

[Bearbeiten] Semantik

[Bearbeiten] Mathematisch-axiomatische Methode

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

[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 
                    = , falls 
                    = , falls 

SETS ELEMENT = E (Menge der Elemente); 
     QUEUE = Q = 
FUNCTIONS
    emptyQueue      = 
    isQueueEmpty(Q) = 
    enqueue(Q,x)    = , falls 
                    = , falls 
    head(S)         = , falls 
                    = , falls 
    dequeue(S)      = , falls 
                    = , falls 
                    = , 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> {
    (Konstruktor in der konkreten Klasse)

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

    // Effekt: Der Stack enthält das Element elem.
    // Ergebnis: Der Stack nach dem Einfügen des Elements elem.
    public IQueue<E> enqueue(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 IQueue<E> dequeue();

    // Voraussetzung: Der Stack ist nicht leer.
    // Ergebnis: Das oberste Element.
    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 Schnittstelle (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.

[Bearbeiten] Siehe auch

• Datentyp
• Programmierparadigma

[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

und für die nicht wissenschaftlich interessierte Öffentlichkeit:

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