↑Programmieren in Rust

Zusammengesetzte Typen

Inhaltsverzeichnis

1. Strukturen
2. Enumerationen
3. Nominale Typisierung
4. Methoden
5. Algebraischer Aspekt

Strukturen

Zum Verständnis möchte ich zunächst auf eine Konstruktion in der Mengenlehre eingehen. Für zwei Mengen A und B ist das kartesische Produkt definiert als

A × B := {(a, b) | a ∈ A ∧ b ∈ B},

das ist die Menge aller geordneten Paare, bei denen die erste Komponente ein Element von A und die zweite Komponente ein Element von B ist.

Bei den Typen gibt es eine direkte Entsprechung des kartesischen Produktes. Man stelle sich einen Datentyp hierfür als Menge von zulässigen Werten vor. In Rust schreibt man den Produkttyp als (A, B), und dessen Elemente als (a, b). Zu beachten ist, dass die Indizierung nicht bei eins startet, sondern bei null. Ein Beispiel dazu:

fn main() {
    let t: (u32, u32) = (360, 240);
    println!("({} | {})", t.0, t.1);
}

Aus ergonomischen Gründen ist es nun wünschenswert, die Komponenten der Tupel nicht unter ihrem Index anzusprechen, sondern über Bezeichner. Man schreibt dann z. B. struct Name {a: A, b: B}, wobei die erste Komponente unter dem Bezeichner a und die zweite unter b angesprochen wird. Ein Beispiel dazu:

struct Point {
    a: u32, b: u32
}

fn main() {
    let t: Point = Point {a: 360, b: 240};
    println!("({} | {})", t.a, t.b);
}

Ein als struct definierter zusammengesetzter Datentyp wird als Struktur bezeichnet. In der theoretischen Informatik spricht man vom Produkt. Bei Pascal und verwandten Sprachen kennt man die synonymen Begriffe Record und Verbund.

Enumerationen

Zum tieferen Verständnis möchte ich zunächst wieder eine Konstruktion der Mengenlehre erläutern. Zu je zwei Mengen A und B darf man die Vereinigungsmenge A ∪ B bilden, die ein Element genau dann enthält, wenn es in A oder in B enthalten ist. Nun kann es sein, dass sich die Mengen A und B überschneiden, dass es also Elemente gibt, die sowohl in A als auch in B enthalten sind. Wir würden die Überschneidung nun gerne künstlich verhindern, beispielsweise, indem die Elemente vor der Vereinigung eingefärbt werden. Alle Elemente von A werden in Blau eingefärbt und alle Elemente von B in Grün.

Anstelle der Einfärbung lässt sich ein Element genauso gut mit einem Tag versehen, auch Diskriminator genannt. Jedes Element von A bekommt das Tag 0 und jedes Element von B das Tag 1. Insofern ist die disjunkte Vereinigung gemäß

A + B := {(0, a) | a ∈ A} ∪ {(1, b) | b ∈ B}

definiert.

Auch zur disjunkten Vereinigung gibt es eine Entsprechung für Typen. Die obige Formulierung würde man als

enum E {T0(A), T1(B)}

schreiben, wobei der Wert E::T0(a) dem Paar (0, a) entspricht, und E::T1(b) dem Paar (1, b). Zu jedem Summand bzw. jedem Tag gibt es eine in die Summe einbettende injektive Funktion. Es gilt folgender Zusammenhang:

E::T0 entspricht der Injektion a ↦ (0, a),
E::T1 entspricht der Injektion b ↦ (1, b).

Tatsächlich darf man

let f: fn(A) -> E = E::T0;

schreiben. Mit E::T0 ist also entweder das Tag oder die zugehörige Injektion gemeint, wobei es nicht sonderlich problematisch ist, zwischen den beiden keine strenge Unterscheidung vorzunehmen.

Aus ergonomischen Gründen ist es nun wieder wünschenswert, wenn Bezeichner anstelle von Indizes als Tags verwendet werden. Das Schlüsselwort enum leitet eine solche Konstruktion ein. Hiermit kann man nun die farbliche Überlegung als

enum E {Blue(A), Green(B)}

darstellen. Ein längeres Beispiel:

enum E {
    Int(i32), Char(char)
}

fn print(x: E) {
    match x {
        E::Int(i) => {println!("Zahl: {}.", i);},
        E::Char(c) => {println!("Zeichen: {}.", c);}
    }
}

fn main() {
    let x: E = E::Int(12);
    let y: E = E::Char('y');
    print(x);
    print(y);
}

Hier ist E eine disjunkte Vereinigung mit den Tags E::Int und E::Char.

Synonym zu Enumeration und Summe spricht man auch von einer diskriminierten Vereinigung, engl. tagged union. Die Entsprechung in der Mengenlehre heißt wie gesagt disjunkte Vereinigung, engl. disjoint union. Die Kategorientheorie abstrahiert die Summe aus der Typentheorie und die disjunkte Vereinigung aus der Mengenlehre zum selben Konzept Koprodukt. Ein solches wird über die Betrachtung der besprochenen Injektionen definiert.

Ein Tag muss nicht unbedingt Daten tragen. Nämlich existiert der Einheitstyp (), der lediglich das leere Tupel () enthält, welches keine Daten tragen kann. Beispielsweise kann man den Typ der Wahrheitswerte damit als

enum Bool {False(()), True(())}

beschreiben. Die Sprache gestattet es, diesen Typ weniger umständlich als

enum Bool {False, True}

zu schreiben. Wahrheitsfunktionen definiert man nun per Fallunterscheidung mit dem Musterabgleich:

use Bool::{False, True};

fn not(a: Bool) -> Bool {
    match a {
        False => True,
        True  => False
    }
}

