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.

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

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

Sprachen für bestimmte Anwendungen, mit bestimmten Paradigmen:

Organisation

Literatur

Zum Vergleich/als Hintergrund:

Inhalt

(nach Sebesta: Concepts of Programming Languages)

Übungen

1. Anwendungsgebiete von Programmiersprachen, wesentliche Vertreter

zu Skriptsprachen: finde die Anzahl der "*.java"-Dateien unter $HOME/workspace, die den Bezeichner String enthalten. (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

2. Maschinenmodelle (Bsp: Register, Turing, Stack, Funktion)

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

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

PostScript (welches Paradigma?)

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

Mit gv ansehen (Menu: State \(\to\) watch file). Mit Editor Quelltext ändern. Finden Sie den Autor dieses Programms!

3. http://99-bottles-of-beer.net/ (top rated …)

Syntax von Programmiersprachen

Programme als Bäume

Token-Typen

alle Token eines Typs bilden eine formale Sprache.

Formale Sprachen

Beispiele:

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\)

  2. zusätzliche nicht-reguläre Operatoren

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

    beachte Unterschied zu \(L^k\)

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

wenn nicht-reguläre Sprachen entstehen können, ist keine effiziente Verarbeitung (mit endlichen Automaten) möglich.

auch reguläre Operatoren werden gern schlecht implementiert (http://swtch.com/~rsc/regexp/regexp1.html)

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, Regulären Ausdrücken

Testfragen

Aufgabe

Wort-Ersetzungs-Systeme

Berechnungs-Modell (Markov-Algorithmen)

Syntax: Programm ist Regelmenge \(R \subseteq \Sigma^* \times \Sigma^*\)

Semantik: die 1-Schritt-Ableitungsrelation \(\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\).

Beispiele:

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

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:

Übungen (CF-Grammatiken)

Übungen (Rewriting, Typ-0-Grammatiken)

Semantik von Programmiersprachen

Statische und dynamische Semantik

Semantik \(=\) Bedeutung

Hilfsmittel: Attributgrammatiken

Bsp statische/dynamische Semantik

Benutzung eines undeklarierten Namens:

Attributgrammatiken (I)

Attributgrammatiken (II)

ein Ableitungsbaum mit Annotationen ist
korrekt bezüglich einer Attributgrammatik, wenn

Plan:

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

technische Schwierigkeit: Attributwerte effizient bestimmen. (beachte: (zirkuläre) Abhängigkeiten)

Donald E. Knuth

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

Arten von Attributen

Wenn Abhängigkeiten bekannt sind, kann man Attributwerte durch Werkzeuge bestimmen lassen.

Attributgrammatiken–Beispiele

Konkrete und abstrakte Syntax

unwesentlich sind z. B. die Knoten, die zu Hilfsvariablen der Grammatik gehören.

abstrakter Syntaxbaum kann als synthetisiertes Attribut konstruiert werden.

E -> E + P  ;  E.abs = new Plus(E.abs, P.abs)
E -> P      ;  E.abs = P.abs

Regeln zur Typprüfung

…bei geschachtelten Funktionsaufrufen

Beispiel

class C {
  static class A {}  static class B {}
  static B f (A y) { .. }
  static A g (B x) { .. }
  .. 
  .. C.g (C.f (new C.A()))  .. }

Bsp. Operationale Semantik: Keller

Kompilation für Kellermaschine

Aufgaben

Übung Attributgrammatiken/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: http://www.imn.htwk-leipzig.de/~waldmann/edu/ws11/cb/folien/main/node12.html, Kombinator-Parser: http://www.imn.htwk-leipzig.de/~waldmann/edu/ws11/cb/folien/main/node70.html

Dynamische Semantik

Operationale Semantik: Sprünge

Denotationale Semantik

Beispiele: Semantik von …ist …

Vorteile denotationaler Semantik:

Vorteil deklarativer Programierung: Programmiersprache ist Beschreibungssprache (ist Mathematik)

Beispiele Denotationale Semantik

Beispiel: Denotationale Sem. von Unterprogr.

Axiomatische Semantik

Notation für Aussagen über Speicherbelegungen:

{ V } A { N }

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

Gültigkeit solcher Aussagen kann man

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

Eiffel

Bertrand Meyer, http://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

Hoare-Kalkül: Überblick

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

Anwendung des Zuweisungs-Axioms

Hoare-Kalkül: Ergänzung

Übungen zur op./den./ax. Semantik

Hausaufgaben:

in der Übung:

Bemerkungen zur Rekursion

Anwendung: Axiom für Verzweigung

Axiom für Verzweigung (Rechnung)

Anwendung des Axioms für Schleifen

Der erweiterte Euklidische Algorithmus

Erweiterter Euklid — funktional

Erweiterter Euklid — funktional (vollst.)

Simultan-Zuweisung

Erweiterter Euklid — imperativ

Übungen Schleifen-Invarianten

  1. Ergänzen Sie das 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 fehlenden Ausdrücke in der Schleife.

  2. 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.

      Beweisen Sie dazu die Invarianz von gcd(a,b) = gcd(A,B).

      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?

Typen

Warum Typen?

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 (http://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

Haskell (http://haskell.org/)

data Tree a = Leaf a 
            | Branch ( Tree a ) ( Tree a )

Java

interface Tree<A> { }
class Leaf<A> implements Tree<A> { A key }
class Branch<A> implements Tree<A> 
  { Tree<A> left, Tree<A> right }

Tree a ist ein algebraischer Datentyp:

Potenz-Typen

\(B^A := \{ f : A \to B \}\) (Menge aller Funktionen von \(A\) nach \(B\))

ist sinnvolle Notation, denn \(|B|^{|A|} = \left|B^A\right|\)

spezielle Realisierungen:

die unterschiedliche Notation dafür (Beispiele?) ist bedauerlich.

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#

Testfall:

class s {public int foo; public string bar;}
s x = new s(); x.foo = 3; x.bar = "bar";
s y = x; y.bar = "foo";
Console.WriteLine (x.bar);

und dann class durch struct ersetzen

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

Übung Typen

Bezeichner, Bindungen, Bereiche

Variablen

Namen in der Mathematik

in der Programmierung:

Namen

Deklaration und Definition

Typen für Variablen

Dynamisch typisierte Sprachen

Statisch typisierte Sprachen

Typdeklarationen

Typinferenz in C# und Java

Konstanten

Lebensort und -Dauer von Name und Daten

Sichtbarkeit von Namen

Verdeckung von Deklarationen

Sichtbarkeit in JavaScript

Übung

  1. Wo steht im Java-Sprachstandard, daß jeder Name vor seiner Benutzung deklariert sein muß?

  2. Beschreiben Sie Sichtbarkeitsbereich und Lebensdauer der Variablen in

    int f (int x) {
  int a = x;
  int b = a+1;
  int c = b+2;
  return c;
}

    Vergleichen Sie mit der Ausgabe (Assemblercode) von gcc -S

  3. Beispiel in Java für: Sichtbarkeit beginnt mit Initialisierung

  4. 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);
}

  5. schreiben Sie ein entsprechendes Java-Programm und vergleichen Sie.

  6. Sichtbarkeit von Deklarationen in Javascript

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

Syntax von Literalen

Der Plus-Operator in Java

Überladene Operatornamen

Automatische Typanpassungen

Implizite/Explizite Typumwandlungen

Explizite Typumwandlungen

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

Typ-Umwandlungen in Javascript

Gary Bernhardt: WAT (2012)

https://www.destroyallsoftware.com/talks/wat

Der Verzweigungs-Operator

Verzweigungs-Operator(II)

Relationale Operatoren

Logische (Boolesche) Ausdrücke

Noch mehr Quizfragen

Erklären durch Verweis auf Java Language Spec.

Der Zuweisungs-Operator

Weitere Formen der Zuweisung

(in C-ähnlichen Sprachen)

Ausdrücke mit Nebenwirkungen

(side effect; falsche Übersetzung: Seiteneffekt)

Auswertungsreihenfolgen

Kritisch: wenn Wert des Ausdrucks von Auswertungsreihenfolge abhängt:

int a; int b = (a = 5) + (a = 6);
int d = 3; int e = (d++) - (++d); 
int x = 3; int y = ++x + ++x + ++x;

Auswertungsreihenfolge in C

Sprachstandard (C99, C++) benutzt Begriff sequence point (Meilenstein): bei Komma, Fragezeichen, && und ||

die Nebenwirkungen zwischen Meilensteinen müssen unabhängig sein (nicht die gleiche Speicherstelle betreffen),

ansonsten ist das Verhalten undefiniert, d.h., der Compiler darf beliebigen Code erzeugen, z.B. solchen, der die Festplatte löscht oder Cthulhu heraufbeschwört. vgl. Aussagen zu sequence points in

http://gcc.gnu.org/readings.html

und

Gurevich, Huggins: Semantics of C,

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.6755

Übungen

  1. Wiederholung Operator-Syntax:

  2. Wiederholung: 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.

  3. über die implizite 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.

    3. Wo ist diese Konversion in der Sprachspezifikation beschrieben?

    4. Gilt \(\text{int}\subseteq\text{double}\)?

      a) laut Spezifikation, b) wirklich?

  4. Verkürzte Auswertung bei logischen Operatoren (in Java, Tests mit jshell ausführen)

    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)

  5. Ausdrücke mit Nebenwirkungen, siehe Aufgabe autotool

    vgl. mit Folie Auswertungsreihenfolge in C

  6. Wer ist Cthulhu? Seine Beziehung zu Semantik von C-Programmen ist Folklore, Belege z.B. after all, we have UB here, and this could just summon cthulhu or anything else.

  7. passend zur Jahreszeit: https://www.mathekalender.de/index.php?page=calendar&lang=de

