mincaml-rs

mincaml-rs は https://github.com/esumii/min-caml のRust版実装です．

対象言語は同一ですが，その他の互換性は一切ありません．多くの機能が異なっています．

コンパイラの構成はrustcに非常によく似たものとなっています．適宜，rustc-dev-guideの記述も参照してください．

このドキュメントについて

This document will be multilingualized using mdbook-i18n-helpers.

このサイトはmincaml-rsの公式ドキュメントです．ここでは，コンパイラのdoc commentには書ききれない，モジュール間の関係や基本となる概念，用語の説明などを書きます．

オリジナル版のドキュメントはOCamlやコンパイラについての知識が乏しくとも読めるように作られていますが，こちらはある程度の前提知識を要求してしまっています．これは意図したものではなく，表現の訂正，内容の変更などの修正案はいつでも歓迎しています．

オリジナル版のドキュメントは速攻MinCamlコンパイラ概説にあります．

このドキュメントが日本語で書かれている理由は，書いている人間の母国語が日本語であることと，講義の実施国が日本であることが主ですが，この分野で書かれた日本語のドキュメントが少ないという主観によるものもあります．

コンパイルの流れ

コンパイルの流れはオリジナルと概ね同様です．中間表現はほぼ同一で，コード生成付近は大きく異なります．

各関数の詳細は，それぞれ該当するdoc commentを参照してください．

メインのターゲットであるWebAssemblyへの出力では仮想アセンブリを経由せずに，クロージャ変換直後の中間表現からコード生成を行っています．

字句解析・構文解析

有名なパーサジェネレーターライブラリを用いて字句解析と構文解析を実装しました．現在それぞれplex, lalrpopしかメンテナンスされていませんが，今後複数のバックエンドをサポートする可能性があります．

対応予定/済のバックエンド：

構文解析の時点では，Setの左辺には任意の式が来て良いものとしています．これにより，ref <- 0のような入力に対して専用のエラーメッセージを発行できる他，パーサジェネレーターの定義を簡単に保つことができます．

.mliファイルを構文解析する機能も同じクレートに含まれています．

名前解決と型推論

名前解決と型推論を同じフェーズで行います．

名前解決

オリジナルでは，識別子が重複したら別の文字列を割り当てるという処理を行っており，これのことをα変換と呼んでいました．これによりすべての変数参照からその定義が一意に定まります．この性質の方が重要で，一般にこのプロセスは名前解決の一貫として行われます．

型推論

構文木に対する型推論はオリジナルと同一です．

構文解析時点ではSetの左辺には任意の式が来ることができましたが，これ以降でそれを禁じます．

クロージャ変換

オリジナル版ではクロージャ変換は無駄に簡潔に書かれています．失敗しうる計算と可変状態を用いてコードゴルフが行われています．

mincaml-rsでは，このプロセスの「失敗しうる」部分を事前に解析することで，他の処理と同じように記述しています．

analyze_let_rec

関数定義に対し，その関数をクロージャとして扱わなくともよいかどうかを解析します．自由変数を持たず，関数が値として使われていない場合はクロージャを形成する必要がありません．また，自由変数を持たない場合は値として使われていても関数内部では直接関数を呼び出すことができます．

オリジナル版における失敗しうる部分は実は一つしかなく，以降でこの関数が変数として扱われていないことを確かめる箇所です．これはクロージャ生成後のこの定義以降の式の自由変数を計算することで調べていますが，それはクロージャ変換前と変わらないはずです（クロージャ変換においてそれ以外のことをすべきでないからです．オリジナル版は不要なクロージャの除去までしているためクロージャ変換前後で自由変数が変わる可能性があります）．この部分を事前に計算するのがこの関数ということです．実装の詳細はdoc commentを読んでください．

オリジナル版同様，自由変数を持たないが後から変数として参照されるものは，その関数外ではクロージャとして扱う一方で，定義する関数内では直接呼び出します．

最適化の余地

• グローバル変数の導入

ir_asm_virtual : 仮想アセンブリ

mincaml-rsが導入する仮想アセンブリは，次の特徴を持つ中間表現です．rustcのmirに近い構造です．基本ブロックの表現はMLIRに似ています．

• アーキテクチャ非依存
• 静的単一代入
• 制御フローグラフ
  • 制御フローグラフへの変換
• if式と引数を持つ基本ブロック
  • phi node
  • MLIRのブロック引数

名前は，文字列ソートしたときにアセンブリの近くに来てほしかったため後置修飾になっています．それ以外の理由はありません．

現在，この形式への変換のデバッグが不十分であり，構造の一部が変更される可能性があります．

アーキテクチャ非依存

この中間表現はアーキテクチャの情報を持ちません．ターゲットのマシンのレジスタの種類・個数，ターゲットの表現によって定まるポインタサイズ，それによって導かれる型のサイズの計算などは行いません．

もっとも，アーキテクチャのことを全く知らずにコンパイラを設計することはできず，アーキテクチャ非依存と言っておきながら，ターゲットがレジスタマシンであることやメモリの扱いができるなどといったことはある程度期待しています．

静的単一代入

