DOOM läuft als TypeScript-Typen [Video]

• Ein Experiment, das das Spiel DOOM von 1993 nicht mit Runtime-Code, sondern ausschließlich mit dem TypeScript-Typsystem bootet und das erste Frame ausgibt
• Bis zum ersten Frame verarbeitete der TypeScript-Type-Checker 3,5 Billionen Zeilen, insgesamt 177 TB, über 12 Tage; die ursprüngliche Schätzung lag bei 1,25 PB und mehr als 3 Monaten
• Die Kernimplementierung ist eine als Typen gebaute WebAssembly-Virtual Machine, die 116 für DOOM benötigte Instruktionen als Logik auf Typebene implementiert und 18 Millionen Instruktionen auswertet
• Während der Entwicklung wurden Beschränkungen des Compilers für Rekursion, Unions, Tupel und tiefe Typ-Instanziierung entfernt, das Endergebnis bleibt jedoch reines TypeScript, das Nutzer selbst ausführen können
• Weil der Umfang die Type-Checks normaler Apps weit übersteigt, waren bestehende Entwicklertools nahezu wirkungslos, sodass 12.364 Tests und Custom-Tools eigens erstellt werden mussten

---

Ein Computer im TypeScript-Typsystem

• DOOM läuft nicht als normales JavaScript, sondern ausschließlich im TypeScript-Typsystem
• Ziel war es, ohne Tricks oder eine andere Ausführungssprache eine WebAssembly-Virtual Machine zu bauen, die allein mit Typen auch andere Programme ausführen kann
• Der Computer auf Typebene besitzt die grundlegenden Bausteine für die Ausführung als Typen
  • RAM
  • Speicherplatz
  • Call Stack
  • Subroutinen
  • Speicherzeiger
  • Ausführungskontext
  • Custom-Entwicklertools
• Die 116 WebAssembly-Instruktionen, die für die Ausführung von DOOM nötig sind, wurden als Logik in TypeScript-Typen implementiert
• Allein durch diese Logik entstanden 18 Millionen Instruktionen, die der Type-Checker einzeln auswerten musste; jede Instruktion repräsentiert einen eindeutigen Maschinenzustand des Systems

Der Umfang bis zum ersten Frame

• Für das erste DOOM-Frame waren 3,5 Billionen Zeilen an Typen nötig, mit einer Gesamtgröße von 177 TB
• Der TypeScript-Compiler TSC lief 12 Tage durchgehend, um das Spiel zu booten und das erste Frame zu erhalten
• Laut erster Berechnung hätte der Computer 1,25 PB an TypeScript-Typen verarbeiten müssen, bei einer geschätzten Laufzeit von mehr als 3 Monaten
• Nach extremen Optimierungen ließ sich der Aufwand auf 177 TB und 12 Tage reduzieren
• Während TSC beim Type-Check normaler Apps typischerweise bei 200.000 bis 500.000 Typ-Instanziierungen liegt, hielt diese Arbeit 12 Tage lang 20 Millionen Instanziierungen pro Sekunde durch
• Die finale Ausgabe ist ein TypeScript-Objekt, bei dem jeder Wert eine Pixelzeile darstellt
  • Das Ausgabeframe hat 320×200
  • Insgesamt ist es ein ASCII-Frame mit 128.000 Pixeln
• Es gibt auch eine Möglichkeit, das Spiel per Tastatureingabe zu steuern

Während der Entwicklung entfernte TypeScript-Schutzmechanismen

• Das Endergebnis ist reines TypeScript, das Nutzer selbst direkt ausführen können
• Um das Experiment möglich zu machen, wurde der TypeScript-Compiler modifiziert und mehrere Limits wurden entfernt
  • Entfernen des Limits für übermäßige Stacktiefe beim Typvergleich
  • Entfernen des Limits für übermäßig tiefe oder potenziell unendliche Typ-Instanziierung
  • Setzen der maximalen Größe von Unions und Tupeln auf Infinity
  • Entfernen des Limits für abgeschnittene Ausgaben
  • Entfernen des bekannten TypeScript-Rekursionslimits
• Auch das Stack-Limit des Computers selbst wurde erhöht
• Nach dem Entfernen dieser Schutzmechanismen konnte der Type-Checker problemlos 100 GB Arbeitsspeicher nutzen
• Der Preis für das Entfernen der Limits war hoch
  • Schon kleine Probleme wie ein Tippfehler in einem Import konnten Endlosschleifen erzeugen
  • Heap-Allokationen konnten den gesamten Speicher verbrauchen und das System abstürzen lassen
  • Stack-Traces wurden enorm groß, und in den meisten Fällen endete ein Fehler schlicht mit einem Hänger

Was zusätzlich für die Ausführung von DOOM gebaut wurde

• Nach 6 Monaten Arbeit konnten kleine C-Programme ausgeführt werden, aber für DOOM war deutlich mehr Implementierung nötig
• Alle Bestandteile von DOOM mussten als Typen kodiert werden
  • Spielkarten
  • Texturen
  • Sprites
  • Sound
  • Gegner-KI
  • Waffen
  • Items
  • Physik-Engine
  • Audio-Subsystem
  • Spielinterne Texte
• Auf Typebene wurden sogar runtime-nahe Funktionen implementiert
  • Garbage Collector
  • L1-CPU-Cache
  • Runtime Dead Code Elimination
  • Echtzeit-Speicherkompaktierung
  • Globaler Wertestack mit Tiefenzählung zum Schutz vor Stack Underflow
  • Dynamische Dispatch-Tabelle
  • Modulweite globale Variablen
  • Labeled goto
  • Ausnahmebehandlung auf Typebene
  • Runtime-Stack-Tracing
  • Vollständige Core Dumps
• Linearer RAM wird als riesiges, unsortierbares Objekt mit 32-Bit-Adressschlüsseln und Byte-Werten dargestellt
• Durch das Finden einer Möglichkeit, die Typauswertung im Typ-User-Space anzuhalten, wurden Core Dumps, Ausnahmebehandlung und Stack-Tracing möglich

Tool-Limits und Einschränkungen der Implementierung

• Dateigrößen von bis zu 1 GB waren nötig und lagen damit jenseits dessen, was Prettier verarbeiten kann
• Language-Server-Integration oder Linter stürzten sofort ab; praktisch funktionierte nur noch die Syntaxhervorhebung einigermaßen
• Das Innere der Engine ist mit in String-Literalen gespeicherten Zweierkomplement-Binärzahlen umgesetzt
• Da TypeScript Strings nur von links nach rechts traversieren kann, mussten alle Binäralgorithmen rückwärts implementiert werden
• Im Inneren der Engine gibt es keine Arrays, Objekte, Strings oder Booleans, sondern nur Binärzahlen
• DOOM verwendet nur 64-Bit- und 32-Bit-Integer, und diese Integer sind weder signed noch unsigned, was einen ganzen Tag brauchte, um es zu verstehen
• Der Entwickler wusste zu Beginn nicht einmal 10 % dessen, was dafür nötig war, baute eigene Tools, schrieb 12.364 Tests von Hand und lernte mehrere Programmiersprachen neu