Anweisungen(I)

Definition

Semantik: Ausführen einer Anweisung bewirkt Zustandsänderung

abstrakte Syntax:

Programm-Ablauf-Steuerung

engl. control flow, falsche Übersetzung: Kontrollfluß;

to control \(=\) steuern, to check \(=\) kontrollieren/prüfen

Blöcke

Folge von (Deklarationen und) Anweisungen

Designfrage: Blöcke

Designfrage/historische Entwicklung: Deklarationen …

Verzweigungen (zweifach)

in den meisten Sprachen:

if Bedingung then Anweisung1 
     [ else Anweisung2 ]

Designfragen:

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); 
}

Kompilation

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

Übung:

Pattern Matching

abstract class Term   // Scala
case class Constant (value : Int) 
    extends Term
case class Plus (left: Term, right : Term) 
    extends Term
def eval(t: Term): Int = {
  t match {
    case Constant(v) => v
    case Plus(l, r) => eval(l) + eval(r)
  } }

Wiederholungen

Designfragen für Schleifen:

Schleifen steuern durch…

Zählschleifen

Idee: vor Beginn steht Anzahl der Durchläufe fest.

richtig realisiert ist das nur in Ada:

for p in 1 .. 10 loop ... end loop;

Vergleiche (beide Punkte) mit Java, C++, C

