Programmierung - eine Einführung in die Informatik mit Standard ML

Vorwort

Inhaltsverzeichnis

1 Schnellkurs

1.1 Programme

1.2 Interpreter

1.2.1 Mehrfachdeklaration

1.2.2 Ergebnisbezeichner

1.2.3 Fehlermeldungen

1.3 Prozeduren

1.4 Vergleiche und Konditionale

1.5 Lokale Deklarationen und Hilfsprozeduren

1.6 Tupel

1.7 KartesischeMuster

1.8 Ganzzahlige Division: Div undMod

1.9 Rekursion

1.10 Natürliche Quadratwurzeln und Akkus

1.11 Endrekursion

1.12 Divergenz

1.13 Festkomma- und Gleitkommazahlen

1.13.1 Festkommazahlen

1.13.2 Gleitkommazahlen

1.13.3 Rundungsfehler

1.13.4 Beispiel: Newtonsches Verfahren

1.14 Standardstrukturen

2 Programmiersprachliches

2.1 Darstellung und Aufbau von Phrasen

2.2 Syntaxübersicht

2.2.1 Wörter

2.2.2 Phrasen

2.3 Klammern

2.4 Freie Bezeichner und Umgebungen

2.5 Tripeldarstellung von Prozeduren

2.6 Semantische Zulässigkeit

2.7 Ausführung

2.7.1 Ausführung von Ausdrücken

2.7.2 Ausführung von Prozeduraufrufen

2.7.3 Ausführung von Deklarationen

2.7.4 Ausführung von Programmen

2.8 Verarbeitungsphasen eines Interpreters

2.9 Semantische Äquivalenz

3 Höherstufige Prozeduren

3.1 Abstraktionen und kaskadierte Prozeduren

3.2 Tripeldarstellung und Rekursion

3.3 Höherstufige Prozeduren

3.3.1 Bestimmte Iteration: Iter

3.3.2 Unbestimmte Iteration: First

3.4 Bestimmte Iteration: Polymorphes Iter

3.5 Polymorphe Typisierung

3.5.1 Monomorphe und polymorphe Bezeichner

3.5.2 Ambige Deklarationen

3.6 Typinferenz

3.7 Typen und Gleichheit

3.8 Bezeichnerbindung

3.8.1 Lexikalische Bindungen

3.8.2 Konsistente Umbenennung und Bereinigung

3.8.3 Statische und dynamische Bindungen

3.9 Spezifikation polymorpher Prozeduren

3.10 Abgeleitete Formen: Andalso, Orelse, Op

3.11 Beispiel: Primzahlberechnung

3.12 Komposition von Prozeduren

3.13 Bestimmte Iteration: Iterup und Iterdn

4 Listen und Strings

4.1 Die Datenstruktur der Listen

4.1.1 Listentypen

4.1.2 Nil und Cons

4.1.3 Regelbasierte Prozeduren

4.2 Append, Rev, Concat und Tabulate

4.3 Map, Filter, Exists und All

4.4 Faltung

4.5 Hd, Tl, Null, Nth und dasWerfen von Ausnahmen

4.6 Regelbasierte Prozeduren undMusterabgleich

4.6.1 Disjunkte und überlappende Regeln

4.6.2 Erschöpfende Regeln

4.6.3 Regelbasierte Abstraktionen und Case-Ausdrücke

4.6.4 Kaskadierte Prozedurdeklarationenmitmehreren

Regeln

4.7 Strings

4.7.1 Zeichenstandards

4.7.2 Lexikalische Ordnung

5 Sortieren

5.1 Sortieren durch Einfügen

5.2 Polymorphes Sortieren

5.3 Inverse und lexikalische Ordnungen

5.4 Sortieren durchMischen

5.5 EndlicheMengen und strikte Sortierung

5.6 Primzerlegung

5.7 Ein überraschender Laufzeitunterschied

6 Konstruktoren und Ausnahmen

6.1 Konstruktoren

6.2 Enumerationstypen

6.3 Typsynonyme

6.4 Darstellung arithmetischer Ausdrücke

6.4.1 Komponenten und Teilausdrücke

6.4.2 Darstellung von Umgebungen

6.5 Ausnahmen

6.5.1 Werfen von Ausnahmen

6.5.2 Fangen von Ausnahmen

6.5.3 Ausführungsreihenfolge und Sequenzialisierung

6.5.4 Konvention für die Spezifikation von Ausnahmen

6.5.5 Beispiel: Test aufMehrfachauftreten

6.6 Typkonstruktoren

6.7 Optionen

7 Bäume

7.1 Reine Bäume

7.1.1 Unterbäume

7.1.2 Gestalt arithmetischer Ausdrücke

7.1.3 Lexikalische Baumordnung

7.2 Teilbäume

7.3 Adressen

7.3.1 Nachfolger und Vorgänger

7.4 Größe und Tiefe

7.5 Faltung

7.6 Präordnung und Postordnung

7.6.1 Teilbaumzugriffmit Pränummern

7.6.2 Teilbaumzugriffmit Postnummern

