Einleitung

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

Sprache

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 ]

Kellermaschine in 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

Mit gv oder kghostview ansehen (Options: watch file). Mit Editor Quelltext ändern. Finden Sie den Autor dieses Programms!

(Lösung: John Tromp, siehe auch http://www.iwriteiam.nl/SigProgPS.html)

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

Übung: Beispiele für Übersetzer

Java:

javac Foo.java # erzeugt Bytecode (Foo.class)
java Foo       # führt Bytecode aus (JVM)

Einzelheiten der Übersetzung:

javap -c Foo   # druckt Bytecode

C:

gcc -c bar.c   # erzeugt Objekt(Maschinen)code (bar.o)
gcc -o bar bar.o # linkt (lädt) Objektcode (Resultat: bar)
./bar         # führt gelinktes Programm aus

Einzelheiten:

gcc -S bar.c # erzeugt Assemblercode (bar.s)

Aufgaben:

gcc für Java (gcj):

gcj -c Foo.java # erzeugt Objektcode
gcj -o Foo Foo.o --main=Foo # linken, wie oben

Syntax von Programmiersprachen

Programme als Bäume

Token-Typen

Token-Typen sind üblicherweise

alle Token eines Typs bilden eine formale Sprache

Formale Sprachen

Beispiele:

Spezifikation formaler Sprachen

man kann eine formale Sprache beschreiben durch:

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 Reg. Ausdr.

Wort-Ersetzungs-Systeme

Berechnungs-Modell (Markov-Algorithmen)

Regelmenge \(R \subseteq \Sigma^* \times \Sigma^*\)

Regel-Anwendung: \(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\).

Beispiel: Bubble-Sort: \(\{ba \to ab, ca \to ac, cb \to bc\}\)

Beispiel: Potenzieren: \(ab \to bba\)

Aufgaben: gibt es unendlich lange Rechnungen für: \(R_1 = \{ 1000 \to 0001110 \}, R_2= \{ aabb \to bbbaaa \}\)?

Grammatiken

0.5 Grammatik \(G\) besteht aus:

0.5

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.

Programmiersprachen werden kontextfrei beschrieben (mit Zusatzbedingungen).

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

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

Übungen

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

Def: der Rand eines geordneten, markierten Baumes \((T,m)\) ist die Folge aller Blatt-Markierungen (von links nach rechts).

Beachte: die Blatt-Markierungen sind \(\in \{\epsilon\} \cup \Sigma \), d. h. Terminalwörter der Länge 0 oder 1.

Für Blätter: \({\operatorname{rand}}(b)=m(b)\), für innere Knoten: \({\operatorname{rand}}(k)={\operatorname{rand}}(k_1) {\operatorname{rand}}(k_2)\ldots {\operatorname{rand}}(k_n)\)

Satz: \(w \in L(G) \iff\) existiert Ableitungsbaum \((T,m)\) für \(G\) mit \({\operatorname{rand}}(T,m)=w\).

Eindeutigkeit

Def: \(G\) heißt eindeutig, falls \(\forall w \in L(G)\) genau ein Ableitungsbaum \((T,m)\) existiert.

Bsp: ist \(\{ S \to aSb | SS | \epsilon \}\) eindeutig?

(beachte: mehrere Ableitungen \(S \to_R^* w\) sind erlaubt, und wg. Kontextfreiheit auch gar nicht zu vermeiden.)

Die naheliegende Grammatik für arith. Ausdr.

expr -> number | expr + expr | expr * expr

ist mehrdeutig (aus zwei Gründen!)

Auswege:

Assoziativität

Assoziativität (II)

X1 + X2 + X3 auffassen als (X1 + X2) + X3

Grammatik-Regeln

Ausdruck -> Zahl | Ausdruck + Ausdruck

ersetzen durch

Ausdruck -> Summe 
Summe    -> Summand | Summe + Summand
Summand  -> Zahl

Präzedenzen

\[(3+2)*4 \stackrel{?}{=} 3+2*4 \stackrel{?}{=} 3+(2*4)\]

Grammatik-Regel

summand -> zahl

erweitern zu

summand -> zahl | produkt
produkt -> ...

(Assoziativität beachten)

Zusammenfassung Operator/Grammatik

Ziele:

Festlegung:

Realisierung in CFG:

Übung Operator/Grammatik

Übung:

Das hängende else

naheliegende EBNF-Regel für Verzweigungen:

<statement> -> if <expression> 
    then <statement> [ else <statement> ]

führt zu einer mehrdeutigen Grammatik.

Dieser Satz hat zwei Ableitungsbäume:

if X1 then if X2 then S1 else S2

Semantik von Programmiersprachen

Statische und dynamische Semantik

Semantik \(=\) Bedeutung

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

String x = "foo"; String y = "bar";

Boolean.toString (x.length() < y.length()));

