WikiDer > Abstrakter Datentyp

EIN abstrakter Datentyp (abgekürzt ADT) oder abstrakter Datentyp ist ein Modellierungskonzept von dem Informatik. Der Begriff leitet sich vom englischen Begriff ab abstrakter Datentyp.

ADTs werden verwendet, um bestehende zu ersetzen Programmiersprachen erweitert werden mit Datentypen die nicht in diese Sprachen integriert sind. Diese Datentypen haben eine höhere Abstraktionsebene als diejenigen, die in die für die Implementierung verwendete Programmiersprache integriert sind, und jeder hat spezifische Operationen zum Bearbeiten von Instanzen des ADT.

Es ist wichtig zu beachten, dass der Begriff abstrakt bei ADTs bezieht sich auf den Abstraktionsgrad der ADT (wie in Abstraktion in dem Mathematik, abstraktes Denken) und nicht auf die Möglichkeit, Umsetzungsteile wegzulassen (wie bei abstrakte Klassen).

Hintergrundbilder

Das Konzept eines ADT hat sich im Laufe der Jahre weiterentwickelt 1960 und '70, wenn die ersten Programmiersprachen mit einem deutlich höheren Abstraktionsgrad als Maschinensprache und Versammlung wurde alltäglich. Im gleichen Zeitraum begann sich die Informatik langsam als spezifischer Zweig der Mathematik und begannen Forscher wie John McCarthy, Tony Hoare, Donald Knuth und Edsger Dijkstraße eine feste, formale Grundlage für die Gestaltung schaffen build Computerprogramme.

Mit zunehmendem Verständnis dieses Designprozesses wurde es immer wünschenswerter, auf einer höheren Abstraktionsebene über Datenstrukturen die in einem Programm verwendet werden. Um ein Programm so zu modellieren, dass die Lösung eines gegebenen Problems transparent wird, hielt man es beispielsweise für wünschenswert, Stapel reden und nicht nur über ein "Array die auf eine bestimmte Art und Weise verwendet wird". Die Einführung solcher Konzepte ermöglichte es, auf einer höheren Ebene über die Funktionsweise eines Programms (von Teilen eines Programms) und über den Umgang mit Daten innerhalb eines Programms nachzudenken.

Mit zunehmender Größe und Komplexität von Programmen bestand jedoch auch ein wachsendes Bedürfnis, den Abstraktionsgrad nicht nur auf dem Papier (im Design) zu erhöhen, sondern dieselben Abstraktionen in die Programme selbst zu tragen: um es im Inneren zu ermöglichen, a Computerprogramm mit Typen, die reichhaltiger und abstrakter sind als nur die von einer Programmiersprache bereitgestellten Typen, wodurch dem Benutzer der Unterschied zwischen dem Konzept einer Datenstruktur und ihrer endgültigen Implementierung verborgen bleibt. Die zur Unterstützung dieser konzeptionellen Erweiterung der Typsystem einer Programmiersprache sind abstrakte Datentypen erwähnt.

Der Begriff abstrakter Datentyp kann (aber nicht sicher) auf eine Veröffentlichung im Mitteilungen des ACM von 1974 von Barbara Liskovy und John Zilles und auf einer Veröffentlichung 1977 von John Guttag.

Aufbau eines ADT

Um es ganz einfach auszudrücken, ein ADT ist eine konzeptionelle Datenstruktur, die in eine Programmiersprache implementiert und dann buchstäblich als Datenstruktur eingegeben wird Quellcode kann verwendet werden.

Das Konzept

Das Wesen eines ADT besteht darin, dass ein Programmierer mit der konzeptionellen Datenstruktur arbeiten kann und sich nicht mehr darum kümmern muss, wie diese Struktur intern funktioniert (da der ADT natürlich mit den in die Programmiersprache eingebauten Datenstrukturen implementiert werden muss). Um dies zu ermöglichen, besteht ein ADT aus einem ganzen "Paket" von Dingen, die dazu dienen, die Abstraktion für den Benutzer aufrechtzuerhalten. Eine davon ist natürlich die interne Implementierung der Datenstruktur, auf die der Benutzer eventuell eine Referenz erhält, um mit dem ADT zu arbeiten. Aber um die Abstraktion beizubehalten, enthält ein bestimmter ADT auch eine Sammlung een Funktionen und Verfahren die Operationen an einem (Instanz eines) ADT ausführen kann. Durch die Nutzung dieser Merkmale muss der Benutzer eines ADT nicht "in das ADT schauen", um mit ihm zu interagieren.

