2019年、ミローネ言語コンパイラや HSP3 GINGER (HSP3 言語の LSP やデバッガなど) を開発した経験に基づく、今後の展開の構想について。
振り返り
昨年 (2019年)、「ミローネ言語」と「HSP3 GINGER」という2つのプロジェクトにある種の区切りをつけました。ミローネ言語は当初の目標であったセルフホスティングを達成し、HSP3 GINGER は一定のクオリティのものをリリースしました。
簡単に紹介すると、ミローネ言語 はプログラミング言語 F# のサブセットである言語です。そして、ミローネ言語をC言語に変換するコンパイラ を実装するプロジェクトです。以下の記事を参照。
HSP3 GINGER はプログラミング言語 HSP3 の開発ツールを作成するプロジェクトです。入力支援とかインテリセンスと呼ばれる機能を提供する LSP を作成したり、デバッガーを作成したりしました。以下の記事を参照。
ミローネ言語の成功
ミローネ言語の成功点はコンパイラ実装に詳しくなれたこと……と言いたかったんですが、F# の言語仕様を再現するために苦心した面が多く、汎用性のある知識がとても増えたとはいえないかもしれません。
また、成果物自体はエラー処理やメモリ管理 (後述) の面で問題が多く、実用レベルではありません。
そのため、どちらかというと「セルフコンパイルできるぐらい複雑なコンパイラを自力で作れる」という成功体験や、数々の反省点を掘り起こしたことなどを挙げたいです。今後の挑戦の燃料にします。
ミローネ言語の反省
反省点を4つあげます。
1つ目は 性能 です。セルフコンパイル、すなわちミローネ言語コンパイラをミローネ言語コンパイラでコンパイルするのに、私の開発マシンで20秒ほどかかります。1万行のソースコードのコンパイルにかかる時間としては長すぎです。原因の目星はついている (おそらくマップのデータ構造が悪い) のですが、解消は容易ではないので今後の課題としています。
2つ目は 中間表現の設計 です。コンパイルの途中でプログラムはツリーの中間表現になりますが、その構造の設計がそこはかとなくいまいちなせいで、アルゴリズムの実装に支障をきたしています。また、中間表現を再設計してはアルゴリズムを手直しする、という工程の反復に無駄に時間をかけてしまったのも課題です。
3つ目は FFI です。Issue で指摘を受けていますが、ミローネ言語には FFI (外部関数インターフェイス) がないため、例えばC言語で書いたコードをリンクできません。F# の extern の構文 がなんかアレというのもあります。また、ミローネ言語は必ず main 関数を必要とする部分があるのも問題で、C言語で書いたプロジェクトにミローネ言語で書いたコードをライブラリとして埋め込む、といったこともできません。
4つ目は メモリ管理 です。ミローネ言語が生成するC言語のコードは ヒープに確保したメモリを解放しない うえに GC がありません。セルフコンパイルには数百MBしか消費しないのでいまのところ問題ありませんが、実用的ではないでしょう。Boehm GC とか、構造体の型定義に工夫するだけでコピーGCがつくとか、いろいろあるようですが、移植性とかも含めて考えます。
あとで読む: C言語でインクルードするだけで使えるNon-movingで正確なコピーGCを作った
HSP3 GINGER の成功
HSP3 GINGER のもっとも良い点は、LSP を短時間で作ったことです。LSP は、挙動の正確性をやや妥協したとはいえ十分に便利で、1週間ばかりで作ったとは思えないぐらいに役に立っています。
もう1つは LSP や DAP の理解が深まったことです。自作言語にインテリセンスやデバッガはなくてはならない存在なため。DAP 準拠のデバッガはまだ完成していませんが、試作版はあります。また、knowbug のクライアントとサーバーの通信方式は DAP をベースにしています。
関連トピック
上記の振り返りを踏まえて、いま関連トピックについて思っていることや調べたことを書きます。
CPS 中間表現
ミローネ言語の中間表現の問題に関して、最近は CPS 中間表現に目をつけています。Standard ML of New Jersey という処理系で採用されていて、静的単一代入 (SSA) 中間表現のような良い性質を持つらしいです。
よく知らないので詳述を避けますが、とりあえず以下の本を読んでいく予定です。
Amazon.co.jp: Compiling with Continuations (English Edition) 電子書籍: Andrew W. Appel: Kindleストア
イミュータブル性の性能へのペナルティ
ミローネ言語は F# のサブセットですが、実装している機能はほとんど「副作用がない」ものに限定しています。printf などの副作用を起こす関数があるので言語としては純粋でありませんが、データ構造はイミュータブル になっています。
イミュータブルにしておくと、コードが読みやすいとか、デバッグしやすいとか、種々の利点があります。一方で、性能面にペナルティがあります。遅くなるか、最適化頼りになる ことです。
例えばツリーの一部を「書き換える」とき、破壊的に変更を許せば一瞬なのに、経路複製 (path copying) により無駄にヒープメモリを消費したりメモリアロケータに負荷をかけます。
あるいは、そのような挙動を処理系が検出して最適化できたとしても、それは「 ソースコードから実行時の効率が見えない 」ことになります。いわゆる「処理系の気持ちを考える」という状況です。
Rust のオブジェクトの可変性
イミュータブルのメリットと性能を両立させる方法は何かないでしょうか。「最速レベル」のプログラミング言語である Rust では、うまくバランスが取れているようにみえます。
雑にいうと、Rust においてデータ構造上のあるフィールドが可変か否かは、そのフィールドや属する型の定義ではなく、おおよそその フィールドの所有者が可変か否か で決まるイメージです。(厳密にいうと全く異なりますが、雰囲気的にはそう。)
例えば以下のトークン型があるとき、これの種類 (kind) や文字列 (text) が可変かどうか、というのは決まっていません。
struct Token {
// (整数)
kind: usize,
text: String,
}
この型がついたオブジェクトを扱う時点では可変か否かは決まっています。
// トークンの種類を取得する関数
fn token_to_kind(token: &Token) -> usize {
// ここで token は不変(参照)なので token.kind や token.text は不変
// 変更操作はコンパイルエラーになる！
// token.kind = 1;
token.kind
}
// トークンを null にする関数
fn token_set_null(token: &mut Token) {
// ^ mut = mutable (可変) の意
// ここで token は可変(参照) なので、
// 変更操作はコンパイルエラーにならない。
token.kind = 1;
token.text = "null".to_string();
}
このように Rust では同じ型でもイミュータブルな方が都合がいいときはイミュータブルとみなし、ミュータブルな方が都合がいいときはミュータブルとみなす、といったことができます。
(補足: 実際にはそこまで単純な話ではなく、例えば Rc などでデータを共有したりしようとすると悩みは増えます。)
(補足: C++ の const もおおむね同様ですが、const は再帰的に伝播しないため、T const& がイミュータブルなデータ構造であるとはいいがたいです。また、Rust の場合も interior mutability を使うと伝播しなくなります。)
諸言語のメモリ管理戦略
古来より2020年まで、メモリ管理は常に重要なトピックでありつづけています。
ガベージコレクション (GC) があればオールオッケーかというと、そうでもなく、例えばヒープアロケーションを避けて GC の負荷を軽減することにより高速化をはかる話はよく耳にします。
プログラミング言語の視点でのメモリ管理戦略については以下の記事が参考になります。(これはC言語の代替になることを狙っているらしいプログラミング言語 Zen のドキュメントの一部です。筆者が Zen を使ったことはありません。)
参考: メモリ管理 | Zen Language Documentation
メモリ管理戦略は主に3通りです。
- 手動
- C言語など
- 解放忘れや二重解放の問題がある。
- ランタイムによる GC
- C#、F# など
- ランタイムがアクセス不能になったヒープメモリを自動的に解放する。(C# など)
- オブジェクトに参照カウンタを埋め込んで参照カウントGCする。(具体例は思いつかないけど、何かあったはず)
- Resource Acquisition Is Initialization (RAII)
- C++、Rust、HSP3 など
- 変数にヒープメモリを所有させ、変数がスコープから外れる際に解放する。
解放しないミローネ言語など
次の言語の構想
そういうわけで、ミローネ言語とは別に自作言語を1つ作ろうとしています。要点は以下の通り。
- 構文: (長くなったので別の記事に書く)
- 型システム: ADT + ジェネリクス + 可変性
- 中間表現: CPS
- メモリ管理: RAII + スマートポインタ
- ランタイム: なし
- C言語に変換してネイティブコンパイル
- ステージ
- パース
- 検査
- 型検査
- 可変性検査
- 変換
- クロージャ変換
- drop の挿入
- 単相化
- C言語への変換
LSP で入力補完とか DAP でデバッグとかできるようにできたらいいな、と思います。
漸進的な開発
ミローネ言語での小さな反省点をさらに1つ挙げると、C言語への変換にこだわったことです。
最終的には (あるいは、ネイティブコンパイルを目指す過程の一点では) C言語への変換 (に相当するもの) は実装することになりますが、途中の段階として C++ への変換 を挟むのも一つの手だったと思います。すなわち、単相化の実装を省略してテンプレートを使うことです。
それにより、セルフホスティングまでの時間を短縮できたはずです。筆者はミローネ言語の開発後期にずっと「ほんとうにセルフホスティングがうまくいくのか」という不安でいっぱいになっていました。セルフホスティングに支障をきたす何らかの問題が実はあって、完全に頓挫するのではないか、と。特にメモリを解放しない点にかなり不安がありました……が、実際にはメモリ使用量は余裕でした。そして、実際に問題になっているのは実行時間です。
次の言語には上記の通り RAII とジェネリクスを導入するつもりですが、コンパイル対象を一時的に C++ にすることでそのあたりの実装は省略し、まずは動くものを作る予定です。
ただセルフコンパイルするのではなく、実際にその言語を使って開発を「進めていく」ようなセルフホスティングを目指したいところです。