(Curry-Howard-Isomorphie)

Übung Attributgrammatiken/SableCC

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

Bsp. Operationale Semantik (I)

arithmetischer Ausdruck \(\Rightarrow\) Programm für Kellermaschine

\(3*x + 1\) \(\Rightarrow\) push 3, push x, mal, push 1, plus

Der erzeugte Code ist synthetisiertes Attribut!

Beispiele: Java-Bytecode (javac, javap),
CIL (gmcs, monodis)

Bemerkung: soweit scheint alles trivial—interessant wird es bei Teilausdrücken mit Nebenwirkungen, Bsp. x++ - --x;

Bsp: Operationale Semantik (II)

Schleife

while (B) A

wird übersetzt in Sprungbefehle

   if (B) ...

(vervollständige!)

Aufgabe: übersetze for(A; B; C) D in while!

Denotationale Semantik

Beispiele

Vorteile denotationaler Semantik:

Vorteil deklarativer Programierung:

Programmiersprache ist Beschreibungssprache

Beispiele Denotationale Semantik

Beispiel: Semantik von Unterprogr.

Unterprogramme definiert durch Gleichungssysteme.

Sind diese immer lösbar? (überhaupt? eindeutig?)

Geben Sie geschlossenen arithmetischen Ausdruck für:

f (x) = if x > 52 
        then x - 11 
        else f (f (x + 12))

g(x,y) = 
  if x <= 0 then 0 
  else if y <= 0 then 0
  else 1 + g (g (x-1, y), g (x, y-1))

Axiomatische Semantik

Notation für Aussagen über Programmzustände:

{ V } A { N }

Beispiel:

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

Gültigkeit solcher Aussagen kann man

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

Kalkül: für jede Form der Anweisung ein Axiom, Beispiele:

Axiom für Schleifen

wenn  { I and B } A { I },
dann  { I } while (B) do A { I and not B }

Beispiel:

Eingabe int p, q; 
// p = P und q = Q
int c = 0;
// inv: p * q + c = P * Q 
while (q > 0) { 
   ???
}
// c = P * Q

Moral: erst Schleifeninvariante (Spezifikation), dann Implementierung.

Übungen (Stackmaschine)

Schreiben Sie eine Java-Methode, deren Kompilation genau diesen Bytecode erzeugt: a)

  public static int h(int, int);
    Code:
       0: iconst_3      
       1: iload_0       
       2: iadd          
       3: iload_1       
       4: iconst_4      
       5: isub          
       6: imul          
       7: ireturn

b)

  public static int g(int, int);
    Code:
       0: iload_0       
       1: istore_2      
       2: iload_1       
       3: ifle          17
       6: iload_2       
       7: iload_0       
       8: imul          
       9: istore_2      
      10: iload_1       
      11: iconst_1      
      12: isub          
      13: istore_1      
      14: goto          2
      17: iload_2       
      18: ireturn

Übungen (Invarianten)

Ergänze das Programm:

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) {
    ???
    b = abrunden (b/2);
}
Ausgabe: p; // p = A^B

Typen

Warum Typen?

Historische Entwicklung

Überblick

Aufzählungstypen

können einer Teilmenge ganzer Zahlen zugeordnet werden

