LunarMLの進捗2022

この記事では、私が数年前から作っているStandard ML処理系「LunarML」の今年の進捗を振り返ります。

これまでの進捗報告記事は以下です：

目次

直近の進捗

月例の進捗報告記事は7月を最後に書いていませんでした。その分の進捗報告を書きます。

VMバックエンドの準備

VMバックエンドを実装するため、中間表現に手を加えました。VMバックエンドではレコードをタプルに脱糖します。レコードフィールドに対応するタプルの中の位置（インデックス）はそのレコードの全てのフィールドがわかってないと決定しないため、レコードの射影（フィールドの取得）に対して全てのフィールドの集合を持たせるようにしました。

ただ、新機能であるVMを実装するよりも先に既存のバックエンドの体裁を整えてリリースするべきではないかという気がしてきたので、VMの作業はしばらく棚上げしています。

浮動小数点数の関数

浮動小数点数周りの細々した関数を実装しました。具体的には以下です：

  • Real.radix
    • 2で決め打ちです。
  • Real.precision
    • 53で決め打ちです。
  • Real.min
    • 0の符号もきちんと扱います。
  • Real.max
    • 0の符号もきちんと扱います。
  • Real.toManExp
  • Real.fromManExp
  • Real.split
  • Real.realMod
  • Real.rem
  • Real.toLargeInt
  • Real.fromLargeInt
  • Real.toLarge
  • Real.fromLarge

Real structureの残りは、 structure Math, *+, *-, nextAfter, toDecimal, fromDecimal となります。

サブコマンド

コマンドライン引数の取り方を変えて、サブコマンドを取るようにしました。コンパイルするには

$ lunarml compile hello.sml

という風に compile サブコマンドを使います。いずれ run や repl などのサブコマンドも実装していきたいです。

ディレクトリー構成

ディレクトリー構成を変え、 lunarml コマンドは bin/ 以下に、その他のファイルは lib/ 以下に置くようにしました。

Luaでのワンショット限定継続

以前HaMLetを動かすために作った「LuaのpcallでCスタックオーバーフローを起こさない」バックエンドを改造して、ワンショット限定継続を使えるようにしました。

一応解説っぽいものを書きました：

CPSによる限定継続と例外

JS-CPSバックエンドで限定継続と例外の食い合わせが良くなかったのを改善しました。

限定継続の参考にしたMonadic Frameworkの論文は言語組み込みの例外を扱っておらず、CPSによる例外の参考にしたCompiling with Continuations, Continuedでは限定継続を扱っていなかったので、CPSによる限定継続と例外の組み合わせ方は自分で考える必要がありました。

限定継続のインターフェース

限定継続関連の関数と型の名前を少し変えました。今はこんな感じです：

structure LunarML : sig
  ...
  structure DelimCont : sig
    type 'a prompt_tag
    type ('a,'b) subcont
    val supportsMultishot : bool
    val newPromptTag : unit -> 'a prompt_tag
    val pushPrompt : 'a prompt_tag * (unit -> 'a) -> 'a
    val withSubCont : 'b prompt_tag * (('a,'b) subcont -> 'b) -> 'a
    val pushSubCont : ('a,'b) subcont * (unit -> 'a) -> 'b
    val shift : 'a prompt_tag * (('b -> 'a) -> 'a) -> 'b
    val control : 'a prompt_tag * (('b -> 'a) -> 'a) -> 'b
    val abort : 'a prompt_tag * 'a -> 'b
    val topLevel : unit prompt_tag (* JS-CPS backend only *)
  end
  ...
end

prompt 型の名前を prompt_tag に変えたのと、 supportsMultishot 変数が増えました。

topLevel はどっちかというとランタイムの話なので、別のモジュールに移すべきかもしれません。

固定長整数型

Int8 / Int16 / Int32 / Int64 を実装しました。

Lua 5.3以降はデフォルトで64ビット整数が使えるので良いのですが（逆に、Luaのビルド時設定がいじられて整数が32ビットの場合のことは考えていません）、LuaJITやJavaScriptはデフォルトの数値型が倍精度浮動小数点数なので困ります。LuaJITではFFI用の int64_t を使って、JavaScriptではBigIntのサブセットとして64ビット整数を実現するようにしました。

このほか、JavaScriptやLuaJITの、倍精度浮動小数点数で表現される整数（いわゆるsafe integer）との相互運用のために、 Int54 を実装するかもしれません。精度53ビットと符号1ビットで54ビットです。範囲を \([-2^{53},2^{53}-1]\) とするとsafe integerの範囲からは微妙にはみ出るので四則演算の実装には注意が必要です。

JavaScriptのArrayは長さ \(2^{32}-1\) までは扱えることになっていますし、TypedArrayだとそれ以上の長さを扱えるので、そのうちデフォルトの int を54ビットにするかもしれません。

最適化

CPS中間表現に対して一部の最適化を実装しました。今のところこれはJS-CPSバックエンドのみに関係します。

