DOOM yang Berjalan dengan Tipe TypeScript [Video]

• Ini adalah eksperimen yang mem-boot game DOOM tahun 1993 dan mencetak frame pertama hanya dengan sistem tipe TypeScript, bukan kode runtime
• Hingga frame pertama, type checker TypeScript memproses 3,5 triliun baris, total 177 TB, selama 12 hari; estimasi awalnya adalah 1,25 PB dan lebih dari 3 bulan
• Implementasi intinya adalah mesin virtual WebAssembly yang dibuat dari tipe, mengimplementasikan 116 instruksi yang diperlukan DOOM dengan logika tingkat tipe dan mengevaluasi 18 juta instruksi
• Selama pengembangan, batasan compiler untuk rekursi, union, tuple, dan instansiasi tipe yang dalam dihapus, tetapi hasil akhirnya tetap berupa TypeScript murni yang dapat dijalankan pengguna
• Karena skalanya jauh melampaui type checking aplikasi biasa, alat pengembangan yang ada hampir tak berdaya, sehingga 12.364 pengujian dan alat kustom harus dibuat sendiri

---

Komputer yang Dibuat di Dalam Sistem Tipe TypeScript

• DOOM tidak berjalan sebagai eksekusi JavaScript biasa, melainkan hanya di dalam sistem tipe TypeScript
• Tujuannya adalah membuat mesin virtual WebAssembly yang dapat menjalankan program lain hanya dengan tipe, tanpa trik atau bahasa eksekusi lain
• Komputer tingkat tipe memiliki komponen dasar yang diperlukan untuk eksekusi dalam bentuk tipe
  • RAM
  • Ruang disk
  • Call stack
  • Subrutin
  • Pointer memori
  • Konteks eksekusi
  • Alat pengembangan kustom
• 116 instruksi WebAssembly yang diperlukan untuk menjalankan DOOM diimplementasikan secara logis sebagai tipe TypeScript
• Logika ini saja menghasilkan 18 juta instruksi yang harus dievaluasi satu per satu oleh type checker, dan setiap instruksi merepresentasikan status mesin yang unik dari sistem tersebut

Skala untuk Mencapai Frame Pertama

• Untuk mendapatkan frame DOOM pertama diperlukan 3,5 triliun baris tipe, dengan ukuran tipe total 177 TB
• Compiler TypeScript TSC dijalankan terus-menerus selama 12 hari untuk mem-boot game dan mendapatkan frame pertama
• Perhitungan awal memperkirakan komputer harus memproses 1,25 PB tipe TypeScript, dengan waktu eksekusi lebih dari 3 bulan
• Setelah optimisasi ekstrem, volume pemrosesan berhasil dikurangi menjadi 177 TB dan 12 hari
• Type checking TSC untuk aplikasi biasa umumnya berada di kisaran 200 ribu–500 ribu instansiasi tipe, tetapi pekerjaan ini mempertahankan 20 juta instansiasi per detik selama 12 hari penuh
• Output akhirnya adalah objek TypeScript, dengan setiap nilai merepresentasikan satu baris piksel
  • Frame keluaran berukuran 320×200
  • Merupakan frame ASCII dengan total 128.000 piksel
• Ada juga cara mengendalikan game dengan input keyboard

Pengaman TypeScript yang Dihapus Selama Pengembangan

• Hasil akhirnya adalah TypeScript murni yang dapat dijalankan langsung oleh pengguna
• Agar eksperimen ini memungkinkan, compiler TypeScript dimodifikasi untuk menghapus berbagai batasan
  • Menghapus batas kedalaman stack yang berlebihan saat membandingkan tipe
  • Menghapus batas instansiasi tipe yang terlalu dalam atau berpotensi tak hingga
  • Mengatur ukuran maksimum union dan tuple menjadi Infinity
  • Menghapus batas pemotongan output
  • Menghapus batas rekursi TypeScript yang terkenal
• Batas stack komputer itu sendiri juga dinaikkan
• Setelah pengaman semacam ini dihapus, type checker dapat dengan mudah menggunakan memori 100 GB
• Harga dari penghapusan batasan itu besar
  • Masalah sepele seperti salah ketik pada import pun bisa membuat loop tak hingga
  • Alokasi heap bisa menghabiskan seluruh memori dan membuat semuanya crash
  • Stack trace menjadi sangat besar, dan sebagian besar kegagalan terjadi dengan cara sekadar berhenti

Hal-hal Tambahan yang Dibuat untuk Menjalankan DOOM

• Setelah 6 bulan pengerjaan, program C kecil sudah bisa dijalankan, tetapi menjalankan DOOM membutuhkan implementasi yang jauh lebih banyak
• Semua komponen DOOM harus dienkode sebagai tipe
  • Peta game
  • Tekstur
  • Sprite
  • Suara
  • AI musuh
  • Senjata
  • Item
  • Mesin fisika
  • Subsistem audio
  • Teks dalam game
• Bahkan fitur yang mendekati runtime diimplementasikan pada tingkat tipe
  • Garbage collector
  • Cache CPU L1
  • Runtime dead code elimination
  • Kompaktor memori real-time
  • Stack nilai global dengan penghitungan kedalaman untuk perlindungan stack underflow
  • Tabel dispatch dinamis
  • Variabel global tingkat modul
  • labeled goto
  • Penanganan exception tingkat tipe
  • Stack tracing runtime
  • Core dump lengkap
• RAM linear direpresentasikan sebagai objek raksasa yang tidak dapat diurutkan, dengan key alamat 32-bit dan nilai byte
• Dengan menemukan cara untuk menjeda evaluasi tipe di ruang pengguna tipe, core dump, penanganan exception, dan stack tracing menjadi memungkinkan

Batasan Alat dan Kendala Implementasi

• Ukuran file yang dibutuhkan mencapai hingga 1 GB, melampaui kemampuan yang dapat ditangani Prettier
• Integrasi language server atau linter langsung crash, dan praktis hanya syntax highlighting yang nyaris masih berfungsi
• Bagian dalam engine diimplementasikan sebagai bilangan biner komplemen dua yang disimpan dalam literal string
• Karena TypeScript hanya dapat menelusuri string dari kiri, semua algoritme biner harus diimplementasikan secara terbalik
• Di dalam engine tidak ada array, objek, string, atau boolean; yang digunakan hanya bilangan biner
• DOOM hanya menggunakan integer 64-bit dan 32-bit, dan integer tersebut bukan signed maupun unsigned, sehingga butuh satu hari untuk memahami hal ini
• Saat memulai, pembuatnya bahkan belum mengetahui 10% dari pengetahuan yang dibutuhkan; ia membuat alat sendiri, menulis 12.364 pengujian secara manual, dan mempelajari beberapa bahasa pemrograman baru