Wie Programme funktionieren (2a): Typen als Spezifikation und Varianz

Track Konzepte · Sprachen und Typen · ca. 55 Min.

Worum es geht

Ein Typ ist mehr als ein Etikett für den Compiler. Ein guter Typ ist eine Spezifikation (specification): Er sagt, welche Werte überhaupt existieren dürfen. Ein schlechter Typ lässt Zustände zu, die es fachlich nie geben darf, und dann musst du in jeder Funktion prüfen, ob du gerade in so einem Zustand gelandet bist. Das Ziel heißt Make illegal states unrepresentable (unmögliche Zustände nicht darstellbar machen).

Dazu kommt eine Frage, die Interviews und Reviews immer wieder stellen: Warum ist eine Liste von Hunden nicht einfach eine Liste von Tieren? Das ist die Frage nach Varianz (variance).

Am Ende von Teil a kannst du Zustände als Sum Type modellieren (Übung 1), Varianz an einer Mini-Typhierarchie berechnen (Übung 2) und einen Subtyp-Prüfer selbst bauen (Übung 3). Type Hints in Python selbst streift Python 2 (Schritt 5 dort). Hier geht es um das Konzept dahinter, das für TypeScript, Python, Kotlin oder Rust gleich gilt.

Teil b (Ausführungsmodelle, JIT und Paradigmen) behandelt, was zwischen Quelltext und Ausführung passiert.

Plane ehrlich 55 Minuten ein: etwa 25 Minuten Lesen (vier Schritte), 28 Minuten Übungen (drei Stück, eine davon kurz).

Von JS/TS her gedacht

Du kennst das Typsystem von TypeScript sehr gut. Hier die Begriffe dieser Lektion, jeweils mit deinem Wissen als Anker:

Begriff TypeScript Python
Sum Type (A oder B oder C) Discriminated Union { kind: "a" } \| { kind: "b" } mehrere dataclass-Klassen, Union, match
Product Type (A und B) Objekt-Typ, Tupel dataclass, tuple
Phantom Type “Branded Types” (string & { __brand: "Id" }) Generic[E], NewType
Varianz Arrays sind kovariant (unsound, siehe Schritt 3) list invariant, Sequence kovariant
Prüfung tsc beim Build, zur Laufzeit gelöscht (type erasure) mypy/pyright als separates Werkzeug

Die Sum-Type-Idee kennst du aus jedem React-Datenabruf. Skizze, nicht ausgeführt (kein tsc in dieser Umgebung):

type Anfrage<T> =
  | { status: "laedt" }
  | { status: "fertig"; daten: T }
  | { status: "fehler"; meldung: string };

function zeige(a: Anfrage<number[]>): string {
  switch (a.status) {
    case "laedt":  return "...";
    case "fertig": return `${a.daten.length} Einträge`;   // daten ist hier sicher da
    case "fehler": return a.meldung;
  }
}

In case "fertig" weiß der Compiler, dass daten existiert, und in "fehler", dass meldung existiert. Genau das bauen wir in Python nach und zeigen, was dabei gleich ist und was nicht.

Konzept

Schritt 1: Typsysteme auf zwei Achsen

Zwei Fragen sind unabhängig voneinander:

  • Statisch oder dynamisch (static vs. dynamic): Wann werden Typen geprüft? Statisch: vor der Ausführung (TypeScript mit tsc, Rust, Java). Dynamisch: erst beim Ausführen, am Wert (JavaScript, Python).
  • Stark oder schwach (strong vs. weak): Wandelt die Sprache Typen still um, wenn sie nicht passen? Schwach: ja (JavaScript). Stark: nein, sie meldet einen Fehler (Python).

Beides in einer Zeile gesehen. Zuerst Python:

Ausgabe:

55
TypeError: can only concatenate str (not "int") to str

Dieselben Ausdrücke in JavaScript (Node 20, echt ausgeführt, console.log("5" * 2, "5" + 2, [] + {}, null + 1)):

10 52 [object Object] 1

JavaScript wandelt "5" bei * in eine Zahl und bei + die Zahl 2 in einen String um, und null + 1 ergibt still 1. Python wirft einen Fehler. Beide Sprachen sind dynamisch, aber JavaScript ist schwach und Python stark. Das sind zwei verschiedene Achsen: TypeScript ist statisch geprüft, aber das Ergebnis läuft als JavaScript, also mit der schwachen Laufzeit.

