Uni des Saarlandes
Informatik
Programmiersysteme
Vorlesungen
Prog-1 2004


Hauptseite
Termine
Service
Skript
Software
Literatur
Prüfungen

Programmierung 1: Inhalt

Die Vorlesung ist eine Einführung in die Programmierung. Sie richtet sich an Informatikstudenten im ersten Semester. Sie behandelt einerseits Datenstrukturen, Algorithmen, Typen, Typabstraktion und Module. Andererseits führt sie in die Theorie und Implementation von Programmiersprachen ein.

Die Themen der Vorlesung sind vielfältig und gehören zu verschiedenen Teildisziplinen der Informatik. Die Vorlesung ist aber so konzipiert, dass sich ihre Teile schnell zu einem eleganten und in sich schlüssigen Gebäude zusammenfügen, in dem jeder Baustein seinen festen Platz hat.

Als Programmiersprache verwenden wir Standard ML, das auf elegante Weise grundlegende und fortgeschrittene Konzepte der programmiersprachlichen Informatik in ein praktisches Werkzeug umsetzt. Mit Standard ML verschwenden wir keine Zeit für programmiersprachliche Tricks und Ungereimtheiten.

Wir beginnen mit mathematischen Datenstrukturen und konzentrieren uns auf die rekursive Definition von Prozeduren (Funktionen) und Typen (Mengen). Standard ML liefert uns eine Sprache, in der wir diese Definitionen präzise aufschreiben können. Statt Papier verwenden wir zum Aufschreiben einen Computer, mit dem wir unsere mathematischen Programme dann auf Konsistenz überprüfen und nach Belieben ausführen können.

Wir lernen, Eigenschaften unserer Programme mit Hilfe von Induktion zu beweisen. Besonders interessieren wir uns dabei für Aussagen über die Korrektheit und die Laufzeit (schnell oder langsam) von Programmen.

Der Weg von mathematischen Programmen zu richtigen Programmen, die sich in die Software-Umgebung eines Computers nahtlos einfügen, ist kurz. Wir benötigen einen Übersetzer sowie Ein- und Ausgabeoperationen für Zeichenreihen.

Als nächstes betrachten wir Datenstrukturen, deren Zustand sich mit dem Fortschreiten einer Berechnung ändert. Unter anderem versetzen uns solche Datenstrukturen in die Lage, abstrakte Speicher zu programmieren.

Wir beginnen jetzt, größere Programme zu schreiben. Dabei ist es in der Praxis essenziell, Abstraktionen einzuführen und deren konsistente Verwendung mit Hilfe von Typen automatisch zu überprüfen. Gleichzeitig beginnen wir, Programme in klar abgegrenzte Module zu zerlegen, die unabhängig von einander realisiert werden können. Mit Standard ML haben wir eine Programmiersprache, die Typabstraktion und Modularisierung besonders gut unterstützt.

Wir beherrschen jetzt eine Programmiersprache sowie einige Programmiertechniken und können damit nützliche Programme schreiben. Unsere Situation ist vergleichbar mit der eines Kindes, das seine Muttersprache leidlich beherrscht, dem aber die Regeln der Grammatik noch völlig fremd sind. Entsprechend analysieren wir jetzt die Struktur von Teilsprachen von Standard ML, die exemplarisch für alle Programmiersprachen sind. Wir lernen die Unterscheidungen zwischen konkreter und abstrakter Syntax sowie statischer und dynamischer Semantik kennen. Die im ersten Teil der Vorlesung behandelten mathematischen Datenstrukturen und rekursiven Definitionstechniken versetzen uns in die Lage, Syntax und Semantik von Programmiersprachen präzise zu definieren. Der Kreis beginnt sich zu schließen.

Wir haben jetzt die Voraussetzungen, um grundlegende Techniken für die Realisierung von Programmiersprachen auf Computern zu lernen. Diese erfolgt mit Programmen. Wir lernen, wie man einen einfachen Interpreter schreibt. Danach betrachten wir eine virtuelle Maschine mit automatischer Speicherverwaltung, die eine hardwarenahe Programmiersprache realisiert. Die Programme für die virtuelle Maschine erzeugen wir mit einem Übersetzer für eine Teilsprache von Standard ML. Den Interpreter, die virtuelle Maschine und den Übersetzer schreiben wir in Standard ML. Der Kreis ist geschlossen.