LunarML進捗・2023年1月

2023年もLunarMLの開発をゆるゆるとやっていきます。

前回の記事：

LunarMLの進捗2022

1 進捗
2 まとめ

進捗

エスケープしない継続はジャンプやwhileにコンパイルする

JS-CPSバックエンドではCPS変換を行い、継続を関数にコンパイルしてきました。しかし、継続の中には関数にコンパイルする必要のないものもあります。エスケープしない継続がそれです（エスケープする継続とは、関数呼び出しに渡される継続です）。

エスケープしない継続は、引数付きのgoto/ラベルにコンパイルできます。

例えば、if式を含む次のコードを考えます：

foo (if cond then 1 + 1 else 2 * 3);

このコードは継続を使った次の擬似コードに変換されます

letcont k1 x = foo k x in (* k はプログラムを終了させる継続 *)
if cond then
  k1 (1 + 1)
else
  k1 (2 * 3)

if式の後に制御が合流する部分が、letcontにより継続 k1 として定義されています。この k1 はエスケープしない継続なので、ジャンプに変換することができます。JavaScriptにコンパイルするなら、次のような感じです：

let k1_x; // 継続の引数の受け渡しに使う変数
k1: {
    if (cond) {
        k1_x = 1 + 1;
        break k1;
    } else {
        k1_x = 2 * 3;
        break k1;
    }
}
foo(k, k1_x);

ジャンプのためにラベル付き文とbreakを使いました。継続の引数の受け渡しにはローカル変数を使っています。

一般に、エスケープしない継続は

letcont k x = ...kの処理... in
... k v ...

から

let k_x;
k: {
    ...
    {
        // 継続kの呼び出し
        k_x = v;
        break k;
    }
    ...
}
...kの処理...

へ変換できます。ラベル付き文からfall throughしたらどうするんだ（制御が暗黙に k に突入するのでは）、と思われるかもしれませんが、ラベル付き文の中身の最後の文は全てジャンプやreturnにコンパイルされているはずなので問題ありません。

ちなみにターゲットがLuaの場合はgotoを使ってこんな感じになります：

local k_x -- 継続の引数の受け渡しに使う変数
do
  ...
  do
    -- 継続kの呼び出し
    k_x = v
    goto k
  end
  ...
end
::k::
...kの処理...

継続が自身を呼び出す再帰的な場合、あるいは相互再帰的な継続の場合を考えます。例えば次の擬似コード

letcont k1 x = ...k1の処理... k2 x ...
    and k2 y = ...k2の処理... k1 y ... in
... k1 42 ... k2 37 ...

は次のJavaScriptにコンパイルされます：

let k1_k2_which, k1_k2_0; // 継続の種類を表す変数と、継続の引数
go_to_k1_or_k2: {
    ...
    {
        // 継続k1の呼び出し
        k1_k2_which = "k1";
        k1_k2_0 = 42;
        break go_to_k1_or_k2;
    }
    ...
    {
        // 継続k2の呼び出し
        k1_k2_which = "k2";
        k1_k2_0 = 37;
        break go_to_k1_or_k2;
    }
    ...
}
k1_k2: while (true) {
    switch (k1_k2_which) {
    case "k1":
        {
            const x = k1_k2_0; // 継続の引数がキャプチャーされる場合に備えて変数を定義しなおす
            ...k1の処理...
            {
                // 継続k2の呼び出し
                k1_k2_which = "k2";
                k1_k2_0 = x;
                continue k1_k2;
            }
            ...
        } // ここには制御は到達しないのでbreakは必要ない
    case "k2":
        {
            const y = k1_k2_0;
            ...k2の処理...
            {
                // 継続k1の呼び出し
                k1_k2_which = "k1";
                k1_k2_0 = y;
                continue k1_k2;
            }
            ...
        } // ここには制御は到達しないのでbreakは必要ない
    }
}

再帰のグループに含まれる継続が一つの場合はwhich変数は必要ありません。

Luaの場合は次のようになるでしょう：

local k1_k2_0
do
  ...
  do
    -- 継続k1の呼び出し
    k1_k2_0 = 42
    goto k1
  end
  ...
  do
    -- 継続k2の呼び出し
    k1_k2_0 = 37
    goto k2
  end
  ...
