LunarML進捗・2022年6月

月刊LunarML進捗報告です。前回は

あたりです。

次の目標:セルフホスト

先月はLunarMLに限定継続を実装しました。大きな機能を実装したということで、一旦立ち止まって次に何をやるべきか考えてみます。

年始に掲げた目標は

  • 標準ライブラリーを整備する
  • 自分自身をコンパイルできるようにする
  • Standard MLで書かれた他の処理系をコンパイルできるようにする
    • →HaMLetをコンパイルできた
  • REPLとインタープリターを実装する
  • JavaScriptバックエンドを作る
    • →作った
  • Webで試せるようにする

でした。

JavaScriptバックエンドが一段落したということで、今度はセルフホストをやっていきたいと思います。(本当は「CPSをやると関数のネストが深くなりすぎてJavaScriptパーサーが死ぬ」という問題がありますが、この解決は後回しにします。)

smlnj-libとmlyacc-lib

LunarMLの実装では、SML/NJに付属するライブラリーであるsmlnj-libとmlyacc-libを使っています。前者は関数型データ構造(RedBlackSetFn/RedBlackMapFn)のために利用しており、後者はml-yaccを使うために必要です。これらはMLtonでも使えます。

LunarMLでLunarML自身をコンパイルするには、「smlnj-libとmlyacc-libをLunarMLでも使えるようにする」または「smlnj-libとmlyacc-libへの依存を解消する」のいずれかが必要です。

LunarMLだけでなく、Standard MLで書かれた他のプログラムからもsmlnj-libやmlyacc-libを使いたいことがあるかもしれません。そうすると、smlnj-libやmlyacc-libをLunarMLで使えるようにするのが長期的には良さそうだと考えられます。

smlnj-libとmlyacc-libの配布元はSML/NJのWebサイトです。tarballになっているのでダウンロードすれば良いのですが、いくつか問題があります。

  • ダウンロードURLがHTTPSじゃない
    • →ダウンロード後にsha256sumを検証することにします。
  • ビルドシステムがCompilation Manager向けに書かれており、MLBファイルが付属しない
    • →Compilation Managerファイルを解釈してMLBファイルを生成するプログラムを用意します。これは非自明な作業です(後述)。
  • SML/NJ特有の機能を使っている(言語機能やSMLofNJモジュール)
    • →パッチを当てたり、コンパイル対象から外したりします。

MLtonではgitリポジトリー中にtarballを含めているようです。LunarMLでは今のところtarballは含めずにcurlで取ってくる形式にしていますが、ユーザーが増えてくると配布元に迷惑になるかもしれないのでそのうちtarballを含めるようにするかもしれません。

smlnj-libを動かすためには更なる標準ライブラリーの拡充が必要でした。というかまだ終わっておらず、面倒になってファイルをいくつかコメントアウトしました。LunarMLで必要なのはRedBlackSetFn/RedBlackMapFnだけなので……。

SML/NJのCompilation Manager

SML/NJのCompilation Managerは複数のSMLファイルをまとめてライブラリー・プログラムを構成するための方法で、.cmファイルにファイルのリスト等を記述します。その際に.cmファイルにファイルを記述する順番は任意で、CMが自動でファイル間の依存関係を見つけ出してコンパイルします。そのため、ファイルのトップレベルはモジュールレベルの何か(structure / signature / functor)である必要があります。

一方、MLBは順序を明示的にユーザーが指定する方式を取ります。つまり、.cmファイルを.mlbファイルに変換するには、.smlファイルの中身を見て依存関係を把握し、ファイルを並び替える(トポロジカルソート)という作業が必要です。

MLtonではこの辺をSML/NJのCMを再利用することでやっているようですが、手元の作業環境(AArch64 Darwin)ではSML/NJはまだ使えないので、依存関係を把握するプログラムを自前で書きました。地味な作業でした。

型推論の高速化

コンパイル対象の規模が大きくなってくると、コンパイルにかかる時間が無視できなくなってきます。HaMLetは171秒、LunarML(String.isSuffixに差し掛かってコンパイルエラーが出るまで)は128秒かかります。

2分かけてコンパイルする→標準ライブラリーの関数が足りないのでエラーが出る→修正する→2分かけてコンパイルする……

というサイクルをやっていたらいくら時間と忍耐力があっても足りないので、改めて型推論の高速化に取り組むことにしました(参考:前回型推論の高速化に取り組んだ時の記事(2月))。今度こそ

