Systematisches Programmieren

Frontmatter

1. Einleitung

Zusammenfassung

Der Computer hat im letzten Jahrzehnt rasch eine Verbreitung und große Bedeutung als Werkzeug in Gewerbe, Industrie und Wissenschaft erlangt. Er ist in diesen Branchen zu einem unerläßlichen Instrument geworden und bewältigt Arbeiten, deren Erledigung ohne ihn unmöglich wären. Der Computer ist ein Automat, der Prozesse nach genau vorgeschriebenen Verhaltensmaßregeln ausführt. Er besitzt im allgemeinen nur ein sehr beschränktes Repertoire von elementaren Befehlen, die er „verstehen“ und befolgen kann. Er führt diese jedoch mit enormer Geschwindigkeit und größter Zuverlässigkeit aus. Der Kern seiner Fähigkeiten und seiner vielseitigen Anwendbarkeit liegt im Vermögen, sehr lange Befehlsfolgen auszuführen, in denen unendlich viele Kombinationen von Elementarbefehlen möglich sind. Die Tätigkeit, solche Befehlsfolgen zu konzipieren, wird Programmieren genannt.

Niklaus Wirth

2. Grundbegriffe

Zusammenfassung

In diesem Kapitel werden einige der wichtigsten Grundbegriffe der Programmierung eingeführt. Sie sind fundamental und können daher nicht formell auf Grund anderer Begriffe definiert werden. Stattdessen seien sie verbal beschrieben und anhand einiger einfacher Beispiele erläutert.

Niklaus Wirth

3. Übersicht über den Aufbau eines Computers

Zusammenfassung

Um ein computergerechtes Programm aufstellen zu können, ist es unerläßlich, daß der Programmierer sein Instrument kennt. Je genauer er seinen Prozessor kennt, um so besser kann ein Algorithmus zu einem Programm zugeschnitten werden, das die speziellen Fähigkeiten dieses Prozessors ausnützt. Um so größer ist anderseits aber auch der Aufwand, der in die Entwicklung dieses Programms investiert werden muß. In der Praxis gilt es, einen „goldenen Mittelweg“ auszumachen und möglichst jene Anpassungen zu finden, die mit wenig Mühe viel Ersparnis an Rechenzeit einbringen. Es gilt daher, die wichtigsten allgemeingültigen Charakteristiken des Computers — aller Computer — aufzuzeigen und die Merkwürdigkeiten einzelner Exemplare zu ignorieren. Bei allen modernen Digitalrechnern lassen sich zwei wesentliche Komponenten unterscheiden:

1.

der Speicher (store, „memory“). Er enthält die Objekte, mit denen gearbeitet wird, in codierter Form. Diese codierten Objekte werden Daten genannt. Die Leistungsfähigkeit eines Speichers wird an seiner Kapazität und an der Geschwindigkeit, mit der Daten ihm eingegeben und entnommen werden können, gemessen. Der Speicher hat in jedem Fall eine endliche Kapazität.

 

2.

der Prozessor (arithmetisch-logische Einheit). In dieser Einheit wird addiert, multipliziert, verglichen; Daten werden aus dem Speicher gelesen und in ihn zurückgegeben. In jedem Zeitpunkt enthält der Prozessor nur die unmittelbar zur Verarbeitung nötigen Daten.

 

Niklaus Wirth

4. Programmierhilfen und Programmiersysteme

Zusammenfassung

Noch bis zum Ende der fünfziger Jahre bestand das Programmieren tatsächlich aus der minutiösen Übersetzung von Befehlen in binär, oktal oder sexadezimal dargestellte Zahlen und deren Aneinanderreihung zu einem sinnvollen Programm. Man bezeichnet diese Tätigkeit mit Codieren. Die Unzulänglichkeiten dieses mühsamen Verfahrens traten aber mit dem Schneller- und Größerwerden der Computer mehr und mehr hervor:

1.

Der Codierer war gezwungen, sein Programm auf die Eigenheiten des spezifischen Computers auszurichten. Er benötigte dazu genaueste Kenntnisse aller Details dieser Maschine, deren Befehlssatz und Prozessororganisation. Der Austausch von Programmen zwischen verschiedenen Maschinen wurde dadurch unmöglich, und Kenntnisse der Codiermethoden eines Computers waren oft wertlos für die Codierung eines anderen. Jedes Institut erstellte eigene Programme und war gezwungen, bei der Neuanschaffung eines Computers diese aufzugeben und die Codierarbeit.neu zu beginnen. Es wurde klar, daß das gezielte Ausrichten von Algorithmen auf die merkwürdigsten Eigenheiten eines bestimmten Computers eine schlechte Verwendung des menschlichen Intellektes war.

 

Niklaus Wirth

5. Einfache Beispiele von Programmen

Zusammenfassung

