Peter Kröner, Webtechnologie-Erklärbär

Vor kurzem hat Chris Heilmann auf Mastodon einen Code-Challenge veröffentlicht: Was ist der kürzeste Code, um eine Liste von Strings anhand des vierten Zeichens in den Strings zu sortieren? Und da ich im Moment nichts Besseres zu tun habe (ernsthaft, ich habe gerade wirklich nichts zu tun; heuert mich an, ich hacke alles rund um Low-Level-Webtech wie JS/TS, mache Code-Reviews, coache Nerds etc.), habe ich mich natürlich sofort der Herausforderung gestellt. Und zwar in reinen TypeScript-Typen, damit es bloß nicht zu einfach wird!

TypeScript-Typen als eigene Programmiersprache

Statt TypeScript-Typen bestimmungsgemäß zur Beschreibung von JavaScript-Programmen einzusetzen, können wir sie auch als ganz eigene Programmiersprache behandeln. Die relevanten Sprachkonstruktionen sind hierfür allesamt vorhanden:

// Typ-Alias ≈ Variable
type A = number;

// Generischer Typ ≈ Funktion
type B<T> = [T];

// Tuple ≈ Liste
type C = ["a", "b", "c"];

// Union ≈ Set
type D = "a" | "b" | "c";

// Conditional Type === Conditional
type E<T> = T extends 1 ? true : false;
type R1 = E<1>; // > true
type R2 = E<2>; // > false

Der wichtigste Bestandteil am Konzept „Typen als Programmiersprache“ sind die generischen Typen, die wir als Funktionen betrachten können. Ähnlich wie JavaScript-Funktionen sind generische Typen technisch gesehen einfach nur normale Typen, aber praktisch gesehen würde besteht ihr einziger Sinn darin, mit Parmetern gefüttert zu werden um neue Ergebnisse zu erzeugen:

// Variablen
let a = 42;
type A = number;

// Funktionen
let b = (x) => [x];
type B<X> = [X];

a und A sind beides normale „Variablen“, die für sich genommen nützlich sind, während b und B wie Funktionen arbeiten und verwendet werden. Kein Web-UI wird je den Inhalt der Variablen b anzeigen und kein konkretes JS-Objekt wird je den Typ B haben. Wenn man aber b oder B mit Inputs füttert, liefern sie nützliche Werte oder Typen – Funktionen eben!

Mit Variablen, Funktionen und Conditionals haben wir alle nötigen Programmier-Zutaten zur Hand. Schwierig am Arbeiten in reinen TypeScript-Typen sind (wenn wir die manchmal auch nicht ganz triviale Frage des „warum“ ausklammern) eigentlich nur zwei Dinge:

1. TS-Typen funktionieren wie eine rein funktionale Programmiersprache. Es gibt weder imperative Sprachkonstrukte (if, for o. Ä.), noch eine wirklich gute Möglichkeit temporäre Variablen anzulegen, noch Features für Debugging. Das ganze „Programm“ ist ein unmittelbar von entweder dem Editor oder dem TypeScript-Compiler ausgewertetes Gleichungssystem, was etwas gewöhnungsbedürftig ist.
2. Das Typsystem ist eine domänenspezifische Sprache für die Beschreibung von JavaScript-Programmen. Alles außerhalb dieser Domäne (die im Wesentlichen aus der Frage „kann Typ A der Variablen B zugewiesen werden“ besteht) ist nur mit großem Aufwand möglich. Strings manipulieren? Sehr schwierig. Zahlen addieren? Fast unmöglich.

Wie können wir unter diesen Bedingungen zwei Strings anhand ihres vierten Zeichens sortieren? Mit gar nicht mal so viel Aufwand, wenn wir es schaffen, String-Vergleichbarkeit herzustellen.

Das Vergleichbarkeits-Problem

Da Chris’ Aufgabenstellung den relevanten Zeichensatz auf ASCII-Kleinbuchstaben zu beschränken scheint, könnte uns als erste Idee eine Lookup-Tabelle in den Sinn kommen, mit der wir einzelne Zeichen über den Umweg ihres ASCII-Codes miteinander vergleichbar machen können:

type ASCII = {
  a: 97,
  b: 98,
  c: 99,
  ...
};

