11Abstrakte Datentypen

Abstrakte Datentypen wurden bereits im Abschnitt 2.3 kurz eingeführt. Ein abstrakter Datentyp fasst die wesentlichen Eigenschaften und Operationen einer Datenstruktur zusammen, ohne auf deren tatsächliche Realisierung im Rechner einzugehen. Hier soll dieser Stoff nun rekapituliert und vertieft werden.

Geheimnisprinzip oder programming by contract

Um Programme möglichst wiederverwendbar zu gestalten und von unnötigen Details zu abstrahieren, sollte man Datenstrukturen unabhängig von ihrer späteren Implementierung in einer konkreten Programmiersprache spezifizieren. Diese Beschreibung ist so zu gestalten, dass Programmierer sich dieser Datenstrukturen bedienen können, um Probleme zu lösen, dass aber die Implementierung jederzeit geändert werden kann, ohne dass die Anwender der Datenstruktur etwas davon merken. Diese Eigenschaft wird auch als Geheimnisprinzip oder programming by contract bezeichnet.

Die Motivation hinter der Spezifikation abstrakter Datentypen lässt sich somit kurz gefasst wie folgt formulieren:

Im Folgenden werden wir das Kürzel ADT für derartig spezifizierte abstrakte Datentypen benutzen.

Ein ADT kann das Verständnis eines in einer Programmiersprache fest integrierten Datentyps verdeutlichen, indem die wesentlichen Eigenschaften knapp und eindeutig festgelegt werden. Interessant ist der Einsatz von ADTs für neu entwickelte Datentypen, die zum Beispiel Teil einer neu realisierten Bibliothek von Funktionen werden. Bei neu entwickelten Datentypen muss man daher jeweils die folgenden beiden Aspekte unterscheiden:

Konkrete vs. abstrakte Datentypen

• Konkrete Datentypen werden aus Basisdatentypen bzw. Java-Klassen konstruiert und sind somit direkt in einer Implementierung einsetzbar.
• Abstrakte Datentypen bilden nur eine Spezifikation der Schnittstelle nach außen, indem sie Operationen und ihre Funktionalität festlegen. Sie sind nicht direkt in ein Programm einbindbar.

Es kann mehrere konkrete Datentypen zu ein und demselben abstrakten Datentyp geben.

In der Softwaretechnik entsprechen Realisierungen von ADTs Softwaremodulen. Derartige Softwaremodule beachten die folgenden Prinzipien:

Kapselung

• Kapselung: Ein ADT-Modul darf nur über seine Schnittstelle benutzt werden.

Geheimnisprinzip

• Geheimnisprinzip: Die interne Realisierung eines ADT-Moduls ist verborgen.

Solche Softwaremodule haben Eigenschaften analog zu Klassen in objektorientierten Programmiersprachen, und somit sind ADTs gewissermaßen Grundlage des Prinzips der objektorientierten Programmierung. Allerdings werden wir sehen, dass ADTs eine einfachere Modellbildung als objektorientierte Programmiersprachen haben und die beiden Konzepte nicht einfach gleichgesetzt werden sollten.

Wir gehen in diesem Kapitel wie folgt vor: Wir beginnen mit der Konkretisierung des Begriffs der Schnittstelle eines ADT und des Modellbegriffs für ADTs, indem das Modell eines ADT eine Algebra bildet. Als Beispiel für die Spezifikation von ADTs betrachten wir die algebraische Spezifikation mittels Gleichungen. In dem darauf folgenden Abschnitt werden wir einige nichttriviale Beispiele für (parametrisierte) ADTs betrachten, um ein Gefühl für das Arbeiten mit der algebraischen Spezifikation zu bekommen. Der letzte Abschnitt ist dann der Umsetzung von ADTs in Programmiersprachen, insbesondere natürlich in Java, gewidmet.

11.1Signaturen und Algebren

Ziel dieses Abschnittes ist es, einige bereits in Abschnitt 2.3 eingeführte Begriffe mathematisch exakt zu konkretisieren, um die Grundlage einer formalen Semantik geben zu können. Eine Signatur ist dabei die formale Schnittstelle eines ADT. Das mathematische Konzept der (mehrsortigen) Algebra dient als Modellbildung für die durch Signaturen charakterisierten ADTs. Für eine gegebene Signatur gibt es natürlich viele Algebren als mögliche Modelle, so dass die Spezifikation der Operationen dort eine Einschränkung vornehmen muss.

Die Spezifikation erfolgt durch logische Axiome, also Formeln, die bestimmte Modelle ausschließen. Ein derart deklarativer Zugang erzwingt bei der Spezifikation die Unabhängigkeit von einer operationalen Implementierung.

