LunarML進捗・2022年2月

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

LunarMLの進捗・2022年1月

です。

Redditで紹介された／GitHubスター数が100を超えた

Redditにはr/smlというコミュニティーがあります。Standard ML全般を扱い（意：特定の処理系専用ではない）、定期的に投稿がある唯一のSNSではないかと思います（他にあったら教えてください。「functional programming slack」の#standard-mlも見ていますが流量が少なすぎます。）。

そこで先月末、LunarMLが紹介されました。

LunarML: A Standard ML compiler that produces Lua
byu/eatonphil insml

それに伴いGitHubのスターも増えて、紹介前は50未満だったのが一気に100スターを突破しました。ありがとうございます。

https://github.com/minoki/LunarML

型推論の所要時間の短縮

ここしばらくはHaMLetを動かそうとしていたのですが、一度のコンパイルに時間がかかります。そうすると、コンパイルを試す（時間がかかる）→ライブラリーの関数が足りないと言われる→修正する→再度コンパイルを試す（時間がかかる）、のサイクルで虚無の時間が発生します。コンパイル時間の改善は急務です。

プログラムの高速化といえばプロファイリングですが、MLtonのプロファイラーを使ってもイマイチ意味のある結果は出てきませんでした。

「やはり最後に頼るのは昔からのprintfデバッグね」……じゃないですが、コンパイルの各フェーズ（字句・構文解析、型推論、コード生成）の所要時間を測ってprintするコードを埋め込んだ結果、型推論で圧倒的に長い時間が消費されていることがわかりました。

型推論の高速化については、思い当たる節があります。型推論の際は型が未知の変数（fn x => ... の x）が現れたらfreshな型変数を導入して割り当てると思いますが、あまりバカスカ型変数を導入すると管理用のテーブルが膨張して遅くなるのです（使用するデータ構造にも依るとは思いますが）。

具体的には、以前、関数適用の型推論の部分を

typeCheckExp env (App (f, x))
  = let val fnType = typeCheckExp env f
        val argType = typeCheckExp env x
        val retType = freshTyVar ()
    in unify (fnType, TyArr (argType, retType));
       retType
    end

という風に書いていたのを、「関数の型が既知の場合は新規の型変数を作らない」つまり

typeCheckExp env (App (f, x))
  = let val fnType = typeCheckExp env f
        val argType = typeCheckExp env x
        val retType = case fnType of
                          TyArr (argType', retType) => (unify (argType, argType'); retType)
                        | _ => let val retType = freshTyVar ()
                               in unify (fnType, TyArr (argType, retType));
                                   retType
                               end
    in retType
    end

という風に書き換えたところ、型推論が結構高速化した覚えがあります。

というわけで、型推論の際に使用される型変数の数をもっと削減すれば、もっと高速化するはずです。

今回採ったのは、「期待される型」を伝播させるという方法です。例えば式に型注釈 〈式〉 : IntInf.int がついていれば、式に期待される型は IntInf.int だとわかります。〈式〉が例えばオーバーロードされた数値リテラル 42 であれば、新たに型変数を導入する必要はなく、「期待される型」が整数かどうかを確かめるだけで良くなります。

また、val宣言 val 〈パターン〉 = 〈式〉 では先に右辺の型検査を行なってからそれを「期待される型」として左辺の型検査を行えば、型変数の生成を抑えることができます。

もう一つ取った方法は、型推論の仕様を変えて、曖昧な型の解決に使う文脈を小さくすることです。

Standard MLでは、リテラルや演算子のオーバーロードの解決、あるいはレコード型の解決に使う文脈は実装に委ねられています。これまでのLunarMLでは、この文脈をかなり大きく、topdecの単位で行っていました。どういうことかというと、例えば以下のコードのコンパイルが通りました：

val x = 42
val f = #foo
structure S = struct end
val y = x : IntInf.int
val z = f { foo = "foo", bar = true }

