- 1993年のゲーム DOOM を、ランタイムコードではなく TypeScriptの型システムだけで 起動し、最初のフレームを出力した実験
- 最初のフレームに到達するまでに、TypeScriptの型チェッカーが 3.5兆行、合計 177TB を12日間処理し、当初の見積もりは1.25PBと3か月以上だった
- 中核実装は型で作られた WebAssembly仮想マシン で、DOOMに必要な116個の命令を型レベルのロジックで実装し、1,800万個の命令を評価した
- 開発中にはコンパイラの再帰・ユニオン・タプル・深い型インスタンス化の制限を取り払ったが、最終成果物はユーザーが実行可能な 素のTypeScript の形で残っている
- 一般的なアプリの型チェック規模をはるかに超える作業だったため、既存の開発ツールはほぼ役に立たず、12,364件のテストとカスタムツールを自作する必要があった
TypeScript型システムの中に作られたコンピューター
- DOOMは通常のJavaScript実行ではなく、TypeScript型システム の中だけで動作する
- 目的は、ごまかしや別の実行言語を使わず、型だけで別のプログラムも実行できる WebAssembly仮想マシン を作ることだった
- 型レベルのコンピューターは、実行に必要な基本構成要素を型として備えている
- RAM
- ディスク領域
- コールスタック
- サブルーチン
- メモリポインタ
- 実行コンテキスト
- カスタム開発ツール
- DOOMの実行に必要な 116個のWebAssembly命令 をTypeScriptの型としてロジック実装した
- このロジックだけでも、型チェッカーが1つずつ評価しなければならない 1,800万個の命令 が生成され、各命令はシステム固有のマシン状態を表している
最初のフレームまでの規模
- 最初のDOOMフレームを得るには 3.5兆行 の型が必要で、全体の型サイズは 177TB だった
- TypeScriptコンパイラ
TSC を12日間動かし続けてゲームを起動し、最初のフレームを得た
- 当初の試算では、コンピューターが 1.25PB のTypeScript型を処理する必要があり、実行時間は 3か月以上 と見積もられていた
- 極限まで最適化した結果、処理量を 177TBと12日 まで削減した
- 一般的なアプリの
TSC 型チェックは通常 20万〜50万回の型インスタンス化 程度だが、この作業では12日間ずっと毎秒 2,000万回のインスタンス化 を維持した
- 最終出力はTypeScriptオブジェクトで、各値が1行分のピクセルを表す
- 出力フレームは 320×200
- 合計 128,000ピクセル のASCIIフレーム
- キーボード入力でゲームを操作する方法もある
開発中に取り払ったTypeScriptの保護機構
- 最終成果物は、ユーザーが自分で実行できる 素のTypeScript である
- この実験を可能にするため、TypeScriptコンパイラを改変して複数の制限を取り払った
- 型比較時の過剰なスタック深度制限を削除
- 深すぎる、または無限になり得る型インスタンス化の制限を削除
- ユニオンとタプルの最大サイズを Infinity に設定
- 出力切り詰め制限を削除
- 有名なTypeScriptの 再帰制限 を削除
- コンピューター自体のスタック制限も引き上げた
- こうした保護機構をなくしたことで、型チェッカーは 100GBのメモリ を簡単に使えるようになった
- 制限解除の代償は大きかった
- importのタイプミスのような些細な問題でも無限ループを引き起こし得た
- ヒープ割り当てがメモリを使い切って全体がクラッシュすることがあった
- スタックトレースは非常に巨大で、ほとんどは単に停止する形で失敗した
DOOM実行のために追加で作られたもの
- 6か月の作業後には小さなCプログラムを実行できるようになっていたが、DOOMの実行 にははるかに多くの実装が必要だった
- DOOMの構成要素をすべて型としてエンコードする必要があった
- ゲームマップ
- テクスチャ
- スプライト
- サウンド
- 敵AI
- 武器
- アイテム
- 物理エンジン
- オーディオサブシステム
- ゲーム内テキスト
- 型レベルでランタイムに近い機能まで実装した
- ガベージコレクタ
- L1 CPUキャッシュ
- ランタイム dead code elimination
- リアルタイムメモリコンパクタ
- スタックアンダーフロー保護のための深度カウント付きグローバル値スタック
- 動的ディスパッチテーブル
- モジュールレベルのグローバル変数
- labeled
goto
- 型レベル例外処理
- ランタイムスタックトレース
- 完全なコアダンプ
- 線形RAMは 32ビットのアドレスキー とバイト値を持つ、巨大でソート不可能なオブジェクトとして表現される
- 型のユーザー空間で型評価を一時停止する方法を見つけたことで、コアダンプ、例外処理、スタックトレースが可能になった
ツールの限界と実装上の制約
- ファイルサイズは最大 1GB 必要で、Prettierが処理できる範囲を超えていた
- 言語サーバー統合やリンターは即座にクラッシュし、事実上 シンタックスハイライト だけが辛うじて動作した
- エンジン内部は文字列リテラルに格納した 2の補数の2進数 で実装されている
- TypeScriptは文字列を左からしか走査できないため、2進アルゴリズムをすべて逆方向で実装しなければならなかった
- エンジン内部には配列、オブジェクト、文字列、ブール値がなく、2進数 だけが使われている
- DOOMは 64ビット整数と32ビット整数 だけを使っており、それらの整数はsignedでもunsignedでもないため、これを把握するのに1日かかった
- 制作者は開始時点で必要な知識の10%も持っておらず、自前のツールを作り、12,364件のテスト を手作業で書き、複数のプログラミング言語を新たに学んだ
まだコメントはありません。