どの変数もその変数への代入は高々1回であるような形式です．変数がイミュータブルなことと，名前解決（オリジナルではα変換）の手続きによりK正規形の時点では静的単一代入形式になっていますが，注意を払わなければこれは容易に崩れ去ります．

なお，対象言語は可変状態の機能を持ちますが，それは変数への代入とは異なります．第4回課題など，配列への代入を変数への代入として扱う場合はこの点に注意する必要があります．

制御フローグラフ

制御フローグラフ（Control flow graph, CFG）とは，制御構造に関心のあるグラフです．詳細は教科書やWikipediaを参照してください．コンパイラ実験の後半の講義でも（当然）登場します．

ここで扱う基本ブロックの命令は，関数呼び出しを含みません．関数呼び出しはブロックの末尾のterminatorにのみ現れることができます．

オリジナル版とは異なりこの形式を採用した理由として次のようなものがあります．

• コンパイラ実験の第8,9,10回とのインテグレーション
• LLVM, MLIR等でごく一般的に用いられる形式であること

制御フローグラフへの変換

クロージャ変換後の式から制御フローグラフへの変換は複雑です．

制御フローグラフの表現で，基本ブロックはインデックスにより管理するようにしています．terminatorは基本ブロックを参照するため，基本ブロック間の依存関係に対応してterminatorの構築順を変える必要があります．

オリジナル版も最終的にはアセンブリを出力するためこの問題に遭遇していますが，ラベルを解決する作業をアセンブラに任せることで回避しています．

mincaml-rsでもラベルのような機構により対応関係を考慮し，terminatorの構築をラベルへの参照をさせることにして遅延させています．

これらの実装の詳細はir_asm_virtual/src/lowering/expr.rsを参照してください．執筆時点で致命的なバグが含まれていることもあり，一部のコードが大規模に変更される可能性があります．

このように，実装面で多少の困難がありますが，この変換で最も重要なのはif式の変換の部分です．

if式と引数を持つ基本ブロック

知っている方向けの説明：if式の変換でphi nodeをMLIRライクな表現により用いています．

コンパイラの対象言語にはif式があります．結果を返さないif式は簡単で，then式とelse式に分岐して，それぞれで合流するだけです．

では，式としての値が変数に束縛されるif式はどうでしょうか？then式とelse式それぞれで異なる式としての評価結果の値が，今後その変数を介してアクセスされます．素朴な方法としては，この変換全体が式を代入に結びつけることをしていたのを思い出して，2つの式それぞれについて各々の末尾に代入文を作ればよいと考えるかもしれません．アセンブリに変換することを考えてもこの方法は自然です．しかし，この方法では直ちに静的単一代入形式を喪ってしまいます．

phi node

phi nodeは，静的単一代入形式を維持（または獲得）するための重要な機構です．ここでは，LLVMのphi命令とそれに類する機構をphi nodeと呼んでいます．

LLVMのphi命令とは，その基本ブロックに到達する直前の基本ブロックに基づいて値を決定する命令です．例えば，if式を次のように表現できます．

br i1 %cond, label %then, label %else

then:
  %x1 = 10
  br label %merge

else:
  %x2 = 20
  br label %merge

merge:
  %x = phi i32 [ %x1, %then ], [ %x2, %else ]

代入は一度しかできないが右辺の式は中間表現を設計する側が自由に定義できることを考えると，自然なアイデアです．

このコンパイラではif式の表現にのみこの表現力を利用していますが，ループやfor文などの言語機能による分岐の表現でも利用できます．

MLIRのブロック引数

phi nodeは仮想的な命令であり，実際にアセンブリに変換する際にはそれぞれの分岐命令に遡ってその前に設置されることになります．また，phi nodeは実装上ブロックの先頭にないと面倒です．

これらのことから，分岐命令が代入先の情報を持っていると便利ですし，phi nodeを命令から追い出して，さらに基本ブロックにphiにより定義される変数の情報を持たせると便利そうです．

MLIRの基本ブロックは引数を取ります．分岐命令が代入先の変数の情報を持ち，引数は命令とは異なる形式で扱えます．重要な注意として，ブロックの引数がその変数への唯一の代入であることを忘れないでください．生存解析やデータフロー解析で必ず意識することになります．

この代入の意味論は逐次ではなく並行代入であることにも注意してください．たとえば，この代入により多変数のswapが可能です．これはアセンブリに変換するときに問題になる可能性があります．

mincaml-rsではこの形式へ変換することを念頭に置いています．

コード生成

mincaml-rsはWebAssemblyへの出力にのみ対応しています．仮想アセンブリを経由せず，クロージャ変換後の式からコード生成を行います．これはWebAssemblyが構造化されたプログラムしか扱わないためです．relooper等で検索してください．

ターゲットとしてWebAssemblyを採用した理由は次の通りです．

• 環境に依存せず実行できる
• コンパイラ実験第11,12回とのインテグレーション
• 他の講義でなかなか登場しない

codegen_wasmはwasm_encoderを直接用いるために多少のプログラミングをしていますが，WebAssemblyへのコード生成は単純です．

ライブラリ関数