end
::k1::
do
  local x = k1_k2_0
  ...k1の処理...
  do
    -- 継続k2の呼び出し
    k1_k2_0 = x
    goto k2
  end
  ...
end
::k2::
do
  local y = k1_k2_0
  ...k2の処理...
  do
    -- 継続k1の呼び出し
    k1_k2_0 = y
    goto k1
  end
  ...
end

再帰のグループに含まれる継続が一つの場合はwhileにコンパイルした方が可読性の面で良いかもしれません。

まあ、まだcontification（普通の関数を継続に変換する最適化）を実装していないのでLunarMLでのコンパイルの際に再帰的な継続が出現することはないのですが。

CPSの最適化

JS-CPSバックエンドでCPSを使うのは限定継続が欲しいからですが、コンパイラーの中間形式をCPSにするのは最適化がやりやすいという恩恵もあります。

というわけで、CPSの最適化として一部の関数の定数畳み込みを実装しました。

また、「副作用がない関数の結果が使われていない場合は関数呼び出しを削除する」最適化も実装しました。これはLunarMLの標準ライブラリー内で使っているfunctorをDCEできるようになるということなので、生成コードサイズの削減に寄与します。ただ、CPS形式はこういう変換に向いていない気もします。

LuaJIT向けコードの問題の解消

LuaJITはLua 5.1の制限を受け継いで、関数の上位値（upvalue; 関数の自由変数のうち、レキシカルなもの）を60個しか持てません。Lua 5.2以降はこの制限は250個だか255個だかに緩和されています。

普通にLuaコードを手書きしていて上位値を60個も使うことは少なそうですし、大抵のSMLコードでもそうでしょう。しかし、ML-Yaccなどで生成されたコードはこの制限に引っ掛かります。

LunarMLでは自身をLuaへコンパイルするために、上位値の制限を掻い潜るコード変換を実装しています。Luaをコンパイルターゲットにするのは大変なのです。

その変換が微妙にバグっており、LuaJITでLunarML自身を動かせない事態になっていました。発生条件も微妙で（簡単なプログラムでは再現しない）、デバッグに2日くらいかかりました。

CI: LuaでLunarML自身を動かす

LuaJITの件は、CIで日頃から「LunarMLをLuaにコンパイルしたものをLuaで動かし、LunarML自身を動かす」ことをやっていればもっと早く気づけたはずです。

ただ、LuaでLunarMLを動かすのはかなり重いので、pushの度にやっていると資源の無駄感が否めません。そこで、「最大で一日一回、コミットがあった日に動かす」という形で設定しました。

実際にやってみると、手元で数十分で完了するコンパイルが6時間経っても終わっていなかったり、killされたりしました。これはメモリ不足の症状です。

自分ではGitHub Actionsのメモリ制限がドキュメントされている箇所を見つけられなかったので「プログラミング言語処理系が好きな人の集まり」で聞いてみたところ、termoshttさんに

About GitHub-hosted runners – GitHub Docs

を教えていただきました。Windows/Linux VMではメモリは7GB、macOS VMではメモリは14GB使えるらしいです。

ということは、Linux VMでメモリが足りなくてもmacOS VMではメモリが足りる可能性があります。そこで、一日一回のやつはmacOSで動かすようにしました。

こういうのをやっていると「無料でクラウドを使うためならどんなことでもする」感があります。

CPSでの例外の扱い方

Compiling with Continuationsでは例外の扱いについて、少なくとも二種類があると述べています：

グローバル変数にハンドラーを設定し、ブロックに入るタイミング、ブロックを正常終了するタイミング、ハンドラーの冒頭でこの変数を書き換える（動的なやり方；SML/NJではこれを採用）
関数に渡す継続を正常終了用と例外発生用の二つにする（double-barrelled CPS; Compiling with Continuations, Continuedではこれを採用）

これまでのLunarMLのCPS変換（JS-CPSバックエンド）では後者を採用していました。しかし、いずれCPS形式からdirect styleに戻してLuaやJavaScriptにコンパイルするバックエンドを作ることを考えると、後者は面倒そうです。Compiling with Continuations, Continuedのネタ元のSML.NETではCPSをdirect styleに戻しているらしいですが、例外をどうやっているのかよくわかりません。

そこで、LunarMLのCPS形式では例外ハンドラーを構文的に扱うことにしました。抽象度を上げることによって異なるやり方に対応しやすくなります。この件に関する先行研究があるのかはよくわかりません。