Zwei Begriffe gehören noch dazu:

  • Nullability (Nullbarkeit): Kann ein Wert “nichts” sein? In TypeScript sagt strictNullChecks, ob string auch null enthält. In Python schreibst du str | None, wenn “nichts” erlaubt ist, und ein Typ-Checker zwingt dich dann, den Fall zu behandeln. Je expliziter ein Typ ist, desto weniger Nullen schleichen sich unbemerkt ein.
  • Generics (parametrische Typen): list[int], Array<Hund>. Ein Typ mit einem Platzhalter. Ihre Tücken (Varianz) sind das Thema von Schritt 3.

Ein wichtiger Punkt für die nächsten Schritte: Typ-Annotationen in Python prüft Python selbst nicht. Sie sind Dokumentation und Futter für Werkzeuge wie mypy. Wenn du in diesem Kapitel siehst, dass etwas “ein Typfehler” ist, dann meldet das ein Checker (hier mypy 1.17.1, lokal ausgeführt, nicht im Browser), und der Code läuft trotzdem.

Schritt 2: Typen als Spezifikation

Zwei Bausteine, die jede Sprache kennt, nur mit anderen Namen. Das sind die algebraischen Datentypen (algebraic data types, ADT):

  • Product Type (Produkttyp, UND): Ein Wert hat Feld A und Feld B. Ein dataclass, ein Tupel, ein Objekt. Die Anzahl möglicher Werte multipliziert sich.
  • Sum Type (Summentyp, ODER): Ein Wert ist Variante A oder B oder C, und jede Variante hat eigene Felder. Die Anzahl addiert sich.

Jetzt der klassische Fehler. Ein Datenabruf als ein Typ mit vielen optionalen Feldern, so wie du es in JavaScript oft schreibst:

Ausgabe:

{'status': 'laedt', 'daten': [1, 2], 'fehler': 'Timeout'}
{'status': 'fertig', 'daten': None, 'fehler': None}
12 erlaubt, davon sinnvoll: 3

Der Typ erlaubt 12 Kombinationen (3 Status mal 2 mal 2), aber nur 3 sind sinnvoll. “Laedt und trotzdem Daten und Fehler” oder “fertig ohne Daten” sind darstellbar, also muss jede Funktion, die eine Anfrage liest, damit rechnen. Das ist die Quelle vieler undefined is not an object-Fehler.

Die Lösung ist ein Sum Type. Jede Variante hat genau die Felder, die in ihrem Zustand existieren:

Ausgabe:

TypeError: Fertig.__init__() missing 1 required positional argument: 'daten'
TypeError: Laedt.__init__() got an unexpected keyword argument 'daten'
ValueError: Ein Fehler braucht eine Meldung

Drei Dinge machen den Unterschied:

  1. Jede Variante hat nur ihre eigenen Felder. Laedt hat gar kein daten, also gibt es “laedt mit Daten” nicht.
  2. Pflichtfelder sind Pflicht. Fertig() ohne daten kann nicht entstehen.
  3. frozen=True (unveränderlich, immutable): Nach dem Erzeugen kann niemand einen gültigen Zustand in einen ungültigen verbiegen. Und __post_init__ prüft Regeln, die ein Typ allein nicht ausdrückt (hier: Meldung nicht leer).

Gelesen wird ein Sum Type mit match. Beachte: daten gibt es nur im Zweig Fertig, genau wie in der TypeScript-Skizze:

Ausgabe: ... | 3 Einträge | Fehler: Timeout.

Was Python nicht macht: Es prüft nicht, ob du alle Varianten behandelt hast. Das erledigt ein Checker. Lokal mit mypy --strict und einer zeige-Funktion, der der Fall Fehler fehlt (lokal ausgeführt, mypy läuft nicht im Browser):

zustand_luecke.py:16: error: Missing return statement  [return]
Found 1 error in 1 file (checked 1 source file)

Mit allen drei Fällen meldet derselbe Aufruf Success: no issues found in 1 source file. Das ist die Exhaustiveness (Vollständigkeitsprüfung): Fügst du später eine vierte Variante hinzu, zeigt dir der Checker alle Stellen, die sie noch nicht behandeln. In TypeScript leistet das ein switch mit never-Prüfung im default.

