DOOM executado com tipos do TypeScript [vídeo]

• Um experimento que inicializou o jogo DOOM, de 1993, não com código em runtime, mas apenas com o sistema de tipos do TypeScript, e gerou o primeiro frame
• Até o primeiro frame, o type checker do TypeScript processou 3,5 trilhões de linhas, totalizando 177 TB, ao longo de 12 dias; a estimativa inicial era de 1,25 PB e mais de 3 meses
• A implementação central é uma máquina virtual WebAssembly feita com tipos, que implementa em lógica no nível de tipos as 116 instruções necessárias para o DOOM e avalia 18 milhões de instruções
• Durante o desenvolvimento, foram removidos limites do compilador para recursão, unions, tuplas e instanciações de tipos profundas, mas o resultado final permanece em TypeScript puro, executável pelos usuários
• Como é uma carga muito além da escala de checagem de tipos de apps comuns, as ferramentas de desenvolvimento existentes ficaram quase inutilizáveis, e foi necessário criar manualmente 12.364 testes e ferramentas customizadas

---

Um computador criado dentro do sistema de tipos do TypeScript

• O DOOM não roda como JavaScript comum, mas funciona apenas dentro do sistema de tipos do TypeScript
• O objetivo era criar, sem truques nem outra linguagem de execução, uma máquina virtual WebAssembly capaz de executar outros programas só com tipos
• O computador em nível de tipos tem, como tipos, os componentes básicos necessários para execução
  • RAM
  • Espaço em disco
  • Pilha de chamadas
  • Sub-rotinas
  • Ponteiros de memória
  • Contexto de execução
  • Ferramentas de desenvolvimento customizadas
• As 116 instruções WebAssembly necessárias para executar o DOOM foram implementadas logicamente como tipos TypeScript
• Só essa lógica gerou 18 milhões de instruções que o type checker precisou avaliar uma por uma, e cada instrução representa um estado de máquina exclusivo do sistema

A escala até o primeiro frame

• Para obter o primeiro frame do DOOM, foram necessários 3,5 trilhões de linhas de tipos, e o tamanho total dos tipos foi de 177 TB
• O compilador TypeScript TSC rodou continuamente por 12 dias para inicializar o jogo e obter o primeiro frame
• Pelos cálculos iniciais, o computador teria de processar 1,25 PB de tipos TypeScript, e o tempo de execução foi estimado em mais de 3 meses
• Com otimizações extremas, o volume foi reduzido para 177 TB e 12 dias
• A checagem de tipos com TSC em apps comuns costuma ficar na faixa de 200 mil a 500 mil instanciações de tipos, mas este trabalho manteve 20 milhões de instanciações por segundo durante todos os 12 dias
• A saída final é um objeto TypeScript, em que cada valor representa uma linha de pixels
  • O frame de saída tem 320×200
  • É um frame ASCII com um total de 128.000 pixels
• Também existe uma forma de controlar o jogo via entrada de teclado

Proteções do TypeScript removidas durante o desenvolvimento

• O resultado final é TypeScript puro, que o usuário pode executar diretamente
• Para tornar o experimento possível, o compilador TypeScript foi modificado para remover várias limitações
  • Remoção do limite de profundidade excessiva de pilha ao comparar tipos
  • Remoção do limite para instanciações de tipos muito profundas ou potencialmente infinitas
  • Definição do tamanho máximo de unions e tuplas como Infinity
  • Remoção do limite de truncamento da saída
  • Remoção do famoso limite de recursão do TypeScript
• O limite de pilha do próprio computador também foi aumentado
• Ao remover essas proteções, o type checker passou a conseguir usar facilmente 100 GB de memória
• O custo de remover os limites foi alto
  • Problemas triviais, como um typo em um import, podiam criar loops infinitos
  • Alocações no heap podiam consumir toda a memória e fazer tudo crashar
  • Os stack traces eram enormes, e a maioria das falhas simplesmente parava a execução

O que mais foi criado para executar o DOOM

• Depois de 6 meses de trabalho, já era possível executar pequenos programas em C, mas executar o DOOM exigiu muito mais implementação
• Todos os componentes do DOOM tiveram de ser codificados como tipos
  • Mapas do jogo
  • Texturas
  • Sprites
  • Som
  • IA dos inimigos
  • Armas
  • Itens
  • Motor de física
  • Subsistema de áudio
  • Textos dentro do jogo
• Até recursos próximos de runtime foram implementados no nível de tipos
  • Coletor de lixo
  • Cache L1 de CPU
  • Dead code elimination em runtime
  • Compactador de memória em tempo real
  • Pilha global de valores com contagem de profundidade para proteção contra stack underflow
  • Tabela de despacho dinâmico
  • Variáveis globais em nível de módulo
  • goto rotulado
  • Tratamento de exceções no nível de tipos
  • Rastreamento de pilha em runtime
  • Core dump completo
• A RAM linear é representada como um enorme objeto impossível de ordenar, com chaves de endereço de 32 bits e valores em bytes
• Ao encontrar uma forma de pausar a avaliação de tipos no espaço de usuário de tipos, tornou-se possível fazer core dumps, tratamento de exceções e rastreamento de pilha

Limites das ferramentas e restrições de implementação

• Como os arquivos precisavam chegar a até 1 GB, isso ultrapassou o que o Prettier conseguia processar
• A integração com language server e linters crashava imediatamente; na prática, só o realce de sintaxe mal funcionava
• Internamente, o engine é implementado com binários em complemento de dois armazenados em literais de string
• Como o TypeScript só consegue percorrer strings da esquerda para a direita, todos os algoritmos binários tiveram de ser implementados ao contrário
• Dentro do engine, não há arrays, objetos, strings nem booleanos; são usados apenas binários
• O DOOM usa apenas inteiros de 64 e 32 bits, e esses inteiros não são nem signed nem unsigned, o que levou um dia para descobrir
• No início, o criador não sabia nem 10% do conhecimento necessário; criou suas próprias ferramentas, escreveu manualmente 12.364 testes e aprendeu várias linguagens de programação novas