Wo ein Tag ein Tupel oder eine Struktur trägt, ist eine alternative Formulierung möglich, bei der auf die doppelte Klammerung verzichtet wird. Beispielsweise lässt sich

struct S {x: i32, y: i32}

enum E {
    T((i32, i32)),
    S(S)
}

let e1 = E::T((0, 0));
let e2 = E::S(S {x: 0, y: 0});

alternativ in der Form

enum E {
    T(i32, i32),
    S {x: i32, y: i32}
}

let e1 = E::T(0, 0);
let e2 = E::S {x: 0, y: 0};

ausdrücken.

Nominale Typisierung

Zu unterscheiden ist zwischen struktureller und nominaler Typisierung. Bei der strukturellen Typisierung – man spricht auch von anonymen Typen – stimmen zwei Typen genau dann überein, wenn sie von gleicher Gestalt sind. Bei der nominalen Typisierung stimmen zwei Typen genau dann überein, wenn sie denselben Namen haben, dessen Definition aber einmalig ist. Die nominale Typisierung behaftet so gesagt einen strukturellen Typ mit einem im gesamten Programm und der gesamten Welt einzigartigen Namen, welcher den resultierenden Typ unterschiedlich von allen anderen Typen macht.

Die folgende Tabelle gibt Aufschluss, wie nominale und strukturelle Typen in Rust erstellt werden:

Die strukturelle Typisierung erlaubt vor allem Ergonomie und Komfort. Die nominale Typisierung ist dagegen grundlegend für die Typsicherheit.

Man kann zu jedem beliebigen Typ T einen neuen nominalen erzeugen, indem man ihn als struct Name(T) einhüllt. Dieser neue Typ wird Hülle, engl. wrapper, genannt.

Die Konstruktion komplexer struktureller Typen führt nun zu langer Syntax, – da tut sich die Frage auf, ob sich das denn nicht abkürzen lässt. Dies geschieht durch einen Typalias, der mit dem Schlüsselwort type eingeleitet wird. Mit der Festlegung

type Pair = (i32, i32);

ist Pair also an jeder Stelle des Programms synonym zu (i32, i32).

Methoden

Jedem neu definierten nominalen Typ darf man angebundene Funktionen hinzufügen. Dies geschieht durch Platzierung der Funktionsdefinitionen in einen Block, eingeleitet mit dem Schlüsselwort impl und dem Typname. Bei den angebundenen Funktionen gibt es eine Unterscheidung zwischen Methoden und assoziierten Funktionen. Die assoziierten Funktionen sind ganz gewöhnliche Funktionen, während die Methoden das Argument self besitzen. Das Argument self ist zunächst ein gewöhnliches Argument, erlaubt aber beim Aufruf die Punkt-Schreibweise.

Das folgende Beispiel zeigt einen Typ für Koordinatenvektoren in der Ebene. Hinzugefügt ist eine assoziierte Funktion new zur Konstruktion und eine Methode abs zur Berechnung des Vektorbetrags.

struct Vector {x: f64, y: f64}

impl Vector {
    fn new(x: f64, y: f64) -> Self {
        Self {x, y}
    }
    fn abs(&self) -> f64 {
        f64::sqrt(self.x*self.x + self.y*self.y)
    }
}

fn main() {
    let v = Vector::new(1.0, 1.0);
    println!("{}", v.abs());
}

Hier ist Self ein Typalias für Vector. Außerdem ist &self eine Kurzschreibweise für self: &Self. Die Punkt-Schreibweise v.abs() ist eine Kurzschreibweise für Vector::abs(&v). Somit ist die folgende Formulierung äquivalent:

impl Vector {
    fn new(x: f64, y: f64) -> Vector {
        Vector {x, y}
    }
    fn abs(self: &Vector) -> f64 {
        f64::sqrt(self.x*self.x + self.y*self.y)
    }
}

fn main() {
    let v = Vector::new(1.0, 1.0);
    println!("{}", Vector::abs(&v));
}

Algebraischer Aspekt

Als Zusammensetzung aus Enumerationen und Strukturen bzw. Tupeln konstruierte Typen bezeichnet man auch als algebraische Datentypen. Es verhält sich nämlich so, dass man mit Typen algebraisch rechnen kann.

Betrachten wir einmal diese Komposition:

enum List<T> {
    Nil, Node {data: T, next: Box<List<T>>}
}

bzw.

enum List<T> {
    Nil, Node(T, Box<List<T>>)
}

Aus dieser rekursiven Definition entstehen einfach verkettete Listen:

Vergessen wir nun einmal all die nominale Typisierung und betrachten nur die Struktur. Die Indirektion über einen Zeiger (Box) ist in Rust notwendig, damit ein Knoten feste Speichergröße hat, kann aber für die weitere Betrachtung fortgelassen werden. Der Typparameter kann außerdem entfernt werden, wenn T ein fester Typ ist. Das ergibt dann:

enum List {Nil, Node(T, List)}

Man schreibt nun A*B anstelle von (A,B), und A+B anstelle enum {A,B}. Außerdem ist Nil strukturell gesehen nichts anderes als der Typ Unit, oder () in Rust, der nur das leere Tupel () enthält. Algebraisch sind Typen durch die Anzahl ihrer Elemente charakterisiert, es gilt also Unit = 1. Damit bekommt man

List := 1 + T*List.

Von der Gestalt her handelt es sich hierbei um eine Fixpunktgleichung. Die erste Iteration und anschließendes Ausmultiplizieren ergibt

List = 1 + T*(1 + T*List) = 1 + T + T*T*List.

Fortwährende Iteration führt zur unendlichen Enumeration

List = 1 + T + T*T + T*T*T + T*T*T*T + ...

Und dies ist genau die Struktur dieses Datentyps. Die Enumeration zählt die Möglichkeiten der Liste auf, eine bestimmte Länge zu haben.