Typen

• Typ ist Menge von Werten mit Operationen
• für jede eigene Menge von Werten (Variablen) aus dem Anwendungsbereich benutze eine eigenen Typ
• halte verschiedene Typen sauber getrennt, mit Hilfe der Programmiersprache
• der Typ einer Variablen/Funktion ist ihre beste Dokumentation

• keine Typen (alles ist int)
• vorgegebene Typen (Fortran: Integer, Real, Arrays)
• benutzerdefinierte Typen

  (algebraische Datentypen;

  Spezialfälle: enum, struct, class)

• abstrakte Datentypen (interface)

• einfache (primitive) Typen
  • Zahlen, Wahrheitswerte, Zeichen
  • benutzerdefinierte Aufzählungstypen
  • Teilbereiche

• zusammengesetzte (strukturierte) Typen
  • Produkt (records)
  • Summe (unions)
  • rekursive Typen
  • Potenz (Funktionen: Arrays, (Tree/Hash-)Maps, Unterprogramme)
  • Verweistypen (Zeiger)

können einer Teilmenge ganzer Zahlen zugeordnet werden

• vorgegeben: int, char, boolean
• nutzerdefiniert (enum)

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

Designfragen:

• automatisch nach int umgewandelt?
• automatisch von int umgewandelt?
• eine Konstante in mehreren Aufzählungen möglich?

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

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?

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)

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!

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.

Typ = Menge, Zusammensetzung = Mengenoperation:

• Produkt (record, struct)
• Summe (union, case class)
• Rekursion
• Potenz (Funktion)

R = A×B×C

Kreuzprodukt mit benannten Komponenten:

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

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

erstmalig in COBOL (≤1960 )

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

R = A∪B∪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;
}

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

physikalische Größe = Maßzahl × 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

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)

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

ist sinnvolle Notation, denn | B|^{| A|} = $\left\vert\vphantom{B^A}\right.$B^A$\left.\vphantom{B^A}\right\vert$

spezielle Realisierungen:

• Funktionen (Unterprogramme)
• Wertetabellen (Funktion mit endlichem Definitionsbereich) (Assoziative Felder, Hashmaps)
• Felder (Definitionsbereich ist Aufzählungstyp) (Arrays)
• Zeichenketten (Strings)

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

Design-Entscheidungen:

• welche Index-Typen erlaubt? (Zahlen? Aufzählungen?)
• Bereichsprüfungen bei Indizierungen?
• Index-Bereiche statisch oder dynamisch?
• Allokation statisch oder dynamisch?
• Initialisierung?
• mehrdimensionale Felder gemischt oder rechteckig?

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

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.

Unterschiede zwischen

• int [][] a
• int [,] a

in

• Benutzung (Zugriff)
• Initialisierung durch Array-Literal

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 [][].)

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

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.

• Typ T , Typ der Verweise auf T .
• Operationen: new, put, get, delete
• ähnlich zu Arrays (das Array ist der Hauptspeicher)

explizite Verweise in C, Pascal

implizite Verweise:

• Java: alle nicht primitiven Typen sind Verweistypen, De-Referenzierung ist implizit
• C#: class ist Verweistyp, struct ist Werttyp

• für Objekte, deren Typ class ... ist:

  Verweis-Semantik (wie in Java)

• für Objekte, deren Typ struct ... ist:

  Wert-Semantik

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

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

• Teilbereichstypen und abgeleitete Typen in Ada (Vergleich mit dimensionierten Typen in F#)
• Arrays in C (Assemblercode anschauen)
• rechteckige und geschachtelte Arrays in C#
• Wert/Verweis (struct/class) in C#