Termination

Satz: Jedes Programm aus

terminiert (hält) für jede Eingabe.

Äquivalenter Begriff (für Bäume anstatt Zahlen): strukturelle Induktion (fold, Visitor, primitive Rekursion)

Satz: es gibt berechenbare Funktionen, die nicht primitiv rekursiv sind.

Beispiel: Interpreter für primitiv rekursive Programme.

Datengesteuerte Schleifen

Idee: führe für jeden Konstruktor eines algebraischen Datentyps (Liste, Baum) eine Rechnung/Aktion aus.

foreach, Parallel.Foreach,...

Zustandsgesteuerte Schleifen

So:

interface Iterator<T> {
  boolean hasNext(); T next ();  }
interface Iterable<T> { 
   Iterator<T> iterator(); }
for (T x : ...) { ... }

Oder so:

public interface IEnumerator<T> : IEnumerator {
  bool MoveNext(); T Current { get; } }
interface IEnumerable<out T> : IEnumerable {
   IEnumerator<T> GetEnumerator() }
foreach (T x in ...) { ... }

(sieben Unterschiede …)

Implizite Iteratoren in C#

using System.Collections.Generic;
public class it {
    public static IEnumerable<int> Data () {
        yield return 3;
        yield return 1;
        yield return 4;
    }
    public static void Main () {
        foreach (int i in Data()) {
            System.Console.WriteLine (i);
}   }   }

Schleifen mit Bedingungen

das ist die allgemeinste Form, ergibt (partielle) rekursive Funktionen, die terminieren nicht notwendig für alle Argumente.

Steuerung

Weitere Änderung des Ablaufes:

Abarbeitung von Schleifen

operationale Semantik durch Sprünge:

while (B) A;
==>
start : if (!B) goto end; 
        A; 
        goto start;
end   : skip;

(das ist auch die Notation der autotool-Aufgabe)

Ü: do A while (B);

vorzeitiges Verlassen

Geschachtelte Schleifen

