DOOM ejecutándose con tipos de TypeScript [Video]

• Un experimento que logró arrancar DOOM y mostrar su primer frame usando solo el sistema de tipos de TypeScript, no código en tiempo de ejecución
• Hasta el primer frame, el verificador de tipos de TypeScript procesó 3.5 billones de líneas y un total de 177 TB durante 12 días; la estimación inicial era de 1.25 PB y más de 3 meses
• La implementación clave es una máquina virtual de WebAssembly hecha con tipos, que implementa con lógica a nivel de tipos las 116 instrucciones necesarias para DOOM y evalúa 18 millones de instrucciones
• Durante el desarrollo se eliminaron límites del compilador sobre recursión, uniones, tuplas e instanciación profunda de tipos, pero el resultado final quedó como TypeScript puro que cualquier usuario puede ejecutar
• Como la escala de verificación de tipos supera por mucho la de una app normal, las herramientas de desarrollo existentes quedaron casi inutilizadas y fue necesario crear 12,364 pruebas y herramientas personalizadas

---

Una computadora construida dentro del sistema de tipos de TypeScript

• DOOM no corre con ejecución normal de JavaScript, sino únicamente dentro del sistema de tipos de TypeScript
• El objetivo era crear una máquina virtual de WebAssembly capaz de ejecutar otros programas solo con tipos, sin trucos ni otro lenguaje de ejecución
• La computadora a nivel de tipos incluye como tipos los componentes básicos necesarios para ejecutar
  • RAM
  • espacio en disco
  • pila de llamadas
  • subrutinas
  • punteros de memoria
  • contexto de ejecución
  • herramientas de desarrollo personalizadas
• Se implementaron con tipos de TypeScript las 116 instrucciones de WebAssembly necesarias para ejecutar DOOM
• Solo con esa lógica, el verificador de tipos tuvo que evaluar 18 millones de instrucciones, y cada instrucción representa un estado único de la máquina

La magnitud hasta el primer frame

• Obtener el primer frame de DOOM requirió 3.5 billones de líneas de tipos, y el tamaño total de tipos fue de 177 TB
• Se ejecutó el compilador de TypeScript TSC de forma continua durante 12 días para arrancar el juego y obtener el primer frame
• En el cálculo inicial, la computadora tendría que procesar 1.25 PB de tipos de TypeScript, y se estimaba un tiempo de ejecución de más de 3 meses
• Tras optimizaciones extremas, la carga se redujo a 177 TB y 12 días
• Mientras que la verificación de tipos de una app normal con TSC suele estar en el rango de 200 mil a 500 mil instanciaciones de tipos, este trabajo sostuvo 20 millones de instanciaciones por segundo durante los 12 días completos
• La salida final es un objeto de TypeScript, y cada valor representa una línea de píxeles
  • El frame de salida es de 320×200
  • Es un frame ASCII de 128,000 píxeles en total
• También hay una forma de controlar el juego con entrada de teclado

Salvaguardas de TypeScript que se quitaron durante el desarrollo

• El resultado final es TypeScript puro que cualquier usuario puede ejecutar directamente
• Para hacer posible el experimento, se modificó el compilador de TypeScript y se eliminaron varios límites
  • Se quitó el límite de profundidad excesiva de pila al comparar tipos
  • Se quitó el límite de instanciación de tipos demasiado profunda o potencialmente infinita
  • El tamaño máximo de uniones y tuplas se fijó en Infinity
  • Se quitó el límite de truncamiento de salida
  • Se eliminó el famoso límite de recursión de TypeScript
• También se aumentó el límite de pila de la propia computadora
• Al quitar estas protecciones, el verificador de tipos pudo usar con facilidad 100 GB de memoria
• El costo de eliminar esos límites fue alto
  • Un problema menor, como un error tipográfico en un import, podía crear un bucle infinito
  • Una asignación en el heap podía consumir toda la memoria y hacer que todo colapsara
  • Los stack traces eran enormes, y en la mayoría de los casos simplemente fallaba quedándose detenido

Cosas adicionales que se construyeron para ejecutar DOOM

• Después de 6 meses de trabajo ya se podían ejecutar pequeños programas en C, pero ejecutar DOOM requirió muchísimo más desarrollo
• Hubo que codificar todos los componentes de DOOM como tipos
  • mapas del juego
  • texturas
  • sprites
  • sonido
  • IA de enemigos
  • armas
  • ítems
  • motor de físicas
  • subsistema de audio
  • texto dentro del juego
• También se implementaron a nivel de tipos funciones cercanas a un runtime
  • recolector de basura
  • caché L1 de CPU
  • eliminación de código muerto en runtime
  • compactador de memoria en tiempo real
  • pila global de valores con conteo de profundidad para proteger contra stack underflow
  • tabla de despacho dinámico
  • variables globales a nivel de módulo
  • goto etiquetado
  • manejo de excepciones a nivel de tipos
  • stack tracing en runtime
  • volcado completo del núcleo
• La RAM lineal se representa como un objeto gigantesco imposible de ordenar, con claves de direcciones de 32 bits y valores de bytes
• Al encontrar una forma de pausar la evaluación de tipos en el espacio de usuario de tipos, se hicieron posibles los core dumps, el manejo de excepciones y el stack tracing

Límites de herramientas y restricciones de implementación

• Se necesitaron archivos de hasta 1 GB, superando lo que Prettier puede manejar
• La integración con el servidor de lenguaje o el linter se caía de inmediato, y en la práctica apenas funcionaba el resaltado de sintaxis
• El interior del motor está implementado con binarios en complemento a dos almacenados en literales de cadena
• Como TypeScript solo puede recorrer cadenas de izquierda a derecha, hubo que implementar todos los algoritmos binarios al revés
• Dentro del motor no hay arreglos, objetos, cadenas ni booleanos; solo binarios
• DOOM usa solo enteros de 64 bits y 32 bits, y esos enteros no eran ni signed ni unsigned, algo que tomó un día completo entender
• El creador no conocía ni el 10% de lo necesario al empezar, y terminó creando sus propias herramientas, escribiendo a mano 12,364 pruebas y aprendiendo varios lenguajes de programación nuevos