Beispiel: Der normale Weg, um a zu bekommen Stapel kann in den meisten Programmiersprachen mit a . implementiert werden Array. Mit einem ADT kann ein Stack auf diese Weise implementiert werden und dennoch für einen Benutzerprogrammierer mit Operationen wie . eine abstrakte Sache sein drücken, Puppe, oben und leer, ohne zu wissen, dass der Stack eigentlich ein Array ist.

Die damit erreichte Unterscheidung zwischen Konzept und Umsetzung hat eine Reihe von Vorteilen. Es wird nicht nur möglich, auf hohem Niveau über Programme und die Programmerstellung nachzudenken, sondern es wird einem Programmierer auch möglich, leicht mit einer von jemand anderem entwickelten Datenstruktur umzugehen, ohne Gefahr zu laufen, sein Programm zu beschädigen, weil der Programmierer die Daten missbraucht Struktur. Es wird auch möglich, die interne Implementierung des ADT (mäßig) zu modifizieren, um beispielsweise eine effizientere Struktur zu erhalten, ohne dass der Rest des Programms umfällt. Und in einer Programmiersprache, die die Aufteilung eines Programms in separate Module ermöglicht, wird es auch möglich, ADTs über mehrere Programme hinweg wiederzuverwenden, ohne den gleichen Code immer wieder schreiben zu müssen, was zumindest Fehler erspart.

Spezifikation eines ADT

Gegenüber der "Außenwelt" ist der wichtigste Teil eines ADT zweifellos die Spezifikation. Die Spezifikation definiert die Eigenschaften des ADT: den Namen des neuen "Typs", die darauf definierten Operationen, die Operation dieser Operationen und die Bedingungen für die korrekte Funktion der Operationen. Diese Spezifikation sagt Programmierern "außerhalb" des ADT, wie mit Instanzen des ADT umzugehen ist.

Für diejenigen, die das ADT implementieren, ist es wichtig, die Spezifikation auf einer abstrakten Ebene zu halten und nicht auf Details der Implementierung einzugehen. Bertrand Meyer gibt in seinem Objektorientierte Softwarekonstruktion ein Beispiel für die Anforderungen an die Ausarbeitung und Spezifikation eines ADT und weist darauf hin, dass eine gute Spezifikation eines ADT im Wesentlichen drei Bedingungen erfüllen muss:

• Die Spezifikation muss präzise und nicht mehrdeutig sein.
• Die Spezifikation muss in der Beschreibung der Wirkung von Operationen vollständig sein.
• Die Spezifikation darf nicht übervollständig in dem Sinne, dass die Spezifikation den ADT nicht an eine bestimmte Implementierung heften sollte.

Eine gute Spezifikation eines ADT besteht im Wesentlichen aus vier Teilen (obwohl diese Teile nicht immer separat dargestellt werden):

Der Typ

Der erste Teil einer Spezifikation sollte definieren, welche Art(en) Benutzern von einem ADT zur Verfügung gestellt werden.

Die Funktionen

Eine abstrakte Spezifikation der mit dem ADT verbundenen Funktionen. Diese Funktionen müssen so spezifiziert werden, dass ihre Wirkung offensichtlich ist, aber sie heften den ADT nicht an eine Implementierung. Eine Möglichkeit hierfür besteht darin, Funktionen mit Worten zu definieren, aber auch eine Spezifikation im Stil der Mathematik ist möglich. In diesem Fall kann es erforderlich sein, Teilfunktionen da es Fälle geben kann, in denen eine Funktion nicht auf einen ADT angewendet werden kann.

