LunarML進捗・2023年3月

引き続きLunarMLの開発をやっています。

前回の記事：

LunarML進捗・2023年1月

最近書いた関連記事：

Standard MLに対する拡張のアイディア

進捗

Time/Timerの実装

LunarMLのコンパイルのどのステップで時間がかかっているのか調べるために、所要時間を表示するモードを実装しました。Standard MLで時間を扱うには Time structureを、CPU時間を計測するには Timer structureを使います。

LunarMLは「自分自身をコンパイルできる」ことを方針としているので、標準ライブラリーに Time と Timer を実装しました。

Standard MLの Timer ではGC時間を調べる関数も用意することになっていますが、LuaやJavaScriptのGC時間を調べる簡単な方法はなさそうなので、GC時間は常に0としています。

Int54の実装

JavaScriptやLuaJIT（というか5.2までのLua）では倍精度浮動小数点数を標準的な数値型としています。この他にJavaScriptにはBigIntが、LuaJITには(u)int64_tがあり、LunarMLではそれらを使って Int64 structureを提供していますが、標準的な数値型ではありません。

これまでのLunarMLではJavaScriptやLuaJITターゲットでは倍精度浮動小数点数の部分集合として32ビット整数を提供してきました。しかし、時間やファイルサイズなど、32ビットでは不足する場合があります。組み込み先のAPIがこれらの量を倍精度浮動小数点数で表現される整数として扱っている場合、LunarMLにもそれに相当する整数型があった方が便利そうです。

倍精度浮動小数点数では\(-2^{53}\)以上\(2^{53}\)以下の整数を正確に表現できます。Standard MLの IntN structureは\(-2^{n-1}\)以上\(2^{n-1}-1\)以下の範囲を想定しているので、\(n=54\)とした Int54 structureを提供するのが適当です。

というわけで Int54 structureを実装しました。互換性のため、（64ビット整数を日常的に使い Int54 の必要性が薄い）Lua 5.3ターゲットでも Int64 の部分集合として Int54 を提供しています。

Standard MLの配列の添字やサイズは int 型で、JavaScriptで使える配列のサイズは\(2^{31}\)を超える場合があるので、JavaScriptの配列をフルに扱えるようにするには標準の int も54ビットにした方がいいかもしれません。

Intのテストの強化

Int54 を追加したついでに、整数型周りのテストを強化しました。バグがいくつか見つかりました。

常にCPS中間表現を利用する

CPS中間表現を経由してdirect styleなLuaコードを出力するコード生成器の完成度が上がってきたので、従来のコード生成器を廃して常にCPS中間表現を使うようにしました。

JavaScriptでも同様に、JS-CPSバックエンドのコード生成器でdirect styleなJSコードも出力できるようにしました。

setGlobal/setFieldを追加

出力するLuaやJavaScriptコードからグローバル変数を設定したり、フィールドの設定ができると便利そうだと思ったので、setGlobal と setField を追加しました。

IntInfの高速化（定数倍）

Lua向けの IntInf の実装（Standard MLで書かれている）ではビットシフトをちょいちょい使っていますが、Standard MLのビットシフトとLuaやJavaScriptのビットシフトは微妙にセマンティクスが違っていたりします。

具体的には、シフト幅が整数型の幅を超えていた場合の挙動が違います。そのため、Standard MLのビットシフトを実装する際にはシフト幅のチェックが必要になります。

ですが、IntInf の実装で使うビットシフトは基本的に整数型の幅未満のシフトです。なので、そういうチェックは無駄です。

というわけで、「シフト幅が整数型の幅を超えないことを前提とするシフト演算」を追加して、より効率的なコードが生成されるようにしました。

JS-CPSバックエンドの例外の扱い方を変更

1月の記事にチラッと書いたように、これまではJS-CPSバックエンドで一般のJavaScript関数を呼び出す際にいちいちtry-catchで囲うコードを生成していました。

これは見た目が良くないので、トランポリン（末尾再帰の実装に使うやつ）の側にtry-catchを書いて、例外ハンドラーはグローバル変数で設定するようにしました。

細かいtry-catchがなくなるので高速化するかと思いましたが、速度的には大きな変化はありませんでした。

CPS中間表現の改造