普通のSMLコンパイラーでは、 val x と val y はコア言語の宣言としては同じグループに属さないため、別々に型推論とデフォルト型への置き換えが行われます。その結果、 x の型は val x を処理した段階で Int.int に確定してしまい、その後 IntInf.int との単一化に失敗します。また、 val f と val z についても似たことが言えて、プログラム全体を見れば f の引数は { foo, bar } という形のレコードだとわかりますが、 val f の段階ではそれがわからないので曖昧なレコード型のエラーとなります。

一方、これまでのLunarMLはtopdecの単位で型推論を行うため、上記のプログラムのコンパイルを通していました。

しかし、ここまでの寛容さは普通は必要になりません。寛容さに甘えたコードをユーザーが書いても、他のSML処理系でコンパイルが通らなくて後々苦しむだけです。また、寛容さと引き換えにコンパイルが遅くなるようではユーザーにとって不利益です。

そこで、LunarMLの型推論の仕様を変えて、コア言語の宣言の単位で型推論と曖昧な型の解決を行うようにしました。

余談ですが、結果として、初心者に優しくない挙動も生まれています。以下のコードを考えます：

(* コンパイルが通らない *)
val f = #foo
val z = f { foo = 42, bar = true };

(* コンパイルが通る *)
val _ = let val f = #foo
            val z = f { foo = 42, bar = true }
        in ()
        end

同じようなval宣言を、トップレベルとlet式の内部でそれぞれ書いていますが、前者はコンパイルが通らないのに対して後者はコンパイルが通ります。

これは、前者は2つのval宣言がコア言語の宣言としては別々のグループに解釈されるのに対して、後者は一個のコア言語の宣言に属するように解釈されるからです。それぞれの構文木をS式で書けば

(* decの単位で型推論が行われる *)
(topdec (strdec (dec (val ...)))
        (strdec (dec (val ...))))

および

(* decの単位で型推論が行われる *)
(topdec (strdec (dec (val _ (let ...)))))

となるでしょう。

さらに余談ですが、MLtonは「コア言語の宣言が連続していたらマージを行う」という処理を挟んでいるので上記のコードのコンパイルが通ります。

話を戻します。これらの変更によってコンパイル時間がどのくらい縮まったのか、HaMLetを対象にして比較してみます。

当初：
- 482.04s user 4.28s system 99% cpu 8:09.14 total
「期待される型」の受け渡し：
- 250.18s user 2.53s system 99% cpu 4:14.45 total
「期待される型」の受け渡しおよび型推論の文脈の変更：
- 152.49s user 1.75s system 99% cpu 2:35.44 total

というわけで、元々8分かかっていたのが2分半まで縮まりました。「一瞬でコンパイルが終わる」という域には達していませんが、結構いい線いっているのではないでしょうか。……と思って他のコンパイラーでも試したらPoly/MLで5秒、MLtonで26秒とかでした。まだまだ改良の余地があるということでしょう。あるいは抜本的なデータ構造とアルゴリズムの変更が必要なのか。

考えてみたら、型推論の実装は割と我流な気がします。「型システム入門」での型推論アルゴリズムはかなり抽象的で、それを具体的なコードに落とす際に素人考えが入り込んでしまっている可能性があります。他の実践的なコンパイラーのコードを読んで勉強するべきなのかもしれません。あるいは単一化で躊躇なく破壊的変更を駆使すればいいのか……。

リテラルの機能追加

標準ライブラリーの Real.maxFinite やら minPos やら minNormalPos やらを記述していると、十六進浮動小数点数リテラル（0x1p1023 みたいなやつ）が欲しくなりました。ついでに、Successor MLの数値リテラル拡張も実装することにしました。

Successor MLのリテラルの話はこの間の記事

Successor MLの話

にも書いて……あんまり書いてなかったな。改めて説明します。