Die Funktion Neu Das vorherige Beispiel ist ein typisches Beispiel für eine Funktion, die einen ADT von einer Konstruktion in der reinen Mathematik unterscheidet: Es ist die Funktion, die eine neue Instanz eines Stack-ADT erstellt. In der Mathematik ist dies natürlich nicht notwendig, innerhalb eines Computerprogramms ist diese Funktion unverzichtbar: Eine solche Funktion ermöglicht nicht nur die korrekte Initialisierung einer neuen Instanz eines ADT, sondern ist auch notwendig, um eine neue erstellen zu können -Instanz, ohne das Innere eines ADT für den Benutzer sichtbar machen zu müssen.

Die Axiome

Da die Funktionen nicht so spezifiziert werden sollen, dass ihr Innenleben aus der Spezifikation ersichtlich ist, ist es oft notwendig, die Funktionen zu beschreiben, anstatt sie vollständig zu spezifizieren. Mittel Axiome Merkmale von Funktionen und Funktionskategorien können so erfasst werden, dass die Abstraktion eines ADT nicht unterbrochen wird.

Die Voraussetzungen

Wie bereits erwähnt, ist es manchmal notwendig, Teilfunktionen und keine Gesamtfunktionen auf einen ADT zu schreiben: In manchen Fällen kann eine Funktion einfach nicht auf eine bestimmte Instanz eines ADT angewendet werden. In diesen Fällen ist es notwendig aufzuzeichnen, wann eine bestimmte Funktion anwendbar ist und wann nicht. Dies geschieht mit den Vorbedingungen (siehe auch Hoarelogica).

Auch hier ist es wichtig, dass eine Spezifikation so verfasst ist, dass ein Anwender aus der Spezifikation genau entnehmen kann, was er mit einem ADT machen und wie er damit umgehen kann, aber keine Erwartungen an die Funktionsweise des ADT wecken kann intern. .

ADTs als Konzept und als Sprachkomponente

Das Konzept eines ADT wurde in erster Linie aus dem Wunsch entwickelt, Programmiersprachen (die normalerweise nur mit relativ einfachen, primitiven Datentypen ausgestattet sind) um Typen zu erweitern, die einen höheren Abstraktionsgrad aufweisen, als es in den Sprachen von . üblich war die 60er und 70er Jahre – also höher als das, was fast sofort auf dem Speichermodell des Mittelwerts abgebildet werden kann Computer.

Die Einführung des ADT als Konzept hat jedoch auch die Gestalt der Programmiersprachen beeinflusst. Verschiedene Programmiersprachen – darunter Turbo-Pascal und Oberon – wurden angepasst und um Einrichtungen zur Implementierung von ADTs erweitert. Turbo Pascal zum Beispiel wurde mit der Idee von a . erweitert Einheit, ein einzelnes Modul (oder eine Bibliothek), das Funktionen, Prozeduren, Variablen oder sogar ganze ADTs enthalten kann. Innerhalb einer solchen Einheit besteht die Möglichkeit, explizit zu trennen, was für den Benutzer der Einheit sichtbar sein soll und was nicht: die Schnittstelle für das Sichtbare und die Implementierung für das Unsichtbare. Ein Stack-ADT in einer solchen Unit könnte so aussehen:

UNIT StackADT;

INTERFACECONST capacity = 128;TYPE stack = array[0..capacity - 1] oder integer;

PROCEDURE push(var s : stack, num: integer);PROCEDURE pop(var s : stack);FUNCTION top(s : stack) : integer;FUNCTION empty(s : stack) : boolean;FUNCTION new():stack;

IMPLEMENTATIONCONSTempty_flag = -32768;

PROCEDURE push(var s : stack, num: integer);VARcounter : integer;BEGINcounter := capacity;while (s[counter - 1] = empty_flag) do counter := counter - 1;{s[counter] ist jetzt der erste freier Speicherplatz}s[Zähler] := numEND

VERFAHREN pop(var s : stack);VARcounter : integer;BEGINcounter := capacity - 1;while (s[counter] = empty_flag) do counter := counter - 1;{s[counter] ist jetzt der oberste}s[counter ] := empty_flagEND

FUNKTION top(s : stack) : integer;VARcounter : integer;BEGINcounter := capacity - 1;while (s[counter] = empty_flag) do counter := counter - 1;{s[counter] ist jetzt top}top : = s[Zähler]END