Zusammengefasst: Ein Typ ist eine Spezifikation, wenn die Menge der darstellbaren Werte der Menge der gültigen Werte entspricht. Nicht erreichbar im Typ heißt: nicht testen, nicht abfragen, nicht dokumentieren müssen.

Phantom Types (Phantomtypen) treiben das weiter. Ein Phantom Type hat einen Typparameter, der nie in den Daten vorkommt, sondern nur im Typ steckt. Beispiel: Längen mit Einheit. Der Wert ist immer nur eine Zahl, aber Laenge[Meter] und Laenge[Fuss] sind verschiedene Typen:

Ausgabe zur Laufzeit:

4
5

Zur Laufzeit wird 2 + 3 gerechnet, also stillschweigend Meter und Fuß addiert. Der Checker sieht es anders (mypy, lokal ausgeführt, Zeilen 17 und 18 der Datei, die genau diesen Code enthält):

phantom.py:18: error: Unsupported operand types for + ("Laenge[Meter]" and "Laenge[Fuss]")  [operator]
Found 1 error in 1 file (checked 1 source file)

Der Phantom Type kostet zur Laufzeit nichts und verhindert eine ganze Fehlerklasse, wenn ein Checker läuft. In TypeScript nennst du das Branded Type. Der gleiche Gedanke steckt in UserId gegen OrderId, die beide string sind, aber nie vertauscht werden sollen.

Schritt 3: Varianz, oder: warum Hunde keine Tierliste sind

Der Prüfstein: Warum ist eine Liste von Hunden nicht einfach eine Liste von Tieren? Intuitiv ist jeder Hund ein Tier, also sollte eine Liste von Hunden eine Liste von Tieren sein. Probier es aus, in Python ohne jeden Checker:

Ausgabe:

wau
AttributeError: 'Katze' object has no attribute 'belle'

Die “Hundeliste” enthält jetzt eine Katze. Der Code, der die Liste liest, verlässt sich darauf, dass nur Hunde drin sind, und bricht. Dasselbe in JavaScript (Node 20, echt ausgeführt): TypeError: h.belle is not a function.

Die Ursache ist Schreiben. Eine Liste kann man lesen und verändern. Aus einer Hundeliste dürfte man nur Hunde lesen, aber über die Tierlisten-Sicht kann man jedes Tier hineinlegen. Darum gilt:

Du nutzt den Container nur zum … Die Regel Name
Lesen (kommt raus) Hund <: Tier, also Sequenz[Hund] <: Sequenz[Tier] kovariant (covariant)
Schreiben (geht rein) Hund <: Tier, aber die Richtung kehrt sich um: Schreiber[Tier] <: Schreiber[Hund] kontravariant (contravariant)
Beidem Liste[Hund] und Liste[Tier] sind unverwandt invariant (invariant)

Das Zeichen <: liest du als “ist ein Subtyp von” (kann überall verwendet werden, wo der andere erwartet wird). Merkhilfe: Was herauskommt, darf spezieller sein, als versprochen. Was hineingeht, darf allgemeiner sein, als verlangt. Ein Schreiber, der jedes Tier annimmt, taugt überall, wo ein Schreiber für Hunde verlangt wird.

Funktionen sind genau diese Regel in einem Typ: Bei Fn(Argument) -> Ergebnis ist das Argument kontravariant (geht rein) und das Ergebnis kovariant (kommt raus). Probe: Ein Aufrufer will eine Funktion Hund -> Tier und gibt ihr Hunde. Eine Funktion Tier -> Hund passt: Sie akzeptiert jedes Tier (also auch Hunde), und was sie liefert (ein Hund), ist ein Tier. Eine Funktion Katze -> Hund passt nicht: Sie bekommt einen Hund, erwartet aber eine Katze.

Das meldet mypy zu genau diesem Code (lokal ausgeführt, Datei mit 22 Zeilen):

from typing import Callable, Sequence

class Tier: ...
class Hund(Tier): ...
class Katze(Tier): ...

def fuettere(tiere: list[Tier]) -> None:
    tiere.append(Katze())

def zaehle(tiere: Sequence[Tier]) -> int:
    return len(tiere)

hunde: list[Hund] = [Hund()]
fuettere(hunde)
zaehle(hunde)