Einfach das vierte Zeichen der zu vergleichenden Strings mithilfe der Tabelle in Zahlen übersetzen und dann einen Größenvergleich machen. Das Haken daran ist, dass ein Vergleich von zwei Zahlen genau das ist, was TypeScript nicht kann. Die einzige Beziehung zwischen zwei „Werten“ (Typen), die TypeScript kennt, ist die Zuweisungskompatibilität, ein Konzept von „größer als“ gibt es hingegen nicht. Für TypeScript sind die Zahlen 1 und 7 wie true und false – sie sind einfach unterschiedliche Werte und haben darüber hinaus keine weiteren Beziehungen wie eben „größer als“ zueinander.

Wie können wir dann modellieren, ob „a“ vor oder nach „b“ kommen soll? Es gibt nur einen Ausweg: wenn alles, was uns TypeScript sagen kann, ist, ob ein „Wert“ (Typ) einem anderen „Wert“ (Typ) zugewiesen werden kann, müssen wir einen Weg finden, die Frage der Buchstaben-Sortierung in eine Frage der Typ-Zuweisungskompatibilität zu übersetzen.

Mein Plan bestand darin, zunächst einen Tuple-Typ mit dem unterstützten Zeichensatz anzulegen:

type Charset = ["a", "b", "c", ...];

Alle Buchstaben manuell aufzulisten wäre recht mühsam, weshalb ich eine generische String-Typ-Split-Funktion aus meinem Code-Giftschrank gekramt habe:

type Split<T, R extends string[] = []> = T extends `${infer First}${infer Rest}`
  ? Rest["length"] extends 0
    ? [First, ...R]
    : [First, ...Split<Rest, R>]
  : [];

Die Syntax sieht ein wenig wild aus, beschreibt aber eigentlich nur eine rekursive Funktion:

1. Die „Funktion“ Split<T, R> hat die zwei Parameter T und R, wobei R auf Subtypen von string[] beschränkt ist und mit einer leeren Liste belegt wird, wenn der Parameter nicht explizit angegeben wurde. Die Klausel extends string[] fungiert praktisch als Typ für den Typ (-Parameter) R.
2. Mit einem Conditional Type prüft die Funktion, ob T dem String Typ ${infer First}${infer Rest} zuweisbar ist. Das ist der Fall, wenn T ein String ist und es der Typinferenz möglich ist, mindestens ein Zeichen am Anfang des Strings zu identifizieren (infer First). Ist das nicht der Fall, liefert die Funktion ein leeres Tuple.
3. Danach wird geprüft, ob der auf First folgende String-Rest (infer Rest) eine Länge gleich 0 hat. Man beachte: Das ist kein Größenvergleich, sondern nur die Feststellung, ob Rest["length"] zuweisungskompatibel zu 0 ist, was nur der Fall ist, wenn der String aus 0 Zeichen besteht. Sollte das der Fall sein, besteht der String offenbar nur aus nur dem Zeichen First und es wird ein Tuple-Typ mit First und dem Inhalt des Tuple-Typs R zurückgegeben.
4. Wenn der Rest-String nicht leer ist, liefert die Funktion einen Tuple-Typ mit First und dem, was Split<Rest, R> liefert.

Anders gesagt: Die Funktion schneidet von einem String-Typ T das erste Zeichen ab und ruft sich selbst wieder auf, um vom Rest-String das nächste erste Zeichen abzuschneiden – und immer so weiter. R wird nur verwendet, um die Liste der vorher abgeschnittenen Zeichen bei der Rekursion durchzureichen. Und Split<T, R> ist eine ganz klassische rekursive Funktion: einen gibt einen Fall für keinen Input (leerer String = leeres Tuple), einen für einen Input (String mit einem Zeichen = Tuple mit einem Zeichen) und einen Fall für alles mit mehr als einem Input (String mit N Zeichen = Tuple mit dem ersten Zeichen darin plus dem Ergebnis der Rekursion über den Rest).

Mit dieser Split-Funktion ist der Zeichensatz einfach und schnell erstellt:

type Charset = Split<"abcdefghijklmnopqrstuvwxyz">;
// > ["a", "b", "c", ..., "y", "z"]

Ähnlich wie ein JavaScript-Array ist das Tuple eine Sammlung von Elementen in einer definierten Reihenfolge, in der Einträge doppelt und dreifach vorkommen können. Und ebenfalls wie in JS können wir Elemente anhand ihres Index aus dem Tuple herauskramen; Charset[1] liefert "b".

Aber wie hilft uns das für Vergleiche weiter?

Von Tuples zu Unions

Die Domäne der TypeScript-Typen ist Zuweisungskompatibilität. Ein Typ A ist einem Typ B zuweisbar, wenn A entweder gleich B oder ein Subtyp von B ist:

type R0 = 1 extends number ? true : false;
// true: 1 ist number zuweisbar

type R1 = "a" extends number ? true : false;
// false: "a" ist keine number

type R2 = { x: number, y: any } extends { x: number } ? true : false;
// true: { x: number, y: any } ist Subtyp von { x: number }

Union Types sind Sets von Typen:

type A = number;    // Set aller Zahlen
type B = 1 | 2;     // Set der Zahlen 1 und 2
type C = 1 | 2 | 3; // Set der Zahlen 1, 2 und 3

Hier gilt, dass Subsets Supertypen von Supersets sind und entsprechend Subsets Supersets zuweisbar sind:

type Subset = 1 | 2;
type Superset = 1 | 2 | 3;

type R0 = Subset extends Superset ? true : false;
// true: "1 | 2" ist "1 | 2 | 3" zuweisbar

type R1 = Superset extends Subset ? true : false;
// false: "1 | 2 | 3" ist nicht "1 | 2" zuweisbar

An dieser Stelle funktioniert extends wie ein Ist-Subset-von-Operator. Und das ist für unsere Buchstaben-Vergleichbarkeit extrem hilfreich, wenn wir es schaffen, für ein gegebenes Zeichen ein Set der im Alphabet vor diesem Zeichen stehenden Zeichen zu bilden! Für "c" wäre das das Set "a" | "b", während das Set für das Zeichen "d" aus "a" | "b" | "c" besteht. Da das erste Set ein Subset des zweiten Sets ist, ist ersteres letzterem zuweisbar, was wir als „c kommt vor d“ interpretieren können!

type CharsBeforeC = "a" | "b";
type CharsBeforeD = "a" | "b" | "c";

type CBeforeD = CharsBeforeC extends CharsBeforeD ? true : false;
// > true

Zu diesen Unions von Zeichen vor einem gegebenen Zeichen kommen wir über eine weiter rekursive Typ-Funktion, die sich so lange durch das Zeichensatz-Tuple arbeitet, bis es ein bestimmtes Zeichen in diesem Tuple erreicht hat:

type ValueOf<Needle, List extends string[] = []> = Charset[List["length"]] extends Needle
  ? [...List, Charset[List["length"]]][number]
  : ValueOf<Needle, [...List, Charset[List["length"]]]>;

type CharsBeforeC = ValueOf<"c">;
type CharsBeforeD = ValueOf<"d">;

type CBeforeD = CharsBeforeC extends CharsBeforeD ? true : false;
// > true

Der Aufbau gleicht der Split-Funktion, mit nur drei Unterschieden:

1. ValueOf arbeitet sich durch einen Tuple-Typ statt durch einen String, verwendet aber die gleiche rekursive Element-vom-Anfang-abschneiden-Technik.
2. Die Abbruchbedingung ist nicht mehr ein komplettes Durcharbeiten des Inputs, sondern die Rekursion endet, wenn ein Zeichen gleich des Such-Parameters Needle gefunden wird.
3. Statt eines Tuples liefert die Funktion eine Union der Tuple-Members.

Ein Tuple funktioniert in TypeScript ziemlich genau wie ein JavaScript-Array und wir können entsprechend seine Einzel-Indizes abfragen:

type Stuff = ["Apples", "Oranges"];
type First = Stuff[0]; // > "Apples"
type Last = Stuff[1]; // > "Oranges"

Weil aber in TypeScript-Typen alle Operationen sowohl mit Einzel-Typen als auch mit Sets von Typen (d. h. Unions) durchgeführt werden können, können wir ein Tuple auch mit dem Typ number (dem Set aller Zahlen) indizieren und bekommen als Ergebnis eine Union aller Inhalte des Tuples:

type Stuff = ["Apples", "Oranges"];
type All = Stuff[number]; // > "Apples" | "Oranges"
// Entspricht type All = Stuff[0] | Stuff[1]

Wenn wir uns nun noch eine Funktion bauen, die uns für einen gegebenen String das Zeichen an einem gegebenen Index liefern kann …

type CharAt<T extends string, I extends number> = Split<T>[I];

type First = CharAt<"hello", 0>; // > "h"
type Second = CharAt<"hello", 1>; // > "e"

… ist es fast schon trivial, eine Funktion zu schreiben, die für die von Chris gestellte Anforderung einen Vergleich durchführt:

type Comparator<A extends string, B extends string> = ValueOf<CharAt<A, 3>> extends ValueOf<CharAt<B, 3>>
  ? ValueOf<CharAt<B, 3>> extends ValueOf<CharAt<A, 3>>
    ? 0
    : 1
  : -1;