Designfragen:

Keine Aufzählungstypen

das ist nett gemeint, aber vergeblich:

#define Mon 0
#define Tue 1
...
#define Sun 6

typedef int day;

int main () {
    day x = Sat;
    day y = x * x;
}

Aufzählungstypen in C

im wesentlichen genauso nutzlos:

typedef enum { 
   Mon, Tue, Wed, Thu, Fri, Sat, Sun 
} day;

int main () {
    day x = Sat;
    day y = x * x;
}

Übung: was ist in C++ besser?

Aufzählungstypen in Java

enum Day {
    Mon, Tue, Wed, Thu, Fri, Sat, Sun;

    public static void main (String [] argv) {
        for (Day d : Day.values ()) {
            System.out.println (d);
        }
    }
}

verhält sich wie Klasse

(genauer: Schnittstelle mit 7 Implementierungen)

siehe Übung (jetzt oder bei Objekten)

Teilbereichstypen in Ada

with Ada.Text_Io;
procedure Day is
   type Day is ( Mon, Tue, Thu, Fri, Sat, Sun );
   subtype Weekday is Day range Mon .. Fri;
   X, Y : Day;
begin
   X := Fri;     Ada.Text_Io.Put (Day'Image(X));
   Y := Day'Succ(X); Ada.Text_Io.Put (Day'Image(Y));
end Day;

mit Bereichsprüfung bei jeder Zuweisung.

einige Tests können aber vom Compiler statisch ausgeführt werden!

Abgeleitete Typen in Ada

procedure Fruit is
   subtype Natural is 
       Integer range 0 .. Integer'Last;
   type Apples  is new Natural;
   type Oranges is new Natural;
   A : Apples; O : Oranges; I : Integer;
begin -- nicht alles korrekt:
   A := 4; O := A + 1; I := A * A;
end Fruit;

Natural, Äpfel und Orangen sind isomorph, aber nicht zuweisungskompatibel.

Sonderfall: Zahlenkonstanten gehören zu jedem abgeleiteten Typ.

Zusammengesetzte Typen

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

Produkttypen (Records)

\(R = A \times B \times C\)

Kreuzprodukt mit benannten Komponenten:

typedef struct {
    A foo;
    B bar;
    C baz;
} R;

R x; ...  B x.bar; ...

erstmalig in COBOL (\(\le 1960\))

Übung: Record-Konstruktion (in C, C++)?

Summen-Typen

\(R = A \cup B \cup C\)

disjunkte (diskriminierte) Vereinigung (Pascal)

type tag = ( eins, zwei, drei );
type R = record case t : tag of
    eins : ( a_value : A );
    zwei : ( b_value : B );
    drei : ( c_value : C );
end record;

nicht diskriminiert (C):

typedef union {
    A a_value; B b_value; C c_value;
}

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

Maßeinheiten in F#

physikalische Größe \(=\) Maßzahl \(\times\) Einheit.

viele teure Softwarefehler durch Ignorieren der Einheiten.

in F# (Syme, 200?), aufbauend auf ML (Milner, 197?)

[<Measure>] type kg ;;
let x = 1<kg> ;;
x * x ;;
[<Measure>] type s ;;
let y = 2<s> ;;
x * y ;;
x + y ;;

http://msdn.microsoft.com/en-us/library/dd233243.aspx

Rekursiv definierte Typen

Haskell (http://haskell.org/)

data Tree a = Leaf a 
            | Branch ( Tree a ) ( Tree a )
data List a = Nil | Cons a ( List 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 }

das ist ein algebraischer Datentyp,

die Konstruktoren (Leaf, Nil) bilden die Signatur der Algebra,

die Elemente der Algebra sind Terme (Bäume)

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)

Design-Entscheidungen:

Felder in C

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

statische Dimensionierung, dynamische Allokation, keine Bereichsprüfungen.

Form: rechteckig, Adress-Rechnung:

int [M][N];
a[x][y]  ==>  *(&a + (N*x + y))

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