def braucht(f: Callable[[Hund], Tier]) -> None: ...
def tier_zu_hund(t: Tier) -> Hund: return Hund()
def katze_zu_hund(k: Katze) -> Hund: return Hund()

braucht(tier_zu_hund)
braucht(katze_zu_hund)
varianz.py:14: error: Argument 1 to "fuettere" has incompatible type "list[Hund]"; expected "list[Tier]"  [arg-type]
varianz.py:14: note: "list" is invariant -- see https://mypy.readthedocs.io/en/stable/common_issues.html#variance
varianz.py:14: note: Consider using "Sequence" instead, which is covariant
varianz.py:22: error: Argument 1 to "braucht" has incompatible type "Callable[[Katze], Hund]"; expected "Callable[[Hund], Tier]"  [arg-type]
Found 2 errors in 1 file (checked 1 source file)

Zeile 14 (fuettere(hunde)): list ist invariant, Fehler. Zeile 15 (zaehle(hunde)): Sequence ist nur lesend und kovariant, kein Fehler. Zeile 21 (tier_zu_hund): kein Fehler. Zeile 22 (katze_zu_hund): Fehler.

Wie lösen Sprachen das? Vier Strategien (Einordnung ist allgemeines Fachwissen):

  1. Mutable Container invariant machen (Python list, Java-Generics). Sicher, aber lästig.
  2. Nur lesende Sicht anbieten, die kovariant ist (Python Sequence, Kotlin List<out T>, TypeScript readonly T[]). Du gibst die Hundeliste als “nur lesbar” weiter.
  3. Varianz am Aufrufort angeben (Java-Wildcards ? extends Tier).
  4. Unsicher, aber bequem erlauben. TypeScript behandelt Arrays kovariant (bekannte Lücke in der Typsicherheit, bitte prüfen mit deinem tsc), und Java-Arrays sind kovariant mit Laufzeitfehler ArrayStoreException (bitte prüfen).

In Python erklärt eine eigene generische Klasse ihre Varianz mit TypeVar("T_co", covariant=True) oder contravariant=True (das vertieft diese Lektion nicht, siehe die Dokumentation des Moduls typing, bitte prüfen).

Grenzen von Generics. Auch zur Laufzeit gilt: Generics sind in Python (und TypeScript, und bei Java als type erasure) nur Typ-Information. Zur Laufzeit gibt es list, nicht list[int]:

Ausgabe:

<class 'list'> list[int]
TypeError: isinstance() argument 2 cannot be a parameterized generic

Subtyping ist nicht Vererbung. Vererbung (inheritance) ist ein Mechanismus zur Wiederverwendung von Code. Subtyping ist eine Aussage zur Ersetzbarkeit: Überall, wo ein Rechteck erwartet wird, muss auch ein Quadrat funktionieren (Liskov Substitution). Ein Quadrat ist mathematisch ein Rechteck, aber als veränderliches Objekt ist es kein gutes Subtyp:

Ausgabe: 10 4. Quadrat erbt von Rechteck, ist aber kein ersetzbarer Subtyp, weil es das Verhalten bricht, auf das sich Aufrufer verlassen (Breite und Höhe sind unabhängig). Das ist eine Designfrage, die der Compiler nicht entscheidet.

Schritt 4: Ein Mini-Subtyp-Prüfer (Hilfsmittel für Übung 2 und 3)

Damit du Varianz berechnen statt raten kannst, bauen wir einen kleinen Prüfer. Typen schreiben wir so: ein Name ist ein String ("Hund"), ein Container ein Tupel mit dem Konstruktor vorn (("Liste", "Hund")). Die Hierarchie ist ein Dict “Kind zu Eltern”:

Ausgabe:

True False False
False
True
False

Die vierte Zeile ist die Falle: Sequenz ist kovariant, aber der Inhalt ist eine Liste, und die ist invariant. Hund gegen Tier reicht dann nicht, es bleibt ein Nein. Varianzregeln wirken verschachtelt, von außen nach innen.

Die vollständige Regeltabelle (für Übung 2 und 3). S <: T heißt “S ist Subtyp von T”:

Fall Regel
Namen A <: B, wenn A == B oder B ein Vorfahr von A ist. Ein unbekannter Name ist nur sich selbst Subtyp.
Liste[S] gegen Liste[T] nur wenn S == T (invariant)
Sequenz[S] gegen Sequenz[T] wenn S <: T (kovariant)
Liste[S] gegen Sequenz[T] wenn S <: T (eine Liste ist eine Sequenz, die man nur lesen soll)
Schreiber[S] gegen Schreiber[T] wenn T <: S (kontravariant, umgekehrt)
Fn(A1) -> R1 gegen Fn(A2) -> R2 gleiche Anzahl Argumente, jedes A2[i] <: A1[i] (Argumente kontravariant) und R1 <: R2 (Ergebnis kovariant)
alles andere nein

Falle

  1. “Die Liste von Hunden ist doch eine Liste von Tieren.” Gilt nur, solange du nur liest. Sobald jemand schreiben darf, nicht mehr. Gib Funktionen, die nur lesen, Sequence, nicht list.
  2. Status-String plus optionale Felder. Der JS-Reflex { status, data?, error? } erlaubt unmögliche Kombinationen (hier 12 Kombinationen, 3 sinnvoll). Ein Sum Type erlaubt nur die gültigen.
  3. Annotation mit Prüfung verwechseln. Python führt Code mit falschen Annotationen aus. Der Typ schützt nur, wenn ein Checker läuft (und im CI laufen muss).
  4. Vererbung mit Subtyping gleichsetzen. Eine Unterklasse, die das Verhalten der Oberklasse bricht, ist kein Subtyp (Quadrat und Rechteck).
  5. Stark und statisch verwechseln. Python ist dynamisch und stark, JavaScript dynamisch und schwach, TypeScript statisch, aber nur bis zur Laufzeit.

Übungen

Übung 1: Zahlung als Sum Type, unmögliche Zustände unmöglich machen (ca. 10 Min.)

Ein Zahlungssystem kennt drei Zustände:

  • Offen: nur ein Betrag.
  • Autorisiert: Betrag und eine Autorisierungs-ID (auth_id), die die Bank vergeben hat.
  • Eingezogen: Betrag, auth_id und eine Belegnummer (beleg_nr).

Die naive Version wäre Zahlung(status, betrag, auth_id=None, beleg_nr=None) und erlaubt “offen mit auth_id”, “eingezogen ohne Belegnummer” und negative Beträge. Das sollst du nicht schreiben. Baue stattdessen:

  • Drei frozen-Dataclasses Offen(betrag), Autorisiert(betrag, auth_id), Eingezogen(betrag, auth_id, beleg_nr) (genau diese Felder, in dieser Reihenfolge). Der Betrag muss eine Zahl größer als 0 sein (nan ist nicht größer als 0), auth_id und beleg_nr dürfen nicht leer sein, sonst ValueError.
  • autorisiere(z, auth_id): nur aus Offen, gibt Autorisiert mit gleichem Betrag zurück.
  • ziehe_ein(z, beleg_nr): nur aus Autorisiert, gibt Eingezogen zurück.
  • Jeder andere Übergang (z. B. autorisiere auf einer schon autorisierten Zahlung, oder ein Wert, der gar keine Zahlung ist) löst ValueError oder TypeError aus.
  • ausstehend(z): der Betrag, der noch eingezogen werden muss (Offen und Autorisiert: der Betrag, Eingezogen: 0). Benutze match. Ein Wert, der keine Zahlung ist, löst TypeError aus.

Der Check versucht, ungültige Zustände zu bauen, und prüft die Übergänge. Die letzte Zeile gibt alles in dieser Reihenfolge zurück.

Welche Felder gehören nur zu einem Zustand, und was passiert, wenn ein Pflichtfeld fehlt? Wo prüfst du Regeln, die über “Feld vorhanden” hinausgehen (Betrag größer als 0, nicht leer)? Und wie unterscheidest du in autorisiere, welche Variante du bekommen hast?

from dataclasses import dataclass

def _pruefe_betrag(betrag):
    if not betrag > 0:
        raise ValueError("Betrag muss größer als 0 sein")

def _pruefe_text(text, name):
    if not isinstance(text, str) or not text:
        raise ValueError(f"{name} darf nicht leer sein")

@dataclass(frozen=True)
class Offen:
    betrag: float
    def __post_init__(self):
        _pruefe_betrag(self.betrag)

@dataclass(frozen=True)
class Autorisiert:
    betrag: float
    auth_id: str
    def __post_init__(self):
        _pruefe_betrag(self.betrag)
        _pruefe_text(self.auth_id, "auth_id")

@dataclass(frozen=True)
class Eingezogen:
    betrag: float
    auth_id: str
    beleg_nr: str
    def __post_init__(self):
        _pruefe_betrag(self.betrag)
        _pruefe_text(self.auth_id, "auth_id")
        _pruefe_text(self.beleg_nr, "beleg_nr")

def autorisiere(z, auth_id):
    match z:
        case Offen(betrag=b):
            return Autorisiert(b, auth_id)
        case _:
            raise ValueError(f"nur eine offene Zahlung kann autorisiert werden, nicht {type(z).__name__}")

def ziehe_ein(z, beleg_nr):
    match z:
        case Autorisiert(betrag=b, auth_id=a):
            return Eingezogen(b, a, beleg_nr)
        case _:
            raise ValueError(f"nur eine autorisierte Zahlung kann eingezogen werden, nicht {type(z).__name__}")

def ausstehend(z):
    match z:
        case Offen(betrag=b) | Autorisiert(betrag=b):
            return b
        case Eingezogen():
            return 0
        case _:
            raise TypeError(f"keine Zahlung: {z!r}")

Offen, Autorisiert, Eingezogen, autorisiere, ziehe_ein, ausstehend

Jede Variante hat nur ihre Felder, darum ist “offen mit auth_id” schon beim Erzeugen unmöglich (TypeError). frozen=True verhindert, dass ein gültiger Zustand später verbogen wird. Die Übergänge sind Funktionen, die die Variante prüfen, nicht einen Status-String. Der Zustand ist der Typ.

Übung 2: Varianz vorhersagen (ca. 4 Min.)

Hierarchie: Apfel und Birne sind Frucht, Frucht ist Lebensmittel. Schreibweise wie in Schritt 4: Liste[Apfel] heißt ("Liste", "Apfel"), Fn(Frucht) -> Birne heißt ("Fn", ("Frucht",), "Birne"). Entscheide für jede Frage, ob der linke Typ ein Subtyp des rechten ist (True oder False), nach der Regeltabelle aus Schritt 4:

  1. Schreiber[Frucht] gegen Schreiber[Apfel]
  2. Liste[Apfel] gegen Liste[Frucht]
  3. Fn(Apfel) -> Apfel gegen Fn(Frucht) -> Apfel
  4. Liste[Apfel] gegen Sequenz[Frucht]
  5. Sequenz[Liste[Apfel]] gegen Sequenz[Liste[Frucht]]
  6. Fn(Frucht) -> Birne gegen Fn(Birne) -> Frucht

Der Check berechnet die Antworten selbst nach den Regeln.

Frage dich bei jedem Typ: Steht der Typ-Parameter an einer Stelle, wo gelesen wird (herauskommt), wo geschrieben wird (hineingeht), oder beides? Bei verschachtelten Typen entscheidet die strengste Stelle von außen nach innen. Bei Funktionen: Argumente und Ergebnis folgen verschiedenen Richtungen.

antworten = (True, False, False, True, False, True)
antworten

1: Schreiber ist kontravariant, und Apfel <: Frucht gilt, also darf Schreiber[Frucht] überall stehen, wo Schreiber[Apfel] verlangt wird. 2: Liste ist invariant. 3: Das Argument müsste kontravariant sein, Frucht <: Apfel gilt aber nicht. 4: Eine Liste ist eine nur gelesene Sequenz, Apfel <: Frucht genügt. 5: Die Liste im Inneren ist invariant. 6: Argument Birne <: Frucht (kontravariant richtig herum), Ergebnis Birne <: Frucht (kovariant).

Übung 3: Einen Subtyp-Prüfer selbst schreiben (ca. 10 Min.)

Schreibe ist_subtyp(a, b, hierarchie) für alle Regeln der Tabelle aus Schritt 4: Namen, Liste, Sequenz, Schreiber und Fn, auch verschachtelt. Anders als in Schritt 4 bekommt die Funktion die Hierarchie als Parameter (ein Dict Kind zu Eltern, die Wurzel hat den Wert None). Die Funktion liefert True oder False.

