コンパイラの実装言語にあると良い機能

コンパイラ

構造体とか配列とかどんな言語にも大体あるものは除きます。あくまで私の主観です。

  1. lex/yacc/gperfなどのツール
    • 特にyaccがないと複雑な言語のパースは大変。
  2. バリアント
    • 構文木の表現に一番適していると思う。
  3. パターンマッチ
    • コンパイラ内部はパターンマッチだらけ。
    • テーブルジャンプを用いた高速な実装ならなおよし。
  4. ハッシュテーブル
    • 名前の管理。必須。
  5. バイナリ処理
    • バイナリファイル触るならもちろん。
  6. ビットベクトル・ビット行列
    • フロー解析で必須。フロー解析に基づく最適化をするなら。
    • 高速な集合演算があると良い。
  7. SetやDisjoint Setなどのコンテナ
    • 最適化の実装で使う。Disjoint Setはエイリアス解析で主に使う。もしやるなら。
  8. グラフ
    • 主にフローグラフ。値グラフでも使ったりする。
    • フローグラフはまばらなので基本的にAdjacency List表現。
    • Predecessor/Successorをイテレートする処理が多い。
    • アルゴリズムはDFSなどの探索系が主。SSA変換では強連結成分の計算も行う。
  9. GC
    • コンパイラはメモリを沢山必要とする。
    • 最適化で構文木を頻繁に書き換える。
    • AST→HIR→MIR→LIRと複数の中間表現を利用する。
    • 変数の数がnとするとフロー解析ではO(n^2)程度のメモリが必要になったりする。コンパイラ内部でテンポラリ変数を沢山生成するので、ここの負荷が高い。
  10. Pretty Printer
    • 地味に重要。必須。
    • 中間言語を見やすい形に出力する。
    • これがないとデバッグが大変。
  11. 例外機構
    • 入り組んでるので、あった方が楽かも。
  12. テストツール
    • ないよりはあった方がいい。

大体こんなところだと思います。なければ自分で作る必要があります。
おまけ：あまりいらない機能

  1. オブジェクト指向
    • 内部で使うコンテナを作るくらいの目的でしか使わない
    • 構文木をクラスと継承で実装するのは面倒
  2. 遅延評価
    • 構文木のDFSとかは綺麗に書けていいんだけど、コンパイラ全体からすると微々たる貢献
    • ノード沢山作るのでメモリがきつい
    • フロー解析とかは解が収束するまでループ回すんだけど、ちゃんと正格評価しないとサンクが膨れ上がって遅くなる
  3. 参照透過性
    • 破壊的代入沢山使います
  4. クロージャとか継続とか
    • あってうれしい場面は少ない

具体的な言語について。自分がコンパイラ実装に使ったことあるものに関して。

  • C/C++
    • 速度面で信頼できる事が大きい。
    • GCを作るのが大変かも。GCなしでやるのはもっと大変。
    • 構文木はunionで作って、タグ埋め込んで、switchでパターンマッチ
  • Java
    • 構文木作るのが大変。
    • なぜなら1ノードタイプにつき1クラス必要で、Javaでは1クラスにつき1ファイル必要。
    • AST一つに2桁のファイル数が必要になったりする。
  • Haskell
    • パターンマッチが非常に使いやすい。
    • コンパイラはメモリを沢山使うのでつらい。
    • フロー解析に基づく最適化はあきらめた方が良い。
    • 破壊的代入を沢山使うバックエンドは書きにくいし遅い。
    • alex/happyは使いやすい。
    • HughesPJ(pretty printer)が非常に使いやすい。
  • OCaml
    • 速度面・機能面共に最もバランスが良いと思う
    • ocamlyacc/ocamllex使いやすい
    • Format(pretty printer)はちょっと奇妙だし使いにくいと思う。面白いけど。
  • Ruby
  • アセンブリ
    • 実は、機能が貧弱な分欲張らないのでサクサク作れてバグも全然出なかった。
    • もちろん大きなコンパイラは無理。