dynamische Dimensionierung und Allokation, Bereichsprüfungen. Nicht notwendig rechteckig.

Felder in C#

Unterschiede zwischen

in

Nicht rechteckige Felder in C?

Das geht:

int a [] = {1,2,3};
int b [] = {4,5};
int c [] = {6};
    e    = {a,b,c};
printf ("%d\n", e[1][1]);

aber welches ist dann der Typ von e?

(es ist nicht int e [][].)

Dynamische Feldgrößen

Designfrage: kann ein Feld (auch: String) seine Größe ändern?

(C: wird sowieso nicht geprüft, Java: nein, Perl: ja)

in Java: wenn man das will, dann will man statt Array eine LinkedList, statt String einen StringBuffer.

wenn man mit Strings arbeitet, dann ist es meist ein Fehler:

benutze Strings zwischen Programmen,
aber niemals innerhalb eines Programms.

ein einem Programm: benutze immer anwendungsspezifische Datentypen.

…deren externe Syntax spiel überhaupt keine Rolle

Kosten der Bereichsüberprüfungen

es wird oft als Argument für C (und gegen Java) angeführt, daß die erzwungene Bereichsüberprüfung bei jedem Array-Zugriff so teuer sei.

sowas sollte man erst glauben, wenn man es selbst gemessen hat.

modernen Java-Compiler sind sehr clever und können theorem-prove away (most) subscript range checks

das kann man auch in der Assembler-Ausgabe des JIT-Compilers sehen.

http://www.imn.htwk-leipzig.de/~waldmann/etc/safe-speed/

Verweistypen

explizite Verweise in C, Pascal

implizite Verweise:

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

Übung Typen

Bezeichner, Bindungen, Bereiche

Variablen

vereinfacht: Variable bezeichnet eine (logische) Speicherzelle

genauer: Variable besitzt Attribute

Bindungen dieser Attribute statisch oder dynamisch

Namen in der Mathematik

in der Programmierung:

Namen

Typen für Variablen

Vor/Nachteile: Lesbarkeit, Sicherheit, Kosten

Dynamisch getypte Sprachen

Daten sind typisiert, Namen sind nicht typisiert.

LISP, Clojure, PHP, Python, Perl, Javascript, …

var foo = function(x) {return 3*x;};
foo(1);
foo = "bar";
foo(1);

Statisch getypte Sprachen

Daten sind typisiert, Namen sind typisiert

Invariante:

woher kommt der statische Typ?

Typdeklarationen

