LunarMLの近況／中間言語に型をつける

私が作っているStandard MLコンパイラー、LunarMLの近況報告記事です。LunarMLに関する直近の記事は

でした。

400スター

GitHubスター数が400に到達しました。ありがとうございます（執筆時点では402に増えています）。まだスターをつけていない方は https://github.com/minoki/LunarML でスターをつけることができます。

スターが350に到達したのは2024年10月、300に到達したのは2024年5月のことだったようです。

（本プロジェクト限定というわけではありませんが）GitHub Sponsorsにも触れておくと、現在は @toyboot4e さんと @kevin-kmetz さんにスポンサーしていただいています。ありがとうございます。

https://github.com/sponsors/minoki

中間言語に型をつけたい：型をつける動機付け

JavaScript連携の記事で、

JavaScriptの Promise の then はコールバックが Promise（正確にはThenable）を返したら更にそれを待ち受ける挙動をします。モナドのbindみたいな感じです。この仕様があると ('a promise) promise みたいな型をいい感じに扱えないので、Standard MLの世界のコードが Promise の中身として Promise を返そうとした場合はラッパーを噛ませるようにします。

と書きました。「Promise の中身として Promise （より正確には Thenable）を返そうとした場合はラッパーを噛ませる」の部分をコードで説明すると、次のような関数 wrapThenable, unwrapThenable の呼び出しを適宜噛ませる形になります：

function ThenableWrapper(x) {
    this.payload = x;
}
function wrapThenable(x) {
    if (typeof x === "object" && typeof x.then !== "undefined") {
        return new ThenableWrapper(x);
    } else {
        return x;
    }
}
function unwrapThenable(x) {
    if (x instanceof ThenableWrapper) {
        return x.payload;
    } else {
        return x;
    }
}

JavaScriptの通常の Promise との相互運用を可能にするため、値が Thenable ではない場合は元の値を活用します。

しかし、Promise の操作をするたびに必ず wrapThenable の呼び出しを挟むというのはダサいです。値の型が string や int など、明らかに Thenable ではないことがわかっている場合は、呼び出しを省略したいです。そのためには、最適化が進んだ段階でもコードの型情報を保持しておくことが必要です（インライン化によって型が判明する状況を考慮する）。現状のLunarMLでは最適化はCPS中間言語に対して行っているので、CPS中間言語を型付きにすることが必要です。

型情報の別の用例を挙げます。次のコードを考えます：

(* val foo : unit -> unit
   val bar : unit -> string *)
val x : unit = foo ()
val _ = bar x

x は unit 型の変数で、情報を保持していません。こんなコードを書く人はいないと思われるかもしれませんが、最適化の結果としてこういうコードが現れることは十分にあり得ます。

この場合、ソース中の x という変数を出力コードに反映させるのは無駄です。特に、Luaではローカル変数は貴重な資源なので、節約したいです。そこで、「型が unit の変数の使用は値 () で置き換える」という変換が考えられます。

そんな感じで、中間言語、特にCPS中間言語に型がついていると便利そうです。

中間言語に型をつけたい：作業

LunarMLの中間言語は

  • ソース（Standard ML）→（いくつかの前処理と型検査）
  • →型付き中間言語→（モジュールの脱糖、オーバーロードとequality typeの脱糖）
  • →System Fωライクな中間言語→（パターンマッチの脱糖）
  • →System Fωライクな中間言語→（CPS変換）
  • →CPS中間言語→（各種最適化）
  • →CPS中間言語→（ネストされた式の回復）
  • →ネストした式のある中間言語→（変換）
  • →LuaやJavaScriptのコード→（変換）
  • →最終的なLuaやJavaScriptのコード

という流れになっています。

従来は、System Fωライクな中間言語までは型がついていて、CPS中間言語には型がないという状況でした。3月ごろに、System Fωライクな中間言語の型検査器を実装しました。

今回、CPS中間言語を型付きにして、型検査器も実装しました。

型付きのCPS変換はしっくりくる先行研究が少なくて、なかなか難航しました。LunarMLの型付きCPSメモにいくつかメモりましたが。

最終的には、「型抽象と型適用は、通常の関数と関数適用と同様に扱う（ただしフラグをつけて区別できるようにする）」「最適化をある程度かけた段階で、多相型を消去する。完全に型を消去するのではなく、漸進的型付けのAnyのような感じで置き換える。その後再び最適化をかける」という形にしました。

最初は中間言語に対する型検査器はなくても良いかなと思っていましたが、型に関するバグがあったときに型検査器がないとエスパーでデバッグする羽目になり、しんどかったです。なので、結局型検査器を実装しました。実装したらしたで無限にバグが見つかってしんどいことになりましたが。

型周りのバグの発見には、過去に書いたテストが役に立ちました。テストは資産です。

悪いニュースとして、CPS中間言語に型をつけたことで、コンパイルが遅くなったり、メモリ使用量が増大したりしています。中間言語の型検査をやめれば時間の増加は軽減されると思いますが、テスト時はしっかり検査したいので、テストの所要時間は減らせなさそうです。

ML Family Workshop

今年のICFPはシンガポールでの開催で、それと併設で10月16日にML Family Workshopというのが開催されます。学会誌なんかは出ない、インフォーマルな集まりのようです。

このML Family WorkshopにLunarMLの話を応募したところ、通りました。というわけで、行ってきます。

このところLunarMLの作業を頑張っているのは、ML Family Workshopで話せる内容を少しでも増やしたいという気持ちからです。ですがCPS中間言語の型付けに時間を使いすぎた感があるので、そろそろ資料作成と発表練習をしないといけません。

バージョン0.3.0

ML Family Workshopの前になるか後になるかは不明ですが、そろそろ新しいバージョンとしてリリースしても良いかもしれないと思っています。ユーザー視点ではJavaScript周り（Promise連携とか）が新機能になるかと思います。GitHub Actionsでビルドする仕組みを整えたので、MLtonでビルドしたバイナリーも配布できると思います。

Spread the love