レイトレーシングプログラムをコンパイルするにはライブラリ関数の実装が必要です．

.mliファイルによりライブラリのインターフェースを入力する機能が実装されています．これは名前解決と型推論に適切な情報を与えるための機構で，実際にライブラリ関数を実装するのはコンパイラのどの部分であっても構いません．オリジナル版同様，ライブラリ関数を使うファイルより前にコンパイラの引数に渡すことでmin-camlソースファイルにより実装を与えることもできます．

WebAssembly向け出力の時点で外部の関数呼び出しとして残ったものは，runtime::mini_ml_runtimeでリンクされるようになっています．runtimeクレートはそのためにあります．

レジスタ割り当て

レジスタ割り当てはこのコンパイラでは実施されません．各班のアーキテクチャをターゲットとする場合はレジスタ割り当てを実装することになる場合があります．

オリジナル版のレジスタ割り当てはif式が存在する状況で実行していることに注意してください．mincaml-rsの仮想アセンブリを元にレジスタ割り当てをする場合，構造化されていない表現が対象となるため，例えばthenとelseで同じレジスタを使うことで節約するなどといった最適化は，適切なデータフロー解析なしではできません．構造化したもののみを扱いたい場合は，クロージャ変換直後の表現から直接変換することを考えてください．

最適化の余地

オリジナル版同様，このコンパイラには最適化の余地が大いにあります．ここでその多くを説明することはしませんが，同じ教材を長い期間運用しているためによく知られた最適化が存在します．ここではそれを説明します．

グローバル変数の導入

プログラム全体で使う値を変数として管理することはよくあります．この対象言語では変数にはそれ以上の種別がないため，そのような変数もクロージャ変換では関数の持つ自由変数と思われてしまいます．

俗に言う「グローバル変数の導入」はこの問題を除去する最適化です．クロージャの生成とそれを介した呼び出しがなくなる分高速になります．

オリジナルとの対応

コマンドライン引数

モジュール

データ型の要素

初期の更新履歴

プロセッサ・コンパイラ実験両方に関係する更新履歴をまとめています．

0.2.0 - 0.2.1

• #15

  • (codegen_wasm) float型関係のコード生成部分を修正しました．ローカル変数の宣言が誤って引数を含んでいるのを修正しました．
  • (codegen_wasm) 自己参照するクロージャが自身をクロージャ経由で呼び出すことができなかったのを修正しました．
  • (ir_closure::lowering) 直接呼べることがわかっている関数が他の関数内で自由変数とみなされる問題を修正しました．
  • (ir_closure::lowering) 引数を持たないが値として使用されるためにクロージャを生成する必要がある関数を，自身の定義内部ではクロージャを経由せず呼び出すようにしました．
  • (runtime) miniMLRuntime.mliの実装に必要なランタイム実装を追加しました．

  cpuex-v1.4 のファイルはこの時点でおおよそ正常に動作することを確認しました．最適化はすべて無効化されているので，画像サイズは 64 × 64 程度にすることを推奨します．

  cargo run -- -i ./globals.ml -i ./minrt.ml -i ./miniMLRuntime.mli -o ./out.wasm
  cargo run -p runtime ./out.wasm < ./contest.sld > ./contest_64_p6.ppm
  

• #14

  • ;に関する優先順位の問題を修正しました．
  • コメントの字句解析時点でstr::trim_start_matchesではなく誤ってstr::trim_matchesを使用していたのを修正しました．
  • 型推論のパターンマッチの順序の誤りを修正しました．

• #12

  パーサーによりminrt.mlが受理できるようにしましたが，この時点では生成される構文木に誤りがありました．#14 で修正されます．

• #10

  00のようなリテラルを無効化したり，-が int と float の両方を受けつけることに対応したりしました．

  仮想アセンブリへの変換で，関数の戻り値を直接 return する式が入力された場合の処理で代入が行われていなかった問題を修正しました．仮想アセンブリへの変換には他の致命的なバグがあり，それはここでは修正されていません．

• #7

  WebAssembly のコード生成におけるクロージャの扱いをまともにしました．この変更前はクロージャを含むコードが実行できませんでした．

• #6

  .mliファイルに関する機能を実装しました．インターフェースの型付けを実装する過程でletの型付けのバグに気づいたため修正しています．この変更前まではスコープの扱いが間違っていたようです． 特に，クロージャ変換でanalyze_let_recが続く式を処理していなかった問題を修正しました． ランタイムの実装を追加してテストした結果に基づき WebAssembly のコード生成の大部分も修正されましたが，クロージャに関してはこの時点で修正されませんでした．

• #4

  仮想アセンブリのデバッグ出力をデバッグし，人間向きになりました．この修正は第 1 回の課題に影響します． 型推論における unify し忘れに対応しました．

• #3

  cargo runによりmainが選ばれるようにし，mainでは WebAssembly のバイナリ形式を出力するようにしました． WebAssembly のランタイムをワークスペースに追加しました．

0.1.0 - 0.2.0

2024 年度の講義が開始した時点で 0.2.0 に上げたため，それ以前の歴史はここには書かないでおきます．