manche Sprachen gestatten Markierungen (Labels) an Schleifen, auf die man sich in break beziehen kann:

foo : for (int i = ...) {
  bar : for (int j = ...) {

    if (...) break foo;

  }
}

Wie könnte man das simulieren?

Sprünge

Sprünge und Schleifen

Sprünge und Schleifen (Beweis)

Satz: zu jedem goto-Programm gibt es ein äquivalentes while-Programm.

Beweis-Idee: 1 : A1, 2 : A2; .. 5: goto 7; .. \(\Rightarrow\)

while (true) {
  switch (pc) {
    case 1 : A1 ; pc++ ; break; ...
    case 5 : pc = 7 ; break; ... 
  }
}

Das nützt aber softwaretechnisch wenig, das übersetzte Programm ist genauso schwer zu warten wie das Original.

Schleifen und Unterprogramme

zu jedem while-Programm kann man ein äquivalentes angeben, das nur Verzweigungen (if) und Unterprogramme benutzt.

Beweis-Idee: while (B) A; \(\Rightarrow\)

void s () {
    if (B) { A; s (); }
}

Anwendung: C-Programme ohne Schlüsselwörter.

Was ist hier los?

class What {
    public static void main (String [] args) {
        System.out.println ("mozilla:open");
        http://haskell.org
        System.out.println ("mozilla:close");
    }
}

Denotationale Semantik (I)

vereinfachtes Modell, damit Eigenschaften entscheidbar werden (sind die Programme \(P_1, P_2\) äquivalent?)

Syntax: Programme

Beispiel:

while (B && !C) { P; if (C) Q; }

Denotationale Semantik (II)

Semantik des Programms \(P\) ist Menge der Spuren von \(P\).

Satz: Diese Spursprachen (von goto- und while-Programmen) sind regulär.

Beweis: Konstruktion über endlichen Automaten.

Damit ist Spur-Äquivalenz von Programmen entscheidbar.
Beziehung zu tatsächlicher Äquivalenz?

Übungen

  1. Syntax If-Then-Else

    1. (Wdhlg) Ergänzen Sie: 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;
  }
}

    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)

Unterprogramme

Grundsätzliches

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übergabe

häufig benutzte Implementierungen:

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

Übung zu CB-value/CB-reference

class M {
  class C { public int foo; }
  static void u (C x) { x.foo=4; x=new C{foo=5};}
  public static void Main (string [] argv) {
    C y = new C {foo=3} ; C z = y; u (y);
    System.Console.WriteLine(y.foo + " " + z.foo);
  }
}

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 (Haskell)

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

Argumente/Parameter

Designfragen bei Parameterzuordnung:

Positionelle/benannte Argumente

Üblich ist Zuordnung über Position

void p (int height, String name) { ... }
p (8, "foo");

in Ada: Zuordnung über Namen möglich

procedure Paint (height : Float; width : Float);
Paint (width => 30, height => 40);

nach erstem benannten Argument keine positionellen mehr erlaubt

code smell: lange Parameterliste,

refactoring: Parameterobjekt einführen

allerdings fehlt (in Java) benannte Notation für Record-Konstanten.

Default-Werte

C++:

void p (int x, int y, int z = 8);
p (3, 4, 5); p (3, 4);

Default-Parameter müssen in Deklaration am Ende der Liste stehen

Ada:

procedure P
    (X : Integer; Y : Integer := 8; Z : Integer);
P (4, Z => 7);

Beim Aufruf nach weggelassenem Argument nur noch benannte Notation

Variable Argumentanzahl (C)

wieso geht das eigentlich:

#include <stdio.h>
char * fmt = really_complicated();
printf (fmt, x, y, z);

Anzahl und Typ der weiteren Argumente werden überhaupt nicht geprüft:

extern int printf 
    (__const char *__restrict __format, ...);

Variable Argumentanzahl (Java)

static void check (String x, int ... ys) {
    for (int y : ys) { System.out.println (y); }
}

check ("foo",1,2); check ("bar",1,2,3,4);

letzter formaler Parameter kann für beliebig viele des gleichen Typs stehen.

tatsächlich gilt int [] ys,

das ergibt leider Probleme bei generischen Typen

Aufgaben zu Parameter-Modi (I)

Erklären Sie den Unterschied zwischen (Ada)

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)

und (C++)

#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;
}

Aufgaben zu Parameter-Modi (II)

Durch welchen Aufruf kann man diese beiden Unterprogramme 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; }

