Wie ,,funktioniert`` Datenabstraktion überhaupt? Der zentrale Begriff für die Datenabstraktion ist der ADT abstrakte Datentyp , abgekürzt ADT. Ein ADT ist eine Klasse von Objekten, die vollständig und ausschließlich durch die Operationen , die mit den Objekten vorgenommen werden können, definiert ist. Die Spezifikation eines ADT besteht folglich aus einer Spezifikation der Operationen. Die Daten sind dadurch untrennbar mit den Operationen, die sie manipulieren, verbunden. Für die Verwendung eines ADT sind Informationen über seine Implementation nicht nötig. Alle Manipulationen einzelner Objekte sind nur mit Hilfe von Operationen möglich, damit wird der Mißbrauch von evtl. vorhandenem Wissen über die Implementation unmöglich gemacht.
Beispiel: Ein in allen Programmiersprachen
existierender ADT ist die Ganzzahl (Integer): die Repräsentation einer
Ganzzahl ist unbekannt (oder sollte zumindest unbekannt sein), die nötigen
Operatoren für Ganzzahlarithmetik werden bereitgestellt
( ,MOD), außerdem eine Sammlung von
mathematischen Funktionen wie ln, sin, cos, tan,
, |x|
usw. Benötigt man allerdings zusätzliche Funktionen, müssen sie aus den
Die meisten benötigten ADT sind allerdings nicht so ,,einfach``, sondern stellen eine strukturierte Sammlung von Datenelemente Datenelementen dar. Datenelemente sind also die Untereinheiten, die einen strukturierten Datentyp bilden. Ein Datenelement kann ebenfalls strukturiert sein; auf der untersten Ebene sind nur die elementaren Datentypen erlaubt, die von der Sprache bereitgestellt werden. In C sind dies ganze Zahlen mit unterschiedlichen Wertebereichen, Zeichen (als Sonderfall von ganzen Zahlen) und Fließkommazahlen.
Die Operationen haben die signifikanten Merkmale Name, Parameter und Rückgabewert. Die von der Definition her naheliegende Schlußfolgerung, daß zur Spezifikation eines ADT keine Angabe über die Datenelemente nötig ist, ist daher falsch: zumindest einige Operationen beeinflussen Datenelemente, in ihren Parameterlisten müssen diese Datenelemente also auch spezifiziert sein. Allerdings werden in der Regel für die interne Verwaltung des ADT zusätzliche Datenelemente notwendig; um diese braucht sich die Programmiererin nicht zu kümmern.
Ein ADT definiert häufig zunächst nicht nur eine bestimmtes Objekt, sondern eine Klasse von Objekten; dann wird er auch Typgenerator Typgenerator genannt. Der Datentyp ,,Liste`` ist ein solcher Typgenerator, da die Elemente der Liste noch nicht festgelegt sind. Erst nach dieser Festlegung (z.B. ,,Liste von reellen Zahlen``) ist aus dem Typgenerator ein Datentyp geworden.
Folgende Vorteile ergeben sich aus der Verwendung von ADT:
Leider unterstützen die am meisten verwendeten Programmiersprachen (C, Pascal, COBOL, FORTRAN usw.) die Programmierung mit abstrakten Datentypen nicht oder nur eingeschränkt. In C gibt es zwar die Typgeneratoren ,,Tabelle``, ,,Struktur`` und ,,Variante``, die jeweils durch einen Satz Operationen unterstützt werden und die auch für viele Zwecke ausreichen; die Datenstrukturen können also als ADT bezeichnet werden. Meist bestehen jedoch implementationsabhängige Randbedingungen (z.B. maximale Größe, Verbot bestimmter Datentypen als Datenelemente), die die Verwendung für einige Problemstellungen unmöglich machen. Der Ausweg, den diese Programmiersprachen zum Teil anbieten, ist die Benutzung von dynamischen Datenstrukturen unter Verwendung von Pointern, die bei zunehmender Komplexität aber schwierig zu implementieren sind; ihr Test muß sehr sorgfältig erfolgen, denn die Speicherverwaltung dynamischer Datenstrukturen ist extrem fehlerträchtig.
Es gibt eine Reihe formaler Methoden zum Umgang mit ADT. Einige basieren auf theoretischer Mathematik, andere sind verwandt mit gängigen Programmiersprachen. Meist gibt es allerdings keine Implementation der Methode, so daß der Einsatz sich auf die formale Spezifikation des ADT beschränkt. Der durch VDM repräsentierte modellorientierte Ansatz hingegen liegt in einer Implementation unter UNIX vor, die die Sprache C um abstrakte Datentypen erweitert. Die theoretischen Grundlagen sind im Abschnitt 2.3 2.3 kurz beschrieben.
Formale Methoden der Abstraktion sind hervorragend dazu geeignet, die
Korrektheit von Programmen zu beweisen . Ist die abstrakte Spezifikation beweisbar die korrekte Lösung des Problems und ist jede Konkretisierung beweisbar äquivalent zur vorhergehenden Abstraktion, folgt daraus, daß auch die Implementation korrekt ist; ein Programmtest ist dann unnötig. In der Praxis ist der vollständige Beweis noch nicht möglich, aber eine formale Methode kann den Korrektheitsbeweis unterstützen und zumindest teilautomatisieren.
Der modellorientierte Ansatz
Abstrakte Datentypen
Abstraktion beim Programmieren