7.6.3 Linearisierungen

7.7 Balanciertheit

7.8 FinitäreMengen und gerichtete Bäume

7.9 Markierte Bäume

7.10 Projektionen

8 Mengenlehre

8.1 Mengen

8.2 Aussagen

8.3 Tupel

8.4 Gerichtete Graphen

8.5 Binäre Relationen

8.5.1 Umkehrrelationen

8.5.2 Funktionale und injektive Relationen

8.5.3 Totale und surjektive Relationen

8.5.4 Komposition von Relationen

8.5.5 Reflexivität, Transitivität und Ordnungen

8.6 Funktionen

8.6.1 Lambda-Notation

8.6.2 Funktionsmengen

8.6.3 Klammersparregeln

8.6.4 Adjunktion

8.6.5 Bijektionen und Darstellungen

8.7 Terminierende Relationen

8.8 Strukturelle Terminierungsfunktionen

9 Mathematische Prozeduren

9.1 Beschreibung

9.2 Ausführung

9.3 Rekursionsfunktionen

9.4 Rekursionsbäume

9.5 Rekursionsrelationen

9.6 Ergebnisfunktionen

9.7 Der Korrektheitssatz

9.7.1 Endrekursive Bestimmung von Potenzen

9.7.2 Endrekursive Bestimmung von Fakultäten

9.8 Größte gemeinsame Teiler

9.9 Gaußsche Formel

9.10 Geschachtelte Rekursion

10 Induktive Korrektheitsbeweise

10.1 Induktion

10.2 Bestimmte Iteration

10.2.1 Iterative Bestimmung von Potenzen

10.2.2 Iterative Bestimmung der Fakultäten

10.2.3 Iterative Bestimmung der Fibonacci-Zahlen

10.3 Unbestimmte Iteration

10.4 Listen und strukturelle Induktion

10.5 Verstärkung der Korrektheitsaussage

10.6 Größenverhältnisse in Bäumen

10.7 Binäre Charakterisierung von Bäumen

11 Laufzeit rekursiver Prozeduren

11.1 Laufzeitfunktionen

11.2 Beispiele

11.2.1 Konkatenation von Listen

11.2.2 Faltung von Listen

11.2.3 Elementtest für Listen

11.3 Rekursive Darstellung von Laufzeitfunktionen

11.4 Laufzeiten und Komplexitäten

11.5 Komplexität von Laufzeitfunktionen

11.6 Naive Komplexitätsbestimmung

11.7 Nebenkosten

11.7.1 Beispiel: Aufteilen von Listen

11.7.2 Beispiel: Sortieren durch Einfügen

11.8 Polynomieller Rekurrenzsatz

11.9 Exponentieller Rekurrenzsatz

11.10 Logarithmischer Rekurrenzsatz

11.10.1 Beispiel: Schnelles Potenzieren

11.10.2 Beispiel: Euklidscher Algorithmus

11.11 Linear-logarithmischer Rekurrenzsatz

12 Statische und dynamische Semantik

12.1 Abstrakte Syntax

12.2 Abstrakte Grammatiken

12.3 Statische Semantik

12.4 Elaborierung

12.5 Dynamische Semantik und Evaluierung

12.6 Rekursive Prozeduren

13 Konkrete Syntax

13.1 Lexikalische Syntax für Typen

13.2 Phrasale Syntax für Typen

13.2.1 Affinität

13.2.2 Eindeutigkeit

13.3 Parsing durch rekursiven Abstieg

13.4 Parser für Typen

13.5 Arithmetische Ausdrücke

13.5.1 Lexer

13.5.2 Parser

13.6 Konkrete Syntax für F

14 Datenstrukturen

14.1 Strukturen

14.2 Implementierung von Datenstrukturen

14.3 Abstrakte Datenstrukturen

14.4 Vektoren

14.5 Binäre Suche

14.6 Schlangen und Darstellungsinvarianten

14.7 Funktoren

15 Speicher und veränderliche Objekte

15.1 Zellen und Referenzen

15.2 Speichereffekte

15.3 Imperative Prozeduren

15.4 Reihungen

15.5 Reversieren und Sortieren von Reihungen

15.6 Agenden

15.7 Effiziente imperative Schlangen

15.8 Schleifen

15.9 Lineare Speicher

15.10 Lineare Darstellung von Listen

15.11 Lineare Darstellung von Bäumen

15.12 Lineare Darstellung von Ausdrücken

15.13 Speicherplatzbedarf bei der Programmausführung

16 Stapelmaschinen und Übersetzer

16.1 Eine Stapelmaschine

16.2 Arithmetische Befehle

16.3 Sprungbefehle und Konditionale

16.4 Imperative Variablen und Schleifen

16.5 Verwendung der Halde

16.6 Ein Übersetzer

16.7 Prozedurbefehle

16.8 Aufrufrahmen

16.9 Endaufrufe

16.10 Dynamische Prozeduren

16.11 Automatische Speicherbereinigung

16.12 Voll- und Halbübersetzung

A Klammersparregeln

Literaturverzeichnis

Index