FUNKTION empty(s : stack) : boolean;BEGINempty := s[0] = empty_flagEND

FUNCTION new():stack;VARs : stack;counter : integer;BEGINcounter := 0;während Zähler < Kapazität dobegins[counter] := empty_flag;counter := counter 1endEND

Beachten Sie im vorherigen Beispiel, dass es der Spezifikation im vorherigen Kapitel nicht vollständig entspricht: Wir können in der vorherigen Implementierung nicht ewig Elemente hinzufügen, irgendwann ist der Stack voll. Eine Spezifikation dieses ADT sollte dies berücksichtigen. Außerdem missbraucht das Beispiel natürlich den Wert von empty_flag als Flag und ist daher eigentlich nicht geeignet, alle Elemente des Integer-Typs aufzunehmen. Das sollte auch angegeben werden.

ADTs als Sprungbrett

Obwohl die ADTs eine wichtige konzeptionelle Ergänzung zu den bestehenden Programmiersprachen waren, stellte sich bald heraus, dass sie bei ihrer Verwendung Nachteile mit sich brachten. Insbesondere der Nachteil, dass es sein kann möglich besteht darin, ein ADT ohne "Cheating" in der Implementierung zu verwenden, aber normalerweise ist es das nicht verboten ist zu betrügen. Außerdem stellte sich schnell heraus, dass es manchmal unpraktisch wurde, einen ADT über ein größeres Programm zu bedienen und damit die richtigen Funktionen einzubringen. Dies beinhaltete Probleme im Zusammenhang mit der Übergabe von ADTs (wenn ein ADT aus mehreren Variablen besteht, wie hält man sie zusammen, wenn ein ADT als Parameter übergeben wird?) und Namenskonflikten (wenn Sie mehrere Module in das Programm eingeben, ist es möglich, dass zwei Module verwenden der gleiche Name für eine Funktion).

Je mehr Menschen mit ADTs und damit mit immer größeren, konzeptionellen Blöcken arbeiteten, wurde zudem immer wünschenswerter, noch mehr Eigenschaften solcher Blöcke einzuführen und als unterstützende Mechanismen in Programmiersprachen zu verarbeiten. Zum Beispiel die Möglichkeit, ein bestimmtes ADT zu erweitern, ohne die vorhandene Implementierung aufbrechen zu müssen. Oder um Teile eines ADT wiederzuverwenden und andere Teile zu modifizieren.

Im 1967 die erste Version von erschien Simula, eine Programmiersprache zum Schreiben von Simulationen. Diese Sprache schlug einen ganz anderen Weg ein als frühere Sprachen und machte das ADT zum zentralen Mechanismus in der Sprache. Anstatt eine Erweiterung des Typsystems zu sein, wurde das ADT zum Weg, das Programm zu schreiben: Das Typsystem wurde erweitert, um das gesamte Programm einzuschließen. Die Trennung zwischen Daten und Funktionen war weg, die Funktionen und Daten wurden in einem nicht mehr auseinanderziehbaren Paket zusammengepackt. Solche Pakete könnten gleichzeitig erweitert und modifiziert werden. Die Idee fand Anklang, zunächst in akademischen Einrichtungen und etwa fünfzehn Jahre später kommerziell. Zu den komprimierten Daten und Funktionen wurden immer mehr Features hinzugefügt und so wurde das ADT durch Simula zum Sprungbrett für die Klasse, es Objekt und der Objekt orientierte Programmierung.

Quellen

• Objektorientierte Softwarekonstruktion 2. Auflage
  Bertrand Meyer
  Prentice Hall PTR, 1997
  ISBN 0-13629155-4
• Programmierteil 2: Algorithmen entwerfen
  Anne Kaldewaij
  Bohn Stafleu van Loghum 1992
  ISBN 90-313-1352-1
• Programmierteil 3: Datenstrukturen und Standardalgorithmen
  Anne Kaldewaij
  Bohn Stafleu van Loghum 1993
  ISBN 90-313-1584-2
• Lernen Sie noch heute Programmieren mit Turbo Pascal
  Borland Visions-Serie
  John Wiley & Söhne, 1991