- コンパイラ系ツールの実装言語は伝統的に OCaml と C++ に分かれてきたが、小さな言語実験では TypeScript が ML 系言語のように軽く使える選択肢になりうる
- Rust は ML と C++ の長所を組み合わせ、安全なマルチスレッドまで提供するが、データの物理配置をモデル化する必要があるため、小さなプロトタイプには負担が大きくなりうる
- Deno は単一バイナリ、組み込みの lint・format、コンパイル段階なし、タスクランナーと watch モードによって、TypeScript による言語実験を素早く始められる
- 例の型チェッカーは、ジェネリック AST、タグ付きユニオン、visitor、bottom-up transform を組み合わせて
Expr<void> を Expr<Type> に変換し、TypeError を型の値として入れることで 連鎖的なエラー を減らす
- TypeScript は補完、柔軟な型システム、必要なときに動的なやり方へ逃げられるランタイム特性によって、小規模な言語ハック用ツールとして生産的になりうる
実装言語選択の従来構図
- コンパイラ系のツールを作る際、実装言語の選択には大きく 2 つの流れがある
- 実装中心で、本番投入の準備が必要な作業では C++ がよく選ばれる
- LLVM、clang、v8、HotSpot はいずれも C++ ベースである
- Rust は ML と C++ の影響を直接受けており、両者の長所を組み合わせつつ、安全なマルチスレッドのような独自の強みも備える
- ただしスペクトラムとしては 本番適性 側により傾いている
- 「とりあえず動く」ビルドシステムはプロトタイピングにも役立つが、データの物理配置をモデル化しなければならない追加の複雑さが伴う
Rust のインデックス方式の利点と小規模コードでの負担
- Rust でコンパイラを作る際によくある助言は、ポインタを避けて インデックス を使うことだ
- インデックスは大規模コードベースで多くの利点を持つ
- サイドテーブルを関連モジュール内に置けるので結合度を下げられる
- インデックスが
u32 で、struct-of-arrays レイアウトを促せるため性能に有利である
- シリアライズしたり、インクリメンタルコンパイルのフレームワークに接続したりしやすく、計算戦略の自由度が高い
- しかし小さな単位のプログラミングでは、インデックス方式そのものが煩雑になり、趣味の実験ではこの負担が致命的になりうる
- OCaml には古さを感じる面もあり、この文脈では TypeScript を ML に相当する代替として使えるかが検討される
Deno と TypeScript がもたらす素早い実験環境
- 開始環境として deno が使われる
- TypeScript をそのまま使える すぐ使える体験 を提供する
- OCaml ではここがつらい点であり、Rust は OCaml や C++ よりましだが、Deno は Rust よりさらに簡単な体験を与える
- Deno の開発体験は小さな PLT ハックに向いている
- 単一バイナリである
- lint と format が組み込みである
- 別個のコンパイル段階がない
- 組み込みのタスクランナーと watch モードがある
- TypeScript 自体も十分に柔軟で、構文上の負担が軽い 型システム を備えている
小さな型チェッカーの例で見る TypeScript のパターン
- AST はファイル位置情報を持つ式から始まる
Location は file、line、column を持つ- TypeScript では文字列はそのまま
string、数値はそのまま number なので、usize と u32 のような区別を考えなくてよい
- 式は位置と kind を分け、のちに
Expr<T> という形で 関連データ をジェネリック化する
- パース直後の式は
void データを持つ
- 型チェッカーが処理した式は
Type データを持つ
- 型推論関数は
ast.Expr<void> を受け取り、ast.Expr<Type> を返す
- TypeScript はランタイムの振る舞いを自動で追加しないため、ユニオン型をマッチさせるには自分でランタイム型情報を入れる必要がある
tag: "binary"、tag: "if" のようなフィールドがその役割を担うtag: "binary" はランタイムでその値が文字列 "binary" にしかなりえないことを意味する
- boolean リテラルと int リテラルはほぼ同じ形なので、
ExprLiteral<T, V, Tag> で抽象化される
ExprBool<T> は ExprLiteral<T, boolean, "bool">ExprInt<T> は ExprLiteral<T, number, "int">
- 型の値は
TypeBool、TypeInt に分かれ、シングルトン値も同じ名前で提供される
- TypeScript は型を完全に消去するため、型関連の名前空間と値関連の名前空間が別に存在する
- この性質を利用して、型と値を同じ名前で定義できる
Visitor、transform、エラー型、desugaring
- TypeScript の
switch は式ではなく文なので、式 kind を扱いやすくするために visitor が定義される
bool、int、binary、if メソッドがそれぞれ対応する kind を処理する- エディタの補完が
switch case や visitor 実装を助けてくれる
transform<U, V> は Expr<U> を Expr<V> に変える一般化された走査関数である
- 変換は bottom-up で実行される
- 内部ノードを訪問するときには下位式がすでに変換済みなので、visitor 型は
Visitor<U, V> ではなく Visitor<V, V> になる
- TypeScript が動的型付き言語でもあることを利用すれば、
Object.keys によるもっと汎用的な走査も作れる
- この場合でも静的な関数シグネチャは維持できる
- 例では必須ではないが、必要なら動的な方法へ逃げる余地がある
- 型エラーは副作用として配列に蓄積せず、
TypeError 型で表現する
Type は TypeBool | TypeInt | TypeError となるTypeError は tag: "Error"、location、message を持つtype_equal はどちらか一方が Error なら true を返し、連鎖失敗 を防ぐ
- 最終的な型チェッカーは binary と if を検査する
- binary 式は左右の被演算子の型が異なる場合、
"binary expression operands have different types" エラーを返す
- if 式は条件が boolean でない場合、
"if condition is not a boolean" エラーを返す
- then と else branch の型が異なる場合、
"if branches have different types" エラーを返す
- できあがったものはある程度の型注釈を必要とするが、補完がかなり補ってくれ、言語と格闘している感じが少なく、問題の形に自然に合っている
- TypeScript が小規模な言語ハック用ツールとして生産的である理由は 3 つに整理される
- Deno は小さく、自己完結的で、強力かつ効果的な開発ワークフローに最適化された スクリプティングランタイム である
- TypeScript のツール群は IDE が有用で生産的であり、Deno のおかげで設定も不要である
- 言語はランタイムとコンパイル時の両面で強力で、型でかなり精巧な表現をしつつ、必要なら動的な方法へ逃げられる
- 追加のアイデアとして、多くの糖衣構文を型安全に desugar する方式も可能である
Expr と ExprKind を関連データではなく、ExprKind 全体に対して再帰的にパラメータ化するExprKindCore は基本式の集合を表すExprKindSugar は基本式、または基本式へ desugar 可能な式を含むdesugar(expr: ExprSugar): ExprCore は糖衣構文の式をコア式へ簡約するdesugar_one(expr: ExprKindSugar<ExprCore>): ExprKindCore<ExprCore> は、下位式がすでに desugar 済みの状態で 1 段階の変換を行う
1件のコメント
Hacker News の意見
TypeScript は全体として優れた言語であり、関数がプロパティ／メソッドを持てるオブジェクトである点は過小評価されている
関数の配列をコマンドのように実行しておき、後から
helpのような説明を付けたり、クロージャ／部分適用で状態を追加したりできるため、Commandのようなクラスを早まって定義しなくて済むオブジェクト指向では名前を早く付けすぎることが多くの摩擦を生み、
VideoCompressor#compress()のような構造よりも、必要な値を関数に渡すほうが自然だと考えている関数のように動作するオブジェクトをサポートする他の言語は https://en.wikipedia.org/wiki/Function_object にまとまっている
net/httpのハンドラのように構造体がserveメソッドを実装することもできるし、ハンドラ関数が自分自身を呼び出してインターフェイスを満たすこともできるClojure では関数
varにメタデータを付けて同様に扱えるし、Lisp なのでマクロでほぼ何でもできるまた
core/asyncの CSP チャネルは実行と通信を分離し、コールバック／Promise／async／awaitのような関数の色問題を避けられるようにしてくれ、コマンド群が結果をチャネルへ送るプロデューサのように動作できるメソッド名が何であれ関数コンテキストで使え、具体的なメソッド名を参照しなくてもよい
ただし、関数がプロパティを持って状態を抱え、同じ引数で呼び出しても挙動が変わり得ることは好まない。関数型プログラミングの大きな利点は、オブジェクト指向的な状態から離れられる点にあると思う
Func、戻り値のない関数はActionとして似たように表現できるJavaScript のラムダ式は C# とかなり似ており、TypeScript と C# の関数シグネチャもかなり近い
JavaScript、TypeScript、C# の類似性を示す小さなリポジトリもある: https://github.com/CharlieDigital/js-ts-csharp
同じロジックを JS/TS/C# で横並びに示すスクリーンショット: https://github.com/CharlieDigital/js-ts-csharp/blob/main/js-...
それほど意外ではない。TypeScript も結局、ML 系の機能のかなりの部分を苦労しながら取り入れた、もう一つの言語だと見ている
本物の パターンマッチング がないので OCaml よりは不便だが、C#、Swift、Dart、Kotlin のような類と比べれば無難な水準だ
TypeScript は型システムは強力だが、土台となる標準ライブラリと言語自体に物足りなさがあり、パターンマッチング／switch 式がない
Dart はオブジェクトモデルが閉じていて動的な自由度が低く、型システムや式もより弱い。メタプログラミング機構もほとんどないため、Java 式のボイラープレートやコード生成器に頼ることになる
C# は挙げられた言語の中では ML の機能に最も近いが、TypeScript と違って合併型がないため、多くのことがより面倒になる
例えば
{ ... }を認識するパーサを他のパーサと組み合わせ、文は制御フロー／宣言／代入のいずれかとして定義できるML 風のリスト処理とパターンマッチングは、中間表現を扱う際に非常に表現力が高かった
本文でも
switchが式ではないため、ビジターパターンで回避しなければならなかったし、JavaScript のイテレータサポートも妙に不足している.map()はあるが配列にしか動作せず、一般のイテレータにはそのまま適用できない違いは多いが移行は難しくなく、個人的には Kotlin のほうを好むとしても、どちらも使える
TypeScript が JavaScript 互換性から離れて WASM にコンパイルするようになったらどうだろうと思う。Kotlin は WASM コンパイラを追加中で、すでに JS トランスパイラもあるが、同じコードが WASM ではより小さく、速くロードされる
ブラウザ JavaScript は良いコンパイルターゲットではなく、新規プロジェクトが最初から TypeScript で始まることが増えたぶん、既存の JavaScript から簡単に移行できなければならないという理由も次第に弱くなっている
Rust と TypeScript を行き来すると、タグ付き列挙型 のような機能がどれほど欠けているかが非常にはっきり見える
ADT 列挙型の提案は止まっているようだが、他に動きがあるのか気になる: https://github.com/Jack-Works/proposal-enum/discussions/19
TypeScript の型システムは面白いが、コンパイラがコンパイル言語で書かれていたらどれほど速かったのか気になる
もちろん「良い実装」という大きな前提が必要
swcとesbuildは良い比較対象ではない。速度向上のかなりの部分は、TypeScript 専用構文を取り除いて JavaScript を生成するためtscは初回実行だけが遅いほうで、incrementalフラグや--transpile-onlyの監視モードを使えば、通常コンパイル時間は 100ms 未満になり、SWC や ESBuild との体感差はほとんどなくなる中規模のプログラムの型チェックに 20 秒かかるなら、たいていは JS だからではなく、型が組み合わせ爆発を起こしているためであることが多い、という話
他のランタイムは並列性や起動時間で利点をもたらす可能性はあるが、全体で 20 倍の高速化を裏付ける CPU 中心のベンチマークは見たことがないとのこと
その後、型ロジック 5 行を一日中デバッグすることになると、自分はどうしてここまで来てしまったのかと自問することになる
SWC の主要開発者が Rust で書いたプロジェクトで、SWC は TS を JS にコンパイルし、STC は TS の型をチェックする
今後の isolated declaration mode はコンパイル時間を最大 75% 短縮できるという: https://github.com/microsoft/TypeScript/pull/53463#issuecomm...
コンパイラを学び始めたばかりの人には、この本を勧める: https://keleshev.com/compiling-to-assembly-from-scratch/
著者は TypeScript のサブセットで 32 ビット ARM アセンブリのコンパイラを作っており、ほとんど疑似コードのように見えて取り組みやすいと説明している
本は 2 部構成で、第 1 部では Java で言語インタプリタを作り、第 2 部では同じ言語をバイトコードにコンパイルしたうえで、C でバイトコード仮想マシンを実装する
実装のすべてのコード行が本の中で参照されている
visitor パターンを避けるには、
runユーティリティ関数で IIFE スタイルの switch を使うことができる即時実行関数の中で
switchを使い、戻り値の型を推論させればよい末尾の
()が嫌で IIFE を避けたいなら、関数を別に定義してから呼び出せばよいTypeScript でコンパイラを書いているところだが、思ったより悪くないという点には同意する
最初は著者と同じく Deno で始めたが、最終的には Bun に移った。粗い部分はあるものの、Deno より満足しており、非常に速い
標準的なパーサジェネレータのフロントエンドとしては Ohm-js がかなり快適: https://ohmjs.org/
公式の
tscコンパイラは巨大すぎるので読むことは勧めず、tscがどう動くかを見るには mini-typescript のほうが良い: https://github.com/sandersn/mini-typescript/特に
centi-typescriptブランチが役に立つ: https://github.com/sandersn/mini-typescript/tree/centi-types...WASM で GC と DOM アクセスが可能になることに期待している
TypeScript はインターフェイスのために追加の負担がもっとあると思っていたので意外
他の分野にも適用できるのか、たとえば言語パースにも向いているのか気になる
コンパイル過程で完全に消える
結果はそれほど驚きではない。TypeScript コンパイラ自体が TypeScript で書かれているため
ML としての TypeScript は、すでに毎日重いプロダクション環境で検証されている
C# でコンパイラを書いたことがあるが、ここで特別に見えるのはユニオン型くらい
個人的には visitor パターンの冗長さを避けることにしており、コンパイル時の網羅性チェックのために閉じた enum 機能を待っているところ
たいていの代替策はぎこちない。直和型ひとつを表すクラスに nullable なプロパティを N 個置いて「常にひとつだけ non-null」というドキュメント上の条件に頼るか、複数のクラスを共通クラスから継承させる方式だが、どちらも重く感じる
重なり合う複数のユニオン型を作ろうとすると、どちらの方式でも重複や巧妙な組み合わせが必要になる