アンダースコアによる区切り： 0x7fff_ffff とか 3.1415_9265_3589 みたいに、数値リテラルをアンダースコアで区切ることができます。一箇所にアンダースコアは複数使えます：11__22_33____44 しかし、数字列の部分をアンダースコアで始めたり、アンダースコアで終えることはできません。ダメな例：1_.5, 3._1415, 1._E2

正規表現とBNFを混ぜたような記法を使えば、文法は

<positive-integer-constant> ::= <digit> ('_'* <digit>)*
<integer-constant> ::= '~'? <positive-integer-constant>
<hexadecimal-integer-constant> ::= '~'? '0x' <hexadecimal-digit> ('_'* <hexadecimal-digit>)*

みたいな感じになると思います。

二進整数リテラル：接頭辞 0b （wordの場合は 0wb）で二進リテラルを書けます。 0b1011_1100_0101 みたいな感じです。

十六進浮動小数点数リテラルはC言語とかIEEE 754でお馴染みのアレです。…と言いたいところですが、

接頭辞の 0x のxは小文字である必要がある
負号にはチルダを使う
指数部は省略できる
小数点の前や後を空にすることはできない

という点が要注意です。文法を書けば

<hexadecimal-integer-constant> ::= '~'? '0' 'w'? 'x' <hexadecimal-digit-sequence>
<hexadecimal-floating-point-constant> ::= '~'? '0x' <hexadecimal-digit-sequence> (<binary-exponent-part> | '.' <hexadecimal-digit-sequence> <binary-exponent-part>?)
<hexadecimal-digit-sequence> ::= <hexadecimal-digit> ('_'* <hexadecimal-digit>)*
<binary-exponent-part> ::= [pP] '~'? <digit> ('_'* <digit>)?

となります。

ちょっと違う話ですが、 1e-10 みたいに指数部の負号をハイフンマイナスで書いたら不親切なエラーが出たので、親切なエラーを出すようにしました。今のLunarMLでは

val x = 1e-10;

をコンパイルすると

/private/tmp/negative.sml:1:11: warning: use tilde (~) for negative sign
val x = 1e-10;
          ^
/private/tmp/negative.sml:1:10: warning: there should be a space between a numeric literal and an identifier
val x = 1e-10;
         ^
/private/tmp/negative.sml:1:10: unknown value name e
val x = 1e-10;
         ^

という警告およびエラーが出ます。

HaMLetが動くようになった（※Luaインタープリターの改造が必要）

足りないライブラリーを色々追加していったらHaMLetが動くようになりました。やったね。先月「LunarMLを実用的にする」と言って掲げた目標の一つは早くも達成です。

HaMLetを動作させるには、ライブラリーを追加するだけではなく、Luaコード生成の部分にも手を加える必要がありました。

以前の記事にも書きましたが、Luaで同一の関数で同時にアクティブなローカル変数の数には200という制限があります。詳しくは lparser.c の MAXVARS を見てください。

これまでのLunarMLでは適宜do-endを挿入して同時にアクティブなローカル変数の変数を削減してやるという手段を使っていたわけですが、それにも限度があります。HaMLetのようなそれなりに規模のあるプログラムではそういう小手先の工夫は焼け石に水です。

そこで、Luaコードに対して「ローカル変数の個数が一定以上になったらローカル変数の代わりにテーブルを使う」という変換を行うことにしました。

例えば、

local a0
... -- たくさんのローカル変数
local a198
do
  local b0 = 42
  local b1 = "Yes!"
  ...
end
local a199 = 1 + 1
local a200 = "foo" .. "bar"

というLuaコードが与えられたら、

local a0
... -- たくさんのローカル変数
local a198
do
  local LOCALS = {}
  LOCALS[1] = 42 -- b0の代わりにLOCALS[1]を使う
  LOCALS[2] = "Yes!" -- b1の代わりにLOCALS[2]を使う
end
local LOCALS = {}
LOCALS[1] = 1 + 1 -- a199の代わりにLOCALS[1]を使う
LOCALS[2] = "foo" .. "bar" -- a200の代わりにLOCALS[2]を使う

