imported>Greenhorn4: /* Angestrebte Eigenschaften */ Die Definitionen von Geschütztheit und Kapselung waren vertauscht.

2022-02-10T10:24:52Z

Angestrebte Eigenschaften: Die Definitionen von Geschütztheit und Kapselung waren vertauscht.

Neue Seite

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

== Beschreibung ==
Da der Zugriff nur über die festgelegten Operationen erfolgt, sind die Daten nach außen [[Datenkapselung (Programmierung)|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 Programmiersprache]]n 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 Programmierung|modulare Programmiersprachen]] wie [[Ada (Programmiersprache)|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 [[Schnittstelle (Programmierung)|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 (Programmierung)|Signatur]] und einer Semantik, die Bedeutung und Interaktion der Operationen festlegt.

Mathematisch betrachtet handelt es sich um die Spezifikation einer [[Termalgebra]] durch [[Signatur (Modelltheorie)|Signatur]], [[Erzeuger (Algebra)|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 (Programmiersprache)|Java]]-Schnittstellen oder die Implementierung des Datentyps in einer [[Funktionale Programmierung|funktionalen Programmiersprache]] wie [[Haskell (Programmiersprache)|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|Last-in-First-out]]''-Prinzip) und [[Warteschlange (Datenstruktur)|Warteschlange]] (''Queue'', arbeitet nach dem ''[[First In – First Out|First-in-First-out]]''-Prinzip) in den angesprochenen vier Spezifikationen definiert.

=== Signatur ===
==== Mathematisch-axiomatische und -algebraische Methode ====
STACK (wird hier definiert)
ELEMENT (ein hier nicht definierter ADT, mit dem der Stack arbeitet)
BOOL

emptyStack: → STACK (erzeugt einen leeren Stack)
isStackEmpty: STACK → BOOL (fragt nach, ob der Stack leer ist)
push: ELEMENT × STACK → STACK (packt ein Element oben auf den Stack)
pop: STACK → STACK (entfernt das oberste Element und gibt den neuen Stack zurück)
top: STACK → ELEMENT (gibt das oberste Element zurück, ohne es zu entfernen)

QUEUE
ELEMENT
BOOL

emptyQueue: → QUEUE
isQueueEmpty: QUEUE → BOOL
enqueue: ELEMENT × QUEUE → QUEUE (fügt ein Element hinten an)
dequeue: QUEUE → QUEUE (entfernt das vorderste Element)
head: QUEUE → ELEMENT (gibt das vorderste Element zurück, ohne es zu entfernen)

==== Informelle Methode (Java) ====
<syntaxhighlight lang="java">
public interface IStack<E> {

public boolean isStackEmpty();
public IStack<E> push(E elem);
public IStack<E> pop();
public E top();
}

public interface IQueue<E> {

public boolean isQueueEmpty();
public IQueue<E> enqueue(E elem);
public IQueue<E> dequeue();
public E head();
}
</syntaxhighlight>

==== Spezifikation durch eine funktionale Programmiersprache (Haskell) ====
<syntaxhighlight lang="Haskell">
data Stack e = E | S e (Stack e)
isStackEmpty :: Stack a → Bool
push :: e → Stack e → Stack e
pop :: Stack e → Stack e
top :: Stack e → e

data Queue e = E | Q (Queue e) e
isQueueEmpty :: Queue e → Bool
enqueue :: e → Queue e → Queue e
dequeue :: Queue e → Queue e
head :: Queue e → e
</syntaxhighlight>

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

==== Mathematisch-axiomatische Methode ====
x: ELEMENT
s: STACK
isStackEmpty(emptyStack()) = TRUE
isStackEmpty(push(x,s)) = FALSE
pop(emptyStack()) = ERROR
pop(push(x,s)) = s
top(emptyStack()) = ERROR
top(push(x,s)) = x
push(top(s),pop(s)) = s, falls s nicht leer

x: ELEMENT
q: QUEUE
isQueueEmpty(emptyQueue()) = TRUE
isQueueEmpty(enqueue(x,q)) = FALSE
head(emptyQueue()) = ERROR
head(enqueue(x,q)) = IF isQueueEmpty(q) THEN x ELSE head(q)
dequeue(emptyQueue()) = ERROR
dequeue(enqueue(x,q)) = IF isQueueEmpty(q) THEN q ELSE enqueue(x, dequeue(q))

==== Mathematisch-algebraische Methode ====
SETS ELEMENT = E (Menge der Elemente) <math>x \in E</math>
STACK = S = <math>\lbrace \langle \rangle \rbrace \cup \lbrace \langle x_1{,}...{,}x_n \rangle|x_i \in E \land\ n\in \mathbb{N} \land n \ge 1 \rbrace</math>
FUNCTIONS
emptyStack = <math>\langle \rangle</math>
isStackEmpty(S) = <math>(S == \langle \rangle)</math>
push(S,x) = <math>\langle x \rangle</math>, falls <math>(S == \langle \rangle)</math>
= <math>\langle x_1{,}...{,}x_n{,}x \rangle</math>, falls <math>(S == \langle x_1{,}...{,}x_{n} \rangle)</math>
top(S) = <math>\perp</math>, falls <math>(S == \langle \rangle)</math>
= <math>x_n\,</math>, falls <math>(S == \langle x_1{,}...{,}x_{n} \rangle, n \ge 1)</math>
pop(S) = <math>\perp</math>, falls <math>(S == \langle \rangle)</math>
= <math>\langle \rangle</math>, falls <math>(S == \langle x \rangle)</math>
= <math>\langle x_1{,}...{,}x_{n-1} \rangle</math>, falls <math>(S == \langle x_1{,}...{,}x_{n} \rangle, n \ge 2)</math>

SETS ELEMENT = E (Menge der Elemente) <math>x \in E</math>
QUEUE = Q = <math>\lbrace \langle \rangle \rbrace \cup \lbrace \langle x_1{,}...{,}x_n \rangle|x_i \in E \land\ n\in \mathbb{N} \land n \ge 1 \rbrace</math>
FUNCTIONS
emptyQueue = <math>\langle \rangle</math>
isQueueEmpty(Q) = <math>(Q == \langle \rangle)</math>
enqueue(Q,x) = <math>\langle x \rangle</math>, falls <math>(Q == \langle \rangle)</math>
= <math>\langle x{,}x_1{,}...{,}x_n \rangle</math>, falls <math>(Q == \langle x_1{,}...{,}x_{n} \rangle)</math>
head(Q) = <math>\perp</math>, falls <math>(Q == \langle \rangle)</math>
= <math>x_n\,</math>, falls <math>(Q == \langle x_1{,}...{,}x_{n} \rangle, n \ge 1)</math>
dequeue(Q) = <math>\perp</math>, falls <math>(Q == \langle \rangle)</math>
= <math>\langle \rangle</math>, falls <math>(Q == \langle x \rangle)</math>
= <math>\langle x_1{,}...{,}x_{n-1} \rangle</math>, falls <math>(Q== \langle x_1{,}...{,}x_{n} \rangle, n \ge 2)</math>

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

<syntaxhighlight lang="java">
public interface IStack<E> {
// Konstruktor in der konkreten Klasse

// Ergebnis: true, wenn der Stack leer ist, false andernfalls
public boolean isStackEmpty();

// Effekt: Der Stack enthält das Element elem als oberstes Element.
// Ergebnis: Der Stack nach dem Einfügen des Elements elem.
public IStack<E> push(E elem);

// Voraussetzung: Der Stack ist nicht leer.
// Effekt: Das oberste Element wird vom Stack gelöscht.
// Ergebnis: Der Stack nach dem Löschen.
public IStack<E> pop();

// Voraussetzung: Der Stack ist nicht leer.
// Ergebnis: Das oberste Element.
public E top();
}
public interface IQueue<E> {
public boolean isQueueEmpty();
public IQueue<E> enqueue(E elem);
public IQueue<E> dequeue();
public E head();
}
</syntaxhighlight>

==== Spezifikation durch eine funktionale Programmiersprache (Haskell) ====
<syntaxhighlight lang="haskell">
emptyStack = E
isStackEmpty E = True
isStackEmpty (S x xs) = False
push e xs = S e xs
pop (S x xs) = xs
top (S x xs) = x

emptyQueue = E
isQueueEmpty E = True
isQueueEmpty (Q xs x) = False
enqueue e xs = Q xs e
dequeue E = E
dequeue (Q (E) x) = E
dequeue (Q (Q ys y) x) = enqueue x (dequeue (Q ys y))
head E = error "Queue ist leer."
head (Q (E) x) = x
head (Q (Q ys y) x) = head (Q ys y)
</syntaxhighlight>

== 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 [[Computerprogramm|Programm]] einbezogen und dort benutzt werden (z. B. in Form einer [[Unit (Programmiersprache Pascal)|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 [[Arbeitsspeicher|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 [[Modul (Software)|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 [[Objektorientierte Programmierung|objektorientiert]] programmiert, können diese Eigenschaften besonders leicht erfüllt werden, weil das objektorientierte [[Programmierparadigma|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 [[Generischer Typ|generische Typen]].

== Literatur ==
* [[Barbara Liskov]], Stephen Zilles: ''Programming with abstract data types''. In: ''SIGPLAN Notices'', Vol. 9, No. 4, 1974, S. 50–59
* [[John Guttag]]: ''Abstract Data Types and the Development of Data Structures''. In: ''Communications of the ACM'', Vol. 20, 1977, No. 6, S. 396–404.
* J. A. Goguen, J. W. Thatcher, E. W. Wagner: ''An Initial Algebra Approach to the Specification, Correctness and Implementation of Abstract Data Types''. In: R.T. Yeh (Hrsg.): ''Current Trends on Programming Methodology'', Vol. IV, 1978, Prentice-Hall Int.
* Hartmut Ehrig, Bernd Mahr: ''Fundamentals of Algebraic Specification 1 – Equations and Initial Semantics''. Springer-Verlag, 1985
* Luca Cardelli, Peter Wegner: ''On Understanding Types, Data Abstraction, and Polymorphism''. In: ''Computing Surveys'', Vol. 17, No. 4, Dezember 1985, S. 470–522
* John C. Mitchell, Gordon D. Plotkin: ''Abstract Data Types Have Existential Type''. In: ''ACM Transaction on Programming Languages ans Systems'', Vol. 10, No. 3, Juli 1988, S. 470–502.
* Peter Müller: ''Introduction to Object-Oriented Programming Using C++''. [https://www.desy.de/gna/html/cc/Tutorial/node4.html Kapitel zu ADT]
* {{Literatur |Autor=Jorge Martinez |Titel=Ordered algebraic structures: proceedings of the Gainesville conference sponsored by the University of Florida 28th February-3rd Marchf, 200 |Verlag=Kluwer Academic Publishers |Ort=Dordrecht; Boston |Datum=2002 |ISBN=978-1-4020-0752-1 |Sprache=en |Online={{Google Buch| BuchID = VocRthxFC68C |SeitenID=PP5}}}}
* {{Literatur |Autor=Rolke, Sennholz |Titel=Grund- und Leistungskurs Informatik |Verlag=Cornelsen |Ort=Düsseldorf |Datum=1992 |ISBN=3-464-57312-5}}

[[Kategorie:Datentyp]]

[[sv:Datatyp#Abstrakta typer]]

Abstrakter Datentyp - Versionsgeschichte

imported>Greenhorn4: /* Angestrebte Eigenschaften */ Die Definitionen von Geschütztheit und Kapselung waren vertauscht.