Formale Grundlagen der Programmierung

Die Programmierung dient keinem Selbstzweck, sondern ist Teil des Weges hin zu einer Problemlösung auf Basis eines Computers. Der Begriff des Problems ist dabei in einem technischen, mathematischen, formalen Sinne zu verstehen, hierbei aber recht weit gefasst.

In diesem Kapitel werden wir sehen, wie die formal saubere Definition der Syntax einer Programmiersprache gelingt und wie der Aufwand, den wir für die Entscheidung darüber treiben müssen, ob ein Programm syntaktisch korrekt ist oder nicht, wesentlich von der Komplexität der Strukturen abhängt, die wir in der Syntax erlauben. Auf Basis der in diesem Kontext entwickelten Theorie ist es heute möglich, einen Compiler als Praktikumsaufgabe implementieren zu lassen, wogegen die Entwicklung des ersten FORTRAN-Compilers bei IBM etwa 30 Mannjahre benötigte.

Grob betrachtet legen wir mit der Syntax einer Programmiersprache fest, wie die Gestalt korrekt geformter Programme aussieht, die Semantik beschreibt dann, was diese Programme bedeuten, d. h. was bei der Ausführung des Programmes geschehen soll. Doch in der Praxis ist diese Trennung nicht so offensichtlich, wie es das Was und das Wie suggerieren. Um eine effiziente Syntaxanalyse zu ermöglichen, verwenden moderne Programmiersprache eine kontextfreie Syntax, auf Konstrukte, die kompliziertere syntaktische Abhängigkeiten benötigen, wird zugunsten der Effizienz verzichtet – aber nur scheinbar. So ist es in den meisten Programmiersprachen Voraussetzung, dass eine Variable, bevor sie im Programm verwendet werden kann, deklariert wird. Auch gibt es Programmiersprachen (z.B. MODULA-2) in denen nur typengleiche Argumente in arithmetischen Ausdrücken vorkommen dürfen (so ist dort z.B. der Ausdruck 7−0.5 unzulässig). Formuliert werden solche Einschränkungen jedoch in der Regel nur verbal und die über eine kontextfreie Grammatik definierte Syntax stellt keine entsprechenden Forderungen an ein korrektes Programm (da dies mit einer kontextfreien Grammatik nicht möglich ist). Werden jedoch von einem Programm solche Forderungen verletzt, so ist es nicht möglich, ihnen eine sinnvolle Bedeutung (Semantik) zuzuordnen. Von daher werden auch sie von einem Compiler verworfen, und zwar als Fehler der sog. statischen Semantik (können zur Compilezeit entdeckt werden). Andere Ursachen für semantiklose Programme wie beispielsweise das Auftreten einer Division durch 0 sind in der Regel zur Compilezeit nicht zu erkennen und werden den sog. dynamischen Semantikfehlern zugeordnet.

Wir haben nun gesehen, wie wir syntaktisch korrekte Programme spezifizieren und diesen eine Bedeutung zuordnen können. Doch welche Funktionen sind es überhaupt, die wir programmieren können? Dieser Frage gilt es in diesem Kapitel nachzugehen, indem wir untersuchen, welche Funktionen wir tatsächlich berechnen können. Dabei werden wir verschiedene Modelle eines Computers betrachten – die uns schon bekannte Turingmaschine ist nur eines davon, mit der wir unsere Betrachtungen zur Berechenbarkeit eigentlich beginnen könnten. Dies wollen wir hier jedoch nicht tun, sondern unsere Studien entlang der historischen Entwicklung der Rechenmaschinen aufbauen. Dabei wollen wir die ersten mechanischen Maschinen zur Addition und Subtraktion zum Startpunkt unserer Reise erklären und deren Können zunächst in ein mathematisches Modell übersetzen, das uns erlaubt, präzise Aussage über das Berechenbare zu formulieren. Von dort aus werden wir unser Modell auf verschiedene Arten erweitern und dabei als Quintessenz sehen, dass alle denkbaren Ansätze letztlich dieselbe Menge berechenbarer Funktionen liefern.