im einfachsten Fall (Java, C#):

Typname Variablenname [ = Initialisierung ] ;
int []  a = { 1, 2, 3 };
Func<double,double> f = (x => sin(x));

gern auch komplizierter (C): dort gibt es keine Syntax für Typen, sondern nur für Deklarationen von Namen.

double f (double x) { return sin(x); }
int * p;
double ( * a [2]) (double) ;

Beachte: * und [] werden von außen nach innen angewendet

Ü: Syntaxbäume zeichnen, a benutzen

Typinferenz in C# und Java

C#:

public class infer {
    public static void Main (string [] argv) {
        var arg = argv[0];
        var len = arg.Length;
        System.Console.WriteLine (len);
    }
}

Ü: das var in C# ist nicht das var aus Javascript.

Java:

für formale Parameter von anonymen Unterprogrammen

Function<Integer,Integer> f = (x) -> x;

Konstanten

\(=\) Variablen, an die genau einmal zugewiesen wird

Vorsicht:

class C { int foo; }
static void g (final C x) { x.foo ++; }

Merksatz: alle Deklarationen so lokal und so konstant wie möglich!

(D. h. Attribute immutable usw.)

Lebensort und -Dauer von Name und Daten

Beachte (in Java u.ä.) in { C x = new C(); } ist x Stack-lokal, Inhalt ist Zeiger auf das Heap-globale Objekt.

Sichtbarkeit von Namen

\(=\) Bereich der Anweisungen/Deklarationen, in denen ein Name benutzt werden kann.

Üblich ist: Sichtbarkeit beginnt nach Deklaration und endet am Ende des umgebenden Blockes

Tatsächlich (Java, C):

Sichtbarkeit beginnt schon in der Initalisierung

int x = sizeof(x); printf ("%d\n", x);

Ü: ähnliches Beispiel für Java? Vgl. JLS Kapitel 6.

Sichtbarkeit in JavaScript

Namen sind sichtbar

Ü: erkläre das Verhalten von

(function(){let x=8; {x=9} return x} )()
(function(){let x=8; {x=9;let x=10} return x} )()

durch die Sprachspezifikation
(und nicht durch Sekundärquellen)

Überdeckungen

Namen sind auch in inneren Blöcken sichtbar:

int x;
while (..) {
  int y;
  ... x + y ... 
}

innere Deklarationen verdecken äußere:

int x;
while (..) {
  int x;
  ... x ... 
}

Sichtbarkeit und Lebensdauer

…stimmen nicht immer überein:

Ausdrücke

Einleitung

Vgl. Trennung (in Pascal, Ada)

Einleitung (II)

Designfragen für Ausdrücke

Syntax von Ausdrücken

wichtige Spezialfälle für Operatoren:

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

Syntax von Konstanten

Was druckt diese Anweisung?

System.out.println ( 12345 + 5432l );

dieses und einige der folgenden Beispiele aus: Joshua Bloch, Neil Gafter: Java Puzzlers, Addison-Wesley, 2005.

Der Plus-Operator in Java

…addiert Zahlen und verkettet Strings.

System.out.println ("foo" + 3 + 4);
System.out.println (3 + 4 + "bar");

Überladene Operatornamen

aus praktischen Gründen sind arithmetische und relationale Operatornamen überladen

(d. h.: ein Name für mehrere Bedeutungen)

Überladung wird aufgelöst durch die Typen der Argumente.

int x = 3; int y = 4; ... x + y ...
double a;   double b; ... a + b ...
String p;   String q; ... p + q ...

Automatische Typanpassungen

in vielen Sprachen postuliert man eine Hierarchie von Zahlbereichstypen:

\(\textrm{byte} \subseteq \textrm{int} \subseteq \textrm{float} \subseteq \textrm{double}\)

im allgemeinen ist das eine Halbordnung.

Operator mit Argumenten verschiedener Typen: (x :: int) + (y :: float)

beide Argumente werden zu kleinstem gemeinsamen Obertyp promoviert, falls dieser eindeutig ist (sonst statischer Typfehler)

(Halbordnung \(\to\) Halbverband)

Implizite/Explizite Typumwandlungen

Was druckt dieses Programm?

long x = 1000 * 1000 * 1000 * 1000;
long y = 1000 * 1000;
System.out.println ( x / y );

Was druckt dieses Programm?

System.out.println ((int) (char) (byte) -1);

Moral: wenn man nicht auf den ersten Blick sieht, was ein Programm macht, dann macht es wahrscheinlich nicht das, was man will.

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

0.5 Absicht: statt

if ( 0 == x % 2 ) {
  x = x / 2;
} else {
  x = 3 * x + 1;
}

0.5 lieber

x = if ( 0 == x % 2 ) {
      x / 2
    } else {
      3 * x + 1
    } ;

historische Notation dafür

x = ( 0 == x % 2 ) ? x / 2 : 3 * x + 1;

?/: ist ternärer Operator

Verzweigungs-Operator(II)

(... ? ... : ... ) in C, C++, Java

Anwendung im Ziel einer Zuweisung (C++):

int main () {
    int a = 4; int b = 5; int c = 6;
    ( c < 7 ? a : b ) = 8;
}

Relationale Operatoren

kleiner, größer, gleich,…

Was tut dieses Programm (C? Java?)

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

Logische (Boolesche) Ausdrücke

Noch mehr Quizfragen

Erklären durch Verweis auf Java Language Spec.

Der Zuweisungs-Operator

Syntax:

Semantik der Zuweisung a = b:

Ausdrücke links und rechts werden verschieden behandelt:

Weitere Formen der Zuweisung

(in C-ähnlichen Sprachen)

Ausdrücke mit Nebenwirkungen

(side effect; falsche Übersetzung: Seiteneffekt)

in C-ähnlichen Sprachen: Zuweisungs-Operatoren bilden Ausdrücke, d. h. Zuweisungen sind Ausdrücke und können als Teile von Ausdrücken vorkommen.

Wert einer Zuweisung ist der zugewiesene Wert

int a; int b; a = b = 5; // wie geklammert?

Komma-Operator zur Verkettung von Ausdrücken (mit Nebenwirkungen)

for (... ; ... ; i++,j--) { ... }

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

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 machen, was er will)