Beispiele (Hierarchie {"Auto": "Fahrzeug", "Fahrzeug": None}):

  • ist_subtyp("Auto", "Fahrzeug", h) ergibt True, ist_subtyp("Fahrzeug", "Auto", h) ergibt False.
  • ist_subtyp(("Sequenz", "Auto"), ("Sequenz", "Fahrzeug"), h) ergibt True.
  • ist_subtyp(("Fn", ("Fahrzeug",), "Auto"), ("Fn", ("Auto",), "Fahrzeug"), h) ergibt True (Argument kontravariant, Ergebnis kovariant).
  • Unbekannte Namen sind nur sich selbst Subtyp, die Funktion darf bei ihnen nicht abstürzen.

Trenne zuerst die Fälle: Namen, Container-Tupel, Funktions-Tupel. Welche Regel ruft sich selbst für das Innere auf, und bei welcher darf das Innere nur gleich sein? Bei Schreiber und den Argumenten von Fn sind die Rollen von a und b im rekursiven Aufruf vertauscht.

def ist_subtyp(a, b, hierarchie):
    if isinstance(a, str) and isinstance(b, str):
        while a is not None:
            if a == b:
                return True
            a = hierarchie.get(a)
        return False
    if not (isinstance(a, tuple) and isinstance(b, tuple)):
        return False
    if a[0] == "Fn" and b[0] == "Fn":
        return (len(a[1]) == len(b[1])
                and all(ist_subtyp(y, x, hierarchie) for x, y in zip(a[1], b[1]))
                and ist_subtyp(a[2], b[2], hierarchie))
    if a[0] == "Liste" and b[0] == "Liste":
        return a[1] == b[1]
    if a[0] in ("Liste", "Sequenz") and b[0] == "Sequenz":
        return ist_subtyp(a[1], b[1], hierarchie)
    if a[0] == "Schreiber" and b[0] == "Schreiber":
        return ist_subtyp(b[1], a[1], hierarchie)
    return False

ist_subtyp

Die Funktion läuft rekursiv durch den Typ. Bei Argumenten und beim Schreiber werden a und b vertauscht (Kontravarianz), beim Ergebnis und bei Sequenz nicht (Kovarianz), und bei Liste wird nicht rekursiv gefragt, sondern auf Gleichheit geprüft (Invarianz).

Merksatz

Ein Typ ist eine Spezifikation, wenn er genau die gültigen Zustände darstellt (Sum Type statt Status-String plus optionale Felder), und Container sind nur dort kovariant, wo man nur liest, und kontravariant, wo man nur schreibt (darum ist eine Hundeliste keine Tierliste).

Prüfstein

  1. Warum ist eine Liste von Hunden nicht einfach eine Liste von Tieren, und wie lösen Sprachen das? Nenne ein Beispiel, bei dem es bricht, und zwei Lösungsstrategien.
  2. Wie machst du “Offen mit Autorisierungs-ID” unmöglich, und was bleibt in Python Aufgabe eines Checkers?

Weiter mit Teil b: Ausführungsmodelle, JIT und Paradigmen.

Quelle: quellen/konzeptuebersicht-software-grundlagen.md, Abschnitt “1. Wie Programme funktionieren” (Typsysteme: statisch vs. dynamisch, stark vs. schwach, Generics, Nullability). quellen/konzeptuebersicht-software-fortgeschritten.docx, Abschnitt “1. Sprachen, Typen und Laufzeit” (Typen als Spezifikation: algebraische Datentypen, Sum Types, Phantom Types, “Make illegal states unrepresentable”; Varianz: Ko- und Kontravarianz, Subtyping vs. Vererbung, Grenzen von Generics; Prüfstein zur Varianz).

Über die Quelle hinaus (allgemeines Fachwissen): die Erklärung der Varianz mit Lesen und Schreiben, die Regeltabelle des Mini-Subtyp-Prüfers (eigene Vereinfachung), die Einordnung der Strategien der Sprachen (Wildcards, out T, Array-Kovarianz in TypeScript und Java, jeweils bitte prüfen). Alle Python-Ausgaben und Node-Ausgaben dieser Lektion stammen aus dem Ausführen des Codes (Python 3.13.9, Node 20). Die mypy-Meldungen stammen aus einem lokalen Lauf mit mypy 1.17.1 und können in anderen Versionen anders formuliert sein. Das TypeScript-Beispiel wurde nicht ausgeführt, weil tsc hier nicht verfügbar war.