Einleitung

Programme und Algorithmen

Deutsch als Programmiersprache

§6 (2) …Der Zuteilungsdivisor ist so zu bestimmen, dass insgesamt so viele Sitze auf die Landeslisten entfallen, wie Sitze zu vergeben sind. Dazu wird zunächst die Gesamtzahl der Zweitstimmen aller zu berücksichtigenden Landeslisten durch die Zahl der jeweils nach Absatz 1 Satz 3 verbleibenden Sitze geteilt. Entfallen danach mehr Sitze auf die Landeslisten, als Sitze zu vergeben sind,…

§6 (5) Die Zahl der nach Absatz 1 Satz 3 verbleibenden Sitze wird so lange erhöht, bis jede Partei bei der zweiten Verteilung der Sitze nach Absatz 6 Satz 1 mindestens die bei der ersten Verteilung nach den Absätzen 2 und 3 für sie ermittelten zuzüglich der in den Wahlkreisen errungenen Sitze erhält, die nicht nach Absatz 4 Satz 1 von der Zahl der für die Landesliste ermittelten Sitze abgerechnet werden können.

https://www.gesetze-im-internet.de/bwahlg/__6.html

Struktur durch Klammern, ist doch klar

Beispiel: mehrsprachige Projekte

ein typisches Projekt besteht aus:

und das ist noch nicht die ganze Wahrheit:

nenne weitere Sprachen, die üblicherweise in einem solchen Projekt vorkommen

In / Into

Sprache

Wie unterschiedlich sind Sprachen?

Konzepte

Paradigmen

Ziele der LV

Arbeitsweise: Methoden, Konzepte, Paradigmen

Ziel:

Beziehungen zu anderen LV

Anwendungsspezifische Sprachen und Paradigmen:

Organisation

Literatur

Zum Vergleich/als Hintergrund:

Inhalt

(nach Sebesta: Concepts of Programming Languages)

Haus-Aufgaben

WS23: (1 oder 2) und (4 oder 5) und 7

  1. Lesen Sie E. W. Dijkstra: On the foolishness of "natural language programming" https://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/EWD667.html

    und beantworten Sie

    • womit wird “einfaches Programmieren” fälschlicherweise gleichgesetzt?

    • welche wesentliche Verbesserung brachten höhere Programmiersprachen, welche Eigenschaft der Maschinensprachen haben sie trotzdem noch?

    • warum sollte eine Schnittstelle narrow sein?

    • welche formalen Notationen von Vieta, Descartes, Leibniz, Boole sind gemeint? (jeweils: Wissenschaftsbereich, (heutige) Bezeichnung der Notation, Beispiele)

    • warum können Schüler heute das lernen, wozu früher nur Genies in der Lage waren?

    • Übersetzen Sie den Satz “the naturalness of …obvious”.

    Geben Sie dazu jeweils an:

    • die Meinung des Autors, belegt durch konkrete Textstelle und zunächst wörtliche, dann sinngemäße Übersetzung

    • Beispiele aus Ihrer Erfahrung

  2. zu John C. Reynolds: Some Thoughts on Teaching Programming and Programming Languages 2008, von An additional reason for teaching programming languages… bis Ende:

    • Warum wird auf Turing-Vollständigkeit verwiesen?

    • Geben Sie Beispiele aus Ihrer Erfahrung für problematische input formats, oder problemfreie.

    • partial list of the kind of capabilities…: ordnen Sie die Listenelemente konkreten Lehrveranstaltungen zu (bereits absolvierte oder noch kommende)

  3. zu Skriptsprachen: finde die Anzahl der "*.java"-Dateien unter $HOME/workspace, die den Bezeichner String enthalten (oder eine ähnliche Anwendung) (Benutze eine Pipe aus drei Unix-Kommandos.)

    Lösungen:

    find workspace/ -name "*.java" | xargs grep -l String       | wc -l
