先日、自作プログラミング言語を自慢する会 に参加しました。非常に熱気のある刺激的なイベントで大変楽しかったです。
その登壇者の id:gfx さんがブログ(「自作プログラミング言語を自慢する会」でWadoを自慢した! - Islands in the byte stream)を書いており、触発されて私も書いてみます。
いま私は、とあるインタプリタ(インタプリタA)とセルフホストAOTコンパイラを作り終えたところなのですが、実は「本当に作りたかったインタプリタ(インタプリタB)」にはまだ手が届いていません。
この記事では、そこに至るまでの実装の経緯と、見えてきた課題などをつらつらと書き起こしました。
背景
今年6月に株式会社エクサウィザーズへ入社して以来、業務で本格的にAIコーディングエージェントを活用するようになりました。
その中で、AIコーディングエージェントとどこまでディープな実装ができるのかを調査・研鑽したくなり、プライベートの開発に取り組み始めました。
自分の手になじんでいるPythonを選び、あえてサードパーティ製ライブラリを一切使わず、Python標準ライブラリのみで以下の基盤を順に実装していきました。
- Apache Lucene / Apache Solr 相当の検索エンジン(BM25、転置インデックスなど)
- SQLite相当の構文(DDL / DML / DCL)とベクトル検索をサポートするデータベース
- Apache TinkerPop / JanusGraph クエリ言語対応のグラフデータベース
- Scrapy 相当のクローラー基盤
- PEGパーサランタイムおよびパーサジェネレータ
...etc
一定ものができると、Pythonで作るのが物足りなくなってきました。
8月中旬からとりかかり、10月くらいまでこれらに注力しました。
次は言語処理系・インタプリタが欲しい。そして、作ったものを載せ替えたり、自前の処理系で動かしたい。
コンパイラのためのインタプリタAを作る
ターゲット言語には、以前から好きだった Scheme を選びました。
まずは仕様の基準点・リファレンス実装や知見を得るため、Pythonを用いて Scheme R7RS-small 準拠のインタプリタを実装しました。
Pythonは標準パッケージが豊富で、また、表現力もあるので、特に問題なくハマることなく実装した。
一方悩んだ・困った点としては、次。
- R7RS-largeを実装するか:一旦実装しなかった
- R7RS-smallのテストケース:他の実装(https://github.com/ashinn/chibi-scheme)のテストケースで評価。
- 速度でない:計測して、改善。Pythonのプロファイラは自作していたので準備しておいてよかった。おかげで継続し、改善のサイクルを実施できた。
この実装をしたことにより、リファレンス実装を手に入れることができた。
コンパイラ
Pythonで動くSchemeが手に入ると、次は高速なネイティブバイナリを吐く AOTコンパイラ が欲しくなりました。
手元の環境がx86であるため、Scheme自身で記述したSchemeコンパイラ(むろんセルフホスト) の開発に着手しました。
コンパイラ自体をSchemeで書くことによりPythonで実装したインタプリタAを有効活用して開始しました。
なお、初期の初期はRuiさんの低レイヤを知りたい人のためのCコンパイラ作成入門 は参考にしました。ありがたい。
サポートしているバックエンド:
- x86向けのアセンブリ
- C言語
- ELF
ちょうどELFは昨日実装を終えた。それまではgccに依存していたが、ELFについては直接出力できるようになりました。
やってよかったこと:
- フロントエンド・IR・バックエンドの分割
- IR・中間言語の定義
- Nanopass フレームワークの導入: 単一の巨大な変換パスを避け、小さなパスを直列に繋ぐことで、中間状態の検証性と変更容易性を向上
- (前述した)複数バックエンドのサポート
- 分散ビルド。.s から .o を作成しgcc(ad, ld)でバイナリ生成
課題:
- デバッグフィードバックの遅さ:コンパイルしてネイティブバイナリを実行するまで、意味論的な不具合やランタイムエラーを捕捉しにくい
- メモリ安全性:Rustのようにメモリ安全ではない
- 低レイヤ実装への過度な依存:アセンブラやレジスタ割り当ての泥臭い記述が多く、言語機能の拡張に対してランタイムがタイトに結合しがち
今後はRPython ツールチェーンや、Truffle言語実装フレームワークのようなメタコンパイラ・ツールチェーンに育てていこうと思います。
副産物
並列処理基盤
この土日はかねてよりErlangの軽量プロセスや、GoのGorutineに相当する並列処理基盤が欲しかったので、実装していました。
設計としては、そのままのSchemeだとcall/ccやeval等が性能に影響を及ぼすのはわかっていたので、それらの機能は制約をつけて、Schemeのサブセット言語を実行できるようにしました。
今日実装の山場に達し、性能測定しました。
Erlangの軽量プロセス、GoのGorutine、RustのTokioと比較してもかなりよいパフォーマンスが出ています。
GCとJIT
コンパイラにGC(Cheney's Copying GC)とJITを実装しました。
ただコンパイラだと通常は、バンプアロケーションで構わない...。
GCがバグって、開発が止まることはよくありました...。
インタプリタBを作る
メタコンパイラ・ツールチェンができたら、やっと自分が作りたい言語のインタプリタを作るフェーズです。
まだ、できていない...。
その言語はSchemeになるのかPythonになるのか、または自作言語にするかは決めかねています。
結び
まだまだ道半ばです。
なにせ本来作りたいインタプリタBができてないためです。インタプリタBを作る段階で、おそらくコンパイラも書き直すことになる予定です。
今後ともAIコーディングエージェントとうまく付き合いながら、思い描いたものを自作して行きます。ぜんぶつくればいいんだ。
また、準備中ですが、OSを実装するかもしれません。
また進捗があればブログや勉強会で報告しようと思います。それではまた!



