2 Einleitung

Literatur: R. Sethi: Programming languages: concepts and constructs, Addison-Wesley 1989, Kapitel 1

• Ein Programm ist die Spezifikation einer Berechnung.

• Eine Programmiersprache ist eine Notation zum Schreiben von Programmen.

• Etwas Geschichte.

• Sprachentwicklung wird geleitet durch die Erkenntnis, daß Komplexität durch Strukturierung handhabbar wird.

2.1 Die Rolle von Struktur in der Programmierung

Berühmtes Beispiel: Mariner I-Absturz (1962)

if not in radar contact then do not correct flight path

Einsichten: Dijkstra (1972)

“The art of programming is the art of organising complexity.”

Anforderungen an Programmiersprachen: Leichte • Lesbarkeit

• Verstehbarkeit

• Modifizierbarkeit von Programmen

Problem: Skalierbarkeit von Techniken

Aus der Psychologie: Miller (1967): Menschen können nur mit bis zu sieben Dingen gleichzeitig operieren. Wichtig, daß in möglichst wenige Symbole möglichst viel Information gepackt wird.

Lösung: Abstraktion und Modularisierung

2.2 Die von-Neumann-Maschine

• Am Anfang waren die Maschinen.

• vNM-Entwicklung: späte 40er Jahre in Princeton unter John von Neumann

• Kontrolle—Arithmetik—I/O—Speicher

• kein Unterschied zwischen Daten und Befehlen bzgl. Speicherung

• Sprünge als Mittel, Iterationen zu programmieren

• Maschinensprache (einschl. Assembler) ist unverständlich; zählen wir nicht zu den Programmiersprachen

2.3 Frühe Erfahrungen

2.3.1 Dominanz der Laufzeiteffizienz

FORTRAN als Alternative zur M.-Programmierung (Backus et al. 1957); für numerische Anwendungen; konzise, mathematische^{1} Sprache; effiziente, automatische Übersetzung; Reduktion des Programmieraufwands auf 20%.

• B*B - 4*A*C sehr ähnlich zu b^{2} − 4ac

• Beginn des Faches Übersetzerbau

• Effizienzeinbußen: Zeit zum Übersetzen; nicht optimierter Zielcode (Speicher und Zeit), selbst ein Faktor 2 gegenüber handgeschriebenen Programmen erschien nicht akzeptierbar

• Der Bau des Übersetzers war das dominierende Problem im FORTRAN-Projekt.

• wurde schnell die wichtigste Basis für die wissenschaftliche (numerische) Programmierung

Das Problem wird immer wieder genannt, wenn argumentiert wird, warum eine der moderneren funktionalen oder logischen Programmiersprachen nicht verwendet werden soll.

2.3.2 Vorteile der Hochsprachen

• Lesbarkeit

• schnellere, problemorientiertere Programmentwicklung

• Maschinenunabhängigkeit, Portabilität

• Frühes Fallbeispiel: Reimplementierung von Unix in C (Ritchie 1978)

– neue Benutzer und Erweiterungen des Systems

– Portabilität: ein maschinenunabhängiges Betriebssystem

– Restrukturierung durch verbesserte Lesbarkeit

– Ritchies Resumée: ”Ganz egal wie viel mehr Zeit und Speicher verbraucht wird, wir würden niemals mehr in Assembler programmieren.“

2.3.3 Nochmals zur Effizienz

• Lesbarkeit und verbesserte Struktur tragen zur Effizienzverbesserung bei; Effizienz wird auf allen Entwurfsebenen beeinflußt, falsche Entscheidungen sind in einer Hochsprache leichter revidierbar

• Knuth 1971: Lange Geschichte der Optimierung der falschen Dinge; weniger als 4% des Codes sei verantwortlich für mehr als 50% der Laufzeit

• Verwendung von profilers

1Formula Translation

2.4 Programmiersprachen als Maschinenerweiterungen

• Maschinen haben keine problemorientierte Struktur im Vergleich zu Formeln in FORTRAN

• Programmiersprachen erweitern die Maschine um grundlegende (mathematische) Struktur und um die Fähigkeit zum Bilden von problemorientierter Struktur

– Berechnungsmodell: die reale Maschine scheint durch oder aber auch gerade nicht; Beispiel: Multiprocessing auf einer Maschine

– Datentypen und Operationen: Typisierung von Daten, strukturierte Daten – Abstraktionsmittel: Typdefinitionen und Funktionsdefinitionen erweitern die

Grundbegriffe der Sprache in problemorientierter Weise;

– Problemlösung = Finden einer geeigneten Notation

– Hat eine Sprache Mittel zur Abstraktion, sind Spezialsprachen unnötig. Beispiel: sqrt aus +, −; queues aus arrays

– Erkennung von Fehlern zur Übersetzungszeit

– Schutz vor unerlaubten Zugriffen auf interne Strukturen

2.5 Wie soll man ein Programm strukturieren?

Programmstruktur ist nicht inhärent sondern die Folge von Entwurfsentscheidungen

Beispiel: Auffinden von Duplikaten in Listen

Lösung 1:

sort | find_adjacent_duplicates

• top-down Reduktion des Problems auf zwei einfachere Teilprobleme

• Transformation elementarer Datenstrukturen

• Teilprobleme sind unabhängig, können in verschiedenen Sprachen implementiert werden

• vgl. FP oder pipes in Unix

Lösung 2:

for each element x in the list do
 if find(x) then write(x) else insert(x)

• Strukturierung beruht auf Verwendung eines abstrakten Datentyps mit dessen Hilfe die Begriffswelt problemorientiert erweitert wird

• bottom-up

• Verwendung einer Tabelle ohne daß man wissen muß, wie sie implementiert ist

• interagierende Objekte

2.6 Sprachbeschreibungen

• Syntax; Metasprachen klar (BNF, Syntaxdiagramme)

• Semantik

– nur wenige Sprachen haben eine präzise oder sogar formale Semantikdefinition;

– welche Metasprache? (ML ist das Acronym für Meta-Language.)

– wozu?

• Pragmatik

2.7 Historisches

• Programmierung gab es schon vor der Erfindung des Computers.

Beispiel: lochkartengesteuerter Webstuhl von Jacquard (1801); bis zu 25000 Karten mit bis zu 1050 Löchern für ein seidengewebtes Portrait von 0.5 Quadratmetern mit Auflösung 1000dpi. Beispiel: Turing-Maschine (um 1935)

• Historische Computer:

mechanische Rechenmaschinen seit der Renaissance;

erste Maschine mit Speicher, CPU (“mill”) und Programmierung: Analytical Engine (Babbage 1864)

• siehe Sethi-Buch für Referenzen auf Arbeiten zur Geschichte der Computer und der Programmierung; Artikel im Informatik-Spektrum von F.L. Bauer

• Strukturierte Prorgammierung (Dijkstra 1972)

• Grundprinzipien der Datenabstraktion (Hoare 1972)

• BNF (Backus 1960; Naur 1963)

• Grundlagen für denotationale Semantik (Scott 1969)