Kann man jedes der beiden von copy-in/copy-out unterscheiden?

Aufgaben zu Parameter-Modi (III)

  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

Weiters zu Unterprogrammen

Lokale Unterprogramme

int f (int x) {
  int g (int y) { return y + 1; }
  return g (g (x));
}

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, Ketten, Indizes

Während ein Unterprogramm rechnet, stehen seine lokalen Daten in einem Aktivationsverbund (Frame).

Indizes werden statisch bestimmt, Frames zur Laufzeit.

Der Zugriff auf den indizierten Wert ist keine Suche!

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 Unterprogramme

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.

Lokale anonyme Unterprogramme

historische Schreibweise: \(\lambda a b . 2a +b\)

(Alonzo Church: The Calculi of Lambda Conversion, 1941)

vgl. Henk Barendregt: The Impact of the Lambda Calculus, 1997, ftp://ftp.cs.ru.nl/pub/CompMath.Found/church.ps

Lokale Klassen (Java)

Lokale Funktionen in Java 8

interface Function<T,R> { R apply(T t); }

bisher (Java \(\le\) 7):

Function<Integer,Integer> f =
    new Function<Integer,Integer> () { 
        public Integer apply (Integer x) { 
            return x*x; 
    } } ;
System.out.println (f.apply(4));

jetzt (Java 8): verkürzte Notation (Lambda-Ausdruck) für Implementierung funktionaler Interfaces

Function<Integer,Integer> g = x -> x*x;
System.out.println (g.apply(4));

Anwendung u.a. in java.util.stream.Stream<T>

Unterprogramme/Zusammenfassung

in prozeduralen Sprachen:

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

Übungen

Dynamische Polymorphie (Objektorientierung)