LuaJITバックエンドでもCPSを経由するようにしたところ、「LuaJIT向けにコンパイルしたLunarMLでLunarML自身をコンパイルする」ことができなくなってしまいました。LuaJITではスタックの大きさが比較的小さいことが原因です。

スタックの消費を抑えるために、CPS中間表現の一部に vector を利用するようにして、木の高さが小さくなるようにしてみました。

ですが、LuaJITのスタックオーバーフローは解消せず、結局LuaJITで動かしたLunarMLでLunarMLをコンパイルすることは諦めることにしました。

コンパイルの高速化

プロファイルを取ったところ、CPS中間表現で項のサイズを計算するところでやたら時間を食っていることがわかりました。項のサイズを計算するのは、「関数のサイズがある程度以下であればインライン化する」というような判定を行うためです。

ここで、巨大な項のサイズを馬鹿正直に計算してしまうと、馬鹿みたいに時間を食ってしまいます。必要なのは「項のサイズが閾値以下かどうか」という情報なので、項のサイズがある程度以上であれば計算を打ち切るようにしました。

別件で、変数の使用状況の調査（「関数の呼び出しが一回だけならサイズに関わらずインライン化する」というような最適化に使う）で使うテーブルを赤黒木からハッシュテーブルに変えると高速化しました。

ドットによる中置演算子

Standard MLに対する拡張のアイディアに書いたやつを実装してみました。

モジュール名がついた識別子も中置化できるのがウリですが、正直言ってモジュール名がついていると見た目がうるさくてあまり恩恵がない気がします。

val z = Word.andb (x, y)
val z = x .Word.andb. y

見た目に関してのHaskellの類似機能との違いは、シンタックスハイライトが対応しているかどうかなので、シンタックスハイライトが対応していればもうちょっとマシになるかもしれません。

実装に関して、手書きの字句解析器をいじるのが億劫になってきました。ML-Lexみたいなやつで字句解析器を宣言的に書けると良さそうですが、ML-Lexは先読みに対応していないので採用しづらいです（先読みがあると「数値リテラルの直後に識別子が続いている場合に警告を出す」というようなことをやりやすそうなので、欲しい）。流石にlexer generatorを自作する時間は今はないので、手書きの字句解析器をゴリゴリやってお茶を濁しました。

WideTextの実装

Standard MLの文字列は8ビット整数列ですが、LunarMLがターゲットとする言語の中には文字列が16ビット整数列のもの（JavaScriptなど）があります。また、将来対応するかもしれない言語の中には文字列がUTF-32のもの（PythonやScheme）があります。

この違いについて、LunarMLでは「標準の string 型は常に8ビット整数列とする」方針を選択しました（他のStandard ML処理系、具体的にはMLjやSML.NETは標準の string 型を16ビット整数列としているようです）。LunarMLのJavaScriptターゲットではStandard MLの文字列は Uint8Array で表現されます。

一方、コンパイル先の言語ネイティブの文字列もうまく扱えた方がいいに決まっているので、それは WideString として実装することにしました。

これまで WideString はJavaScriptの場合に最低限の比較演算などが定義されているだけでしたが、今回、もうちょっと関数を充実させ、Luaターゲットでも実装してみました。

Luaターゲットの WideString は通常の8ビット文字列のopaqueな別名です。WideChar の述語は（ASCIIの範囲のみについて述語が非自明な結果を返す Char とは異なり）ロケールに依存することが認められていますが、UTF-8全盛の時代にロケール依存とか言っても仕方がないので WideChar は単に Char のopaqueな別名としています。

また、JavaScriptの WideChar は16ビットですが、BMPの範囲に限定して非自明な結果を返す isAlpha とかを実装してもあまり嬉しくなさそうなので、これもASCIIの範囲のみについて非自明な結果を返すようにしています。

不要コード除去の強化

不要コード除去 (dead code elimination) を強化しました。以前は適当にやっていましたが、今回、変数の使用状況に関するグラフを構築して実際に使用されているものだけを辿るようにしました。

LunarMLの開発について

春になって、個人的にやりたいこと・作りたいものが新たに色々出てきました。LunarMLも引き続き作りたいものの一つですが、割ける時間は少し減るかもしれません。

気持ちとしては、年内にリリースを出すつもりでやっていきたいと思います。

Spread the love

雑記帳

人生やっていき