Der modellorientierte Ansatz Abstrakte Datentypen Abstraktion beim Programmieren

Was sind abstrakte Datentypen ?

Definition

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.

Vor- und Nachteile von ADT

Folgende Vorteile ergeben sich aus der Verwendung von ADT:

• Da nur die Operationen Informationen über die Implementation benötigen, ist es leicht möglich, eine Implementation zu ersetzen, wenn eine bessere Repräsentation des ADT gefunden wird. Nur die Operationen müssen neu erstellt werden, alle Programme, die diesen ADT verwenden, bleiben unverändert.
• Die Programmiererin braucht während der Programmentwicklung auch keinerlei Rücksicht auf die Implementation des ADT zu nehmen, sie kann den bestmöglichen Algorithmus zur Lösung des Problems verwenden.
• Die tatsächliche Implementation des ADT kann zeitlich nach hinten verlagert werden, so daß bei der Auswahl mehr Informationen über die Programmanforderungen an den ADT vorliegen; auch die Operationen können also mit ,,maßgerechten`` Algorithmen realisiert werden.
• Universelle ADT können leicht in anderen Programmen wiederverwendet werden. Dies ist umso häufiger möglich, je ,,genereller`` der ADT ist -- wie z.B. Listen, Kellerspeicher, Bäume.
• Die Realisierung des ADT kann von anderen Programmiererinnen durchgeführt werden, die Arbeitsteilung wird also unterstützt.
• Viele Methoden zur Datenabstraktion stellen Mittel zum Beweis der Korrektheit von Programmen zur Verfügung, indem die abstrakte Spezifikation in mehreren Schritten konkretisiert wird, die einzeln bewiesen werden können. Selbst wenn der Beweis zu aufwendig ist, leisten sie in der Regel Hilfestellung bei der Auswahl von Testfällen.

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.

Formale Methoden

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