コンパイラを書いてセルフホストした

Quartzという言語をデザインしてコンパイラを書いて自身をコンパイルできるところまで到達したので記録として書く

https://github.com/myuon/quartz

(人に使ってもらうことなどは特に想定してないので、ドキュメントなどはありません)

Quartzについて

言語機能的にはGoとかに近く、syntax的にはRustに近い言語としてデザインした。ターゲットとしてWASM(wat形式)のみサポート。
元々の想定として、ゲームのスクリプトやアプリケーションのプラグインなど、動的に読み込めて気軽にかけて、型やLSPなどの現代的なDXは提供したいというモチベで作り始めた。

例えばfizzbuzzのコードは以下のような感じ。

fun main() {
    for i in 1..100 {
        if i % 15 == 0 {
            println("FizzBuzz");
        } else if i % 3 == 0 {
            println("Fizz");
        } else if i % 5 == 0 {
            println("Buzz");
        } else {
            println("{}", i.to_string());
        }
    }
}

言語としては、以下のような機能を備えている。

• bool, i32, u32, i64, string, byteなどの組み込み型とvecとmapをサポート
• 構造体とenum
• Rustの?-syntaxに相当するtry構文と、Result型に相当するor型
• ランタイムの値に型タグを埋め込んでいて、リフレクションができる
• メソッド呼び出し
• 可変長引数
• (ファイルIOや標準出力などはWASMではできないのでRustで実装したものをランタイムから提供する形)

一方でまだ実装できていないが実装が必要なこととして、

• GC (これは優先度が高い)
• インターフェイス
• ジェネリクス

あたりは近いうちにやりたいと思っている。

また、GCの実装をサボっていることとWASMが無限にローカル変数を宣言できることを使って、まだまともにスタックとヒープを管理する機能も実装をしていないのでその辺りも徐々にやっていきたい。
(WASMが変に高級なため、例えばx64ターゲットのコンパイラ実装なんかに比べると結構サボれる場所があってその辺りはかなり感覚が違うと思われる。)

LSPとか

今回のコンパイラ実装で地味に一番勉強になったこととして、LSPについて頑張って調べたことと初めて実際に実装をしてみた。

今Quartzで実装しているコンパイラの周辺ツールとしては、以下のようなものがある。

• syntax highlight
• 型チェックの結果の表示
• 定義ジャンプ
• ホバーした時の型表示
• グローバル関数、構造体のプロパティ、構造体のメソッドの補完
• フォーマッター
• コンパイルエラー時に、ソースコードのエラー箇所を表示する機能

特に、ホバー時の型表示とフォーマッターは結構悩みながら実装をした。

型表示の主にしんどいところとしては、例えば m. というコード断片からmの型を推測して、そのメソッドやプロパティを返さなければならない。しかしドットで終わるこのコード断片は当然parseができるような形式になっていないため、そのままパーサーを通してもエラーになる。
結局こういう形式の時は無理やり m; に書き換えてパースしてから推測するみたいな頭の悪い実装したが、どうするのが普通の実装なのかいまいちわからない🤔

また、フォーマッターでしんどいのはコメントと空行の復元だった。基本的な流れとしてはソースコード→parse→AST→ASTをいい感じにprintしてファイルに書き込むという流れになる。
ASTにはコメントまでは入れていないので(コメントは書ける場所が多いため、全部をASTに載せるととんでもない量になりそうだったため)、どうにかしてコメントを復元する必要がある。あるいは関数内の文が連続する箇所で、人間が可読性のために1行空行を入れる場合があるが、それらも復元してあげる必要がある。
結局、parseする時にlexerで字句解析を行なっているのでその結果を保存しておき、文をフォーマットしている時に一緒に字句解析の結果を見てコメントがあればコメントを挿入、字句のソースコード位置を見て空行があれば空行を入れるみたいな実装をした。

LSPだと通常のコンパイラとは違い、パースエラーが起きても上手く回復したり続行したりすることが求められるので、普通のパーサーとは勝手が違って新鮮だなと感じることが多かった。

セルフホストに向けて

セルフホストすることは結構早い段階での目標だったので、それに必要と思われる言語機能を優先的に実装するなどした。
特に、構造体、メソッド呼び出し、エラーハンドリング、optional型などはあったら便利だろうと思っていたので結構早い段階で入れている。

コンパイラのおおまかなフェーズとしては、lexer→parser→typecheck→irへの変換→コード生成というまあ標準的な流れになっていて、Rustである程度の機能を実装したらQuartzでRustコードをほぼ写経するというやり方で実装をした。
またコンパイラのコードを書きながら上述のLSPの実装なども進めていたので、言語機能やLSPを実装するたびに便利で文明的な環境になっていくのを肌で感じられてよかった(これで効率が良かったのかは不明)

最終的にセルフホストができた結果のコード行数などは以下の通り。Rustのコードはテストも含みます。

おおよそ1万行くらいで実装できる程度の規模のコンパイラということになる。

Rustで書いたコンパイラを第0世代とし、Quartzで書いたコンパイラのソースコードを第0世代でコンパイルしたものを第1世代、同じソースコードを第1世代をコンパイルしたものを第2世代…とすると、第2世代と第3世代のコンパイラの中身が一致していることを最後に確認して、セルフホスト達成とした。

https://twitter.com/myuon_myon/status/1660689372243709952

実装時の主なつらみポイントはやはり第1世代では動くが第2世代では動かない系のバグであろう(醍醐味とも言える)。
これはQuartzのコンパイラが動いて欲しくないところで動いてしまうものによることが主だったので、コンパイラで異常系に対してやサポートされていない使い方について強めに制限をかけておけば良かったな〜と最後に後悔したところでもあった。

あるいは、RustのコードをQuartzに移植する過程で誤って違う実装になってしまっている箇所もあり(多分見つかってないだけで今でもある)、こういうの今流行りのChatGPTとかに入れて意味が変わってたらエラーを出すやつとかやったら便利そうだな〜と妄想したりした。

ひとまずv1としてリリースを打って自分の中で一区切りついたので、またコツコツ実装を進めていけたらいいなと思っている。