をベースにやっていきます。

ですが、その前にリファクタリングを、と思ってリファクタリングしてたらHaMLetのコンパイルが6.4秒、LunarML(途中まで)のコンパイルが6.2秒まで縮みました。20倍以上の高速化!?詳しいメカニズムは謎ですが、元々のアルゴリズムがよっぽどアホだったのでしょう。

気を取り直して、リンク先のsound_eager相当を実装しました。ただ、参考にしたやつは純粋なラムダ計算なのに対し、LunarMLは

  • value restriction(よくみたらリンク先のページの最後に言及がありますね)
  • 多相にできない型制約(レコード関連、オーバーロード関連)

があるので、その辺の調整は必要でした。

また、レコード拡張の仕組みが従来(参考:実装時の記事(1月))のように型制約でゴニョゴニョやっていたのではうまくいかないことがわかったので、よりrow polymorphism的…というか「レコード拡張」を表す型を導入して制約の部分を簡素化しました。レコード多相ではないし列変数を導入したわけではないのでrow polymorphismとは呼べませんが。

その結果、HaMLetのコンパイル時間は3.4秒、LunarML(途中まで)の時間は1.36秒まで縮まりました。

VM / バイトコード

LuaバックエンドでHaMLetをコンパイルしたらパーサーの深さ制限に引っかかったり、JS-CPSバックエンドでHaMLetをコンパイルしたらやはりパーサーの深さ制限に引っかかったりしました。

これらの回避方法はありますが、スクリプト言語を出力するという形ではターゲット言語のパーサーを考慮に入れないといけないのがしんどいです。

LunarMLでもREPLやインタープリターを実装したいと思っており、その場合はASTをトラバースするか、自前のバイトコードにコンパイルして実行することになります。

なので、VM/バイトコードターゲットの方に少しずつ気持ちが傾いています。

関数型言語用のVMはどういうのがいいのでしょうか。最近出たコンパイラーの本はSECD機械をターゲットにしていました。あるいは既存の関数型言語処理系の実装を見るのも良さそうです。知っている範囲では

  • Poly/ML
  • OCaml
  • GHC

などがバイトコードバックエンドを持っています。あとはScheme界隈を覗くのも良いかもしれません。

身近なVMとしてはLua VMもありますが、関数型言語にどの程度適しているかはよくわかりません。制限もきついし。

妄想:JVM/共通言語ランタイム

スクリプト言語や独自VMだけでなく、JVMや C#用VM 共通言語基盤をターゲットとするのも面白そうです。一方、WebAssemblyは現状GCがないので厳しそうです。

JVM/共通言語ナンチャラについて妄想するのはタダなので妄想しておきます。JVMをターゲットとするMLjや共通言語ナンチャラをターゲットとするSML.NETは、ターゲットの型システムと連携できるようにStandard MLを拡張しています。LunarMLでそういうのをターゲットとすることになった時にも言語拡張があったほうが良いのかもしれません。

重大な問題として、JVMや共通型システムには高階多相がありません。どこで困るかというと、LunarMLのfunctorの実装方法がターゲットに高階多相がある(または型消去できる)ことを期待しているのです。最悪、全部object型にしてしまえばいいのですが、ボックス化とかの観点からそれはできれば避けたいです。JVMやCILをターゲットとする場合はfunctorはstatic interpretationで消去することになるのかなあ、と思います。

一方でスクリプト言語ターゲットに関しては将来的に第一級モジュールを入れたいと考えています。色々思想の違いがあるので、LunarMLという単一のプロジェクトでスクリプト言語とJVM/CILの両方をターゲットにするのは無理がある気もします。

まとめ

今月は(MinCamlもやりましたが、)LunarMLをセルフホストするために色々頑張りました。あとは標準ライブラリーをひたすら充実させていけばセルフホストできるはずです(出力の構文木の深さから目を逸らしつつ)。

LunarMLはGitHubで開発しています。スターを頂けると励みになります。


LunarML進捗・2022年6月」への2件のフィードバック

  1. ピンバック: LunarMLが自身をコンパイルできるようになった | 雑記帳

  2. ピンバック: LunarML進捗・2022年7月:LuaJIT対応など | 雑記帳

コメントを残す

メールアドレスが公開されることはありません。