int x = 3; int y = ++x + ++x + ++x;

vgl. Aussagen zu sequence points in http://gcc.gnu.org/readings.html

Gurevich, Huggins: Semantics of C, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.6755

Anweisungen(I)

Definition

Semantik: Anweisung hat Wirkung (Zustandsänderung), die bei Ausführung eintritt.

abstrakte Syntax:

Programm-Ablauf-Steuerung

Ausführen eines Programms im von-Neumann-Modell:

Was? (Operation) Womit? (Operanden) Wohin? (Resultat) Wie weiter? (nächste Anweisung)

strukturierte Programmierung:

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: Deklarationen gestattet

Verzweigungen (zweifach)

in den meisten Sprachen:

if Bedingung then Anweisung1 
     [ else Anweisung2 ]

Designfragen:

Mehrfach-Verzweigung

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

Designfragen:

Switch/break

das macht eben in C, C++, Java nicht das, was man denkt:

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

C#: jeder Fall muß mit break (oder goto) enden.

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

Anweisungen(II)

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.

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?

Auswertung der Umfrage

http://www.imn.htwk-leipzig.de/~waldmann/edu/ws13/pps/umfrage/

Unterprogramme

Grundsätzliches

Ein Unterprogramm ist ein benannter Block mit einer Schnittstelle. Diese beschreibt den Datentransport zwischen Aufrufer und Unterprogramm.

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

by value:

static void u (int x) { x = x + 1; }
int y = 3 ; u (y); 
Console.WriteLine(y); // 3

by reference:

static void u (ref int x) { x = x + 1; }
int y = 3 ; u (ref y); 
Console.WriteLine(y); // 4

Übung: ref/kein ref; struct (Werttyp)/class (Verweistyp)

class C { public int foo }
static void u (ref C x) { x.foo=4; x=new C{foo=5};}
C y = new C {foo=3} ; C z = y; u (ref y);
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?

Lokale Unterprogramme

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

Statische und dynamische Sichtbarkeit

Zugriff auf nichtlokale Variablen? (Bsp: Zugriff auf X in F)

with Ada.Text_Io; use Ada.Text_Io;
procedure Nest is
   X : Integer := 4;
   function F (Y: Integer) return Integer is
   begin return X + Y; end F;
   function G (X : Integer) return Integer is
   begin return F(3 * X); end G;
begin Put_Line (Integer'Image (G(5)));
end Nest;

Frames, Ketten

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

Jeder Frame hat zwei Vorgänger:

Jeder Variablenzugriff hat Index-Paar \((i,j)\):

im \(i\)-ten statischen Vorgänger der Eintrag Nr. \(j\)

lokale Variablen des aktuellen UP: Index \((0,j)\)

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;

Flache Unterprogramme (C)

Entwurfs-Entscheidung für C:

Folgerung:

Lokale Unterprogramme in C# und Java

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.

Polymorphie

Übersicht

poly-morph \(=\) viel-gestaltig

ein Bezeichner (z. B. Unterprogramm-Name) mit mehreren Bedeutungen

Arten der 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

Durch extends/implements entsteht eine 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\}\)

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

Generische Polymorphie

parametrische Polymorphie:

Bsp: Generische Methode in C#

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

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

Dynamische Polymorphie (Objektorientierung)

Definitionen