Eine ADT-Spezifikation besteht nun aus einer Signatur und Axiomen. Auch hier gilt Folgendes: Für eine gegebene Spezifikation gibt es in der Regel ebenfalls mehrere (noch zu viele) Algebren als mögliche Modelle! Daher ist die Auswahl einer Algebra als Standardmodell notwendig. Im Folgenden wird dies anhand der Gleichungsspezifikation (Spezialfall der algebraischen Spezifikation) kurz erläutert. Der theoretische methodische Rahmen der algebraischen Spezifikation ist allerdings derart anspruchsvoll, dass wir die Themen hier nur anreißen können und auf vertiefende Literatur und weiter gehende Vorlesungen verweisen müssen.

Definition 11.1 Signatur

Eine Signatur Σ ist definiert als

Σ = (S, Ω)

wobei Folgendes gilt:

• S ist eine Menge von Sorten.
• Ω = {f_S*, S} definiert die Funktionssymbole für Funktionen f: s₁ × … × s_n → s mit Parametersorten s₁, …, s_n und Ergebnissorte s.

  Funktionen ohne Parameter heißen Konstanten.

In ADT-Spezifikationen ist in der Regel eine Sorte als neu zu definierende Sorte ausgezeichnet, während die anderen importiert werden.

Basierend auf der Definition einer Signatur sind wir nun in der Lage, auch das Konzept der Algebra zu definieren.

Definition 11.2 Algebra zu einer Signatur

Eine Algebra A_Σ zu einer Signatur Σ ist definiert als

A_Σ = (A_S, A_Ω)

wobei Folgendes gilt:

• A_S sind die Trägermengen der Sorten in S.
• A_Ω = {A_f : A_s1 × … × A_sn → A_s} sind Funktionen auf diesen Trägermengen.

Eine Algebra heißt partiell definiert, wenn mindestens eine der Funktionen eine partielle Funktion ist.

Parametrisierte Signaturen

Für die Spezifikation von Container-Typen wie »Liste« oder »Menge« benötigen wir parametrisierte Signaturen, bei denen eine oder mehrere der Sorten durch eine Sortenvariable ersetzt sind. Da die Übertragung von Sortenparametern auf Algebren als Modelle nicht trivial ist, gehen wir davon aus, dass Algebren in diesen Fällen nur definiert sind, wenn der formale Sortenparameter durch eine konkrete Sorte ersetzt wurde (etwa »Liste von ganzen Zahlen«).

11.2Algebraische Spezifikation

Gleichungsspezifikation

Als Beispiel für einen Formalismus für die Spezifikation von ADTs betrachten wir in diesem Abschnitt die Gleichungsspezifikation, bei der als Axiome ausschließlich Gleichungen zwischen über der Signatur gebildeten Termen auftreten.

Eine Spezifikation eines ADT besteht hierbei aus den folgenden Bestandteilen:

• Die Angabe der Signatur legt die Namen der Typen sowie die Funktionssignaturen fest.
• Gleichungen dienen als Axiome zur Einschränkung möglicher Algebren als Modelle.
• Zusätzlich erfolgt eventuell ein Import anderer Spezifikationen.

Algebraische Spezifikation der natürlichen Zahlen

Ein typisches Beispiel für eine derartige Spezifikation zeigt die folgende Spezifikation der natürlichen Zahlen:

Konstruktor

Es gibt eine Sorte Nat für die natürlichen Zahlen. Die Konstante 0 ergibt einen Wert des ADT; die beiden Funktionen suc für Successor (die Nachfolgerfunktion »+1«) und add für die Addition erzeugen die weiteren Werte. Die Successorfunktion spielt hierbei die Rolle eines Konstruktors : Alle Werte 1, 2, 3, 4, … werden durch Anwendung von suc aus der 0 konstruiert. Die Addition wird mit Gleichungen (die uns aus der Definition funktionaler Algorithmen vertraut sein sollten) auf diese konstruierten Werte zurückgeführt.

Der Leser hat sicher eine genaue Vorstellung davon, wie eine Algebra aussehen könnte, die zu dieser Spezifikation passt – eben die Algebra der natürlichen Zahlen N mit Operatoren »+1« und »+«. Ist dies aber die einzige Algebra, für die diese Spezifikation in Frage kommt? Wir werden im folgenden Abschnitt sehen, dass dies leider nicht der Fall ist und wir somit uns einen Mechanismus für die Festlegung einer »Standardalgebra« für eine gegebene ADT-Spezifikation überlegen müssen.

11.2.1Spezifikationen und Modelle

Algebra der Wahrheitswerte

Sei nun eine Spezifikation gegeben – wie sieht dann die Klasse der Modelle aus, die zu dieser Spezifikation passt? Wir beginnen mit der Diskussion einer möglichst einfachen Algebra, nämlich der Algebra der Wahrheitswerte:

Der Einfachheit halber haben wir keinerlei Operatoren angegeben, nur die Signatur (das ist ein Spezialfall, den wir natürlich immer berücksichtigen müssen). Wie könnten nun Modelle für diese Spezifikation aussehen? Wir betrachten einige Varianten:

1. Die »gewünschte« Algebra ist natürlich tatsächlich die zweielementige Algebra der Wahrheitswerte:

   A_Bool = {T, F}; A_true := T; A_false := F

2. In einigen Programmiersprachen werden Wahrheitswerte über den ganzen oder natürlichen Zahlen realisiert, so dass zum Beispiel die folgende Algebra zugrunde liegen könnte:

   A_Bool = ; A_true := 1; A_false := 0

   Diese Realisierung ist eventuell akzeptabel, aber die Trägermenge ist eigentlich zu groß – sie enthält Elemente, die weder benötigt werden noch das Ergebnis irgendeines Terms über der Signatur sein können.

3. Zu der Signatur würde auch die folgende Algebra passen, die nur ein einzelnes Element besitzt:

   A_Bool = {1}; A_true := 1; A_false := 1

   Diese Algebra ist sicherlich als Modell nicht erwünscht!

Eine Algebra kann also »zu viele« Werte enthalten, also Werte, die überhaupt nicht durch Berechnungen mittels der Operationen konstruierbar sind, bzw. »zu wenige« Werte unterscheiden, also bei einer Spezifikation der natürlichen Zahlen etwa die Zahlen 3 und 4 gleichsetzen. Andererseits sollen die Axiome natürlich gewisse Werte gleichsetzen – beispielsweise die berechneten Werte 3 + 4 und 4 + 3!

Standardalgebra für Axiomenmenge

Für uns ergibt sich somit die folgende Fragestellung: Wie komme ich zu einem »kanonischen« Standardmodell (also genau einer Algebra, die die Axiome respektiert) für eine gegebene Spezifikation? Diese Algebra sollte dabei weder zu wenige noch zu viele Elemente in ihren Trägermengen enthalten. Im Englischen wird dieses Ziel übrigens knapp mit »no confusion, no junk« charakterisiert.

Wir gehen dazu in zwei Schritten vor: In einem ersten Schritt konstruieren wir eine Algebra, die keine unnützen, also keine nicht durch Funktionsberechnung konstruierbaren Werte enthält. Im zweiten Schritt setzen wir dann die Werte gleich, die mittels der Gleichungen als gleich charakterisiert werden (und nicht mehr!).

11.2.2Termalgebra und Quotiententermalgebra

Unser Ziel ist nun die Konstruktion genau einer ausgewählten Algebra für eine Spezifikation. Hierzu betrachten wir erneut unsere Nat-Algebra, um mögliche Modelle zu charakterisieren.

Eine (etwas ungewöhnliche) Algebra, die zu dieser Spezifikation passt, ist die Termalgebra.

Definition 11.3 Termalgebra

Die Termalgebra zu einer gegebenen Spezifikation ist definiert durch

• die Trägermenge, bestehend aus allen korrekt gebildeten Termen der Signatur,
• und der Funktionsanwendung als Konstruktion des zugehörigen Terms.

Die Hauptidee ist somit, dass Terme nicht interpretiert, also nicht ausgerechnet werden. Werte der Trägermenge sind quasi die Zeichenketten, die diesen Term beschreiben. In der Termalgebra ist kraft Definition kein »junk« enthalten, also kein Wert, der nicht mit einer Berechnung konstruierbar ist – unser erstes Ziel haben wir also bereits erreicht.

Die Termalgebra setzt keinerlei Terme gleich, ignoriert also die Gleichungen völlig. Die Gleichungen werden mit einem zweiten Schritt berücksichtigt, nämlich mit der Konstruktion der sogenannten Quotiententermalgebra, kurz QTA.

Definition 11.4 Quotiententermalgebra

Die Quotiententermalgebra QTA ist wie folgt definiert:

• Die Trägermenge besteht aus den Äquivalenzklassen auf den Termen gemäß der durch die Axiome induzierten Gleichheit »=«.
• Die Operationen auf den Äquivalenzklassen nehmen jeweils Repräsentanten der Äquivalenzklassen und haben als Ergebnis die Äquivalenzklasse des Ergebnisterms über den Repräsentanten.

Diese Definition ist zugegebenermaßen nicht vollständig, weil einige der verwendeten Begriffe (»durch »=« induzierte Äquivalenzklasse«) nicht genauer ausgeführt wurden. Die folgenden Betrachtungen sollen dieses etwas verdeutlichen.