Ü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
alert (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 soll wissen, 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

Vererbung

Def: Klasse \(D\) ist abgeleitet von Klasses \(C\):

Anwendung: dynamische Polymorphie

Dynamische Polymorphie (Beispiel)

class C { 
  int x = 2; int p () { return this.x + 3; } 
}
C x = new C() ; int y = x.p ();

Überschreiben:

class E extends C { 
  int p () { return this.x + 4; } 
}
C x =           // statischer  Typ: C
      new E() ; // dynamischer Typ: E
int y = x.p ();

Vererbung bricht Kapselung

Einordnung Objekorientierung

Übung Dynamische Polymorphie

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

  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/11/docs/api/java.base/java/util/AbstractCollection.html#retainAll(java.util.Collection)

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

Durch extends/implements entsteht Halbordnung auf Typen, Bsp.

class C;class D extends C;class E extends C definiert Relation \((\le) = \{ (C,C), (D,C), (D,D), (E,C), (E,E) \}\)
auf \(T=\{C,D,E\}\)

dadurch entsteht Halbordnung auf Methoden-Signaturen (Tupel der Argument-Typen, ohne Resultat-Typ)

Bsp: Relation \(\le^2\) auf \(T^2\):

\((t_1,t_2)\le^2 (t_1', t_2') :\iff t_1\le t_1' \wedge t_2\le t_2'\)

es gilt \((D,D)\le^2(C,C); (D,D)\le^2(C,D);\)
\((C,D)\le^2 (C,C); (E,C)\le^2(C,C)\).

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

Übung Ad-Hoc-Polymorphie

Polymorphie

Übersicht

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

Arten der Polymorphie:

Generische Polymorphie (Typ-Argumente)

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

class Pair<A,B> {
  final A first; final B second;
  Pair(A a, B b) 
    { this.first = a; this.second = b; }
}
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 C {
  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 = 
    C.<String,Integer>swap(p);

Typargumente können auch inferiert werden:

Pair<Integer,String> q = C.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.

Übung Typparameter

  1. Sortieren mit Vergleichsfunktion als Parameter

    (Quelltext: git clone https://gitlab.imn.htwk-leipzig.de/waldmann/pps-ws18.git)

    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)

    2. warum hat dieser weniger Typparameter als intersectionWith?

Mehr zu Polymorphie

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, I<C> <= I<E>

Obere Schranken für Typparameter

Untere Schranken für Typparameter

Vergleich: Varianz und Schranken

Unterscheidung:

Generics und Arrays (in Java)

Übung Polymorphie

Ergänzungen

Statisch typisiert \(\Rightarrow\) sicher und effizient

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?

Fachmännisches Programmieren

so auch bei Programmiersprachen: entworfen für (manchmal auch von) Leute(n) ohne (viel) Fachwissen

Legacy-Sprachen: ECMA-Script (Javascript)

semantisch ist das LISP (z.B. Funktionen als Daten), syntaktisch ist es Java

Aktuelle Entwicklungen: JS

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

Legacy-Sprachen: PHP

Aktuelle Entwicklungen: PHP

Julien Verlaguet: Facebook: Analyzing PHP statically, 2013,

http://cufp.org/2013/julien-verlaguet-facebook-analyzing-php-statically.html

vgl. Neil Savage: Gradual Evolution, Communications of the ACM, Vol. 57 No. 10, Pages 16-18,

http://cacm.acm.org/magazines/2014/10/178775-gradual-evolution/fulltext

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://idris-lang.org/ …aspects of a program’s behaviour can be specified precisely in the type.

(++) : Vec p a -> Vec q a -> Vec (p+q) a

head : Vect (S p) a -> a -- \(S=\) Nachfolger

Nicht reguläre Typen

Zusammenfassung

Themen

Sprachen kommen und gehen, Konzepte bleiben.

Wie weiter? (LV)

Anwendung und Vertiefung von Themen PPS z.B. in VL

Übungen

  1. Colin McMillen, Jason Reed, and Elly Fong-Jones, 2011: Programming Language Checklist https://famicol.in/language_checklist.html You appear to be advocating a new … programming language. Your language will not work. Here is why:…

    Diskutieren Sie die dort genannten Eigenschaften (Pragmatik). Wie sind sie (in dieser VL) definiert? (Semantik)

  2. zu Folie nicht reguläre Typen:

    1. Objekte vom Typ List Bool Int konstruieren,

    2. vom Typ Tree Bool

    3. Data.Sequence: wie sieht eine Folge der Länge 10 intern aus? (der finger tree unter dem Seq-Konstruktor)

  3. Typescript, Rust, Idris, Agda,…ausprobieren

Testfragen

Die folgende Grammatik \(G\) über dem Alphabet \(\Sigma=\{w,f,u,i\}\) soll Ausdrücke mit den Konstanten \(w,f\) und den binären Operatoren \(u,i\) beschreiben: \[G=(\Sigma,\{E\},\{E \to w \mid f \mid E i E \mid E u E\},E).\] Begründen Sie, daß \(G\) mehrdeutig ist.

Gesucht ist eine zu \(G\) äquivalente eindeutige kontextfreie Grammatik \(G'\), für deren Ableitungsbäume gilt: der Operator \(u\) ist linksassoziativ, der Operator \(i\) ist rechtsassoziativ, der Operator \(u\) bindet stärker als der Operator \(i\).

Wie sieht unter diesen Bedingungen der abstrakte Syntaxbaum für \(f i w u f i w\) aus?

Untersuchen Sie, ob \(G_1, G_2, G_3\) die gewünschten Eigenschaften erfüllen. (Falls nein: begründen, falls ja: konkreten Syntaxbaum für \(f i w u f i w\) angeben.)

Nach welcher Regel bestimmt man, ob ein Ausdruck f(x) korrekt getypt ist? (Ohne Berücksichtigung von Vererbung oder Generizität.)

Wie werden die folgenden Operationen für Typen in Programmiersprachen realisiert?

In Java gibt es keine direkte Realisierung der Vereinigung, was wird stattdessen empfohlen?

Für das Ada-Programm:

Zeichnen Sie die Frames mit allen Einträgen und Verweisen zu dem Zeitpunkt direkt vor dem ersten Aufruf von Put_Line.

Wie wird auf die Werte von X und Y zugegriffen, die in Integer'Image(X+Y) benötigt werden?

Für folgende Deklaration:

int a [] = { 1,2,0 }; void p (int x, int y) { a[y] = x; x = y; }

betrachten wir den Aufruf p(a[0], a[1]).

Geben Sie die Ausführungsschritte sowie die resultierende Speicherbelegung an, falls zur Parameterübergabe benutzt wird:

Für die Deklarationen:

class C { }    class D extends C { }
static void p (Object x, C      y) { System.out.println ("1"); }
static void p (D      x, C      y) { System.out.println ("2"); }
static void p (C      x, Object y) { System.out.println ("3"); }

Beschreiben Sie, wie die Überladung für die folgenden Aufrufe aufgelöst wird: