On this page:
Informatik 1, WS 2023/  24 Universität Tübingen

Informatik 1, WS 2023/24 Universität Tübingen

Prof. Dr. Klaus Ostermann

mit Beiträgen von Jonathan Brachthäuser, Yufei Cai, Yi Dai und Tillmann Rendel

Große Teile dieses Skripts basieren auf dem Buch "How To Design Programs" von M. Felleisen, R.B. Findler, M. Flatt und S. Krishnamurthi.

    1 Programmieren mit Ausdrücken

      1.1 Programmieren mit arithmetischen Ausdrücken

      1.2 Arithmetik mit nicht-numerischen Werten

      1.3 Auftreten und Umgang mit Fehlern

      1.4 Kommentare

      1.5 Bedeutung von BSL Ausdrücken

    2 Programmierer entwerfen Sprachen!

      2.1 Funktionsdefinitionen

      2.2 Funktionen die Bilder produzieren

      2.3 Bedeutung von Funktionsdefinitionen

      2.4 Konditionale Ausdrücke

        2.4.1 Motivation

        2.4.2 Bedeutung konditionaler Ausdrücke

        2.4.3 Beispiel

        2.4.4 Etwas syntaktischer Zucker...

        2.4.5 Auswertung konditionaler Ausdrücke

        2.4.6 In der Kürze liegt die Würze

      2.5 Definition von Konstanten

      2.6 DRY: Don’t Repeat Yourself!

        2.6.1 DRY durch Konstantendefinitionen

        2.6.2 DRY Redux

      2.7 Bedeutung von Funktions- und Konstantendefinitionen

      2.8 Programmieren ist mehr als das Regelverstehen!

    3 Systematischer Programmentwurf

      3.1 Funktionale Dekomposition

      3.2 Vom Problem zum Programm

      3.3 Systematischer Entwurf mit Entwurfsrezepten

        3.3.1 Testen

        3.3.2 Informationen und Daten

        3.3.3 Entwurfsrezept zur Funktionsdefinition

        3.3.4 Programme mit vielen Funktionen

      3.4 Information Hiding

      3.5 Signaturen als Teil des Codes

    4 Batchprogramme und interaktive Programme

      4.1 Batchprogramme

      4.2 Interaktive Programme

        4.2.1 Das Universe Teachpack

    5 Datendefinition durch Alternativen: Summentypen

      5.1 Aufzählungstypen

      5.2 Aufzählungstypen mit überprüfbaren Signaturen

      5.3 Intervalltypen

      5.4 Summentypen

        5.4.1 Entwurf mit Summentypen

      5.5 Unterscheidbarkeit der Alternativen

    6 Datendefinition durch Zerlegung: Produkttypen

      6.1 Die posn Struktur

      6.2 Strukturdefinitionen

      6.3 Verschachtelte Strukturen

      6.4 Datendefinitionen für Strukturen

      6.5 Fallstudie: Ein Ball in Bewegung

      6.6 Tagged Unions und Maybe

      6.7 Erweiterung des Entwurfsrezepts

      6.8 Formale Signaturen für Produkttypen

    7 Datendefinition durch Alternativen und Zerlegung: Algebraische Datentypen

      7.1 Beispiel: Kollisionen zwischen Shapes

      7.2 Programmentwurf mit ADTs

      7.3 Refactoring von algebraischen Datentypen

    8 Bedeutung von BSL

      8.1 Wieso?

      8.2 Kontextfreie Grammatiken

        8.2.1 Beispiel einer kontextfreien Grammatik

        8.2.2 Syntax von EBNF in EBNF

        8.2.3 Konstruktion von Ableitungsbäumen

      8.3 Syntax von BSL

      8.4 Die BSL Kernsprache

      8.5 Werte und Umgebungen

      8.6 Auswertungspositionen und die Kongruenzregel

      8.7 Nichtterminale und Metavariablen - Keine Panik!

      8.8 Bedeutung von Programmen

      8.9 Bedeutung von Ausdrücken

        8.9.1 Bedeutung von Funktionsaufrufen

        8.9.2 Bedeutung von Konstanten

        8.9.3 Bedeutung konditionaler Ausdrücke

        8.9.4 Bedeutung von Strukturkonstruktoren und Selektoren

      8.10 Reduktion am Beispiel

      8.11 Bedeutung von Daten und Datendefinitionen

      8.12 Refactoring von Ausdrücken und Schliessen durch Gleichungen

    9 Daten beliebiger Größe

      9.1 Rekursive Datentypen

      9.2 Programmieren mit rekursiven Datentypen

      9.3 Formale Signaturen für rekursive Datentypen

      9.4 Listen

        9.4.1 Listen, hausgemacht

        9.4.2 Listen aus der Konserve

        9.4.3 Die list Funktion

        9.4.4 Datentypdefinitionen für Listen

        9.4.5 Aber sind Listen wirklich rekursive Datenstrukturen?

        9.4.6 Natürliche Zahlen als rekursive Datenstruktur

      9.5 Mehrere rekursive Datentypen gleichzeitig

      9.6 Entwurfsrezept für Funktionen mit rekursiven Datentypen

      9.7 Refactoring von rekursiven Datentypen

      9.8 Programmäquivalenz und Induktionsbeweise

    10 Pattern Matching

      10.1 Pattern Matching am Beispiel

      10.2 Pattern Matching allgemein

        10.2.1 Syntax von Pattern Matching

        10.2.2 Bedeutung von Pattern Matching

        10.2.3 Reduktion von Pattern Matching

        10.2.4 Pattern Matching Fallstricke

    11 Quote und Unquote

      11.1 Quote

      11.2 Symbole

      11.3 Quasiquote und Unquote

      11.4 S-Expressions

      11.5 Anwendungsbeispiel: Dynamische Webseiten

    12 Sprachunterstützung für Datendefinitionen und Signaturen

      12.1 Ungetypte Sprachen

      12.2 Dynamisch getypte Sprachen

      12.3 Dynamisch überprüfte Signaturen und Contracts

      12.4 Statisch getypte Sprachen

    13 Sprachunterstützung für Algebraische Datentypen

      13.1 ADTs mit Listen und S-Expressions

      13.2 ADTs mit Strukturdefinitionen

      13.3 ADTs mit define-type

      13.4 Ausblick: ADTs mit Zahlen

      13.5 Diskussion

      13.6 Ausblick: ADTs mit Dictionaries

    14 DRY: Abstraktion überall!

      14.1 Abstraktion von Konstanten

      14.2 Funktionale Abstraktion

      14.3 Funktionen als Funktionsparameter

      14.4 Abstraktion in Signaturen, Typen und Datendefinitionen

        14.4.1 Abstraktion in Signaturen

        14.4.2 Signaturen für Argumente, die Funktionen sind

        14.4.3 Funktionen höherer Ordnung

        14.4.4 Polymorphe Funktionen höherer Ordnung

        14.4.5 Abstraktion in Datendefinitionen

        14.4.6 Grammatik der Typen und Signaturen

      14.5 Lokale Abstraktion

        14.5.1 Lokale Funktionen

        14.5.2 Lokale Konstanten

        14.5.3 Intermezzo: Successive Squaring

        14.5.4 Lokale Strukturen

        14.5.5 Scope lokaler Definitionen

      14.6 Funktionen als Werte: Closures

      14.7 Lambda, die ultimative Abstraktion

      14.8 Wieso abstrahieren?

    15 Programmieren mit Higher-Order Funktionen

      15.1 Funktionskomposition und "Point-Free Style"

      15.2 Currying und Typisomorphien von Funktionstypen

      15.3 Map, filter, flatmap

      15.4 Konstruktion von Listen mit unfold

      15.5 Fold und unfold zusammen, Deforestation

      15.6 Verallgemeinerung von fold und unfold auf beliebige algebraische Datentypen

    16 Bedeutung von ISL+

      16.1 Syntax von Core-ISL+

      16.2 Werte und Umgebungen

      16.3 Bedeutung von Programmen

      16.4 Auswertungspositionen und die Kongruenzregel

      16.5 Bedeutung von Ausdrücken

        16.5.1 Bedeutung von Funktionsaufrufen

        16.5.2 Bedeutung von lokalen Definitionen

        16.5.3 Bedeutung von Konstanten

      16.6 Scope

    17 Generative Rekursion

      17.1 Wo kollidiert der Ball?

      17.2 Schnelles Sortieren

      17.3 Entwurf von generativ rekursiven Funktionen

      17.4 Terminierung

    18 Akkumulation von Wissen

      18.1 Beispiel: Relative Distanz zwischen Punkten

      18.2 Beispiel: Suche in einem Graphen

      18.3 Entwurf von Funktionen mit Akkumulatoren

        18.3.1 Wann braucht eine Funktion einen Akkumulator

        18.3.2 Template für Funktionen mit Akkumulatoren

        18.3.3 Die Akkumulator-Invariante

        18.3.4 Implementation der Akkumulator-Invariante

        18.3.5 Nutzung des Akkumulators