Abstrakter Datentyp

Grundidee und Abgrenzung

Ein abstrakter Datentyp (ADT) ist ein Verbund von Daten und der Definition aller zulässigen Operationen, die auf diese Daten zugreifen. Er legt damit fest, was mit einer Datenstruktur gemacht werden darf.

Der Zugriff erfolgt ausschließlich über die festgelegten Operationen. Dadurch sind die Daten nach außen gekapselt: Nutzende kennen die erlaubten Funktionen und deren Bedeutung, nicht jedoch die interne Speicherung oder Umsetzung.

Ein ADT beschreibt die Semantik, also was Operationen tun sollen, aber nicht ihre Implementierung, also wie sie dies technisch tun. ADTs können etwa mit Pseudocode oder mathematisch notiert werden. Objektorientierte Sprachen unterstützen sie durch Klassen, abstrakte Klassen und Interfaces: Klassen binden Daten und Operationen zusammen, schützen die Daten und legen die zulässigen Zugriffe fest. Auch modulare Sprachen wie Ada oder Modula-2 unterstützen ADTs.

Signatur und Arten der Spezifikation

Eine ADT-Spezifikation besteht aus Signatur und Semantik. Die Signatur nennt die verwendeten Typen sowie die Operationen mit ihren Ein- und Ausgabetypen. Die Semantik bestimmt Bedeutung und Zusammenspiel dieser Operationen.

Mathematisch ist dies die Spezifikation einer Termalgebra durch Signatur, Erzeuger und Axiome. Bei der mathematisch-axiomatischen Methode wird die Semantik durch Axiome beziehungsweise Gleichungen beschrieben. Die mathematisch-algebraische Methode beschreibt die inhaltliche Bedeutung der Operationen durch mathematische Mittel wie Mengen, Matrizen, Vektoren oder Folgen.

Daneben gibt es die informelle Methode, etwa durch eine Java-Schnittstelle mit Voraussetzungen sowie Effekt oder Ergebnis der Methoden. Eine funktionale Sprache wie Haskell kann ebenfalls zur Spezifikation dienen. Obwohl dies wie eine Implementierung wirkt, kann sie als Spezifikation für spätere prozedurale oder objektorientierte Implementierungen dienen. Ihr Vorteil ist, dass sich unmittelbar testen lässt, ob die Spezifikation sinnvoll ist; dies ist besonders bei der axiomatischen Methode nicht ohne Weiteres möglich.

Stack und Queue als Signaturen

Das Beispiel behandelt Stapelspeicher (Stack) und Warteschlange (Queue). Ein Stack arbeitet nach dem Last-in-First-out-Prinzip: Das zuletzt eingefügte Element wird zuerst entfernt. Eine Queue arbeitet nach dem First-in-First-out-Prinzip: Das zuerst eingefügte Element wird zuerst entfernt.

Für den Stack werden die Typen STACK, ELEMENT und BOOL verwendet. Seine Operationen sind:

• emptyStack: → STACK erzeugt einen leeren Stack.
• isStackEmpty: STACK → BOOL prüft, ob er leer ist.
• push: ELEMENT × STACK → STACK legt ein Element oben auf.
• pop: STACK → STACK entfernt das oberste Element und liefert den neuen Stack.
• top: STACK → ELEMENT liefert das oberste Element, ohne es zu entfernen.

Für die Queue gibt es entsprechend emptyQueue, isQueueEmpty, enqueue: ELEMENT × QUEUE → QUEUE zum Einfügen hinten, dequeue: QUEUE → QUEUE zum Entfernen vorne und head: QUEUE → ELEMENT zum Auslesen des vordersten Elements ohne Entfernen. Java-Interfaces IStack<E> und IQueue<E> führen dieselben Methoden auf; eine konkrete Klasse implementiert das Interface. In Haskell werden etwa data Stack e = E | S e (Stack e) und data Queue e = E | Q (Queue e) e als Typformen angegeben.

Semantik der beiden Datenstrukturen

Die identischen Arten von Signaturangaben machen den Unterschied zwischen Stack und Queue noch nicht sichtbar; er entsteht erst durch die Semantik.

Für den Stack gelten unter anderem: isStackEmpty(emptyStack()) = TRUE, isStackEmpty(push(x,s)) = FALSE, pop(push(x,s)) = s und top(push(x,s)) = x. pop(emptyStack()) und top(emptyStack()) ergeben ERROR. Für einen nicht leeren Stack gilt außerdem push(top(s),pop(s)) = s.

Für die Queue gilt: isQueueEmpty(emptyQueue()) = TRUE und isQueueEmpty(enqueue(x,q)) = FALSE. Bei einer leeren Queue führen head(emptyQueue()) und dequeue(emptyQueue()) zu ERROR. Sonst lautet die Definition head(enqueue(x,q)) = IF isQueueEmpty(q) THEN x ELSE head(q); entsprechend entfernt dequeue(enqueue(x,q)) das vorderste Element.

Die algebraische Spezifikation beschreibt Stack und Queue als endliche Folgen aus einer Elementmenge E, einschließlich der leeren Folge ⟨⟩. Bei einem Stack liefert top(⟨x₁,...,xₙ⟩) das letzte Element xₙ; pop entfernt es. Bei einer Queue liefert head(⟨x₁,...,xₙ⟩) ebenfalls xₙ; dequeue entfernt dieses Element. Auf der leeren Folge liefern top, pop, head beziehungsweise dequeue den undefinierten Wert ⊥.

Die funktionale Haskell-Spezifikation setzt beispielsweise emptyStack = E, push e xs = S e xs, pop (S x xs) = xs und top (S x xs) = x. Für die Queue sind emptyQueue = E, enqueue e xs = Q xs e sowie rekursive Definitionen für dequeue und head angegeben; head E = error "Queue ist leer.".

Qualitätsmerkmale

Ein gut programmierter ADT und meist auch eine gut spezifizierte Datenstruktur sollen folgende Eigenschaften haben:

• Universalität: Ein einmal entworfener und implementierter ADT soll in beliebige Programme einbezogen und dort verwendet werden können, etwa als Unit.
• Präzise Beschreibung: Die Schnittstelle zwischen Implementierung und Anwendung muss eindeutig und vollständig sein.
• Einfachheit: Für die Anwendung ist die interne Realisierung unwichtig; der ADT verwaltet seine Repräsentation und seinen Speicher selbst.
• Geschütztheit: Die Schnittstelle bildet eine hermetische Grenze. Nutzende sollen genau wissen, was ein ADT tut, aber nicht, wie er es tut.
• Kapselung: Ein Eingriff in die interne Datenstruktur ist nicht möglich. Dies verringert das Risiko, Daten ungewollt zu löschen oder zu verändern und Programmierfehler zu machen.
• Modularität: Programmteile lassen sich übersichtlich, sicher und austauschbar gestalten. Bei der Fehlersuche können einzelne Module isoliert untersucht werden; Verbesserungen am ADT können ohne Änderungen in allen Umgebungs- oder Anwendungsprogrammen übernommen werden.

Objektorientierte Programmierung erleichtert das Erfüllen dieser Eigenschaften. Auch generische Typen können ADTs erstellen, gegebenenfalls zusammen mit objektorientierter Programmierung.