JS-CPSバックエンドでは構文的な例外ハンドラーを従来通り二種類の継続を扱うようにコンパイルします。他のdirect styleなバックエンドではターゲットのtry-catch文（Luaの場合はpcall）を使うようにコンパイルします。

ただ、JS-CPSバックエンドではJavaScript呼び出しとMLの処理で異なる例外システムを使うことになってしまいます。具体的には、JavaScript呼び出しをいちいちtry-catchで囲って発生した例外をMLの例外ハンドラーに渡すということをしています。これは非効率的な気がするので、グローバル変数に例外ハンドラーを設定し、トランポリンの外側にtry-catchを設置して飛んできた例外を現在の例外ハンドラーへ渡す、という形にするべきかもしれません。

CPS経由でdirect styleなLuaコードを出力する

先に述べた通り、CPS形式にいくつかの最適化を実装しました。これからも実装される最適化は増えていくでしょう。

direct styleなコード生成をするLuaやJavaScriptターゲットでもこういう最適化の恩恵を受けたいです。direct styleな中間コードだとANF with join pointsがそういう最適化をしやすいようですが、すでにそれと同等なCPS中間形式を実装しているのに改めてANFを実装するのは手間です。そこで、CPS中間形式をdirect styleなコードにコンパイルしたいです。

（あるいは最適化をANFで実装して、JS-CPSバックエンドの場合はその後でCPS変換するというやり方も考えられますが。）

すでに「エスケープしない継続をジャンプに変換する」のところで考察は行ったので、あとは「全ての継続をエスケープしないものとみなす」ようにするだけです。「関数呼び出しに継続を渡す」のを「関数呼び出ししてから（関数の戻り値を引数として）継続を起動する」に変えます。

それで簡単なプログラムは動作するようになったのですが、LunarML自身をLuaにコンパイルして再びLunarML自身をコンパイルしようとすると、Luaのスタックオーバーフローが出てしまいました。

原因はローカル変数が多い関数で深い再帰を行っていたことです。例えば次のLuaコードを考えます：

function foo(x)
  local tmp1 = ...
  local tmp2 = ...
  local tmp3 = ...
  if tmp3 then
    foo(x-1)
    return
  else
    -- tmp1, tmp2, tmp3は以後使われないものとする
    ...
  end
end

tmp1, tmp2, tmp3 は条件分岐のみに使われ、以後参照されないものとします。ここで foo を再帰呼び出しすると、これらの「死んだ」変数がスタックに残ったままになってスタックを圧迫するのです。

従来のLuaバックエンドでは、MLの式に近い単位で適宜do-endで囲っていたからこの手の問題が起きにくくなっていました。例えば

foo (bar () + baz ())

というMLの式だったら

local tmp4
do
  local tmp1 = bar()
  local tmp2 = baz()
  local tmp3 = tmp1 + tmp2
  tmp4 = foo(tmp3)
end

という感じで、最終的な結果を保持する tmp4 以外は外のスコープに漏れないようにしていました。

if文だったら

do
  local tmp1 = ...
  local tmp2 = ...
  local tmp3 = ...
  if tmp3 then
    ...thenの処理...
    -- 処理の最後にgotoやreturnをして、制御は返さないものとする
  end
end
...elseの処理...

という風にすれば「elseの処理」に変数が漏れ出すのは防げます。

CPS経由のLuaバックエンドでも似たようなことをすれば良いのですが、「MLの式」という単位がCPS変換でフラットになってしまっているため、動作させるまでに苦労しました。結局、「死んだローカル変数が溜まってきた場合、do-endを挿入する」のと「ifの内側はgotoだけを書いて、条件分岐に使ったローカル変数を抹消できるようにする」などの工夫を行いました。

do
  local tmp1 = ...
  local tmp2 = ...
  local tmp3 = ...
  if tmp3 then
    goto then_
  else
    goto else_
  end
end
::then_::
...thenの処理...
::else_::
...elseの処理...

ですが、全てのif文にgotoを使うのは見た目が美しくありません。なので、もうちょっとアルゴリズムを洗練させていきたいです。

まとめ

今月（というか、2022年のまとめ記事以降）はCPS周りのことをやりました。CPSのことがﾁｮｯﾄだけﾜｶﾙようになったと思います。

雑記帳

人生やっていき