月刊LunarML進捗報告です。前回は
で、3月はHaskellの記事を書くのに忙しかったので休刊でした。
今月の進捗を一言で言うと、JavaScriptバックエンドの実装を進めました。
面白いと思った方はGitHubにスターをつけてください：
目次
浮動小数点数の基数変換
LunarMLの入力言語には十六進浮動小数点数リテラルがある。JavaScriptにはそれがない。ということは、コンパイルの際に浮動小数点数の基数変換を行う必要がある。
というわけで、基数変換のアルゴリズムを調べ、実装した。詳しくは
を参照。採用したのはDragon4の原型で、効率は度外視している。
ソースに書かれたのが十六進の場合のみこのアルゴリズムを適用するようにしているが、ソース中にあまりにも長い十進小数が記述されていた場合にもアルゴリズムを適用してリテラルの長さの最小化を図るべきかもしれない。
文字列の機能追加
JavaScriptの文字列はUTF-16を意図された16ビット整数列である。LunarMLではJavaScriptの文字列を WideString.string 型として利用できるようにする。というわけで、複数の文字列型に対応できるようにLunarMLを改修した。
この際、文字列リテラル中のUnicodeエスケープシーケンスを強化し、新たに \Uxxxxxxxx （Successor MLのやつ・十六進8桁）と \u{xxxxx} （独自拡張・十六進可変長）に対応させた。
前者はC言語とかPythonでお馴染みのやつで、後者はJavaScriptとかLuaでお馴染みだと思う。
Standard ML/Successor MLにある \uxxxx や \Uxxxxxxxx は1文字で表現することを意図しており、可変長UTF（UTF-8, UTF-16）全盛の時代には居場所がないということは以前の記事で述べた。
そこで \u{} だ。これは、文字列型に応じてUTF-8, UTF-16, UTF-32のいずれかで適切にエンコードされる。通常のSMLで
print "\u3042\n";
と書いても0x3042を char で表現できないのでコンパイルエラーとなるが、LunarMLで
print "\u{3042}\n";
と書けばU+3042がUTF-8でエンコードされて標準出力に書き出される。
JavaScriptバックエンド
実装した。コマンドラインオプションで --js を指定すると有効になる。
基本的な方針は前回書いた通り。
IntInfやWord64の実装にはES2020で追加されたBigIntを使うことにした。ES2020未満の環境への対応が必要になった場合は考え直す。
テストを実行するには標準出力へのアクセスが必要となるため、Node.jsに依存している。ここで、Node.jsのモジュールを使うのにCommonJS（require関数）を使うかES modulesを使うかという問題がある。ES modulesは静的なため、使うためにはLunarML側に構文の追加が必要になるだろう。当面はCommonJSを使うが、LunarMLは未来志向なのでいずれかのタイミングでES modulesも使えるようにしたい。
対象とする動作環境はいろいろ考えられる：
- Node.js/CommonJS
- 当面はこれ。
- Node.js/ES modules
- 拡張子が
.mjsとなる。
- 拡張子が
- Web/standalone
- <script>で読み込むための単体のファイルを出力する。
- 標準入出力やファイルシステムは使えない。
- Web/ESM
- バンドラーに食わせる。あるいは最近のブラウザーなら直で読み込める？
- 標準入出力やファイルシステムは使えない。
- Web/各種エミュレーション付き
- 仮想ターミナル（xterm.js）や仮想ファイルシステム（memfsなど）と組み合わせて、Webでも標準入出力やファイルシステムを扱えるようにする。
- シェルが欲しくなるかも。
SMLは末尾呼び出し最適化（TCO）を必要とするが、JavaScriptにはない（JavaScriptはECMAScriptではないので）。SMLでループを表現するには末尾呼び出し（末尾再帰）しかないので、コンパイラーがTCOを実装しなければならない。
TCOのない実行環境でTCOを実装するテクニックとしてはトランポリンがある。詳しい説明は省くが、コード例を挙げると
fun factTail (n, acc) = if n = 0 then
acc
else
factTail (n - 1, n * acc);
print (Int.toString (factTail (5, 1)) ^ "\n");
というSMLコードは
function factTail(arg) {
var n = arg[0], acc = arg[1];
if (n === 0) {
return [true, acc];
} else {
return [false, factTail, [n - 1, n * acc]];
}
}
function factTail_wrap(arg) {
var result = factTail(arg);
while (!result[0]) {
var g = result[1];
var arg = result[2];
result = g(arg);
}
return result[1];
}
print(Int.toString(factTail_wrap([5, 1])) + "\n");
という風にコンパイルされる。関数から値を返す部分は return [true, 値] にコンパイルされ、それが末尾呼び出しであれば return [false, 関数, 引数] にコンパイルされる。factTailを通常の関数として呼び出したい側は、factTailが [true, 値] を返せばその値を取り出し、 [false, 関数, 引数] を返せば次のループで関数に引数を適用する。
ちなみに先行するSMLtoJsはTCOをちゃんとやっていないらしい（末尾再帰のループへの変換くらいは行うのだろうか？）。
もちろん、全ての末尾呼び出しでトランポリンしていたら遅いので、呼び出し対象が自身の場合（末尾再帰）はループに変換するとか、「許容できるコールスタックの深さ」を管理して許容できる場合は通常の（JavaScriptの）末尾呼び出しを使う、などの最適化が考えられる。
ところで、WebにせよNode.jsにせよ、JavaScriptで書く種類のプログラムでは非同期処理が多用される。JavaScriptにコンパイルする言語の側でも非同期処理を同期的に書ける機構があると良いかもしれない。プログラムをCPS変換してcall/ccを導入すればいいのだろうか？しかしcall/ccそのものにはいろいろ難点があるらしい：
何にせよ、勉強する必要がある。
まだやっていないこと
前回書いた型推論の高速化に関して、Twitterでlevel-based generalizationというのを教えていただいた。
…が、まだ実装していない。JavaScriptバックエンドが落ち着いたらやりたい。
ピンバック: LunarMLと継続 | 雑記帳
ピンバック: LunarML進捗・2022年6月 | 雑記帳