Die Konstruktion der QTA startet mit der bereits bekannten Termalgebra. Können nun zwei Terme durch die Datentyp-Gleichungen gleichgesetzt werden, kommen diese in dieselbe Äquivalenzklasse. Praktisch startet man also mit einer Äquivalenzklasse pro Term und verschmilzt zwei Klassen sobald sie zwei gleichgesetzte Terme enthalten. Dieser Prozess wird so lange durchgeführt, bis keine Klassen mehr verschmolzen werden können. Natürlich ist das nur ein Gedankenmodell, da jede nichttriviale Signatur eine Termalgebra mit einer unendlichen Trägermenge konstruiert – aber für das Verständnis des Prozesses ist dieses Gedankenmodell trotzdem hilfreich.

Konstruktorfunktionen

Die derartig konstruierten Äquivalenzklassen bilden die Werte der Trägermengen der Sorten des ADT. Da Äquivalenzklassen als Wertebereiche etwas unhandlich sind, werden methodisch oft Konstruktorfunktionen eingesetzt, die jeweils genau einen Repräsentanten pro Äquivalenzklasse konstruieren. Am Beispiel Nat erhalten wir dabei mit den Konstruktorfunktionen 0 und suc die folgende Situation:

Der Einsatz von Konstruktorfunktionen erzwingt eine gewisse Sorgfalt bei der Spezifikation: Verschieden konstruierte Werte sollten nicht gleichgesetzt werden und andere Operationen müssen mittels Gleichungen immer auf konstruierte Repräsentanten zurückführbar sein.

Äquivalente Algebren

An dieser Stelle ist ein kurzer Exkurs in die theoretischen Grundlagen angebracht, der allerdings die Probleme nur anreißen kann. In der Theorie ist man nicht an der konkret konstruierten Algebra interessiert, sondern betrachtet äquivalente Algebren. Algebren sind dann äquivalent, wenn eine Bijektivität betreffend einer strukturerhaltenden Abbildung, eines sogenannten Morphismus, zwischen ihnen existiert. Bijektivität erzwingt im Wesentlichen, dass man die Algebren durch eine eindeutige Umbenennung der Elemente der Trägermengen ineinander überführen kann und die Operationen auf beiden (nach Umbenennung der Werte) den gleichen Effekt haben. In diesem Sinne ist die Quotiententermalgebra zu Nat äquivalent zu den natürlichen Zahlen N mit den Operationen 0, +1 und +.

Initiale Semantik

Die QTA erfüllt das Prinzip der maximalen Ungleichheit – zwei Elemente sind ungleich, sofern nicht ihre Gleichheit mittels der Axiome bewiesen werden kann. Dieses Prinzip nennt man auch Initialität, da die QTA folgendes Prinzip erfüllt: Jede die Gleichungen erfüllbare Algebra ist Abbild einer totalen Abbildung der QTA (genauer eines Morphismus, d.h., die Gültigkeit der Funktionsanwendungen bleibt erhalten). Die initiale Semantik einer Spezifikation definiert die Klasse aller initialen Algebren (diese sind im obigen Sinne zueinander äquivalent) als Bedeutung einer Spezifikation. Diese Art der Semantikfestlegung ist nicht ganz unproblematisch, wie wir noch sehen werden.

Terminalität

Als Bemerkung erwähnen wir, dass die Terminalität als duales Prinzip auch zur Semantikfestlegung genutzt wird. Terminalität fordert die maximale Gleichheit: Zwei Elemente sind genau dann ungleich, wenn ihre Ungleichheit bewiesen werden kann. Man sieht sofort, dass allein mit Gleichungen Terminalität kein sinnvolles Prinzip ist, da man mit Gleichungen alleine keine Ungleichheit beweisen kann – entweder muss man explizite Ungleichungen zusätzlich benutzen oder man fordert die Bewahrung der Ungleichheit der aus anderen Datentypen übernommenen Werte (wird oft für Spezifikation mit true ≠ false eingesetzt).

11.2.3Probleme mit initialer Semantik

Initiale Semantik nicht immer angemessen

Die initiale Semantik ist eine elegante und einfache Semantik und führt beim Beispiel der natürlichen Zahlen direkt zum gewünschten Ergebnis. Allerdings ist sie nicht immer angemessen, wie das Mengen-Beispiel zeigt. Spezifiziert wird eine Menge von Elementen, wobei Item ein Sortenparameter ist.

Diese Spezifikation beschreibt tatsächlich das aus der Mathematik bekannte Konzept der endlichen, duplikatfreien Menge. Folgendes gilt aufgrund der bekannten Mengensemantik:

Man kann sich leicht klar machen, dass dies auch in der Beispielspezifikation gilt, auch wenn diese Gleichungen nicht explizit angegeben sind. Eine Menge kann man nur mit is_empty und is_in »beobachten«, und deren Gleichungen respektieren diese Regeln, wie man leicht erkennen kann.

Diese Regeln können aber nicht mit den Gleichungen bewiesen werden – daher sind zum Beispiel insert(insert(s,i),i) und insert(s,i) unterschiedliche Elemente in der QTA! Die initiale Semantik definiert also unnötig viele verschiedene Elemente.

Dieses Problem kann zum Beispiel mit dem Einsatz der terminalen Semantik behoben werden (Maximierung der Gleichheit), erfordert aber zumindest die Ungleichheit true ≠ false, da sonst eine entartete Algebra mit nur einem einzigen Wert resultiert.

11.3Beispiele für abstrakte Datentypen

Nach der Diskussion der theoretischen Grundlagen ist es nun Zeit, die Konzepte von abstrakten Datentypen anhand einiger Beispiele zu vertiefen. Wir werden diese Vertiefung dazu nutzen, gleichzeitig auch eine mögliche Operationalisierung von ADT-Spezifikationen zu diskutieren. Ein weiterer Schwerpunkt ist die modulare Konstruktion von ADTs auf der Basis einfacherer Datenstrukturen.

Spezifikation von Listen

Wir beginnen mit der Spezifikation von Listen von Elementen aus einem nicht näher spezifizierten Datentyp T. T übernimmt hierbei also die Rolle eines Sortenparameters.

Eine nichtleere Liste besteht aus dem ersten Element (head) und dem jeweiligen Rest der Liste (tail). Die leere Liste wird als [] notiert. Die Notation _ : _ ist eine spezielle Schreibweise für die Definition von Infix-Operatoren (wie + in arithmetischen Ausdrücken), hier wird damit der Konstruktor für Listen definiert. Zusätzlich haben wir eine Funktion length zur Bestimmung der Länge einer Liste; für diese Operation müssen wir den Datentyp Nat importieren. Mittels des Schlüsselworts import werden bereits definierte Datentypen importiert.

Mögliche Werte für Listen über Zahlen sind nun:

Hierbei wurden die runden Klammern zur Verdeutlichung gesetzt. Die vier Listen haben der Reihe nach die Längen 0, 1, 3 und 2; head der dritten Liste ist 5.

Nach dieser Einführung werden wir mit dem Kellerspeicher und der Warteschlange zwei typische (parametrisierte) Datentypen spezifizieren und deren Realisierung über Listen diskutieren.

11.3.1Der Kellerspeicher (Stack)

LIFO-Prinzip

Eine der einfachsten Datenstrukturen mit einem beschränkten Zugriff auf gespeicherte Elemente ist der Kellerspeicher oder englisch Stack. Ein Stack verwirklicht das sogenannte LIFO-Prinzip (LIFO für Last-In-First-Out-Speicher): Beim Auslesen eines Elementes wird das jeweils zuletzt gespeicherte Element zuerst ausgelesen, danach das vorletzte etc. Der Kellerspeicher wird daher auch als Stapel bezeichnet: Elemente werden sozusagen übereinander gestapelt und dann wieder in umgekehrter Reihenfolge vom Stapel genommen.

ADT Stack

Eine ADT-Spezifikation eines Stacks könnte nun wie folgt lauten:

Die Operation push packt ein Element des Parametertyps T auf den Stapel, pop entfernt das oberste Element. Mittels top kann man sich das oberste Element anschauen (ohne es zu entfernen). All diese Operationen sind als Funktionen mit einem (ersten) Parameter vom Typ Stack (genauer natürlich Stack(T)!) als Eingabe definiert. empty erzeugt einen leeren neuen Stapel, is_empty testet auf leeren Stack.

Die beiden ersten Gleichungen definieren nun die Stapeleigenschaft. push und empty sind die Konstruktorfunktionen von Stack – die anderen drei Operatoren werden auf diese durch die vier Gleichungen zurückgeführt. Wir können daher bei der Definition von pop und top davon ausgehen, dass der Parameterwert vom Typ stack entweder empty ist oder die Form push(s,x) hat. In der Form push(s,x) ist x der zuletzt gespeicherte Wert – dieser wird bei top(push(s,x)) als Ergebnis zurückgeliefert und damit die LIFO-Eigenschaft erreicht.

Abb. 11–1 Verdeutlichung des Stack-Prinzips

Abbildung 11–1 verdeutlicht das Prinzip eines Kellerspeichers. Mit push werden Werte auf den Keller gelegt, mittels pop heruntergenommen und nur top erlaubt den lesenden Zugriff (auf das jeweils oberste Element).

Anhand des Stack-Beispiels wollen wir nun einige Aspekte von ADTs diskutieren, die uns später bei der Nutzung von Datenstrukturen intensiver begegnen werden. Es ist üblich, eine neue Datenstruktur nicht von Grund auf neu zu programmieren, sondern existierende, oft einfachere Datenstrukturen zu nutzen. Ein neuer Datentyp wird dabei über einem anderen Datentyp implementiert, so dass sich Implementierungshierarchien aufeinander aufbauender Datentypen entwickeln. Wir werden dies in diesem Abschnitt abstrakt anhand des Keller-Beispiels vorstellen, später werden wir weitere Beispiele mit realen Programmen kennen lernen.

Keller implementiert über Liste

Abstrakt können wir den Stack über der bereits realisierten Liste durch folgende Gleichsetzungen implementieren:

Die letzten beiden Gleichsetzungen ließen sich mit den aus den applikativen Algorithmen bekannten bedingten Termen zu einer Zeile zusammenfassen.

Fehlersituationen

In der vorliegenden Spezifikation haben wir das Eintreten von Fehlersituationen bisher nicht betrachtet. Die Anwendung von pop(empty) oder top(empty) führt zu einem Fehler, da der Effekt nicht auf die Konstruktoren bzw. auf einen gültigen Wert zurückführbar ist. Die Operationen top und pop sind also partielle Funktionen. In unserer vereinfachten Darstellung lassen wir die Behandlung dieser Effekte weg; ein tatsächlich eingesetzter Formalismus für die Beschreibung von ADTs muss natürlich auch Sprachmittel zur Behandlung von derartigen Fehlersituationen und resultierenden partiellen Funktionen bereitstellen. In Java werden wir als Lösungsvorschlag bei der Realisierung von Datentypen hierfür das Konzept der Ausnahmebehandlung nutzen.

11.3.2Beispiel für Kellernutzung

Bereits auf der Ebene abstrakter Spezifikationen kann man die spezifizierten Datentypen anwenden. Wir präsentieren ein einfaches Beispiel für den Einsatz von Kellerspeichern: die Analyse und Auswertung von arithmetischen Ausdrücken. Ähnliche Techniken werden tatsächlich in Taschenrechnern und Programmiersprachen-Interpretern eingesetzt, so dass es sich hierbei um ein tatsächlich relevantes Problem und nicht um eine künstliche Spielzeugproblemstellung handelt.

Für die Auswertung einfacher, vollständig geklammerter arithmetischer Ausdrücke müssen wir die analysierte Sprache in BNF festlegen:

Der nicht weiter verfeinerte Bereich Int definiert eingegebene ganze Zahlen. Die Terminalsymbole sind nicht hervorgehoben und umfassen neben den Zahlen die drei Symbole =+* sowie die Klammern. Ein Beispiel für einen korrekten Ausdruck könnte nun wie folgt lauten:

Ziel ist es nun, derartig geklammerte und damit beliebig tief geschachtelte arithmetische Ausdrücke auszuwerten. Aufgrund der Schachtelung werden dabei noch nicht auswertbare Teilausdrücke im Keller zwischengespeichert.

Als vereinfachte Notation kürzen wir mit z₁..z_nS = push(…(push(S, z_n), …z₁) einen Keller mit auf ihm gespeicherten Elementen ab, das zuletzt gespeicherte Element steht also jeweils vorne. Mit x + y wird der Wert der Addition berechnet, Analoges gilt für die anderen Operationen. Diese Notation wird auch genutzt, um aus einer eingelesenen Zahl x den intern verarbeitbaren Wert x zu berechnen.

Auswertung von Termen mittels Stack

Die Arbeitsweise unseres Interpreters wird durch die folgenden Bearbeitungsregeln festgelegt, die die Auswertung einer Funktion value angewendet auf einen Term t definieren:

In der Zeile (11.9) wurde ein anderer Zeichensatz für x genutzt, um zu verdeutlichen, dass es sich um eine zu interpretierende Eingabe handelt, die von gespeicherten Werten (»x«) zu unterscheiden ist.

Die eigentliche Auswertung erfolgt durch die Funktion eval für »Evaluieren«, die einen Stack als Zwischenspeicher benutzt. Initial wird diese Funktion mit dem Eingabeterm und dem leeren Stack aufgerufen. Die angegebenen Regeln sind formal nicht ganz korrekt: Eigentlich darf jeweils nur genau ein Element pro Schritt vom Keller mit pop genommen bzw. mit top gelesen werden. Allerdings ist eine Umformung in die korrekte Form natürlich möglich, würde das Beispiel aber unnötig aufblähen. Als Konvention werden die Regeln jeweils von oben nach unten durchsucht, bis eine passende linke Seite gefunden wird, und diese Regel dann ausgeführt. Das Regelwerk arbeitet insofern also ähnlich einem Markov-Algorithmus.

Zur Verdeutlichung des Prinzips zeigt Abbildung 11–2 die Auswertung für den Eingabeterm »((3+(4*5))*(6+7))=«. Für den leeren Stack und gleichzeitig für den »Boden« des Stapels verwenden wir das Symbol ].

Abb. 11–2 Auswertung eines arithmetischen Terms mit einem Stack

Die in Abbildung 11–2 gezeigte Abarbeitungsfolge wird mittels der ersten Regel 11.1 gestartet. Nach Abarbeitung dieser »Zwischenzustände« (genauer eigentlich Parameter in einer rekursiven Aufrufkette) wird mit Regel 11.8 der Wert 299 als Ergebnis ausgegeben.

Keller: Komplexeres Beispiel

Das bisherige Beispiel zeigt schon einige wesentliche Aspekte der Nutzung von Kellerspeichern zur Auswertung von geschachtelten Termen. Derartige Verfahren werden in der Analyse von Programmiersprachen oder auch direkt in Taschenrechnern verwendet. Hier werden allerdings verfeinerte Verfahren genutzt, die es etwa vermeiden, auf den Keller sowohl Zahlenwerte als auch Symbole abzulegen, um den Keller mit üblichen Datentypen einfach realisieren zu können.

Ein derartig erweiterter Terminterpreter könnte etwa die folgende Sprache verarbeiten:

Es handelt sich somit nun um arithmetische Ausdrücke ohne vollständige Klammerung, so dass der Interpreter die unterschiedlichen Prioritäten der Operatoren berücksichtigen muss. Als Lösungsansatz benutzen wir zwei Stacks, einen für die Operatoren, den zweiten für die Operanden.

Wir geben wieder Auswertungsregeln an, die nunmehr zwei Stacks als Parameter nutzen, um den Term rekursiv mittels der Funktion eval auszuwerten. Die Regeln lauten wie folgt:

Die Regeln werden wie im vorigen Beispiel jeweils von oben nach unten auf Anwendbarkeit überprüft. Dies ist notwendig, da etwa Regel 11.13 und 11.14 sonst im Konflikt stehen könnten. Die Priorität der Operatoren wird dadurch gewährleistet, dass für + und * nun unterschiedliche Regeln angegeben wurden – Regel 11.13 sorgt dafür, dass beim Lesen eines Pluszeichens erst einmal alle aktuell offenen Multiplikationen ausgerechnet werden. Als Beispiel für eine Auswertung betrachten wir den Term »(3+4*5)*(6+7)=«. Die Auswertung dieses Terms ist in Abbildung 11–3 skizziert.

Abb. 11–3 Auswertung eines arithmetischen Terms mit zwei Kellern

In den folgenden Abschnitten werden wir weitere Einsatzmöglichkeiten für das Kellerprinzip kennen lernen. Allgemein lässt sich sagen, dass Kellerstrukturen für die Verarbeitung geschachtelter Strukturen benötigt werden, um die korrekte Klammerung analysieren zu können. Kellerspeicher werden ebenfalls intern in ausführbaren Programmen eingesetzt, um rekursive Funktionen verarbeiten zu können – dazu werden wir aber später noch kommen, wenn es im Kapitel 13 um Implementierungsvarianten und weitere Nutzung von Stacks gehen wird.

11.3.3Die Warteschlange (Queue)

FIFO-Prinzip

Um die Prinzipien der Spezifikation von parametrisierten Datenstrukturen zu vertiefen, betrachten wir kurz eine weitere Datenstruktur, nämlich die Warteschlange oder englisch Queue. Eine Queue realisiert das sogenannte FIFO-Prinzip, also einen First-In-First-Out-Speicher. Das FIFO-Prinzip modelliert eine Warteschlange, bei der man sich hinten anstellt: »Wer zuerst kommt, mahlt zuerst«.

Spezifikation einer Queue

Die Spezifikation einer Queue sieht auf den ersten Blick sehr ähnlich zu der eines Stacks aus, obwohl das Verarbeitungsprinzip komplett entgegengesetzt ist:

Im Unterschied zum Stack kann jetzt bei leave und bei front nicht der jeweilig letzte gespeicherte Parameter bearbeitet werden. Stattdessen ist es nötig, durch rekursiv aufgebaute Gleichungen sich bis zum jeweils »innersten« Wert des Queue-Terms vorzuarbeiten.

Abbildung 11–4 verdeutlicht das Prinzip einer Queue. Mit enter werden Werte der Warteschlange hinzugefügt, mittels leave wird das am längsten gespeicherte Element herausgenommen und nur front erlaubt den lesenden Zugriff (auf das jeweils am längsten gespeicherte Element).

Abb. 11–4 Verdeutlichung des Queue-Prinzips

Auch Warteschlangen lassen sich auf dem vorgestellten Datentyp der Listen implementieren. Da wir uns in Kapitel 13 noch ausführlicher mit der Realisierung von Warteschlangen befassen werden, verzichten wir hier auf die Angabe einer geeigneten Umsetzung.

Einsatz von Warteschlangen

Warteschlangen werden ebenfalls in vielfältiger Weise in Softwaresystemen eingesetzt, da sie das Abarbeiten von Aufträgen in Eingangsreihenfolge realisieren können: so etwa zur Prozessverwaltung in Betriebssystemen, zur Speicherverwaltung, für Warteschlangen bei Druckaufträgen, für Nachrichtenpuffer in der Kommunikationssoftware etc.

11.4Entwurf von Datentypen

Wir haben bisher in diesem Kapitel einige einfache Beispiele für abstrakte Datentypen kennen gelernt und deren Spezifikationen mit Gleichungen angegeben. Wenn man selbst nun einen derartigen ADT spezifizieren möchte, wird man dann allerdings mit einigen Fragen konfrontiert:

• Wie komme ich zu den Gleichungen?
• Wann habe ich genug Gleichungen?
• Wann fehlt mir ein Axiom?

Leider sind hier, wie auch beim Algorithmenentwurf, keine einfachen Antworten zu erwarten. Ganze Bücher widmen sich diesen Fragestellungen, ohne dass am Ende ein einfaches »Kochrezept« zum Finden der optimalen Axiomenmenge steht.

Systematischer Entwurf von ADTs

Statt einer tieferen Diskussion des Entwurfs geben wir einige Hinweise auf eine systematische Vorgehensweise, mit der man gerade einfache Datentypen gut spezifizieren kann. Hier empfiehlt sich folgende Vorgehensweise, die wir anhand des Stack- und des Set-Beispiels erläutern:

Konstruktoren

1. Die Festlegung der Konstruktorfunktionen legt den Bereich der Basisterme fest, die den später implementierten Werten entsprechen, und sollte daher mit besonderer Sorgfalt erfolgen.
   Im Stack-Beispiel benötigt man einen Konstruktor für den leeren Stack und die push-Operation, um alle zu realisierenden Stack-Werte zu definieren.
2. Eventuell ist es nötig, auch Axiome zur Gleichsetzung von Konstruktortermen einzuführen. Der Set-Datentyp ist ein gutes Beispiel hierfür.

Selektoren

1. 3.Die Definition geeigneter Selektorfunktionen erlaubt den lesenden Zugriff auf die konstruierten Werte, ohne einen neuen Wert zu konstruieren. Typischerweise ist das Ergebnis einer Selektion daher ein Wert eines importierten Datentyps.

Vertreter dieser Operationenklasse sind allgemeine Funktionen wie is_empty, count oder spezifische Funktionen wie top.

Die Auswertung der Selektoren kann auf ausschließlich mittels Konstruktoren gebildete Terme zurückgeführt werden.

Manipulatoren

1. 4.Dann müssen die weiteren Operationen festgelegt werden, sozusagen die Manipulatoren der Datenwerte. Manipulatorfunktionen haben als Ergebnistyp den neu spezifizierten Datentyp.

Im Stack-Beispiel ist pop der einzige Manipulator. Bei der Definition der Manipulatoren muss auf eine vollständige Fallunterscheidung geachtet werden.

1. 5.Der letzte Schritt besteht darin, Fehlersituationen abzufangen.

Axiome für Manipulatoren

Der schwierigste Teil ist hierbei oft die Festlegung weiterer Operationen zur Manipulation. Wenn möglich, sollten diese Funktionen direkt auf Konstruktoren und Selektoren zurückgeführt werden. Allgemein ist es sinnvoll, die Regeln von links nach rechts als Ersetzungsregeln aufzubauen und nicht beliebige Gleichungen zu formulieren. Hierzu sollte man Folgendes beachten:

• Die rechte Seite sollte »einfacher« als die linke Seite sein, also etwa einen Parameterwert »schrumpfen«.
• Bei rekursiv definierten Funktionen sollte man auf Folgendes achten:
  • Die Argumente sollten beim rekursiven Aufruf »einfacher« werden und somit eine echt monoton schrumpfende Folge bilden.
  • Natürlich muss man darauf achten, dass der Abbruch garantiert ist.
• Allgemein empfiehlt sich ein Vorgehen analog zur Definition applikativer Algorithmen. Hier entspricht die linke Seite der Gleichung dann einem Aufruf mit Parametern, während die rechte Seite die Auswertung festlegt. Leider bieten sich nicht immer derartig einfache Gleichungen an.

Insgesamt ist es wichtig, eine vollständige Fallunterscheidung durchzuführen, d.h., jeder Konstruktor muss bei den Parametern auch berücksichtigt werden.