For every problem there is a solution
that is simple, neat, and wrong.
Zu den wesentlichen Bestandteilen des PSP gehört das Fehlermanagement, das versucht, Fehler zuallererst zu vermeiden, und falls sie doch auftreten, sie so früh wie möglich wieder zu entdecken und zu beseitigen. Die wichtigsten Mittel zum Fehlerfinden sind dabei die Durchsichten (reviews). Üblicherweise wird im PSP eine Entwurfsdurchsicht und eine Codedurchsicht durchgeführt. Unter Entwurf wird im PSP nicht nur der Grobentwurf verstanden, also die Definition von Modul- oder Klassenschnittstellen, sondern auch der Feinentwurf, in dem Datenstrukturen entworfen werden und die inneren Funktionsweisen der Prozeduren oder Methoden, in schwierigen Fällen bis hin zu Pseudocode.
Der PSP schlägt keine Entwurfsmethode vor; diese soll jeder Programmierer passend zu seinen eigenen Vorlieben, Bedürfnissen und seinem Anwendungsgebiet aussuchen. Der PSP empfiehlt aber eine Reihe von Methoden, um Entwürfe auf Korrektheit zu prüfen und zwar unabhängig von der Entwurfsmethode. Dazu gehören zum Teil auch Notationen, mit denen bestimmte Aspekte von Entwürfen dargestellt werden können, soweit die jeweilige Entwurfsmethode nicht eine alternative Darstellung für den gleichen Zweck schon bereithält.
Die empfohlenen Notationen sind
Endliche Automaten eignen sich in sehr vielen Fällen zur Darstellung des Verhaltens von zustandsbehafteten Modulen oder Datenobjekten. Der Vorteil dieser Darstellung besteht darin, daß sich dafür Methoden angeben lassen, mit denen leicht Plausibilitätsprüfungen für einen Entwurf vorgenommen werden können, die viele Entwurfsfehler aufdecken. Dazu mehr in einem separaten Abschnitt unten.
Folgende Entwurfsprüfungsmethoden werden im PSP vorgeschlagen:
Bei der Auswahl und dem Einsatz von Entwurfsprüfungsmethoden sollten einige Punkte stets beachtet werden. Erstens und vor allem sind in der Praxis immer die Kosten einer Entwurfsprüfung von Bedeutung. Deshalb scheiden manche Methoden eventuell aus, obwohl sie im Prinzip nützlich sein könnten. Die Kostengesichtspunkte bei der Auswahl von Methoden gelten aber nicht gleichmäßig für den ganzen Entwurf, sondern jeder Entwurf hat kritische Abschnitte, von denen klar ist, daß sie im Vergleich zum Rest besonders gut geprüft werden sollten, entweder, weil sie besonders fehlerträchtig sind, oder weil sie besonders kritisch für das Funktionieren des Programms sind. Für diese Abschnitte sind höhere Prüfungskosten akzeptabel als für den Rest. Das richtige Identifizieren kritischer Abschnitte in einem Entwurf ist eine Fertigkeit, die ein Entwerfer lernen kann und muß. Manche Methoden könnte man auf denselben Abschnitt in unterschiedlich großer Detailtiefe anwenden. Auch hierbei ist ein Gespür für das Kosten-Nutzen-Verhältnis als Leitmaßstab notwendig.
Zweitens ist die Eignung der Methoden für einen Anwendungsfall unterschiedlich. Oft lassen sich zwar im Prinzip mehrere Methoden anwenden, aber manche sind erheblich einfacher oder ergiebiger als andere. Diese Auswahl ist nur manchmal schwierig, meist liegt es auf der Hand; insbesondere lassen sich viele der unten besprochenen Methoden nur bei recht fein spezifizierten Entwürfen einsetzen (Pseudokode).
Drittens ist es wichtig, die eigene Beherrschung einer jeden Methode für einen Anwendungsfall einschätzen zu können. Es hat keinen Sinn, eine Methode einzusetzen, mit der man bei der Entwurfsprüfung mehr Fehler macht als beim Entwurf. Bei der Auswahl zwischen zwei Methoden ist eventuell die eigentlich etwas weniger geeignete der beiden vorzuziehen, wenn man sie nämlich erheblich sicherer oder schneller zu benutzen versteht. Als allgemeine Regel gilt, daß ein Entwurf, zu dem man keine Prüfungsmethode gut genug beherrscht, um ihn zuverlässig prüfen zu können, zu kompliziert und deshalb schlecht ist; er sollte nach Möglichkeit komplett neu gemacht werden.
Die meisten zustandsbehafteten Objekte oder Module in Programmen haben eine so große Zahl von Zuständen, daß eine Behandlung aller dieser Zustände in einer Zustandsmaschine hoffnungslos und zudem unsinnig wäre. Es gibt aber innerhalb dieser Zustandsmenge in den allermeisten Fällen eine recht kleine Zahl von disjunkten Teilmengen, deren Vereinigung die gesamte Menge ist und die jeweils für ein qualitativ unterschiedliches Verhalten des Objekts oder Moduls stehen. Eine Modellierung des Zustandsautomaten über diese qualitativ unterschiedlichen Zustände reduziert die Zustandsbetrachtung auf das wesentliche und erlaubt eine Prüfung des Entwurfs auf Vollständigkeit und Konsistenz mit moderatem Aufwand.
Welches sind diese qualitativ verschiedenen Zustände? Wie findet man sie? Leider kann man hierfür keine einfachen Regeln angeben. Als Richtschnur kann man sagen, daß die Unterscheidung der Zustände möglichst oft mit den Fallunterscheidungen zusammenfallen sollte, die in der Programmlogik notwendig sind, und daß die Gesamtzahl der Zustände klein bleiben muß (unter 10), weil sonst die vollständige Prüfung zu aufwendig wird. Welche zusammengefaßten Zustände am besten geeignet sind, ist schwer zu sagen. Manchmal ergeben sich mehrere Möglichkeiten zur Einteilung, die sich gegenseitig ausschließen. Dann kann man mehrere dieser Möglichkeiten getrennt voneinander zur Prüfung heranziehen.
Die Beschreibung des Objekts oder Moduls als Zustandsmaschine gibt zunächst einmal an, aus welchen Zuständen welche Operationen zu welchen anderen Zuständen führen; also die Zuständsübergänge.
Hier ein sehr simples Beispiel: Wir betrachten eine Stapelklasse, deren Realisierung bis zu maxentries Stapeleinträge zulassen soll. Sie habe die Operationen empty (ist der Stapel leer?), top (sag mir das oberste Element), push (packe ein Element auf den Stapel) und pop (entferne das oberste Element vom Stapel und gib es mir).
Dann empfiehlt es sich, drei Zustände zu unterscheiden. none: Der Stapel ist leer, also entries = 0 (Fallunterscheidungen bei empty, top und pop). full: der Stapel ist ganz voll, also entries = maxentries (Fallunterscheidung bei push). some: der Stapel ist teilweise voll (Fallunterscheidung bei empty).
Die Zustandsübergänge lassen sich folgendermaßen beschreiben:
Vom Zustand none
in den Zustand none: empty, top, pop;
in den Zustand some: push;
in den Zustand full: kommt nicht vor.
Vom Zustand some
in den Zustand none: pop wenn entries = 1;
in den Zustand some: push wenn entries < maxentries -
1, pop wenn entries > 1, empty, top;
in den Zustand full: push wenn entries gleich
maxentries - 1.
Vom Zustand full
in den Zustand none: kommt nicht vor;
in den Zustand some: pop;
in den Zustand full: push, empty, top.
Was haben wir übersehen?
Die obige Tabelle stimmt nicht, wenn maxentries gleich 1 ist.
Macht das was? Nein.
Diese Beschreibung gibt uns nun eine Anleitung für den Entwurf der Operationen. Erstens müssen wir dafür sorgen, daß für jede Operation für jeden Ausgangszustand eine Aktion vorgesehen ist. Dies ist die Vollständigkeit des Entwurfs bzw. zunächst die Vollständigkeit der Zustandsmaschine. Zweitens dürfen sich die Zustände nicht überlappen. Dies ist die Orthogonalität. Drittens muß die Aktion jeweils in den richtigen Folgezustand führen. Dies ist die Korrektheit der Zustandsmaschine und zusammen mit den übrigen Wirkungen der Aktion die Korrektheit der Operation. Viertens dürfen nicht mehrere Folgezustände für den gleichen Fall spezifiziert sein. Dies ist die Konsistenz.
Eine vollständige Zustandsmaschine mit orthogonalen Zuständen nennen wir eine ordentliche Zustandsmaschine. Eine solche ist eine brauchbare Grundlage für einen Entwurf. Der erste Schritt bei der Entwurfsprüfung besteht also darin zu prüfen, ob alle Zustandsmaschinen vollständig und orthogonal sind.
Der Entwurf selbst kann wieder in einem ähnlichen Format an den
Zuständen orientiert aufgeschrieben werden
Beispiel:
Die Operation empty
im Zustand none: true.
im Zustand some: false.
im Zustand full: false.
Die Operation top
im Zustand none: Fehler.
im Zustand some: Oberstes liefern.
im Zustand full: Oberstes liefern.
Die Operation push
im Zustand none: aufstapeln.
im Zustand some: aufstapeln.
im Zustand full: Fehler.
Die Operation pop
im Zustand none: Fehler.
im Zustand some: entstapeln.
im Zustand full: entstapeln.
In diesem Format läßt sich die Vollständigkeit leicht prüfen, so daß typische Unterlassungsfehler nicht so leicht unentdeckt bleiben. Zum Beispiel könnte man in einem entsprechend komplizierteren Fall leicht eine Prüfung wie die auf den Überlauf bei push vergessen. Die explizite Angabe des Folgezustands wurde hier ebenso wie die genauere Beschreibung der Operation selbst unterlassen. In komplizierteren Fällen wird man auch dies noch tun, um die Prüfung der Korrektheit zu ermöglichen.
Meist kann man diese Darstellung wieder vereinfachen, indem man Zustände noch weiter zusammenfaßt. Beispielsweise reicht bei push der some-Fall für alle drei Zustände aus, wenn man ihn als ,,Fehler falls Stapel voll, aufstapeln sonst`` formuliert.
Ein Vorgehen mit dieser Notation steigert einerseits die Disziplin bei der Erstellung des Entwurfs und vermeidet so Fehler und ermöglicht andererseits ein systematisches Vorgehen bei der Prüfung von Vollständigkeit und Korrektheit der Realisierung des Zustandsautomaten. Ein weiterer Vorteil liegt darin, daß die Anwendung dieser Methode bei zu ,,cleveren`` Entwürfen, die mit raffinierten Tricks zu arbeiten versuchen, recht schwierig wird, so daß die Versuchung, solche schwerer verständlichen und fehleranfälligeren Konstruktionen zu benutzen, sinkt. Es sei betont, daß das obige Beispiel nur zur Illustration des Vorgehens dient; die Vorteile der Methode werden dabei nur zu kleinen Teilen sichtbar, sie entfalten sich erst in komplizierteren Fällen. Die Synthese und Analyse von Klassenentwürfen mit geeignet ausgewählten Zustandsmaschinen ist eine der leistungsfähigsten Methoden, um Unterlassungen und Inkonsistenzen in solchen Entwürfen aufzudecken.
Die Einhaltung von Konventionen zu prüfen, kann ein wesentlicher Beitrag zur Qualitätsverbesserung eines Entwurfs sein. Zwei Arten von Konventionen sind vor allem zu beachten, nämlich Anforderungen an das entworfene Produkt und Anforderungen an das Entwurfsdokument als solches.
Produktkonventionen dienen dazu, das äußere Erscheinungsbild des Softwareprodukts gegenüber dem Benutzer zu vereinheitlichen. Bei interaktiver Software fallen hierunter Vereinbarungen über das Aussehen, den Inhalt und die Benutzung von Menüs und Dialogboxen, bei Bibliotheken sind es Namensgebungs- und Aufrufkonventionen und so fort. Die Prüfung von Produktkonventionen verbessert den Entwurf in zweierlei Weise: erstens durch bessere Einhaltung der Konventionen selbst, die als Qualitätsmerkmale der Software gar nicht unbedeutend sind und zweitens dadurch, daß eine Verletzung von Produktkonventionen häufig anzeigt, wo insgesamt beim Entwurf weniger sorgfältig gearbeitet wurde und vermutlich noch weitere Probleme zu erwarten sind, insbesondere übersehene oder mißverstandene Anforderungen.
Standards im Entwurfsdokument dienen dazu, die Lesbarkeit des Dokuments zu verbessern, die Orientierung darin zu erleichtern und Mißverständnisse seines Inhalts zu vermeiden. Das ist zwar in der Phase der Herstellung der Software eventuell noch nicht sehr wichtig, insbesondere, wenn der Entwerfer den Entwurf selbst realisiert, bekommt aber in jedem Fall in der Wartung erhebliche Bedeutung. Auch hier deuten Abweichungen von den Konventionen auf Mängel im Entwurf hin und eignen sich deshalb neben ihrer direkten Bedeutung als äußerliches Prüfkriterium zum Aufspüren sonstiger Entwurfsprobleme.
Eine dritte Klasse von Konventionen, deren Prüfung sich lohnt, können Richtlinien über die Gestaltung wiederverwendbarer Komponenten sein. Zur Entwurfsprüfung gehört dann einerseits die Prüfung, ob die neu entworfenen Komponenten, welche zur Wiederverwendung gedacht sind, gemäß dieser Konventionen entworfen wurden und andererseits, ob die Verwendung existierender Komponenten, die im Entwurf vorgesehen ist, diesen Konventionen entspricht.
Symbolische Ausführung eignet sich manchmal zur Prüfung exakt spezifizierter kurzer Anweisungsabschnitte. Die Idee hierbei lautet, die Variablen nicht durch ihre Werte zu ersetzen, sondern für sich selbst stehen zu lassen, mit dem Wert, den sie am Eingang des Programmstücks haben, und bei jeder Operation dann mit Variablenbezeichnern zu rechnen, so wie man es aus der Mathematik kennt. Beispiel: Das Programmstück
a := b + 1; (* now a = b+1 *) c := 2*a; (* now c = 2b+2 *) IF a > 7 THEN c := c + 1 (* now c = c+1 if b+1 > 7 and c = 2*b+2 otherwise *) ELSE a := b (* now a = b if b+1 <= 7 and a = b+1 otherwise *) FI;liefert als Ergebnis, daß
a = IF NOT b > 6 THEN b ELSE b+1 b = b c = IF b > 6 THEN c+1 ELSE 2*b+2wobei die Variablen auf der linken Seite die Ausgabewerte des Programmstücks bezeichnen und die auf der rechten Seite des Gleichheitszeichens die Eingabewerte.
Symbolische Ausführung ist im Prinzip sehr mächtig, sprengt aber sehr schnell die Grenzen dessen, was sich als symbolischer Ausdruck noch handhaben, geschweige denn verstehen läßt. Aus diesem Grund ist es wie gesagt nur für kurze Programmstücke geeignet, kann dort aber gelegentlich sehr nützlich sein.
Gedanklich verwandt mit der symbolischen Ausführung ist der Induktionsbeweis, der sich zur Prüfung von Schleifen oder vor allem Rekursionen eignet. Hier konzentriert sich die symbolische Umformung allerdings auf einen bestimmten Aspekt des Programms, der die nachzuweisende Eigenschaft beschreibt. Die übrigen Teile werden häufig nicht symbolisch, sondern mit anderen Methoden, auch nichtformalen, gehandhabt.
Ausführungstabellen sind ein Hilfsmittel für die Ausführung eines Programmes ,,von Hand``. Sie beschreiben sämtliche Schritte der Programmausführung für eine bestimmte Eingabe, samt der Folgen, die jeder Schritt auf die Inhalte aller relevanten Variablen hat. Das Verfahren ist sehr simpel, universell und aufwendig.
Dazu wird eine breite Tabelle angelegt, in deren erste Spalte sukzessive immer der nächste auszuführende Programmschritt eingetragen wird. Im Normalfall liegt dieser als Pseudokode vor, wobei die Granularität eventuell recht grob sein darf, solange die Folgen der Operation auf die betrachteten Variablen klar sind. In die weiteren Spalten werden die Werte aller relevanten Zustandsgrößen eingetragen. Jede solche Größe hat eine eigene Spalte, in die ein Eintrag nur dann gemacht wird, wenn sich in diesem Schritt der Zustand oder Wert ändert. Solche Zustandsgrößen sind Variablen, Umgebungsgrößen (z.B. der Wert, den ein bestimmter Aufruf eines anderen Moduls ergeben würde), Dateiinhalte und -positionen etc. Insbesondere gibt es eine Spalte, in der die Ergebnisse von Bedingungsauswertungen notiert werden. Im Fall von Schleifen treten die entsprechenden Anweisungen mehrfach in der linken Spalte auf.
Um noch einmal das simple Beispiel von oben zu verwenden:
Schritt Bedingung a b c (START) 5 a := b + 1; 6 c := 2*a; 12 IF a > 7 THEN false ELSE a := b 5 FI;Eine Ausführungstabelle liefert also nicht nur die Ergebnisse der Programmausführung (abzulesen aus dem jeweils letzten Eintrag jeder Spalte, also hier a = 5, b = 5, c = 12), sondern bietet auch Einblicke in die Arbeitsweise der Programmlogik, die sogar dann zur Entdeckung von Fehlern führen können, wenn das Ergebnis richtig ausfällt.
Für fertigen Programmcode könnte man anstatt der Ausführungstabelle auch eine schrittweise Ausführung des Programms in einem Debugger verwenden. Das hat den zusätzlichen Vorteil, Irrtümer bei der Simulation zu vermeiden, hat aber drei erhebliche Nachteile. Erstens ist bei der Handsimulation aufgrund von deren Langsamkeit die Neigung nicht so groß, das Mitdenken einzustellen. Auf diese Weise werden Fehler oft schon sehr viel früher gefunden, was die Langsamkeit kompensieren kann. Zweitens ist die Übersicht über die Variablenzustände und vor allem deren Historie in der Tabellenform oft besser, jedenfalls, solange die Menge der relevanten Variablen klein genug ist. Drittens und vor allem kann man eine Ausführungstabelle auf höheren Abstraktionsniveaus benutzen als den Debugger: nicht erst für fertigen Programmcode, sondern auch für Pseudokode oder noch grobere Methoden der Beschreibung (beispielsweise dort, wo ganze Unterprogramme, die schon benutzt werden, noch gar nicht entworfen sind).
Verfolgungstabellen kombinieren mehrere der obigen Techniken miteinander, nämlich Ausführungstabellen, symbolische Ausführung und Induktionsbeweise. Dadurch kann man eine Überprüfung erreichen, die trotz (teilweiser) Abstützung auf die Primitivtechnik der Ausführungstabellen mehr Fälle abdeckt, als mit jenen möglich ist und dennoch im Umfang erträglich bleibt (eventuell sogar kleiner als eine einzige Ausführungstabelle es wäre).
Der Grundgedanke von Verfolgungstabellen besteht darin, ähnlich wie bei Ausführungstabellen konkret die Logik eines Programms, das in Pseudokode spezifiziert ist, abzulaufen und zu prüfen, ob es das gewünschte Verhalten zeigt. Im Gegensatz zu Ausführungstabellen wird jedoch nicht nur mit einem einzelnen Eingabebeispiel gearbeitet, sondern eine komplette Prüfung aller Eingabefälle oder einer erheblichen Untermenge davon angestrebt. Dies geschieht durch die Kombination von Ausführungstabellen mit symbolischer Ausführung und Induktionsbeweisen. Zunächst werden alle Eingabefälle identifiziert, für die die Programmlogik qualitativ unterschiedlich verläuft (ähnlich wie beim Strukturtesten). Dann wird jeder dieser Fälle einzeln untersucht, wobei er eben nicht in einer Form gegeben ist wie ,,Die Eingabe für a lautet 17``, sondern als Bedingung, also in einer Form wie ,,Die Eingabe für a ist größer als 1``, weil beispielsweise die Fälle a = 0 und a = 1 getrennt untersucht werden müssen, da dann die Programmlogik anders verläuft.
Entwurfsprüfung nach diesem Verfahren ist relativ aufwendig, bietet aber auch eine gute Abdeckung und kann die meisten Fehler auch subtilerer Art finden. Es ist auch nicht aufwendiger als ein vergleichbar gründlicher Test des Programms, mit dem Unterschied, daß der Test gegebenenfalls nur anzeigt, daß ein Fehler vorliegt, aber nicht, worin er besteht. Deshalb kann eine Prüfung mit Verfolgungstabellen erheblich an Arbeit sparen. Da ein beträchtlicher Teil der Arbeit in der Identifikation der zu untersuchenden Fälle besteht und dies auch für den Test gemacht werden muß, ist der effektive Zeitaufwand geringer, als man annehmen könnte.
Ein ausführliches Beispiel findet sich in [Hum95, Seite 400ff].
Die formale Verifikation, zum Beispiel nach dem wp-Kalkül von Gries, das aus der Informatik-Grundvorlesung bekannt ist, eignet sich nur zur Prüfung von Programmlogik, deren Zweck erstens formal spezifiziert ist und die zweitens selbst auch schon recht detailliert angegeben ist. Unter diesen Voraussetzungen ist sie eine sehr leistungsfähige Methode, was das Auffinden von Fehlern angeht, aber auch eine sehr aufwendige Methode. Wegen der sehr hohen Kosten kann sie nur selten und auch dann nur für kurze Programmstücke eingesetzt werden. Die Kosten und der Aufwand verringern sich erheblich, wenn man die Verifikation gleich bei der Konstruktion des Programmstücks vornimmt. In diesem Fall wird das Programmstück erstens so konstruiert, daß die Verifikation nicht so kompliziert wird und zweitens wahrscheinlich von vornherein mit nur sehr wenigen Fehlern, die zudem sehr früh erkannt werden. Über das Vorgehen zur Konstruktion von Programmen samt Korrektheitsbeweis gibt es eigene Vorlesungen, so daß wir hier nicht weiter darauf eingehen.
Eine zweite Methode zur Absenkung des Aufwands besteht darin, nur die kritischsten Aspekte des Programmstücks zu verifizieren, nämlich die Schleifen. Hierbei wird dann nur die Schleifeninvariante aufgestellt und geprüft, ob die Schleife diese auch einhält, wenn man annimmt, daß der Schleifenrumpf die gewünschten Operationen durchführt. Es wird also nur die Schleifenbedingung getestet, so daß der korrekte Abbruch der Schleife geprüft wird, sowie die Operationen, die von einem Schleifendurchlauf zum nächsten weiterschalten sollen und mit der Abbruchbedingung richtig zusammenspielen müssen.
Drittens kann man die Verifikation vereinfachen, indem man von der kompletten formalen Verifikation zu einer halbformalen übergeht, bei der zwar die gleichen strengen Schlußweisen verwendet werden, um die Korrektheit zu untersuchen, aber mit weniger streng gefaßtem Inhalt. Die grobe Architektur der Argumentation soll also einem formalen Beweis entsprechen, aber bei den Einzelteilen darf über Details hinweggegangen werden. Eine solche Einschränkung ist ohnehin unvermeidlich, wenn gar keine komplette formale Spezifikation vorliegt, sondern Teile der Spezifikation mit sprachlichen Begriffen operieren. Im Abschnitt über die Cleanroom-Methode (7) werden wir ein Beispiel einer solchen Vorgehensweise sehen.