Abstrakter Datentyp
# Abstrakter Datentyp

Ein Abstrakter Datentyp (ADT) ist ein Verbund von Daten zusammen mit der Definition aller zulässigen Operationen, die auf sie zugreifen.

## Beschreibung

Da der Zugriff nur über die festgelegten Operationen erfolgt, sind die Daten nach außen gekapselt.

Ein ADT beschreibt, was die Operationen tun (Semantik), aber noch nicht, wie sie es tun sollen (Implementierung). Auch kann das Konzept des ADTs unterschiedlich spezifiziert und ein ADT auf verschiedene Weise notiert werden, bspw. durch Pseudocode oder durch eine mathematische Beschreibung. Modernere Programmiersprachen unterstützen allerdings gezielt die Erstellung von ADTs.

Objektorientierte Programmiersprachen unterstützen durch ihr Klassenkonzept die Erstellung von ADTs, da hier Daten und Operationen gebunden werden, die Daten geschützt und die zulässigen Operationen festgelegt werden können. Einige modulare Programmiersprachen wie Ada oder Modula-2 unterstützen ebenfalls gezielt die Erstellung von ADTs. In der Regel ist es möglich, einen ADT durch Definition der Daten und der Signaturen der Operationen festzulegen, während die Semantik als Kommentartext beschrieben wird.

### Beispiel

    Java unterstützt ADTs durch Klassen, abstrakte Klassen und Interfaces. In einem Interface werden nur Daten und Signaturen der Operationen definiert, eine festgelegte Klasse implementiert erst das Interface. Allgemein legt eine Klasse die Daten und die darauf zulässigen Operationen fest.

## Spezifikationen

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

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

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

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

## Angestrebte Eigenschaften

Anzustrebende Eigenschaften eines gut programmierten ADT und meist auch einer gut spezifizierten 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.
* Geschütztheit (integrity): 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.
* Kapselung (encapsulation): 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.