というコードに変換します。

関係ない値を同じテーブルに放り込んだらGCに関して本来関係ない値が関連づけられて悪影響がある可能性があります。が、仕方がない。

別の制限として、LuaパーサーのCスタックの使用に関する制限があります。Luaは手書きの温かみある再帰下降パーサーを使っているわけですが、その際に律儀に再帰の深さを確認して段数が200（これは LUAI_MAXCCALLS というマクロで調整できます）を超えるとエラーを投げるのです。Lua 5.3では Too many C levels (limit is 200) というメッセージが、Lua 5.4では C stack overflow というメッセージが出ますが、同じことです。

この制限を回避するのは大変そうだったので、当面は独自にビルドしたLua処理系を使ってHaMLetを試すことにしました。LuaのMakefileの MYCFLAGS のところに -DLUAI_MAXCCALLS=500 とでも書き込んでmakeすればOKです。

こうして独自にビルドしたLuaを使うことで、HaMLetが無事動作しました。やったね。

【追記】動かす際にluafilesystemも必要になります。

次にやりたいこと：JavaScriptバックエンド

最近、「WebGLを使って何かしたい」という気持ちが高まっています。どうせなら関数型言語からWebGLを叩きたいところですが、GHCJSは環境構築に難がある（Nixとか使えばいいんでしょうか）のでアレです。PureScriptも良い選択肢だと思いますが最近触っていないので再学習のコストがアレです。そうだ、ここにJavaScriptバックエンドを実装する予定の関数型言語処理系があるじゃないか！

ということでJavaScriptバックエンドに本格的に着手しようと思います。動機は今書いたやつの他に、「Luaは各種制限があって所詮オモチャなのではないか、JavaScriptの方が大規模プログラムに耐えるまともな言語なのではないか」という疑念が湧いてきたというのもあります。

JavaScriptバックエンドの考察は以前にも行いました。

LunarMLの進捗と妄想

その時と比べて時間が経って考えが深化したと思います。要点をまとめると、

末尾呼び出し最適化：トランポリンを使う。末尾再帰のループへの変換は後回しにする。
文字列：8ビット文字列 String.string には Uint8Array を使う。JavaScriptの16ビット文字列は WideString.string として扱えるようにする。8ビット文字列をJavaScriptの文字列のサブセットとして実装する手もあるが、混同を避けるためにあえて Uint8Array を使う。パフォーマンスが悪かったら考え直す。
JavaScriptの世界へのFFI：Luaの場合と同じように、「JavaScriptの世界へのAPI」を用意する。ただ、ES5の範囲だと val new : (* constructor *) value * (* arguments *) value vector -> value の実装に eval が必要になる。ES2015ならspreadか Reflect.construct が使えるのでES2015を要求することにする。
例外型 exn にはクラスっぽい表現を使う。コンストラクターには new MyExn(arg) を、パターンマッチには instanceof を使う。
タプルのインデックスは、SMLは1始まりだが、JavaScriptの世界では0始まり（キーが連続した整数のみの場合は配列）にする。
標準ライブラリー実装はJavaScript用のものを作り直す。地味にこれが一番きついかもしれない。「他のバックエンドと共用できる部分」をうまく括り出すのがコツか。

となります。

末尾呼び出し最適化については、MLの型 arg -> result のJavaScriptにおける表現を

type Trampoline<Result> = [true, Result] | exists X. [false, MLFunction<Result, X>, X]
interface MLFunction<Result, Arg> {
    (arg: Arg): Result;
    _MLTAIL_?: (arg: Arg) => Trampoline<R>;
}
// MLで実装された関数には専用の呼び出し規約に対応した _MLTAIL_ プロパティーが生えている

みたいな感じにします。

JavaScriptには十六進浮動小数点数リテラルがないので、まずは「ソース中の十六進浮動小数点数リテラルを十進表記に変換する」コードを書くところから始めようと思います。