type A = Comparator<"aaaa", "bbbb">; // > 1
type B = Comparator<"zzzz", "yyyy">; // > -1
type C = Comparator<"ffff", "ffff">; // > 0

Kommt A vor B, bekommen wir 1, für B vor A gibt’s -1, und bei Gleichheit wird 0 ausgespuckt. Wären wir in normalem JavaScript unterwegs, könnten wir diese Funktion in Array.prototype.sort verwenden und hätten die Aufgabe bewältigt. Aber natürlich gibt es auf Ebene von TypeScript-Typen keine eingebaute Sortierfunktion, sodass wir uns auch hierum selbst kümmern müssen. Das stellt sich allerdings als das kleinste Problem heraus.

Quicksort und Haskell

Quicksort ist ein rekursiver Sortieralgorithmus und damit in TypeScript-Typen wunderbar einfach umzusetzen:

type Quicksort<List extends string[]> =
  List extends [infer First extends string, ...infer Rest extends string[]]
    ? [...Quicksort<FilterLte<Rest, First>>, First,...Quicksort<FilterGt<Rest, First>>]
    : [];

1. Erste Zeile: Funkionssignatur-Äquivalent
2. Zweite Zeile: Aufteilung von nicht leeren Input-Liste in ein erstes Element First und den Rest Rest
3. Dritte Zeile: Der Rest der Liste Rest wird in eine Liste von Elementen kleiner oder gleich First und eine Liste größer First einsortiert, die Teillisten werden per Rekursion sortiert und via Spread-Operator mit First in der Mitte verkettet
4. Vierte Zeile: falls die Input-Liste leer ist, eine leere Liste zurückgeben

Da weder Algorithmen noch funktionales Programmieren besondere Stärken von mir sind, habe ich aus dem Wikipedia-Artikel zu Quicksort eine Haskell-Implementierung gemopst und nach TypeScript portiert. Haskell ist auch eine rein funktionale Sprache und meist gut genug lesbar, um als Quell der Inspiration zu dienen. Ich bediene mich für meiner TypeScript-Mentalgymnastik öfter an Algorithmen und Verfahren aus Haskell – man soll schließlich nicht ständig das Rad neu erfinden!

Was nun noch fehlt, sind die Filter-Funktionen FilterLte<List, X> (List auf alle Werte kleiner oder gleich X reduzieren) und FilterGt<List, X> (List auf alle Werte größer X reduzieren), doch die sind, da wir schon eine Vergleichsfunktion haben, schnell gebaut:

type FilterGt<List extends string[], Element extends string> =
  List extends [infer First extends string, ...infer Rest extends string[]]
    ? Comparator<First, Element> extends -1
      ? [First, ...FilterGt<Rest, Element>]
      : FilterGt<Rest, Element>
    :[];

type FilterLte<List extends string[], Element extends string> =
  List extends [infer First extends string, ...infer Rest extends string[]]
    ? Comparator<First, Element> extends -1
      ? FilterLte<Rest, Element>
      : [First, ...FilterLte<Rest, Element>]
    : [];

Es ist zweimal der fast gleiche Code, nur wird einmal First behalten, wenn die Vergleichsfunktion -1 liefert und einmal weggeworfen. Da sich nun herausstellt, dass die Vergleichsfunktion nur den Fall „A kleiner B“ identifizieren können muss, können wir sie noch ein wenig vereinfachen …

type Comparator<A extends string, B extends string> =
  ValueOf<CharAt<A, 3>> extends ValueOf<CharAt<B, 3>> ? 1 : -1;
// Kein Anlass, Gleichheit von A und B gesondert zu behandeln

... und schon haben wir Quicksort in TypeScript fertig implementiert und Chris' Code Challenge bewältigt:

type Result1 = Quicksort<["bbbb", "aaaa", "dddd", "cccc", "eeee"]>;
// > ["aaaa", "bbbb", "cccc", "dddd", "eeee"]

type Result2 = Quicksort<["strawberry", "helicopter", "wales", "acorn"]>;
// > ["strawberry", "wales", "helicopter", "acorn"]

Was lernen wir daraus?

Zugegeben: für das Beschreiben der Typen des durchschnittlichen JavaScript-Programms – also das, wofür TypeScript eigentlich gedacht ist – braucht es vermutlich keine Sortieralgorithmen. Ich finde aber, dass die Übung zwei sehr relevante Aspekte von Typ-Level-Programmierung in TS aufzeigt.