ですが、最終的にCPSしないバックエンドでも中間コードは（ANFとかではなく）CPSにする方向に傾いています。そのため、CPSのcontinuationはsecond-classにしようと思っています。LuaやJavaScriptの生成時にはsecond-class continuation / join pointはなるべく関数を作らないようにして、LuaのgotoやJavaScriptのlabel付きbreakにコンパイルしたいです。

JS-CPSバックエンドであっても、エスケープしない継続（条件分岐やループのみで使われる継続）はジャンプやwhileにコンパイルできるとよさそうです。

今年の進捗まとめ

今年やったことを列挙していきます。

  • リテラルのオーバーロード（1月）
  • record extension / update（1月）
  • 型推論の改良（2月、6月）
  • リテラルの改良（2月）
  • HaMLetが動くようになった（2月）
  • JavaScriptバックエンド（4月）
  • 限定継続（5月〜）
  • .cmの取り込み（6月）
  • 自身のコンパイル（7月）
  • LuaJIT対応（7月）
  • VMの調査・準備（8月以降）

今年の前半はわかりやすい進捗が出ていました。一方、今年の後半はVMの調査と準備をやっていた関係もあり、月例の記事を書くほどの目立つ進捗が出ていません。

1月に掲げた目標を振り返る

1月の記事では2022年の目標として「LunarMLを実用的な処理系にする」ことを掲げました。具体的には、以下の目標です：

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

これらがどの程度達成できたのか、振り返っていきます。

標準ライブラリーの整備：整備は進めています（直近では Real structureの細々した関数や Int{8,16,32,64} の実装を進めました）が、未実装のものも多く残っています。SMLUnitなどが動作するレベルには達していません。

自分自身のコンパイル：自分自身をコンパイルできるようになりました。達成です。

HaMLetの動作：動作しました。達成です。

REPLとインタープリター：未実装です。

JavaScriptバックエンド：作りましたが、まだNode.jsだけしか考慮しておらず、Webでの動作は未対応です。

……というわけで、1年あっても全ての目標を達成することは難しいことがわかりました。

あと、「実用的にする」と言っているのに「リリースする」が目標に入っていなかったことに最近気づきました。

今後の目標

今後（あえて来年とは言わない）の目標を列挙していきます。

  • リリースする
  • インタープリターの実装（その場で実行できるようにする）
  • REPLの実装
  • JavaScriptバックエンド：Web対応
  • Webで試せるようにする
  • おしゃれなロゴ
  • 最適化の実装
  • パターンマッチ
  • PHPバックエンド
  • LunarMLを利用したアプリケーションを書く

順に見ていきます。

リリースする

リリースするのは大事です。GitHubで永遠に開発中、アルファ版のままでは使ってくれる人は極めて少ないでしょう。ある程度使い物になることを宣言するためにどこかでリリースを出さなくてはなりません。

まあ下手にバズってGitHubにIssueやPRがいっぱい立って対応に追われると嫌だなあ、的な気持ちは若干あります。

インタープリターの実装

現在はコンパイルしてからLuaやNode.jsで生成物を実行、という感じでやっています。それに対して、MLのプログラムを一発で実行するサブコマンドがあると良さそうです。 lunarml run foo.sml という感じで。実行には独自のVMを使いたいです。

REPLの実装

REPLがあると良いです。実行には独自のVMを使いたいです。

あるいは、最近はJupyter Notebookに対応するのがクールなのでしょうか。

Web対応

Web向けのJavaScriptを出力できるようにしたいです。

Webブラウザーの上でできることは限られるので、標準ライブラリーが制限されます。あるいは、独自のファイルシステムとか標準入出力の仕組みを実装するか……。

Webで試せるようにする

Webで試せるとインストール不要なので便利そうです。

おしゃれなロゴ

あるといいですね。

最適化の実装

LunarMLは出力コードが読めてしまうので、あまり下手なコードを出力していると「手書きした方がマシでは」と思われてしまう可能性があります。なので、最適化をちゃんとしたいです。

特に、Hello worldの出力コードの行数をもっと減らしたいです。優れたdead code eliminationのために簡易的なエフェクト解析が必要になるかもしれません。

パターンマッチ

パターンマッチは現在はifの羅列にコンパイルしているので、もうちょっと高度なコンパイル手法を採用したいです。

それから、Successor MLのパターンマッチ関連機能も実装したいです。

PHPバックエンド

Webサーバー側のプログラムを書くうえでPHPは割と特権的な位置にある言語だと思います（特にレンタルサーバー上）。mod_phpみたいなやつがあったり。あと、WordPressのプラグインを書けたりします。なので、PHPを出力できると良いかもしれません。

PHPは整数演算のオーバーフロー時にfloatに変換されるので、Wordのwrap aroundする演算を提供するのが面倒そうです。

アプリケーションを書く

実用志向のコンパイラーを作るのは実用的なプログラムを動かしたいからです。なので、Standard MLで何らかのアプリケーションを書きたいです。

読んで頂いてありがとうございました。今年の残りと、来年もLunarMLをよろしくお願いします。

Spread the love

「LunarMLの進捗2022」への2件のフィードバック

  1. ピンバック: 2022年振り返りと来年に向けて | 雑記帳

  2. ピンバック: LunarML進捗・2023年1月 | 雑記帳

コメントは停止中です。