ein Bezeichner mit mehreren Bedeutungen

poly-morph \(=\) viel-gestaltig. Formen 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)

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

class C { 
   void p () { ... q(); ...  }; 
   void q () { .. };
}

Jetzt wird q überschrieben (evtl. auch unabsichtlich—in Java), dadurch ändert sich das Verhalten von p.

class D extends C {
   void q () { ... }
}

Korrektheit von D abhängig von Implementierung von C

\(\Rightarrow\) object-orientation is, by its very nature, anti-modular …

http://existentialtype.wordpress.com/2011/03/15/teaching-fp-to-freshmen/

Ü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

für diese findet kein dynmischer Dispatch statt. (Beispiele—Puzzle 48, 54)

Damit das klar ist, wird dieser Schreibstil empfohlen:

Generische Fkt. höherer Ordg.

Anwendung: 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)

Anonyme Typen (Wildcards)

Wenn man einen generischen Typparameter nur einmal braucht, dann kann er ? heißen.

List<?> x = Arrays.asList
    (new String[] {"foo","bar"});
Collections.reverse(x);
System.out.println(x);

jedes Fragezeichen bezeichnet einen anderen (neuen) Typ:

List<?> x = Arrays.asList
    (new String[] {"foo","bar"});
List<?> y = x;
y.add(x.get(0));

Vererbung und generische Polym. (I)

interface I { void P (); }
static void Q (IList<I> xs) 
    { foreach (I x in xs) { x.P(); } }
static void R<C> (Action<C> S, IList<C> xs)
    { foreach (C x in xs) { S(x); } }

für gleichzeitige Behandlung mehrerer Objekte
ist Vererbungspolymorphie meist ungeeignet

(z. B. Object.equals(Object o) falsch, Comparable<T>.compareTo(T o) richtig)

Vererbung und generische Polym. (II)

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:

Statische Sicherheit

Obere Schranken für Typparameter

Untere Schranken für Typparameter

Wildcards und Bounds

List<? extends Number> z = 
    Arrays.asList(new Double[]{1.0, 2.0});
z.add(new Double(3.0));

variante generische Interfaces (C#)

Kontravarianz (in P), Kovarianz (out P)

interface I<in P> { // kontravariante Dekl.
  // 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 {} // E <= C
I<C> x = new K<C>(); 
I<E> y = x; // erlaubt, I<C> <= I<E>

Vergleich: Varianz und Schranken

Unterscheidung:

Generics und Arrays

das gibt keinen Typfehler:

class C { }
class E extends C { void m () { } }

E [] x = { new E (), new E () };
C [] y = x;

y [0] = new C ();
x [0].m();

aber …(Übung)

Generics und Arrays (II)

warum ist die Typprüfung für Arrays schwächer als für Collections?

Historische Gründe. Das sollte gehen:

void fill (Object[] a, Object x) { .. }
String [] a = new String [3];
fill (a, "foo");

Das sieht aber mit Generics besser so aus: …

Ü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 Jahrtzehnten (Algol 1960, ML 1970, C++ 1980, Java 1990 usw.)

Was dagegen?

Fachmännisches Programmieren

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

wichtige falsche Sprachen: JS

ECMA-Script (Javascript)

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

wichtige falsche Sprachen: PHP

Aktuelle Entwicklungen: JS

…was ist mit Microsoft? Die haben auch viel Geld und clevere Leute? — Ja:

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

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

Die Zukunft: Typen für Ressourcen

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

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

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

Zusammenfassung

Themen

Sprachen kommen und gehen, Konzepte bleiben.

autotool-Auswertung

117 : 6*76* :   4   1   2                       1    
 77 : 6*25* :   1   1   2   1   1       1   1   1    
 67 : 6*23* :   3                       1   1        
 55 :

Bemerkungen

Wie weiter? (LV)

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

Wie weiter? (Masterprojekt/Arbeit, WHK)

Die neue autotool-Oberfläche

https://autotool-test.imn.htwk-leipzig.de/semester/81/vorlesungen

Testfragen