Aus dem vorigen Abschnitt geht hervor, daß ein Programm aus einer Folge von Anweisungen bestehen muß, die der Computer „versteht“. Auch wenn vorläufig nicht genau definiert ist, was ein Computer „versteht“ und welche Anweisungsarten und -formen eine Programmiersprache enthält, so ist doch festzuhalten, daß diese Anweisungen die beabsichtigten Handlungen exakt spezifizieren müssen. Dies ist vielleicht der grundlegende Unterschied zwischen dem Verkehr mit einer Maschine und dem Verkehr mit Menschen. Die Arbeit mit dem Computer erzieht zur Exaktheit im Ausdruck. Unklarheiten, Ungenauigkeiten oder Mehrdeutigkeiten sind ausgeschlossen.

Niklaus Wirth

6. Endlichkeit von Programmen

Zusammenfassung

Die Schleifenstruktur ist ein Charakteristikum von Computer-Programmen, denn sie spezifiziert die Repetition einer Handlung, wozu sich Automaten besonders gut eignen. Ihre Eigenschaft, selbst nach tausenden von Wiederholungen derselben Handlung weder zu ermüden noch in der Zuverlässigkeit und Exaktheit nachzulassen, ist besonders wertvoll. Andererseits ist gerade diese Unermüdlichkeit des Computers ein Grund für erhöhte Aufmerksamkeit auf der Seite des Programmierers. Er hat dafük zu sorgen, daß alle Prozesse, die nach einem bestimmten Programm ablaufen können, nach einer endlichen Anzahl von Wiederholungen terminieren. Er muß die Endlichkeit des Programms garantieren können. Leider ist in der Praxis das Nichtterminieren eines Prozesses (genannt „Hängenbleiben“des Computers) ein ebenso häufiges wie kostspieliges Vorkommnis. Es kann mit der nötigen Gewissenhaftigkeit beim Programmieren verhältnismäßig leicht vermieden werden. Die dazu nötigen Vorsichtsmaßregeln sollen anhand des allgemeinen Strukturschemas (6.1) erläutert werden.

Niklaus Wirth

7. Lineare Notation, Programmiersprachen

Zusammenfassung

Die Darstellung von Programmen durch Flußdiagramme ist für den Einsatz von Rechenanlagen ungeeignet. Die zweidimensionale, bildliche Form kann von den üblichen Datenerfassungsgeräten nicht verarbeitet werden. Programme, die in der Form von Flußdiagrammen vorhegen, müssen daher zuerst in eine maschinell erfaßbare Form übersetzt werden. Bei dieser Übersetzung können sich jedoch leicht Fehler einschleichen, und es stellt sich unwillkürlich die Frage, welche der Formen als gültige Definition des Programms angesehen werden soll. Es erscheint als wünschenswert, Programme in einer Darstellungsweise zu verfassen, die sowohl für den Autor leserlich, übersichtlich und wohldefiniert als auch von Maschinen direkt verarbeitbar ist.

Niklaus Wirth

8. Datentypen

Zusammenfassung

Bereits in Abschnitt 5 wurde angedeutet, daß die summarische Aufzeichnung aller verwendeten Variablen am Anfang eines Programmes zu dessen Verständlichkeit und Leserlichkeit wesentlich beiträgt. Insbesondere gehört zu einer guten Dokumentation die explizite Angabe des Wertebereiches einer jeden Variablen. Die wichtigsten Gründe dafür sind die folgenden:

1.

Die Kenntnis des Wertebereiches einer Variablen ist entscheidend für das Verständnis eines Algorithmus. Ohne explizite Angabe des Wertebereiches ist es meistens schwierig, festzustellen, welche Art von Objekten eine Variable repräsentiert, und die Ermittlung möglicher Fehler wird erheblich erschwert.

 

2.

Die Zweckmäßigkeit und die Korrektheit eines Programms sind in den meisten Fällen abhängig von den Anfangswerten der Argumente, und sie sind nur für bestimmte Bereiche garantiert. Daher gehört es zur Dokumentation eines Algorithmus, daß diese Bereiche explizit aufgeführt sind.

 

3.

Der Speicherbedarf für die Repräsentation einer Variablen im Speicher eines Computers hängt von deren Wertebereich ab. Damit ein Compiler die nötigen Speicherzuordnungen vornehmen kann, ist die Kenntnis der Wertebereiche unerläßlich.

 

Niklaus Wirth

9. Programme mit Rekursionsrelationen

Zusammenfassung

Nachdem in den vorangegangenen Kapiteln einfache Programmstrukturen eingeführt und die wichtigsten Rechenobjekte und ihre Operatoren behandelt wurden, sollen in diesem Kapitel solche Programme näher untersucht werden, die eine einfache Wiederholung darstellen, also allgemein die Form

$$ while\,B\,do\,A $$

(9.1)

besitzen. Erstens ist zu wiederholen, daß eine sinnvolle Repetition nur dann zum Ziel führt, wenn die Anweisung A die Variablen in dem Sinne verändert, daß nach einer endlichen Anzahl von Ausführungen von A die Bedingung B nicht mehr erfüllt ist. Dies aber impliziert, daß A mindestens eine der im Ausdruck B verwendeten Variablen beeinflussen muß. Wird eine Sammelbezeichnung V für die Gesamtheit der Variablen eingeführt, d.h. wird jede Variable des Programms als eine Komponente von V betrachtet, so kann die Anweisung (9.1) allgemeingültig dargestellt werden als

$$ V: = {v_o};whilep\left( V \right)doV; = f\left( V \right) $$

(9.2)

wobei p ein Prädikat (Boolesche Funktion) und f eine Funktion ist.

Niklaus Wirth

10. Die Strukturart „File“

Zusammenfassung

Die vorstehend behandelten skalaren Datentypen zeichnen sich dadurch aus, daß ihre Werte unteilbare Einheiten darstellen und daß im bezeichneten Wertebereich eine Ordnungsrelation besteht (daher „skalar“). In der Datenverarbeitung ist es aber wichtig, daß nicht nur einzelne Werte, sondern ganze Wertemengen als Kollektiv mit einem Namen behaftet und behandelt werden können. Werte, die solchermaßen als Mengen von Werten betrachtet werden, nennt man strukturiert. Es gibt verschiedene Arten der Strukturierung, die sich vor allem durch die Art und Weise, in der die Komponentenwerte bezeichnet werden, und durch die Mechanismen oder Operationen, die sie zugreifbar machen, unterscheiden.

Niklaus Wirth

11. Die Strukturart „Array“

Zusammenfassung

Eine Variable, welche die Strukturart „Array“ besitzt, besteht wie eine File-Variable aus einer Menge von Komponenten des gleichen Typs. Die folgenden Eigenschaften unterscheiden jedoch die beiden Strukturarten:

1.

Jede einzelne Komponente eines „Array“ ist explizit benennbar.

 

2.

Die Anzahl der Elemente wird bei der Einführung der Array-Variablen festgelegt und bleibt danach unverändert.

 

Niklaus Wirth

12. Unterprogramme — Prozeduren und Funktionen

Zusammenfassung

Es kommt sehr häufig vor, daß in einem Programm eine Folge von Anweisungen an mehreren Stellen in genau oder fast genau der gleichen Form auftritt. Um dem Programmierer in diesen Fällen Schreibarbeit zu ersparen, bieten Programmiersprachen das Konzept des Unterprogramms an: Der besagten Folge von Anweisungen wird ein Name zugeordnet, der an den verschiedenen Stellen als Abkürzung für die Anweisungsfolge eingesetzt werden kann. In Anlehnung an die Terminologie von ALGOL werden Unterprogramme Prozeduren genannt; falls sie einen Resultatwert darstellen und innerhalb von Ausdrücken einsetzbar sind, werden sie als Funktionen bezeichnet. Die Definition der Abkürzung heißt Prozedur-(oder Funktions-) Vereinbarung. Die Verwendung der Abkürzung heißt Prozedur-Anweisung oder Prozedur-Aufruf. Der Name einer Funktion kann als Operand in einem Ausdruck auftreten und wird als Funktions-Aufruf bezeichnet.

Niklaus Wirth

13. Transformationen von Zahlendarstellungen

Zusammenfassung

Der abstrakte Begriff der Zahl ist unabhängig von einer Darstellung der Zahlen. Operationen mit Zahlen können abstrakt durch Axiomensysteme definiert werden; sollen sie jedoch an bestimmten Werten ausgeführt werden, so ist zur Erkennung des Resultates die Wahl irgendeiner Darstellung notwendig.

Niklaus Wirth

14. Textverarbeitung mit Array- und File-Strukturen

Zusammenfassung

In diesem Abschnitt sollen einige wenig zusammenhängende Probleme behandelt werden, deren sichtbarer gemeinsamer Nenner lediglich darin besteht, daß Strukturen von Schriftzeichen inspiziert und transformiert werden. Die Beispiele sind jedoch typisch für viele verwandte Probleme und sollen als Übungen für die Anwendung der in den vorangegangenen Abschnitten eingeführten Konzepte dienen.

Niklaus Wirth

15. Schrittweise Programmentwicklung

Zusammenfassung

Aus den bisherigen Ausführungen, und besonders aus den Beispielen des vorigen Kapitels geht klar hervor, daß das Programmieren im Sinne des Konstruierens und Formulierens von Algorithmen im allgemeinen ein komplizierter Vorgang ist, da hierbei auf unzählige Bedingungen und Umstände geachtet werden muß. Ferner ist auch klar, daß sich als Lösung nur in den seltensten Fällen ein einziges Programm anbietet. Meistens gibt es sogar derart viele Lösungsmöglichkeiten, daß die Wahl eines „optimalen“ Programms nicht nur eine gründliche Analyse der in Frage kommenden Algorithmen und des zu benutzenden Computers, sondern auch eine Untersuchung der häufigsten Art der Verwendung des Programmes bedingt. Wäre das Programmieren ein strikt deterministischer Prozeß, der nach festen Regeln abläuft, so wäre es bereits seit langem automatisiert worden.

Niklaus Wirth

Backmatter