find workspace/ -name "*.java"   -exec grep -l String {} \; | wc -l

    Das dient als Wiederholung zur Benutzung von Unix (GNU/Linux): führen Sie vor:

    • eine Shell öffnen

    • in der Manpage von find die Beschreibung von -exec anzeigen. Finden Sie (mit geeignetem Shell-Kommandos) den Quelltext dieser Manpage, zeigen diesen an. (Wie benutzt man man? so: man man.)

    • was bedeutet der senkrechte Strich? in welcher Manpage steht das? in welcher Vorlesung war das dran?

    • erklären Sie https://xkcd.com/378/, führen Sie die vier genannten Editoren vor, in dem Sie jeweils eine einzeilige Textdatei erzeugen.

    Bei Vorführung (dann mit Screen-Sharing)

    • schwarze Schrift auf weißem Grund

    • große Schrift

  4. funktionales Programmieren in Haskell (http://www.haskell.org/)

    ghci
:set +t
length $ takeWhile (== '0') $ reverse $ show $ product [ 1 .. 100 ]

    • zeigen Sie (den Studenten, die das noch nicht gesehen haben), wo die Software (hier ghc) im Pool installiert ist, und wie man sie benutzt und die Benutzung vereinfacht (PATH)

    • Werten Sie den angegebenen Ausdruck aus sowie alle Teilausdrück ([1..100], product [1..100], usw.

    • den Typ von reverse durch ghci anzeigen lassen

    • nach diesem Typ in https://hoogle.haskell.org/ suchen. (Einschränken auf package:base) Die anderen (drei) Funktionen dieses Typs aufrufen.

    • eine davon erzeugt unendliche Listen, wie werden die im Speicher repräsentiert, wie kann man sie benutzen? (Am Beispiel zeigen.)

  5. PostScript

    42 42 scale 7 9 translate .07 setlinewidth .5 setgray/c{arc clip fill
setgray}def 1 0 0 42 1 0 c 0 1 1{0 3 3 90 270 arc 0 0 6 0 -3 3 90 270
arcn 270 90 c -2 2 4{-6 moveto 0 12 rlineto}for -5 2 5{-3 exch moveto
9 0 rlineto}for stroke 0 0 3 1 1 0 c 180 rotate initclip}for showpage

    In eine Text-Datei what.ps schreiben (vgl. Aufgabe [edit]) ansehen mit gv what.ps (im Menu: State \(\to\) watch file).

    Mit Editor Quelltext ändern, Wirkung betrachten.

    • Ändern Sie die Strich-Stärke!

    • wie funktioniert die Steuerung einer Zählschleife?

    • warum ist PostScript: imperativ? strukturiert? prozedural?

    • führen Sie wenigstens ein weiteres ähnliches PostScript-Programm vor (kurzer Text, aber nichttriviale Rechnung). Quelle angeben, Programmtext erklären!

    • nennen Sie einige Aspekte von PS, die in PDF übernommen wurden (Beantworten Sie anhand der Original-Dokumentation.)

    • Warum sollte man niemals “online und ganz umsonst PS to PDF converter” benutzen?

  6. In SICP 1.1 werden drei Elemente der Programmierung genannt. Illustrieren Sie diese Elemente durch Beispiele aus http://99-bottles-of-beer.net/

    Führen Sie nach Möglichkeit vor (im Pool, nicht in irgendeiner Web-Oberfläche von Dritt-Anbietern).

  7. Stellen Sie Ihren Browser datenschutzgerecht ein (Wahl des Browsers, der Default-Suchmaschine, Blockieren von Schadsoftware.)

    In einem neuen Firefox-Profil (about:profiles) ausprobieren und diskutieren: Umatrix (dessen Log betrachten), Temporary Containers.

    Vgl.

    https://restoreprivacy.com/firefox-privacy/

    (hat selbst viele Tracker!) und weitere.

Syntax von Programmiersprachen

Programme als Bäume

Token-Klassen

alle Token einer Klasse bilden eine formale Sprache.

Formale Sprachen

Beispiele:

Lexik (Bsp): numerische Literale

Spezifikation formaler Sprachen

man kann eine formale Sprache beschreiben:

Sprach-Operationen

Aus Sprachen \(L_1, L_2\) konstruiere:

Def: Sprache regulär \(:\iff\) kann durch diese Operationen aus endlichen Sprachen konstruiert werden.

Satz: Durchschnitt und Differenz braucht man dabei nicht.

Reguläre Sprachen/Ausdrücke

Die Menge \(E(\Sigma)\) der regulären Ausdrücke
über einem Alphabet (Buchstabenmenge) \(\Sigma\)
ist die kleinste Menge \(E\), für die gilt:

Jeder solche Ausdruck beschreibt eine reguläre Sprache.

Beispiele/Aufgaben zu regulären Ausdrücken

Wir fixieren das Alphabet \(\Sigma=\{a,b\}\).

Erweiterte reguläre Ausdrücke

  1. zusätzliche Operatoren (Durchschnitt, Differenz, Potenz),

    die trotzdem nur reguläre Sprachen erzeugen

    Beispiel: \(\Sigma^* \setminus ( \Sigma^* ab \Sigma^*)^2\)

    ähnlich in Konfiguration der autotool-Aufgaben

  2. zusätzliche nicht-reguläre Operatoren

    Beispiel: exakte Wiederholungen \(L^{\fbox{$k$}} := \{ w^k \mid w\in L \}\)

    Bsp.: \((ab^*)^{\fbox{2}} = \{aa, abab, abbabb, ab^3ab^3, \dots\}\notin\mathsf{REG}\)

  3. Markierung von Teilwörtern, definiert (evtl. nicht-reguläre) Menge von Wörtern mit Positionen darin

Implementierung regulärer Ausdrücke

Bemerkung zu Reg. Ausdr.

Wie beweist man \(w\in \operatorname{L}(X)\)?

(Wort \(w\) gehört zur Sprache eines regulären Ausdrucks \(X\))

Beispiel: \(w = abba, X = (ab^*)^*\).

\(w = abb\cdot a = ab^2 \cdot a b^0 \in ab^* \cdot ab^* \subseteq (ab^*)^2 \subseteq (ab^*)^*\).

Übungen zu Lexik (Testfragen)

(ohne Wertung, zur Wiederholung und Unterhaltung)

Aufgaben zu regulären Ausdrücken: autotool. Das ist Wiederholung aus VL Theoretische Informatik—Automaten und Formale Sprachen. Fragen dazu notfalls im Git.Imn-Tracker.

Hausaufgaben

WS 23: KW 44 keine Ü wegen Feiertag. Ein bis zwei Aufgaben von 3 …7 können in KW 45 präsentiert werden.

  1. Für jedes Monoid \(M=(D,\cdot,1)\) definieren wir die Teilbarkeits-Relation \(u\mid w := \exists v: u \cdot v = w\)

    Geben Sie Beispiele \(u\mid w\), \(\neg(u\mid w)\) an in den Monoiden

    • \((\mathbb{N},+,0)\)

    • \((\mathbb{Z},+,0)\)

    • \((\mathbb{N},\cdot,1)\)

    • \((\{a,b\}^*,\cdot,\epsilon)\)

    • \((2^\mathbb{N},\cup,\emptyset)\)

    Zeigen Sie (nicht für ein spezielles Monoid, sondern allgemein): die Relation \(\mid\) ist reflexiv und transitiv.

    Ist sie antisymmetrisch? (Beweis oder Gegenbeispiel.)

    NB: Beziehung zur Softwaretechnik:

    • Monoid ist die Schnittstelle (API, abstrakter Datentyp),

    • \((\mathbb{N},0,+)\) ist eine Implementierung (konkreter Datentyp).

    • allgemein zeigen bedeutet: nur die in den Axiomen des ADT (API-Beschreibung) genannten Eigenschaften benutzen

  2. Zeichnen Sie jeweils das Hasse-Diagramm dieser Teilbarkeitsrelation

    • für \((\mathbb{N},+,0)\), eingeschränkt auf \(\{0,1,\dots,4\}\)

    • für \((\mathbb{N},\cdot,1)\), eingeschränkt auf \(\{0,1,\dots,10\}\)

    • für \((2^{\{p,q,r\}},\cup,\emptyset)\)

    • für \((\{a,b\}^*,\cdot,\epsilon)\) auf \(\{a,b\}^{\le 2}\)

    Geben Sie eine Halbordnung auf \(\{0,1,2\}^2\) an, deren Hasse-Diagramm ein auf der Spitze stehendes Quadratnetz ist.

    Diese Halbordnung soll intensional angegeben werden (durch eine Formel), nicht extensional (durch Aufzählen aller Elemente).

  3. Führen Sie vor (auf Rechner im Pool Z430, vorher von außen einloggen und probieren)

    Editieren, Kompilieren, Ausführen eines kurzen (maximal 3 Zeilen) Pascal-Programms

    Der Compiler fpc (https://www.freepascal.org/) ist installiert (/usr/local/waldmann/opt/fpc/latest).

    (Zweck dieser Teilaufgabe ist nicht, daß Sie Pascal lernen, sondern der Benutzung von ssh, evtl. tmux, Kommandozeile (PATH), Text-Editor wiederholen)

    Zu regulären Ausdrücke für Tokenklassen in der Standard-Pascal-Definition https://archive.org/details/iso-iec-7185-1990-Pascal/

    Welche Notation wird für unsere Operatoren \(+\) und Stern benutzt? Was bedeuten die eckigen Klammern?

    In Ihrem Beispiel-Programm: erproben Sie mehrere (korrekte und fehlerhafte) Varianten für Gleitkomma-Literale. Vergleichen Sie Spezifikation (geben Sie den passenden Abschnitt der Sprachdefinition an) und Verhalten des Compilers.

    Dieser Compiler (fpc) ist in Pascal geschrieben. Was bedeutet das für: Installation des Compilers, Entwicklung des Compilers?

  4. Führen Sie vor (wie und warum: siehe Bemerkungen vorige Aufgabe): Editieren, Kompilieren (javac), Ausführen (java) eines kurzen (maximal 3 Zeilen) Java-Programms.

    Suchen und buchmarken Sie die Java Language Specification (Primärquelle in der aktuellen Version) Beantworten Sie damit (und nicht mit Hausaufgabenwebseiten und anderen Sekundärquellen):

    gehören in Java

    • null

    • Namen für Elemente von Aufzählungstypen

    zur Tokenklasse Literal, reserviertes Wort (Schlüsselwort), Bezeichner (oder evtl. anderen)?

    Wo stehen die Token-Definitionen im javac-Compiler? https://hg.openjdk.java.net/jdk/jdk15/file/ (bzw. aktuelle Version)

    In Ihrem Beispiel-Programm: erproben Sie verschiedene Varianten von Ganzzahl-Literalen (siehe vorige Aufgabe)

  5. Führen Sie vor (wie vorige Aufgaben): Kompilation und Ausführung eines sehr kurzen Ada-Programms

    with Ada.Text_IO; use Ada.Text_IO;
procedure floating is
begin put_line (float'image( 2)); -- fehlerhafter Quelltext!
end floating;

    Verwenden Sie den GNU Ada Translator, ist Teil von GCC (GNU Compiler Collection).

    Ist im Pool installliert, siehe https://www.imn.htwk-leipzig.de/~waldmann/etc/pool/

    Aufrufen mit gnatmake floating.adb (kompilieren und linken), ausführen mit ./floating.

    Erläutern Sie die Fehlermeldung durch Verweis auf den Sprachstandard. Setzen Sie passende Literale ein (ändern Sie den Rest des Programms nicht). Probieren Sie dabei alle Zweige und Optionen in den regulären Ausdrücken des Standards (2.4.1).

  6. Im WS22 hatten Teilnehmer dieser LV diese Fehler im GNU Ada Translator (gnat, Teil von gcc) gefunden:

    Untersuchen Sie ähnliches für Compiler für andere Sprachen.

  7. Suchen und diskutieren Sie Wadler’s law (of language design).

    Am Entwurf welcher Programmiersprachen war der Autor beteiligt? Welche Sprache hat er in einem aktuellen Lehrbuch benutzt?

    Untersuchen Sie für (wenigstens) Java und Haskell, ob Block-Kommentare geschachtelt werden können. Belegen Sie durch

    • Sprachstandard (exakte Definition von Kommentaren)

    • und eigene Beispiele (einfachste Programme, die vom Compiler akzeptiert oder abgelehnt werden)

  8. Gelten die Aussagen von Cox (2007) (but it’s slow in…) jetzt immer noch? Überprüfen Sie das praktisch (die Testfälle aus dem zitierten Paper oder ähnliche).

Syntaxbäume

Wort-Ersetzungs-Systeme

Berechnungs-Modell (Markov-Algorithmen)

Syntax: Programm ist Regelmenge \(R \subseteq \Sigma^* \times \Sigma^*\),
Semantik: die 1-Schritt-Ableitungsrelation \(\to_R\), Hülle \(\to_R^*\)

\(u \to_R v \iff \exists x,z\in\Sigma^*, (l,r) \in R: u = x \cdot l\cdot z \wedge x \cdot r \cdot z = v\).

Grammatiken

Grammatik \(G\) besteht aus:

Grammatik
  { terminale 
       = mkSet "abc"
  , variablen
       = mkSet "SA"
  , start = 'S'
  , regeln = mkSet
       [ ("S", "abc")
       , ("ab", "aabbA")
       , ("Ab", "bA")
       , ("Ac", "cc")
       ]
  }

von \(G\) erzeugte Sprache: \(L(G) = \{ w \mid S \to_R^* w \wedge w \in \Sigma^* \}\).

Formale Sprachen: Chomsky-Hierarchie

Tokenklassen sind meist reguläre Sprachen.

Syntax von Programmiersprachen meist kontextfrei.

Zusatzbedingungen (Bsp: Benutzung von Bezeichnern nur nach Deklaration) meist Teil der statischen Semantik

(Menge der stat. korrekten Programme ist nicht kontextfrei)

Typ-3-Grammatiken

(\(=\) rechtslineare Grammatiken)

jede Regel hat die Form

(vgl. lineares Gleichungssystem)

Beispiele

Sätze über reguläre Sprachen

Für jede Sprache \(L\) sind die folgenden Aussagen äquivalent:

Beweispläne:

Kontextfreie Sprachen

Def (Wdhlg): \(G\) ist kontextfrei (Typ-2), falls \(\forall (l,r) \in R(G): l \in V^1\)

geeignet zur Beschreibung von Sprachen mit hierarchischer Struktur.

Anweisung -> Bezeichner = Ausdruck
    | if Ausdruck then Anweisung else Anweisung
Ausdruck -> Bezeichner | Literal
    | Ausdruck Operator Ausdruck

Bsp: korrekt geklammerte Ausdrücke: \(G = ( \{ a,b\}, \{S\}, S, \{ S \to aSbS, S \to \epsilon \} )\).

Bsp: Palindrome: \(G = ( \{ a,b\}, \{S\}, S, \{ S \to aSa, S \to bSb, S \to \epsilon )\).

Bsp: alle Wörter \(w\) über \(\Sigma=\{a,b\}\) mit \(|w|_a = |w|_b\)

Klammer-Sprachen

Abstraktion von vollständig geklammerten Ausdrücke mit zweistelligen Operatoren

(4*(5+6)-(7+8)) \(\Rightarrow\) (()()) \(\Rightarrow aababb\)

Höhendifferenz: \(h : \{a,b\}^* \to \mathbb{Z}: w \mapsto |w|_a - |w|_b\)

Präfix-Relation: \(u \le w :\iff \exists v: u\cdot v = w\)

Dyck-Sprache: \(D=\{w \mid h(w)=0 \wedge \forall u\le w: h(u)\ge 0\}\)

CF-Grammatik: \(G = (\{a,b\},\{S\},S,\{S\to\epsilon,S\to aSbS\})\)

Satz: \(L(G)=D\). Beweis (Plan):

\(L(G)\subseteq D\) Induktion über Länge der Ableitung

\(D\subseteq L(G)\) Induktion über Wortlänge

(erweiterte) Backus-Naur-Form

Backus-Naur-Form (BNF) \(\approx\) kontextfreie Grammatik

<assignment> -> <variable> = <expression>
<number> -> <digit> <number> | <digit>

Erweiterte BNF

kann in BNF übersetzt werden

Ableitungsbäume für CF-Sprachen

Def: ein geordneter Baum \(T\) mit Markierung \(m: T \to \Sigma\cup\{\epsilon\}\cup V\) ist Ableitungsbaum für eine CF-Grammatik \(G\), wenn:

Ableitungsbäume (II)

Eindeutigkeit

Assoziativität

Assoziativität (II)

Präzedenzen

Zusammenfassung Operator/Grammatik

Ziele:

Festlegung:

Realisierung in CFG:

Hausaufgaben

WS 23: Aufgabe 6. falls Zeit ist: 4 oder 5

  1. Definition: für ein Wortersetzungssystem \(R\):

    Die Menge der \(R\)-Normalformen eines Wortes \(x\) ist: \(\textsf{Nf}(R,x):=\{y \mid x\to_R^* y \wedge \neg\exists z: y\to_R z\}\)

    Für das \(R=\{ab\to baa\}\) über \(\Sigma=\{a,b\}\):

    bestimmen Sie die \(R\)-Normalformen von

    • \(a^3 b\), allgemein \(a^kb\),

    • \(a b^3\), allgemein \(a b^k\),

    die allgemeinen Aussagen exakt formulieren, für \(k=3\) überprüfen, durch vollständige Induktion beweisen.

  2. Für Alphabet \(\Sigma=\{a,b\}\), Sprache \(E=\{w : w\in \Sigma^* \wedge |w|_a=|w|_b \}\), Grammatik \(G=(\Sigma,\{S\}, S,\{ S\to \epsilon, S\to SS, S\to aSb, S\to bSa \})\):

    • Geben Sie ein \(w\in E\) mit \(|w|=8\) an mit zwei verschiedenen \(G\)-Ableitungsbäumen.

    • Beweisen Sie \(L(G)\subseteq E\) durch strukturelle Induktion über Ableitungsbäume.

    • Beweisen Sie \(E\subseteq L(G)\) durch Induktion über Wortlänge. Benutzen Sie im Induktionsschritt diese Fallunterscheidung für \(w\in E\): hat \(w\) einen nicht leeren echten Präfix \(u\) mit \(u\in E\)? Wenn ja, dann beginnt eine Ableitung für \(w\) mit \(S\to SS\). Wenn nein, dann mit welcher Regel?

  3. Vergleichen sie Definitionen und Bezeichnungen für phrase structure grammars Noam Chomsky: Three Models for the Description of Language, 1956, Abschnitt 3, https://chomsky.info/articles/, mit den heute üblichen (kontextfreie Grammatik, Ableitung, erzeugte Sprache, Ableitungsbaum)

    Erläutern Sie The rule (34) … cannot be incorporated… (Ende Abschnitt 4.1)

  4. vergleichen Sie die Syntax-Definitionen von Fortran (John Backus 1956) und Algol (Peter Naur 1960),

    Quellen: Historic Documents in Computer Science, collected by Karl Kleine, http://web.eah-jena.de/~kleine/history/ (benutze Wayback Machine https://web.archive.org/)

    Führen Sie Kompilation und Ausführen eines Fortran-Programms vor (im Pool ist gfortran installiert, als Teil von GCC (GNU Compiler Collection))

    Verwenden Sie dabei nur einfache Arithmetik und einfache Programmablaufsteuerung.

    Geben Sie den Assembler-Code aus (Option -S). Vergleichen Sie mit Assembler-Code des entsprechenden C-Programms.

  5. für die Java-Grammatik (nach JLS in aktueller Version)

    • es werden tatsächlich zwei Grammatiken benutzt (lexikalische, syntaktische), zeigen Sie deren Zusammenwirken an einem einfachen Beispiel (eine Ableitung, bei der in jeder Grammatik nur wenige Regeln benutzt werden)

    • bestimmen Sie den Ableitungsbaum (bzgl. der syntaktischen Grammatik) für das übliche hello world-Programm,

    • Beispiele in jshell vorführen. Wie lautet die Grammatik für die dort erlaubten Eingaben? Ist das Teil der JLS? Wenn nein, finden Sie eine andere Primärquelle.

  6. bzgl. der eindeutigen Grammatik für arithmetische Ausdrücke (aus diesem Skript):

    • Ableitungsbaum für 1*2-3*4

    • Grammatik erweitern für geklammerte Ausdrücke,

      Eindeutigkeit begründen,

      Ableitungsbaum für 1*(2-3)*4 angeben

    arithmetische Ausdrücke in Java:

    • welche Variable der Java-Grammatik erzeugt arithmetische Ausdrücke?

    • Ableitungsbaum für 1*(2-3)*4 von dieser Variablen aus angeben (und live vorführen durch Verfolgung der URLs der Grammatik-Variablen)

    • Beziehung herstellen zu den Regeln auf Folie Zusammenfassung Operator/Grammatik.

Semantik von Programmiersprachen

Statische und dynamische Semantik

Bsp statische/dynamische Semantik

Benutzung eines nicht deklarierten Namens:

Attributgrammatiken (I)

Attributgrammatiken (II)

ein Ableitungsbaum \(T\) mit Annotationen \(A\) ist
korrekt bezüglich einer Attributgrammatik \((G,E)\), wenn

Plan:

Ursprung: Donald Knuth: Semantics of Context-Free Languages, (Math. Systems Theory 2, 1968)

technische Schwierigkeit: Existenz und effiziente Berechnung der Attributwerte

Donald E. Knuth

https://www-cs-faculty.stanford.edu/~uno/

Arten von Attributen

Attributgrammatiken–Beispiele

Konkrete und abstrakte Syntax

Typisierung von Funktionsaufrufen

Bsp. Operationale Semantik: Keller

Kompilation für Kellermaschine

Attributgrammatiken mit SableCC

Bemerkungen (häufige/nicht offensichtliche Fehlerquellen)

Kommentar: in Java fehlen: algebraische Datentypen, Pattern Matching, Funktionen höherer Ordnung. Deswegen muß SableCC das simulieren — das sieht nicht schön aus. Die richtige Lösung sehen Sie später im Compilerbau.

Abstrakter Syntaxbaum, Interpreter: https://www.imn.htwk-leipzig.de/~waldmann/edu/ws11/cb/folien/main/node12.html, Kombinator-Parser: https://www.imn.htwk-leipzig.de/~waldmann/edu/ws11/cb/folien/main/node70.html

Auswertung arithmetischer Ausdrücke

(das ist ungefähr die erste VL Compilerbau)

Kombinator-Parser f. arith. Ausdrücke

Hausaufgaben

WS 23: Aufgabe 1 hier (und Aufgabe 6 von voriger Woche)

  1. arithmetische Ausdrücke (keine Programmablaufsteuerung), Beispiel

    class C { static int f (int x) {return 3*x; }}

    von Java nach Java-Bytecode übersetzen mit javac und Resultat betrachten mit javap -c.

    Zeigen Sie durch ähnnliche Beispiele, daß richtig behandelt werden:

    • Links-Assoziativität der Subtraktion

    • Punkt- vor Strich-Rechnung

    Vergleichen Sie den Bytecode mit dem Verfahren aus VL.

    Schlagen Sie für einige der vorkommenden Bytecode-Befehle die Semantik in der JVM-Spezifikation (aktuelle Version) nach.

    Erläutern Sie die JVM-Befehle dup, pop. Geben Sie Java-Programme an, in dessen Bytecode diese vorkommen.

  2. zum angegebenen Beispiel Sablecc

    • Test vorführen.

    • das dabei verwendete Makefile erklären.

      Was ist die Semantik der Ziele und Regeln eines Makefiles? Was ist bei der Syntax zu beachten? (Hinweis: ein besonderer Whitespace)

    • Grammatik ergänzen: Multiplikation.

      Eindeutigkeit der Grammatik und semantisch korrekte Auswertung vorführen und begründen.

    • (in der Übung, jeder selbst) Subtraktion, Klammern.

  3. (Zusatz) Generalized Algebraic Data Types (ein Thema aus OS FKPS SS22)

    Verwenden/ergänzen Sie diesen AST-Typ

    {-# language GADTs #-}
data Exp a where
  Literal :: Integer -> Exp Integer
  Plus :: 
    Exp Integer -> Exp Integer -> Exp Integer
  Greater :: 
    Exp Integer -> Exp Integer -> Exp Bool
  Ifthenelse :: Exp Bool -> ...

    Erklären Sie den Fehler in Ifthenelse (Literal 0) (Literal 1) (Literal 2). Rufen Sie Ifthenelse typkorrekt auf.

    Passen Sie den Interpreter (die Funktion value) an.

  4. (Zusatz) Kombinatorparser (ein Thema aus VL Compilerbau SS22)

    einfache Beispiele vorführen und erklären (elementare Parser char, eof; Kombinatoren (>>), many, sepBy; ggf. buildExpressionParser)

    cabal install --lib parsec
ghci
import Text.Parsec
parseTest (many (char 'f') >> many (char 'o')) "foobar"

Typen

Der Nutzen der statische Typisierung

Typ-Information und Laufzeitdaten

Historische Entwicklung

Überblick

Zahlenbereiche

Aufzählungstypen

können einer Teilmenge ganzer Zahlen zugeordnet werden

Designfragen:

Maßeinheiten in F#

Zeichen und Zeichenketten

Zusammengesetzte Typen

Typ \(=\) Menge, Zusammensetzung \(=\) Mengenoperation:

Produkttypen (Records)

Summen-Typen

Vereinigung mittels Interfaces

\(I\) repräsentiert die Vereinigung von \(A\) und \(B\):

interface I { }
class A implements I { int foo; }
class B implements I { String bar; }

Notation dafür in Scala (M. Odersky, 2004, https://scala-lang.org/)

abstract class I
case class A (foo : Int) extends I
case class B (bar : String) extends I

Verarbeitung durch Pattern matching

def g (x : I): Int = x match {
    case A(f) => f + 1
    case B(b) => b.length()  }

Rekursive algebraische Datentypen

Potenz-Typen

Felder (Arrays)

Felder in C

int main () {
    int a [10][10]; 
    a[3][2] = 8;
    a[2][12] = 5;
    printf ("%d\n", a[3][2]);   
}

Felder in Javascript

Felder in Java

int [][] feld = 
         { {1,2,3}, {3,4}, {5}, {} };
for (int [] line : feld) {
    for (int item : line) {
       System.out.print (item + " ");  }
    System.out.println (); }

Kosten der Bereichsüberprüfungen

Felder in C#

Übung: Unterschiede zwischen

in

Verweistypen

Verweis- und Wertsemantik in C#

Algebraische Datentypen in Pascal, C

Rekursion unter Verwendung von Verweistypen

Pascal:

type Tree = ^ Node ;
type Tag = ( Leaf, Branch );
type Node = record case t : Tag of
  Leaf : ( key : T ) ; 
  Branch : ( left : Tree ; right : Tree );
end record;

C: ähnlich, benutze typedef

Null-Zeiger: der Milliarden-Dollar-Fehler

Hausaufgaben Typen

WS 23: INM/MIM jeweils eine von 1/2, 3/4. Zusatz: eine von 5/6/7

  1. für Mengen \(A=\emptyset,B=\{0\},C=\{1,2\},D=\{3,4,5\},E=\{6,7,8,9\}\),

    geben Sie an:

    • alle Elemente von \(A\times C, B\times D, A\cup B, B^A, A^B,C^B,B^C,C^D\)

    • ein Element aus \((C\times D)^E\)

    • die Kardinalitäten von \((C\times D)^E, C^{D\cup E}\)

    ähnliche Aufgabenstellungen vorbereiten, die Sie dann in der Übung den anderen Studenten stellen.

  2. Geben Sie eine Isomorphie zwischen den Mengen \((A^B)^C\) und \(A^{(B\times C)}\) an.

    Illustrieren Sie das durch konkrete kleine endliche Mengen \(A,B,C\).

    Diskutieren Sie auch die Fälle, daß \(A,B,C\) leer sind.

    Diese Isomorphie wird in Haskell durch die Funktion curry realisiert. Zeigen Sie das in ghci. Verwenden Sie dabei für \(A,B,C\) paarweise verschiedene Typen. Wie lautet die Umkehrfunktion?

    Begründen Sie, daß \((A^B)^C\) nicht immer isomorph ist zu \(A^{(B^C)}\). In welchen Fällen besteht Isomorphie?

  3. zur Folie Felder in C:

    Programm kompilieren, ausführen.

    Assembler-Code ausgeben und erklären (gcc -S oder clang -S)

    Unterschiede zwischen -O0 und -O3?

  4. zu Folie Felder in Javascript:

    das zitierte Beispiel vorführen (node), mit Verweisen auf Sprachstandard erklären.

    Untersuchen Sie die Aussage eines Kommentators: Typescript prevents all of these errors. (Lokal im Pool: npm install typescript; npx tsc, auch ts-node ist nützlich. Keine Online-Dienste verwenden.)

  5. Erläutern und variieren Sie das Verhalten von

    #include <stdio.h>
typedef union { double foo; long int bar; } U;
int main () 
  { U x;
    x.bar =   0; printf ("%ld\n", x.bar);
    x.foo = 7.0; printf ("%ld\n", x.bar);
  }

    Wiederholen Sie dabei die Gleitkomma-Darstellung (genau — welche Bits bedeutet was?)

    Fügen Sie zu der Vereinigung einen weiteren Typ der gleichen Länge hinzu, z.B. Array von Bytes;

    sowie einen Typ anderer Länge, z.B. float.

  6. zu Folie Kosten der Bereichsprüfungen und dort angegebener Quelle:

    führen Sie den Testfall vor, analysieren Sie die Ausgabe des Disassemblers (im Pool installiert). Vergleichen Sie verschiedene JIT/JVM-Versionen.

    Schreiben Sie das äquivalente Matrix-Multiplikationsprogramm in C, betrachten Sie den Assembler-Code, vergleichen Sie.

  7. Beispiele vorführen, Spezifikation zeigen (Primärquellen) zum Vergleich von

    • Data.Maybe (Haskell),

    • java.util.Optional,

    • nullable in C#

Bezeichner, Bindungen, Bereiche

Variablen

Namen in der Mathematik

in der Programmierung:

Konkrete Syntax von Namen

Deklaration und Definition

Typen für Variablen

Dynamisch typisierte Sprachen

Statisch typisierte Sprachen

Typdeklarationen

Typinferenz in C# und Java

Code-Inferenz

Konstanten

Lebensort und -Dauer von Name und Daten

Sichtbarkeit von Namen

Verdeckung von Deklarationen

Sichtbarkeit in JavaScript

Hausaufgaben

  1. Beobachten und erklären Sie die Ausgabe von

    #include <stdio.h>
int main (int argc, char **argv) {
  int x = 3;
  { printf ("%d\n", x);
    int x = 4;
    printf ("%d\n", x);
  }
  printf ("%d\n", x);
}

    schreiben Sie ein entsprechendes Java-Programm und vergleichen Sie (statische und dynamische Semantik: experimentell und mit Sprachspezifikation)

  2. Sichtbarkeit von Deklarationen in Javascript.

    Siehe Folie, Original-Dokumentation zeigen und Beispiele vorführen (node), ergänzen durch weitere Beispiele mit nicht offensichtlicher Semantik, Bsp: Variablen-Deklaration in einem Zweig einer Verzweigung.

    nur Sichtbarkeiten — Programmablaufsteuerung soll trival sein (keine Schleifen, keine Unterprogramme)

  3. frühere Folie Verweis- und Wertsemantik in C#: den angegebenen Testfall durchführen (mit Mono C# Shell, csharp), Lebensort (Stack, Heap) der Daten angeben, dann class durch struct ersetzen.

Ausdrücke

Definition, Abgrenzung

Vgl. Trennung (in Pascal, Ada)

Ü: wie in Java ausgedrückt? wie stark getrennt?

Syntax von Ausdrücken

wichtige Spezialfälle für Operatoren:

Wdhlg: Syntaxbaum, Präzedenz, Assoziativität.

Designfragen für Ausdrücke

Beziehungen zw. Ausdruck und Anweisung

Überladene Operatornamen

Automatische Typanpassungen

Wahrheitswerte in C, C++

Der Plus-Operator in Java

Explizite Typumwandlungen

sieht gleich aus und heißt gleich (cast), hat aber verschiedene Bedeutungen:

Typumwandlungen in Haskell

Der Zuweisungs-Operator

Weitere Formen der Zuweisung

(in C-ähnlichen Sprachen)

Teil-Ausdrücke mit Nebenwirkungen

(side effect; falsche Übersetzung: Seiteneffekt)

Auswertungsreihenfolgen

Ausdrucks-Semantik von C

Logische (Boolesche) Ausdrücke

Der ternäre Verzweigungs-Operator ?:

Übungen

  1. Gary Bernhardt: WAT (2012) https://www.destroyallsoftware.com/talks/wat

  2. Wiederholung Operator-Syntax:

  3. Was spricht dafür und dagegen, daß in einem Programmtext neue Operatoren definiert werden?

    In C++ darf man keine neuen Operatoren deklarieren, aber vorhandene Operatoren neu implementieren. Begründen Sie diese Design-Entscheidung.

Hausaufgaben

WS 23: (1 oder 3), 4, 5

  1. Konversion von int nach float in Java:

    1. Es gilt nicht \(\text{int}\subseteq\text{float}\), denn:

      • beide Mengen sind gleich groß (wie groß?)

      • und es gibt (viele) \(y\in\text{float}\setminus\text{int}\) (welche?)

    2. Geben Sie ein \(x\in\text{int} \setminus\text{float}\) explizit an.

      (eine ganze Zahl, die keine exakte Darstellung als float besitzt)

    3. Wo ist diese Konversion in der Sprachspezifikation (JLS) beschrieben?

    4. desgleichen für long zu double

    5. Gilt \(\text{int}\subseteq\text{double}\)? (nach JLS, nach IEEE-Standard)

  2. durch Verweis auf JLS erklären:

    • System.out.println ("H" + "a");
System.out.println ('H' + 'a');
    • char x = 'X'; int i = 0;
System.out.print (true  ? x : 0);
System.out.print (false ? i : x);
    • long x = 1000 * 1000 * 1000 * 1000;
long y = 1000 * 1000;
System.out.println ( x / y );
    • System.out.println 
    ((int) (char) (byte) -1);

    Quelle: Joshua Bloch, Neil Gafter: Java Puzzlers, Addison-Wesley, 2005.

  3. statische Semantik (Typisierung) und dynamische Semantik (Auswertung) dieses Programms (in C, in Java)

    int a = -4; int b = -3; int c = -2;
if (a < b < c) {
    printf ("aufsteigend");
}

    dazu den AST für a < b < c zeichnen und annotieren.

  4. UB (undefined behaviour) für C-Ausdrücke mit abhängigen Teilausdrücken zwischen Sequence Points:

    1. Finden Sie C- oder C++- Programme, bei denen

      • verschiedene Compiler (gcc, clang, g++, clang++)

      • ein Compiler bei verschiedenen Optionen (-O0, -O3)

      • verschiedene Versionen eines Compilers (im Pool: verschiedene gcc sind installiert)

      unterschiedliche Semantik realisieren. Beispiel:

      int y = 1; int z = (y=2) + (y=3);

    2. Wo ist dieses (undefined) Verhalten im (draft) C++-Standard beschrieben? (http://www.open-std.org/jtc1/sc22/wg21/)

    3. Vergleichen Sie mit Semantik des entsprechenden Java-Programms. (Ausführen, Bytecode ansehen, Sprachspezifikation)

    4. Wer ist Cthulhu, wo wohnt er (derzeit), was hat er vor? Seine Beziehung zu Semantik von C-Programmen ist Folklore (kann nur durch Internet-Quellen belegt werden).

  5. Verkürzte Auswertung bei logischen Operatoren in Java und JS (Tests mit jshell, node)

    1. einen Testfall angeben, der die verkürzte Auswertung bei || zeigt.

    2. Der Operator | verknüpft Zahlen bitweise. (Testfall angeben) Es gibt | auch für boolean. Worin besteht der Unterschied zu || ? (Testfall angeben)

    3. desgl. für &

    4. das gleiche für JS oder TS untersuchen

  6. Verkürzte Auswertung bei logischen Operatoren in Ada: Sprachstandard und Vorführung. Benutze GNAT (GNU Ada Translator) als Teil von GCC (GNU Compiler Collection), ist im Pool installiert

Semantik (Teil 2)

Dynamische Semantik

Anweisungen: Definition

Programm-Ablauf-Steuerung

Operationale Semantik: Sprünge

Axiomatische Semantik

Notation für f. Aussagen über Speicherbelegungen: Hoare-Tripel: { V } A { N }

Beispiel:{ x >= 5 } y := x + 3 { y >= 7 }

Beachte: {x >= 5} while (true) ; {x == 42}

Gültigkeit solcher Aussagen kann man

Eiffel

Bertrand Meyer, https://www.eiffel.com/

class Stack [G]     feature 
    count : INTEGER
    item : G is require not empty do ... end
    empty : BOOLEAN is do .. end
    full  : BOOLEAN is do .. end
    put (x: G) is
       require not full do ...
       ensure not empty
              item = x
              count = old count + 1

Beispiel sinngemäß aus: B. Meyer: Object Oriented Software Construction, Prentice Hall 1997

Sprachstandard: Eiffel: Analysis, design and programming language ECMA-367 (2nd edition, June 2006)

Hoare-Kalkül: Überblick

zu jedem Knotentyp in abstrakten Syntaxbäumen von strukturierten imperativen Programmen ein Axiom-Schema

Axiom für Zuweisung

Simultan-Zuweisung

Logische Axiome

Axiom für Verzweigung

Axiom für Verzweigung (Rechnung)

Axiom für Schleifen

Erweiterter Euklidische Algorithmus (Spezif.)

Erweiterter Euklid — imperative Impl.

Partielle und totale Korrektheit

Beispiele für Maßfunktionen

Wie findet man die Maßfunktion?

Automatische Laufzeitanalyse

Hausaufgaben

Für alle Programme: Diskussion der Eigenschaften (Hoare-Tripel, Invarianten) im Pseudocode. Geben Sie zusätzlich eine Implementierung in einer Programmiersprache Ihrer Wahl an, die dem Pseudocode optisch nahe kommt.

WS 23: 2, 4, 5

  1. zur Folie Zuweisungs-Axiom:

    • bestimmen Sie die Vorbedingung zu a := a + b; ..., aus den Axiomen für Zuweisung und Nacheinanderausführung.

    • Geben Sie ein ähnliches Verfahren an, das mit a := a XOR b beginnt, wobei XOR die bitweise Antivalenz bezeichnet.

    • Für das C++-Programm

      #include <iostream>

void sub (int & a, int & b) {
  a = a + b; b = a - b; a = a - b;
}

int main () {
  int p = 3; int q = 4;
  sub (p, q);  // (*)
  using namespace std;
  cout << p << q << endl;
}

      Kompilieren Sie mit -O3,

      betrachten Sie den erzeugten Assemblercode:

      für sub: wieviele Register werden benutzt?

      für main: vergleichen Sie mit der Variante, bei welcher der markierte Unterprogrammaufruf auskommentiert wird (beide Varianten abspeichern, z.B. g++ -O3 -S -o prog.s prog.cc, diff benutzen)

  2. https://www.imn.htwk-leipzig.de/~waldmann/edu/ws21/inf/folien/#(114) (Parteien A, B, C).

    Vgl. auch die Folien davor (20 und 21 Kugeln)

    https://www.imn.htwk-leipzig.de/~waldmann/edu/ws21/inf/folien/#(9) (91 Atome)

  3. Ergänzen Sie das folgende Programm, so daß die Spezifikation (das Potenzieren) erfüllt wird:

    Eingabe: natürliche Zahlen a, b;
// a = A und b = B
int p := 1; int c := ???;
// Invariante:  c^b * p = A^B
while (b /= 0) {
    if (b ist ungerade) 
      then (c,p) := ...
      else (c,p) := ...
    //  Z
    b := abrunden (b/2);
}
Ausgabe: p; // p = A^B

    • Initialisieren Sie c so, daß die Invariante gilt.

    • Wieso folgt aus der Invariante bei Verlassen der Schleife die Korrektheit der Ausgabe?

    • Bestimmen Sie eine geeignete Aussage Z als Vorbedingung der nachfolgenden Anweisung bezüglich der Invariante.

    • Bestimmen Sie daraus die Lücken (...)

  4. Für das Programm

    Eingabe: positive natürliche Zahlen A, B;
(a,b,c,d) := (A,B,B,A)
while (a /= b) {
  if (a > b) then (a,d) := (a-b,c+d)
             else (b,c) := (b-a,d+c)   }
Ausgabe: (a+b)/2 , (c+d)/2

    • zeigen Sie, daß die erste Ausgabe gleich gcd(A,B) ist.

      Zeigen Sie dazu: gcd(a,b) = gcd(A,B) ist invariant.

      Welche Eigenschaften des gcd werden benötigt?

    • was ist die zweite Ausgabe? Geben Sie eine Vermutung an und beweisen Sie mit einer geeigneten Invariante.

    • wozu ist die Bedingung positiv notwendig?

  5. Es können zusätzlich Aufgaben aus dem Math+-Adventskalender https://www.mathekalender.de/wp/de/kalender/ bearbeitet werden—wenn eine Beziehung zur Vorlesung hergestellt wird, z.B. Verwendung einer Methode aus dem Skript oder einer esoterischen Programmiersprache.

    Zum Lesen der Aufgaben ist keine Registrierung erforderlich.

    In unserem Issue-Tracker diskutieren, pro Woche max. eine Aufgabe zur Präsentation in der Übung, sofern Zeit ist. Aufgaben müssen nicht vollständig gelöst werden.

Anweisungen

Definition (Wiederholung)

Blöcke

Verzweigungen (zweifach)

Mehrfach-Verzweigung

Syntax:

switch (e) {
   case c1 : s1 ; 
   case c2 : s2 ;
   [ default : sn; ]  }

 

Semantik

if (e == c1) s1
else if (e == c2) s2 
  ... else sn

switch/break

switch (index) {
  case 1  : odd  ++; 
  case 2  : even ++;
  default : 
    printf ("wrong index %d\n", index); 
}

Verzweigungen in Ausdrücken

Kompilation der Mehrfachverzweigung

ein switch (mit vielen cases) wird übersetzt in:

Übung:

Pattern Matching (Def., Bsp. Scala)

Pattern Matching (Bsp. Java)

Wiederholungen (Schleifen)

Schleifen steuern durch…

Zählschleifen

Datengesteuerte Schleifen

Zustandsgesteuerte Schleifen

Implizite Iteratoren in C#

Bedingungsgesteuerte Schleifen

Dynamische Semantik von Schleifen

vorzeitiges Verlassen

Geschachtelte Schleifen

Sprünge

Sprünge und Schleifen

Schleifen und Unterprogramme

Garantierte Initialisierung in Java

Analyse des Programmablaufes lt. JLS

Aufgaben zur Programm-Äquivalenz

Approximierte Spur-Semantik v. Programmen

Hausaufgaben

WS 23: Aufgaben 1, 2; optional: 3, 4

  1. Syntax If-Then-Else

    1. (Wdhlg) Ergänzen: das Problem des dangling else ist die Mehrdeutigkeit der Grammatik mit den Regeln …

    2. (Wdhlg) Geben Sie ein Bespielprogramm \(P\) mit 2 Ableitungsbäumen bzgl. einer solchen Grammatik an.

    3. Suchen Sie die entsprechenden Regeln der Java-Grammatik,

    4. geben Sie den Ableitungsbaum für voriges \(P\) bzgl. dieser Grammatik an, begründen Sie, daß diese Grammatik eindeutig ist.

    5. Suchen Sie die entsprechenden Regeln in der Grammatik der Programmiersprache Ada,

    6. wie muß \(P\) geändert werden, damit es durch diese Grammatik erzeugt werden kann?

  2. Kompilation für Mehrfachverzweigung

    1. Schreiben Sie ein Programm, das einen C-Programmtext dieser Form ausgibt

      void p(int x) {
  switch (x) {
    case   0 : q0(); break;
    case   1 : q1(); break;
    ...
    case 999 : q999(); break;    } }

      Unterprogramme \(q_i\) nicht definieren, es geht nur um Kompilation (zu Objektfile, ohne Linking)

    2. Betrachten Sie den Assemblercode, der dafür von gcc -O2 -S erzeugt wird.

    3. Ändern Sie das Programm zu

      case     0 : ...
case   100 : 
...
case 99900 :

      beobachten und erklären Sie (ggf. weiter Abstände ausprobieren)

  3. pattern matching (bzw. Pläne dafür) in JS, TS, C# zeigen (mit Primärquellen)

  4. ein (kurzes) (Gewinner-)Programm eines IOCCC vorführen und erläutern, bei dem Programmablaufsteuerung nicht offensichtlich ist

Unterprogramme

Grundsätzliches

Beispiele Denotationale Semantik

Beispiel: Denotationale Sem. von Unterprogr.

Aufgabe Denotationale Semantik

Parameter-Übergabe (Semantik)

Datenaustausch zw. Aufrufer (caller) und Aufgerufenem (callee): über globalen Speicher

#include <errno.h>
extern int errno;

oder über Parameter.

Datentransport (entspr. Schüsselwörtern in Ada)

Parameter-Übergabe (Implementierungen)

Parameterübergaben in versch. Sprachen

häufig benutzte Implementierungen:

Verweis-Typ und Verweis-Variable

Call-by-value, call-by-reference (C#)

Call-by-name

formaler Parameter wird durch Argument-Ausdruck ersetzt.

Algol(68): Jensen’s device

int sum (int i, int n; int f) { 
  int s = 0;
  for (i=0; i<n; i++) { s += f; }
  return s;
}
int [10][10] a; int k; sum (k, 10, a[k][k]);

moderne Lösung

int sum (int n; Func<int,int> f) {
   ...  { s += f (i); }
}
int [10][10] a; sum (10, (int k) => a[k][k]);

Call-by-name (Macros)

#define thrice(x) 3*x // gefährlich
thrice (4+y)  ==>  3*4+y

“the need for a preprocessor shows omissions in the language”

weitere Argumente:

Ü: was kann der Präprozessor in C# und was nicht? Warum? (Wo ist der C#-Standard? http://stackoverflow.com/questions/13467103)

Call-by-name in Scala

Parameter-Typ ist => T, entspr. eine Aktion, die ein T liefert (in Haskell: IO T)

call-by-name

def F(b:Boolean,x: =>Int):Int = 
    { if (b) x*x else 0 }
F(false,{print ("foo "); 3})
//     res5: Int = 0
F(true,{print ("foo "); 3})
//    foo foo res6: Int = 9

Man benötigt call-by-name zur Definition von Abstraktionen über den Programmablauf.

Übung: If, While als Scala-Unterprogramm

Bedarfsauswertung

Beispiele f. Bedarfsauswertung (Scala)

Bedarfsauswertung für eine lokale Konstante (Schlüsselwort lazy)

def F(b:Boolean,x: =>Int):Int = 
    { lazy val y = x; if (b) y*y else 0 }
F(true,{print ("foo "); 3})
//   foo res8: Int = 9
F(false,{print ("foo "); 3})
//   res9: Int = 0

Beispiele f. Bedarfsauswertung (Haskell)

Aufgaben zu Parameter-Modi

WS 23: Aufgaben 2, 4, optional: 3

  1. Semantik dieses Ada-Programm erklären (verschiedene GCC/GNAT-Versionen) unter Bezug auf Sprachstandard (2012, vgl. mit früheren) und Rationale.

    with Ada.Text_IO; use Ada.Text_IO;
procedure Check is
   procedure Sub (X: in out Integer;
                  Y: in out Integer;
                  Z: in out Integer) is
   begin
      Y := 8; Z := X;
   end;
   Foo: Integer := 9;   Bar: Integer := 7;
begin
   Sub (Foo,Foo,Bar);
   Put_Line (Integer'Image(Foo));
   Put_Line (Integer'Image(Bar));
end Check;

    (in Datei Check.adb schreiben, kompilieren mit gnatmake Check.adb)

    Vergleichen mit diesem C++-Programm:

    #include <iostream>

void sub (int & x, int & y, int & z) {
  y = 8;
  z = x;
}

int main () {
   int foo = 9;
   int bar = 7;

   sub (foo,foo,bar);
   std::cout << foo << std::endl;
   std::cout << bar << std::endl;
}

  2. Call by value, call by reference

    class C { public int foo; }
class M { public  static void u (C x) 
  { x.foo=4; x=new C{foo=5}; } }

C y = new C {foo=3}
C z = y
M.u (y)
y.foo 
z.foo

    • Kompilieren/ausführen (mit csharp CLI), beobachten, erklären. Diagramm zeichnen, das die Speicherbelegung verdeutlicht.

    • Ersetzen Sie class C durch struct C. Kompilieren, …

    • Ersetzen Sie void u (C x) durch void u (ref C x). Welche weitere Änderung ist erforderlich? Kompilieren, …

    • class C und u (ref C x)

  3. call by name, call by reference:

    Wie kann man diese beiden Unterprogramme aus Sicht des Aufrufers semantisch voneinander unterscheiden:

    • Funktion (C++): (call by reference)

      void swap (int & x, int & y) 
   { int h = x; x = y; y = h; }

    • Makro (C): (call by name)

      #define swap(x, y) \ 
   { int h = x; x = y; y = h; }

    Geben Sie einen Ausdruck \(E\) an, in dem ein Name swap benutzt wird, so daß für beide Definitionen von swap gilt:

    • \(E\) ist syntaktisch korrekt,

    • \(E\) ist statisch korrekt,

    • dynamische Semantiken von \(E\) sind unterschiedlich

    Also nicht einfach so:

    int a = 3; int b = 4; swap (a,b);

  4. Simulation von call-by-name durch Unterprogramme als Argumente:

    1. Die Fakultäts-Funktion in ECMA-Script

      function f(x) { return x==0 ? 1 : x * f(x-1) }
f(4)
==> 24

    2. Die Verzweigung als Funktion

      function ite(b,j,n) { return b ? j : n }
ite(false,2,3) 
==> 3

    3. Ersetzen Sie ?: in f durch ite, werten Sie f(4) aus, erklären Sie Ihre Beobachtung.

    4. Simulation von call-by-name durch Unterprogramme als Argumente:

      function ite(b,j,n) { return b ? j() : n() }

      wie muß ite(false,2,3) jetzt aussehen?

    5. passen Sie die Def. von f an und testen Sie

Weiteres zu Unterprogrammen

Lokale UP, UP als Daten

UP und Sichtbarkeit von Namen

{ const x = 3; 
  function step(y) { return x + y; }
  for (const z of [ 1,2,4 ]) { 
    console.log(step(z+1)); } }

vgl. Spezifikation:

https://tc39.github.io/ecma262/#sec-lexical-environments, https://www.ecma-international.org/ecma-262/7.0/

Frames, statische Kette, Index

Übersetzungszeit und Laufzeit

Lokale Unterprogramme: Beispiel

with Ada.Text_Io; use Ada.Text_Io;
procedure Nested is
 function F (X: Integer; Y: Integer) 
 return Integer is
  function G (Y: Integer) return Integer is
  begin
   if (Y > 0) then return 1 + G(Y-1);
   else return X; end if;
  end G;
 begin return G (Y); end F;
begin
 Put_Line (Integer'Image (F(3,2)));
end Nested;

Globale Unterprogramme

Entwurfs-Entscheidung für C (1972):

Auswirkungen:

Lokale UP, UP als Daten: Geschichte

Simulation von UP als Daten

Unterprogramme als Argumente

static int d ( Func<int,int> g ) { 
    return g(g(1));              }
static int p (int x) {
    Func<int,int> f = y => x + y;
    return d (f);                }

Betrachte Aufruf \(p(3)\).

Das innere Unterprogramm \(f\) muß auf den \(p\)-Frame zugreifen, um den richtigen Wert des \(x\) zu finden.

Dazu Closure konstruieren: \(f\) mit statischem Vorgänger.

Wenn Unterprogramme als Argumente übergeben werden, steht der statische Vorgänger im Stack.

(ansonsten muß man den Vorgänger-Frame auf andere Weise retten, siehe später)

Unterprogramme als Resultate

static int x = 3;   
static Func<int,int> s (int y) {
    return z => x + y + z;     
}
static void Main () {
    Func<int,int> p = s(4);
    Console.WriteLine (p(3));  
}

Wenn die von \(s(4)\) konstruierte Funktion \(p\) aufgerufen wird, dann wird der \(s\)-Frame benötigt, steht aber nicht mehr im Stack.

\(\Rightarrow\) Die (Frames in den) Closures müssen im Heap verwaltet werden.

Anwendung von UP as Daten (Beispiel)

Lokale Klassen (Java)

Unterprogramme/Zusammenfassung

in prozeduralen Sprachen:

in objektorientierten Sprachen: ähnliche Überlegungen bei lokalen (inner, nested) Klassen.

Hausaufgaben

WS 23: 2 oder 1, 3 oder 4, 5.

  1. Assembler-Code für Programm von Lokale UP: Beispiel mit gcc -c -O0 -S nested.adb,

    • welche Variablen-Benutzung hat Index \((i,j)\) mit \(i>0\),

    • wo steht das im Assemblercode?

    • vergleiche Assemblercode des Hauptprogramms bei -O0 / -O3

  2. Lokale anonyme UP (Lambda-Ausdrücke) in C++:

    #include <iostream>
#include <functional>
using namespace std;
int x = 3;
function<int(int)> s (int y) {
  return [](int z){ return x+y+z;};
}
int main () {
  auto p = s(1);
  auto q = s(5);  
  cout << p(2) << endl;
}

  3. Das most recent-Problem (McGowan 1972) erklären

    van den Hove d’Ertsenryck: Dissolving a half century old problem about the implementation of procedures, 2017 https://ir.cwi.nl/pub/26757

    Beispiele in der autotool-Aufgabe vorführen (soweit möglich) oder in JS (aber Autotool zeigt die Frames)

  4. Donald Knuth: Man or Boy?, Algol Bulletin 1960, zitiert in

    http://www.chilton-computing.org.uk/acl/applications/algol/p006.htm (Atlas Computer Labs)

    …handle recursion and non-local references properly

    Beispiel-Programm vorführen und diskutieren (in einer heutigen Sprache - oder in Algol. Aber auf eigenem Rechner!) Ggf. Sekundärquellen heranziehen.

  5. Beispiele zur Verwendung von Funktionen höherer Ordnung zur Verarbeitung von Containern mit Haskell, LINQ (C#) und Streams (Java) vorführen. Ggf. auch in JS.

    Z.B.: foldl (siehe Skript), map, filter; wie kann man scanl,mapAccumL übersetzen?

    • Beispiele in der jeweiligen CLI (ghci, csharp, jshell)

    • Primärquellen verwenden! (API-Dokumenation)

  6. Aussagen über Graphen mit Knotenmenge \(=\) Frames einer Programmausführung, Kanten \(\to_\text{dyn}, \to_\text{stat}\).

    • \(\to_\text{dyn}\) ist ein Baum

    • \(\to_\text{stat}\) ist ein Baum

    • sind beliebige Kombinationen von Bäumen möglich? Nein, \(\to_\text{dyn}\) und \(\to_\text{stat}\) besitzen eine gemeinsame topologische Ordnung. Woher kommt diese?

    • sind alle Kombinationen mit gemeinsamer topologischer Ordnung möglich?

Zur autotool-Aufgabe zu Frames: siehe auch https://gitlab.imn.htwk-leipzig.de/autotool/all0/issues/124

Dynamische Polymorphie

Übersicht

poly-morph \(=\) viel-gestaltig; ein Bezeichner (z. B. Unterprogramm-Name) mit mehreren Bedeutungen

Arten der Polymorphie:

Objekte, Methoden

Motivation: Objekt \(=\) Daten \(+\) Verhalten.

Einfachste Implementierung:

typedef struct {
   int x; int y; // Daten
   void (*print) (FILE *fp); // Verhalten
} point;
point *p; ... ; (*(p->print))(stdout);

Anwendung: Datei-Objekte in UNIX (seit 1970)

(Merksatz 1: all the world is a file) (Merksatz 2: those who do not know UNIX are doomed to re-invent it, poorly)

Objektbasierte Sprachen (JavaScript)

(d. h. objektorientiert, aber ohne Klassen)

Objekte, Attribute, Methoden:

var o = { a : 3, 
  m : function (x) { return x + this.a; } };

Vererbung zwischen Objekten:

var p = { __proto__ : o };

Attribut (/Methode) im Objekt nicht gefunden \(\Rightarrow\) weitersuchen im Prototyp \(\Rightarrow\) …Prototyp des Prototyps …

Übung: Überschreiben

p.m = function (x) { return x + 2*this.a }
var q = { __proto__ : p }
q.a = 4
q.m(5)

Klassenbasierte Sprachen

gemeinsame Datenform und Verhalten von Objekten

typedef struct { int (*method[5])(); } cls;
typedef struct {
    cls * c;
} obj;
obj *o; ... (*(o->c->method[3]))();

allgemein: Klasse:

Objekt:

this

Motivation: Methode erfährt, für welches Argument sie gerufen wurde

typedef struct { int (*method[5])(obj *o); 
} cls;
typedef struct {
    int data [3]; // Daten des Objekts
    cls *c; // Zeiger auf Klasse
} obj;
obj *o; ... (*(o->c->method[3]))(o);
int sum (obj *this) {
    return this->data[0] + this->data[1]; }

jede Methode bekommt this als erstes Argument

(in Java, C# geschieht das implizit)

Klassen in ECMA-Script

Dynamische Polymorphie

Dyn. P. und statische Typisierung

Dynamische Polymorphie (Beispiel)

Vererbung bricht Kapselung

Einordnung Objekorientierung

Statische Polymorphie: Ad-Hoc-Polymorphie

Beispiel: Überladung im Argumenttyp:

static void p (int x, int    y) { ... }
static void p (int x, String y) { ... }
p (3, 4); p (3, "foo");

keine Überladung nur in Resultattyp, denn…

static int    f (boolean b) { ... }
static String f (boolean b) { ... }

Typhierarchie als Halbordnung

Ad-Hoc-Polymorphie und Typhierarchie

Auflösung von p (new D(), new D()) bzgl.

static void p (C x, D y);
static void p (C x, C y);
static void p (E x, C y);

Überschreiben und Überladen

Equals richtig implementieren

class C { 
  final int x; final int y;
  C (int x, int y) { this.x = x; this.y = y; }
  int hashCode () { return this.x + 31 * this.y; }
}

nicht so:

  public boolean equals (C that) {
    return this.x == that.x && this.y == that.y;
  }

Equals richtig implementieren (II)

…sondern so:

public boolean equals (Object o) {
  if (! (o instanceof C)) return false;
  C that = (C) o;
  return this.x == that.x && this.y == that.y;
}

Die Methode boolean equals(Object o) wird aus HashSet aufgerufen.

Sie muß deswegen überschrieben werden.

Das boolean equals (C that) hat den Methodenamen nur überladen.

Statische Attribute und Methoden

Hausaufgaben

WS 23: Aufgaben 3, 4, 1

  1. Beispiel auf Folie Objektbasierte Sprachen (JS) ausprobieren, Beobachtungen erklären (Speicherbelegung grafisch darstellen),

    und erweitern. Längere Prototyp-Ketten, überraschendes Verhalten, oder ändere einen Bezeichner, so daß Ausgabe …. Beispiele vorher bekanntgeben, Auflösung dann in Übung.

  2. zu Folie Vererbung bricht Kapselung:

    vgl. Joshua Bloch: Effective Java (Pearson 2018)

    Item 19: Design and document for inheritance or else prohibit it.

    Diskutieren Sie die Einhaltung dieser Regel am Beispiel https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/AbstractCollection.html#retainAll(java.util.Collection)

  3. Wo und wie ist das Verfahren zur Auflösung der Ad-Hoc-Polymorphie im Java-Standard beschrieben? Gemeinsamkeiten und Unterschiede zur Beschreibung hier im Skript?

    Gegeben sind diese Klassen und Methoden eines Java-Programmes:

    class D extends B; class B extends A; class A; 
                   class C extends A; 
static void p (B x, C y);
static void p (A x, D y); 
static void p (B x, A y);

    Beschreiben Sie, wie die Überladung in p (new D(), new C()) aufgelöst wird.

  4. Folien Equals richtig…: Beispiel vorführen (falsches Verhalten des HashSet bei falschem equals).

    Welche Hilfen geben IDEs?

    Warum besteht diese Problem (versehentliches Überladen anstatt Überschreiben) bei compareTo nicht?

    Wie sieht das in C# aus?

Polymorphie

Übersicht

poly-morph \(=\) viel-gestaltig; ein Bezeichner (z. B. Unterprogramm-Name) mit mehreren Bedeutungen

Arten der Polymorphie:

Beispiele f. generische Polymorphie

Statische Semantik der generischen Pol.

Softwaretechnischer Zweck der gen. Pol.

Dynamische Semantik der generischen Pol.

Bsp: Generische Methode in C#

class C {
   static T id<T> (T x) { return x; }
}

beachte Position(en) von

string foo = C.id<string> ("foo");
int    bar = C.id<int>    (42);

Bsp: Generische Klasse in Java

record Pair<A,B> (A first, B second) {}
Pair<String,Integer> p = 
    new Pair<String,Integer>("foo", 42);
int x = p.second() + 3;

vor allem für Container-Typen (Liste, Menge, Keller, Schlange, Baum, …)

Bsp: Generische Methode in Java

class S {
  static <A,B> Pair<B,A> swap (Pair<A,B> p) { 
    return new Pair<B,A>(p.second(), p.first()); } }
Pair<String,Integer> p = 
    new Pair<String,Integer>("foo", 42);
Pair<Integer,String> q = 
    S.<String,Integer>swap(p);

Typargumente können auch inferiert werden:

Pair<Integer,String> q = S.swap(p);

Generische Fkt. höherer Ordg.

Bsp. Generische Fkt. höherer Ordg. (I)

Sortieren mit Vergleichsfunktion als Parameter

using System; class Bubble {
  static void Sort<T> 
    (Func<T,T,bool> Less, T [] a) { ...
      if (Less (a[j+1],a[j])) { ... } } 
  public static void Main (string [] argv) {
    int [] a = { 4,1,2,3 };
    Sort<int> ((int x, int y) => x <= y, a);
    foreach (var x in a) Console.Write (x);
} }

Ü: (allgemeinster) Typ und Implementierung einer Funktion Flip, die den Vergleich umkehrt: Sort<int> (Flip( (x,y)=> x <= y ), a)

Bsp. Generische Fkt. höherer Ordg. (II)

bulk operations auf Collections, z.B.

Vererbung und generische Polym.

Generics und Subtypen

Warum geht das nicht:

class C { } 

class E extends C { void m () { } }
 
List<E> x = new LinkedList<E>();

List<C> y = x; // Typfehler

Antwort: wenn das erlaubt wäre, dann:

variante Typ-Argumente (C#)

Kontravarianz (in P), Kovarianz (out P)

interface I<in P> { // Typ-Arg. ist kontravariant
  // P get (); kovariante Benutzung (verboten)
  void set (P x); // kontravariante Benutzung
}
class K<P> : I<P> { public void set (P x) {} } 
class C {} class E : C {void m(){}} // E <= C
I<C> x = new K<C>(); 
I<E> y = x; // erlaubt, Kontravarianz: I<C> <= I<E>
x.set<C>(new C()); // erlaubt
y.get<E>().m(); ??

Obere Schranken für Typparameter

Untere Schranken für Typparameter

Vergleich: Varianz und Schranken

Unterscheidung:

Generics und Arrays (in Java)

Aufgaben

WS 23: 1, 2, 3, 6a, 6b

  1. Sortieren mit Vergleichsfunktion als Parameter

    (https://git.imn.htwk-leipzig.de/waldmann/pps-ws23/-/blob/main/generic/Bubble.cs)

    1. Flip implementieren.

    2. Welches ist der allgemeinste Typ von Flip?

  2. Bulk-operations auf Collections.

    1. Bestimmen Sie den Typ von Data.Map.unionWith (API-Dokumentation oder ghci), warum hat dieser weniger Typparameter als intersectionWith?

    2. einfache Messungen mit ghci. Nach jeder Deklaration/Ausdruck anzeigten Kosten diskutieren

      :set +s
import qualified Data.Set as S
a = S.fromList [1 :: Int .. 10^6 ]
length a
length a
b = S.map (+ 10^6) a
length b
S.intersection a b -- bulk operation
S.filter (\ x -> S.member x a) b -- naive elementweise Implementierung

    3. warum ist die bulk operation hierfür langsamer?

      c = S.map (* 2) a ; d = S.map succ c

      und trotzdem noch schneller als elementweise?

      (Nur die Kosten der Operation messen, nicht die der Konstruktion oder der Ausgabe.)

    Ergänzung: S.Set Int ist unzweckmäßig, denn Data.IntSet.Set ist effizienter!

  3. (Folie untere Schranken…) binarySearch aufrufen (Java), so daß beide ? von T verschieden sind

  4. (siehe Folie variante Typ-Parameter…)

    Implementieren Sie set und get in K<P>, ergänzen Sie das Hauptprogramm so, daß schließlich eine Methode m() eines C-Objektes aufgerufen würde — was jedoch durch statische Typ-Prüfung verhindert wird.

  5. Wildcards (?) und Capture Conversion in JLS nachlesen, Beispiele vorführen.

  6. Wiederholung Axiomatische Semantik, Invarianten:

    1. Bundeswettbewerb Mathematik 2023, 1. Runde, 1. Aufgabe (Tick, Trick und Track haben jeweils …)

      https://www.mathe-wettbewerbe.de/fileadmin/Mathe-Wettbewerbe/Bundeswettbewerb_Mathematik/Dokumente/BWM_2023.1_Aufgabenblatt.pdf

    2. BW Math 2024, 1. Runde, 1. Aufgabe (Arthur und Renate)

  7. Improve powerSet performance

    https://github.com/haskell/containers/issues/890

    1. Warum gibt es kein Typconstraint im Typ von Data.Set.powerSet?

    2. angegebene Ideen beschreiben, implementieren, verbessern: mglw. Masterarbeit

Zusammenfassung, Ausblick

Themen

Sprachen kommen und gehen, Konzepte bleiben.

Methoden, softwaretechnische Ziele

Well-Typed Programs Don’t Go Wrong

Statische Typisierung: für und wider

Für statische Typisierung spricht vieles.

Es funktioniert auch seit Jahrzehnten (Algol 1960, ML 1970, C++ 1980, Java 1990 usw.)

Was spricht dagegen?

Thinking With Types

Fachmännisches Programmieren

Legacy-Sprachen: ECMA-Script (Javascript)

Aktuelle Entwicklungen: JS, TS

Personen: Luke Hoban, Anders Hejlsberg, Erik Meijer, …

Aktuelly: Web Assembly

Die Zukunft: Typen für Ressourcen

https://www.rust-lang.org/

…a systems programming language that …prevents segfaults and guarantees thread safety.

https://github.com/rust-lang/rust-wiki-backup/blob/master/Note-research.md#type-system,

lineare Logic (Girard 1987), siehe

https://www.cs.cmu.edu/~fp/courses/linear/lectures/lecture16.html

Die Zukunft: Datenabhängige Typen

https://wiki.portal.chalmers.se/agda/ (Thierry Coquand et al., 1990; Ulf Norell, Andreas Abel 2005) …express properties of programs in the typing system.

data Vec : Nat -> Type -> Type
(++) : Vec p a -> Vec q a -> Vec (p+q) a
head : Vect (S p) a -> a   -- S : Nachfolger

Die Zukunft (Planung Lehrveranstaltungen)

Hausaufgaben

  1. Colin McMillen, Jason Reed, and Elly Fong-Jones, 2011: Programming Language Checklist:

    You appear to be advocating a new … programming language. Your language will not work. Here is why:…

    https://web.archive.org/web/20210406235046/https://famicol.in/language_checklist.html

    Geben Sie die Definitionen (aus dieser VL) der genannten Eigenschaften an (Syntax, Semantik), diskutieren Sie Auswirkungen (Pragmatik)

  2. Auch mit den schönsten Programmiersprachen kann man Software schreiben, deren Anwendung Menschen schadet. Informieren Sie sich über

    und beachten Sie das bei der Wahl Ihres Arbeitgebers.