Vienna Development Method
Abstrakte Datentypen
Was sind abstrakte Datentypen
Der modellorientierte Ansatz stellt eine
formale Sprache bereit, in der diese Spezifikation in Form einer repräsentationalen
und einer operationalen Abstraktion geschrieben wird, entsprechend den beiden
Bestandteilen eines ADT (Daten und Operationen).
Die repräsentationale Abstraktion
ist die Spezifikation von Klassen und Objekten abstrakter Datentypen im
Hinblick auf ihre Eigenschaften, aber unabhängig von ihrer Repräsentation. Sie
besteht aus dem Namen des Datentyps und der Spezifikation der notwendigen
Datenelemente . Die Beschreibung des inneren Aufbaus soll
so abstrakt wie möglich sein; allerdings orientiert sich die Entwicklerin sehr
frühzeitig an den von der formalen Sprache bereitgestellten, sehr mächtigen
Modellen von Datenstrukturen
(daher der Name des Ansatzes), das sind universelle Typgeneratoren, die
keinerlei Restriktionen unterworfen sind. Dies sind z.B. die Datentypen Menge,
Man könnte nun argumentieren, das damit das ADT-Konzept torpediert wird; man
kann den ADT nicht völlig selbständig und losgelöst definieren, sondern
wird gezwungen, sich an zwar sehr mächtigen, aber letztlich doch beschränkten
Typgeneratoren zu orientieren. Dem ist allerdings folgendes zu entgegnen: eine
Entwicklerin, die eine ,,reine``, der obigen Definition entsprechende
Spezifikation erhält und sie implementieren soll,
orientiert sich ebenfalls an bestimmten, ihr geläufigen Datenstrukturen.
Einige eignen sich besonders gut zur Repräsentation des geforderten ADT,
andere überhaupt nicht. Schließlich wird die Entwicklerin die Datenstruktur
wählen, deren Eigenschaften den geforderten am nächsten kommen; einige der
Anforderungen lassen sich vielleicht nur umständlich und ineffizient erfüllen,
da der gewünschte ADT sicherlich zumindest in Details von dem gewählten
,,Standard-Typ`` abweicht. Demzufolge ähnelt die grundsätzliche Vorgehensweise
in der Praxis auch bei einem völlig selbständig definierten ADT dem Vorgehen
des modellorientierten Ansatzes. Der einzige Unterschied könnte sein, daß die
Entwicklerin mehr Datenstrukturen kennt, als die formale Sprache anbietet.
Daher sollte die formale Sprache um neue Typgeneratoren erweitert werden
können.
Die operationale Abstraktion ist die
Spezifikation der Operationen und Funktionen, die auf Objekte angewendet
werden, ebenfalls unabhängig von ihrer Realisierung. Diese Funktionen
stellen komplexere Manipulationen an den Objekten dar, die allerdings aus
elementaren Operationen zusammengesetzt werden können; sie zählen also nicht
zu den ADT-Operationen , die den ADT ,,charakterisieren``,
und brauchen demnach auch nicht spezifiziert zu werden. Es schadet allerdings
nichts, wenn die Programmiererin, die die Implementation vornehmen soll, schon
über komplexere Anwendungen des Typs informiert ist -- die Auswahl der
Repräsentation kann dadurch entscheidend beeinflußt werden.
Zur Spezifikation müssen folgende Elemente vorhanden sein:
- Name der Operation
- Argumentmenge (in Form einer Liste von Parametern, bestehend aus Name
und Typ, wie von den Funktionsdefinitionen in C bekannt)
- Zielmenge in Form eines Rückgabewertes
- konstruktive oder implizite Spezifikation der Semantik
Die
Semantik ist die ,,Bedeutung`` einer
Operation, beschreibt also ihre Auswirkung, während die ersten drei Punkte die
Syntax der Operation definieren, d.h. Informationen, wie
man die Operation korrekt benutzt.
Die konstruktive Spezifikation ist
eine Beschreibung der Manipulation, die von der Operation durchgeführt wird,
in der formalen Sprache. Die implizite Spezifikation hingegen beschreibt die Wirkung in Form zweier Bedingungen: die
Prä-Kondition (precondition)
muß erfüllt sein, damit die Funktion aufgerufen werden darf -- sonst liefert
sie einen Fehlercode. Die
Post-Kondition (
Durch eine schrittweise Verfeinerung wird nun die
Ausgangsspezifikation in eine lauffähige Implementation
umgewandelt. Schritt für Schritt nimmt die Abstraktion ab, die Repräsentation
der Datenobjekte und die Algorithmen für die Operationen werden konkreter.
Dabei kann jeder Schritt durch einen formalen
Korrektheitsbeweis (siehe
abgesichert werden; die endgültige Implementation ist dann eine korrekte
Repräsentation der ursprünglichen Spezifikation. Aufgrund der Orientierung an
Typgeneratoren (Modellen) ist die Konkretisierung relativ schnell möglich. Bei
entsprechender Auslegung der formalen Sprache ist auch der Übergang von der
konstruktiven Spezifikation der Operationen zu einer Implementation in einer
beliebigen Programmiersprache einfach möglich.
Vienna Development Method
Abstrakte Datentypen
Was sind abstrakte Datentypen
VDM Class Library