Vorletzte Woche war ich auf einer etwas enterprisigen Konferenz und im Rahmen eines TypeScript-Talks warf jemand aus dem Publikum ein, dass das gezeigte Typ-Gehacke (das deutlich weniger abgefahren als der Inhalt dieses Artikels war) ja wohl „komplett unlesbar“ und daher „in ernsthaften Projekten“ komplett unbrauchbar sei. Einmal abgesehen davon, dass die einzige Alternative zu Typ-Level-Gebastel any, die bête noire der „ernsthaften Entwickler“ ist, würde ich sagen, dass Leserlichkeit nicht das relevante Problem ist. Nicht zuletzt durch die sehr einfache Übernahme des Quicksort-Algorithmus aus Haskell wird deutlich, dass die Struktur eines Typ-Programms gar nicht mal so seltsam ist. Haskell ist freilich nicht ganz so Mainstream wie Java oder JavaScript, aber auch kein totaler Exot – es ist einfach eine funktionale Programmiersprache und damit, sobald man sein Hirn auf Rekursion eingestellt hat, nicht komplett undurchdringbar oder gar „unlesbar“.

Zum Anderen sehen wir hier aber auch, wo die Grenzen der Programmiersprache „TypeScript-Typen“ wirklich liegen: nämlich in der Tatsache, dass es sich um eine domänenspezifische Sprache für die Beschreibung von JavaScript-Programmen handelt. Alles, was TS-Typen beschreiben können, ist die Kompatibilität von Typen zu anderen Typen. Nichts jenseits von basaler Set-Logik existiert. Die Verrenkungen, die ich anstellen musste, um zu ermitteln, ob der Buchstabe „a“ im Alphabet vor „b“ steht, fand ich tatsächlich nicht unerheblich. Das Bemerkenswerteste an ts-sql (einer zu 100% in TypeScript-Typen implementierten Mini-SQL-Datenbank) ist nicht der Query-Parser, sondern der manuell angelegte Typ Integers:

type Integers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ..., 256]

TypeScript hat einfach kein Konzept von Zahlen, und sobald man irgendwas mit Zahlen anstellen möchte, wird der Aufwand enorm und absurd.

An sich sind die Type-Level-Programmier-Features von TypeScript schon extrem praktisch zu Beschreibung von sehr dynamischen JavaScript-Programmen. Auch wenn TS längst nicht jeden Aspekt von JS modellieren kann, so kann es doch sehr viel. Nutzt man diese Möglichkeiten nicht, schränkt man sich in der Nutzung von dem, was TypeScript eigentlich kann, unnötig stark ein. Ich würde sogar so weit gehen, dass TypeScripts diverse Nachteile bzgl. Kosten (komplexere Toolchain, Breaking Changes, Kompilier-Zeitaufwand) nur dann überkompensiert werden, wenn man sich seiner kompletten Feature-Bandbreite bedient und mithilfe von Typ-Hacking eine Kombination aus Typsicherheit und Flexibilität herstellt.

Aber wie immer bei der Programmierung ist irgendwann ein Punkt erreicht, an dem Aufwand und Ertrag in keinem Verhältnis mehr zueinander stehen. Der Zwischenrufer auf der Enterprise-Konferenz sah diesen Punkt offenbar in der originellen Syntax der TypeScript-Typen erreicht – daher der Einwand der „Unlesbarkeit“. Ich würde diesen Punkt aber eher im mit der Komplexität größer werdenden Semantik-Delta zwischen dem, wofür TypeScript gemacht ist (JavaScript beschreiben) und dem, was es so gerade eben kann, verorten. Das Quicksort-Typ-Programm, das wir in diesem Artikel gesehen haben, besteht eigentlich nur ein paar fast identisch aufgebauten rekursiven Funktionen. Sein Kern, die Quicksort-Funktion, sieht noch nicht mal besonders seltsam aus. Die Syntax ist nicht das Problem. Ein Problem entsteht erst, wenn wir gegen unsere Tools ankämpfen müssen, um unsere Ziele zu erreichen – und dieser Punkt ist meiner Meinung nach dann erreicht, wenn wir TypeScript über die Bedeutung von Strings und Zahlen räsonieren lassen wollen. Die Limitierungen von TypeScript machen an dieser Stelle Dinge, die in anderen Sprachen einfach sind, vielleicht nicht unleserlich, aber fast unverständlich und damit auch nicht wirklich empfehlenswert.