LunarMLが自身をコンパイルできるようになった

1件のフィードバック

LunarML進捗報告、号外です。前回の記事

からそんなに時間が経っていませんが、「自分自身をコンパイルできるようにする」という重要なマイルストーンを達成したので報告します。

ところで前回の記事で「セルフホスト」とか書きましたが、用例を探すとself-hostingとかself-hostedがほとんどですね。そりゃそうか。

目次

人はなぜself-hostedなコンパイラーを目指すのか

自分自身をコンパイルできるコンパイラーを書きたいというのはコンパイラーを書く人にとっての目標です。実際、汎用言語の実用的なコンパイラーはしばしば対象となる言語自身で記述されていて、自分自身をコンパイルできます。GCCはC/C++で書かれているし、HaskellのコンパイラーGHCはHaskellで書かれているし、RustのコンパイラーrustcはRustで、という具合です。

では、コンパイラーが自分自身をコンパイルできると何が嬉しいのでしょうか。まあこの問いはググれば100万件くらい回答がヒットしそうですが、ここにも改めて書いておきます。

まず、コンパイラーはそれなりに複雑なソフトウェアです。それをコンパイルできるということは、コンパイラーがそれなりに実用的であるという証拠になります。自身をコンパイルすることでバグを洗い出せるかもしれません。

自分自身を普段使いすることで、言語やコンパイラーの改善のモチベーションになるという効果もあります。例えば、現状のLunarMLは最適化が未熟なので、高速なコンパイラーを得るために最適化を頑張ろうという意欲が発生します。コンパイラーの記述のためにレコード拡張が欲しいとなったら、自分で実装してしまえば使えるようになります。

コードの深さの対策

前にHaMLetをコンパイルできるようになったと報告しましたが、その時は条件付きでした。というのは、出力されたhamlet.luaをLuaインタープリターで読み込もうとするとパーサーがスタックオーバーフローを起こすので、特別に細工（上限を緩和）したインタープリターを用意する必要があったのです。詳しくは

を見てください。

今回、Luaのパーサーのスタック消費量を削減する工夫を導入して、素のLua処理系でもHaMLet（や、これからコンパイルするLunarML自身）をパースできるようにしました。

工夫と言っても今回適用したのは簡単なもので、

if <cond> then
  <stmts1>
  return <exp>
else
  <stmts2>
  return <exp>
end

という形のif文の代わりに

if <cond> then
  <stmts1>
  return <exp>
end
<stmts2>
return <exp>

を出力するようにしただけです。簡単な工夫ですが、elseの部分にさらにネストしたif文が何段も重なっている場合に効果を発揮します。ML-Yaccで生成した関数に長いパターンマッチの羅列（if-then-elseの羅列にコンパイルされる）が含まれていたようで、そこに効いたようです。

一方で、JS-CPSバックエンドでもパーサーの制限にぶち当たりました。こちらはCPS変換で生成された関数のネストが問題でした。

その辺のJavaScript処理系の制限は

で調べましたが、単純なブロックのネスト {{{...}}} はSpiderMonkeyで855段が限界です。

今回は、簡単のためにブロックや式の深さは考慮せず、function同士のネストだけを見て、200段を超えたらクロージャー変換もどきを実行します。

クロージャー変換もどきというのは、例えばこういうコード

function f() {
    var a = 42;
    var g = function(x, y) {
        if (x <= 1) {
            return a + x + y;
        } else {
            return g(x - 1, y);
        }
    };
}

があって g の深さが深すぎるとなったら、gの定義を外のスコープに追い出して

function g$1(a, g, x, y) {
    if (x <= 1) {
        return a + x + y;
    } else {
        return g(x - 1, y);
    }
}
function f() {
    var a = 42;
    var g = function(x, y) {
        return g$1(a, g, x, y);
    };
}

という形に変換することです。新しい g の定義は、実質 bind メソッドを呼んでいるようなものですが、再帰的な参照とかを考慮した結果この形にしました。bind メソッドで済む場合はその方がいいかもしれません。

パーサーの都合に合わせて出力コードを調整しないといけないのは、スクリプト言語を出力するコンパイラー特有かもしれません。……いや、ネイティブコードでも「ジャンプ先のラベルまでの距離への配慮」みたいなのが発生したりするか……

インデント

JS-CPSバックエンドではやたらインデントの深いコードが生成されます。HaMLetやLunarMLのようにある程度でかいソフトウェアをビルドすると、出力コード中のインデントだけで「JavaScriptの文字列の長さの限界」に達する可能性が出てきます。

この問題を緩和するため、JavaScriptバックエンドではひとまずインデントの量を「一段につきインデント幅1、タブ文字も幅8として併用する」としました。Emacsで見るといい感じになるアレです。将来的にはこの辺もカスタマイズ可能にしたいです。

リスト処理とスタックオーバーフロー

LunarMLをコンパイルした結果生成されるLuaやJavaScriptのコードは膨大なものになります。生成途中の文字列をいちいち連結していると遅くなりそうなので、LunarMLでは長い文字列を生成する際に一旦 string list （文字列を要素とするリスト）に変換してから String.concat : string list -> string で連結しています。問題は、ここのリストがあまりにも長いと、コードの書き方次第ではスタックオーバーフローが出るのです。

要するに末尾再帰しろという話です。

LunarMLの標準ライブラリーでは、驚くべきことに、ここに至るまで List.rev を末尾再帰ではない形で実装していました。従来のコードは次のようなものです：

fun rev [] = []
  | rev (x :: xs) = rev xs @ [x]

多分LunarMLで再帰関数が定義できるようになった頃に @ が使えるぜヒャッハーという気持ちで書いたのだと思いますが、この rev の定義は長いリストを処理させたときにスタックオーバーフローを起こすので実用的ではないのです。スタックオーバーフローが起きなくても、実行時間が長さの2乗に比例しそうです。

List.rev のまともな実装は次の通りです：

fun revAppend ([], ys) = ys
  | revAppend (x :: xs, ys) = revAppend (xs, x :: ys)
fun rev xs = revAppend (xs, [])

この実装は末尾再帰で、実行時間はリストの長さに比例します。

この修正をした結果、LunarMLでコンパイルしたLunarMLが自分自身をコンパイルできるようになりました。大勝利です。

第2世代と第3世代と実行時間

MLtonでコンパイルしたLunarMLの実行ファイルを第1世代のコンパイラーとします。

第1世代のLunarMLでLunarML自身をコンパイルしてできたLuaファイルを第2世代のコンパイラーとします。

第2世代のLunarMLでLunarML自身をコンパイルしてできたLuaファイルを第3世代のコンパイラーとします。

コンパイルの際に非決定的な処理が使われていなければ、第2世代と第3世代のコンパイラーは一致するはずです。しました。

これで、コンパイラーがある程度正常に動作することが確認できました。JavaScriptでも同じような検査ができます。

ただ、現状のLunarMLは最適化がそこまで実装されていないので、第2世代のコンパイラーの実行にはやたら時間がかかります。

参考までに、Apple M1での実行時間を載せておきます。

MLtonによるLunarML（第1世代）のコンパイル：

$ time mlton -output lunarml LunarML.mlb
mlton -output lunarml LunarML.mlb  48.75s user 2.09s system 99% cpu 51.055 total

MLtonはコンパイルの際に時間とリソースを食うことで有名です。LunarMLのビルドには51秒かかりました。

第1世代コンパイラーによるLunarMLのLuaへのコンパイル：

$ time ./lunarml -o lunarml.gen2.lua LunarML.mlb
./lunarml -o lunarml.gen2.lua LunarML.mlb  4.23s user 0.53s system 90% cpu 5.242 total

LunarML（ネイティブ）を使ったLunarMLのLuaへのコンパイルは5秒で済みました。

Lua 5.4.4で実行する、第2世代コンパイラーによるLunarMLのコンパイル：

$ time ../lua-5.4.4/src/lua lunarml.gen2.lua -o lunarml.gen3.lua LunarML.mlb
../lua-5.4.4/src/lua lunarml.gen2.lua -o lunarml.gen3.lua LunarML.mlb  373.40s user 16.88s system 98% cpu 6:38.03 total
$ diff --report-identical-files lunarml.gen2.lua lunarml.gen3.lua
Files lunarml.gen2.lua and lunarml.gen3.lua are identical

こちらはそこそこ時間がかかりました。6分38秒です。MLtonより遅いです。第2世代と第3世代が一致することも確認しています。

JavaScriptでもやってみましょう。

第1世代によるLunarMLのJavaScriptへのコンパイル：

$ time ./lunarml -o lunarml.gen2.js --js-cps LunarML.mlb
./lunarml -o lunarml.gen2.js --js-cps LunarML.mlb  68.57s user 24.18s system 91% cpu 1:41.07 total

LunarML（ネイティブ）を使ったLunarMLのJavaScriptへのコンパイルには1分41秒かかりました。Luaバックエンドと比べても遅いのはCPS変換が影響しているのでしょうか。

Node.jsで実行する、第2世代コンパイラーによるLunarMLのコンパイル：

$ time node lunarml.gen2.js --js-cps -o lunarml.gen3.js LunarML.mlb
node lunarml.gen2.js --js-cps -o lunarml.gen3.js LunarML.mlb  10996.68s user 319.72s system 82% cpu 3:47:55.33 total
$ diff --report-identical-files lunarml.gen2.js lunarml.gen3.js
Files lunarml.gen2.js and lunarml.gen3.js are identical
$ node --version
v17.9.1

こちらはものすごく時間がかかりました。3時間以上です。気軽に試せません。最適化の余地がかなりありそうです。

自分自身をコンパイルできるようになったらLunarML自身でLunarMLの開発を、と言いたいところでしたが、もうしばらくは日々の開発にはMLtonに頼らざるを得なさそうです。LunarML自身にrecord updateを使えたら便利なのになあ……。

HaMLetは動くのか：エラー処理でのCスタックオーバーフロー

前にHaMLetが動いたというのは、「Cスタックの制限を緩和したLuaインタープリター」を使っての話でした。

出力されるコードの深さを緩和した今、HaMLetは無改造のLuaで動作するのでしょうか？

答えは否です。HaMLetではネストしたhandle（Standard MLの例外処理機構。他の言語のtry-catchに相当）を多用しているのが関係しています。

Luaには例外処理用の文法はありません。例外の送出も捕捉も、ライブラリーの関数を呼び出すことで実現します。前者は error 関数、後者は pcall や xpcall 関数です。

LunarMLのLuaバックエンドでは、これまで普通に pcall を呼んで例外の捕捉を実装してきました。例えば

foo () handle Fail e => print e;

というSMLコードは次のようなLuaコードにコンパイルされます：

local function _handle(f)
  local success, result = pcall(f)
  -- 実際はLuaのエラーをSMLの例外としてラップする処理が挟まる
  return success, result
end

local function _raise(e, location)
  -- 実際には例外を表す値に location を引っ付ける処理が挟まる
  error(e, 1)
end

local success, result = _handle(function()
  return foo()
end)
if not success then
  -- resultは例外を表す値
  if result.tag == _Fail_tag then
    io.write(result.payload)
  else
    -- 再スロー
    _raise(result, nil)
  end
end

例外が捕捉される処理は pcall の中で実行されます。pcall を介した呼び出しはLua処理系のCスタックを消費するので、ネストが深いとCスタックオーバーフローを起こすのです。

この問題を回避する方法はないのでしょうか？

最悪、CPS変換を使って独自に例外処理機構を実装すればCのスタックは消費しなくなるでしょう。しかしそれは大掛かり過ぎますし、コンパイルされたコードが（最適化を実装しない限り）遅くなります。

幸い、LuaにはCPS変換をしなくても独自の大域脱出を行える機構が備わっています。コルーチンです。これを上手く活用できないでしょうか。

ところで、JavaScriptでは末尾呼び出しがないためにトランポリンという技法を使ってコールスタックの深さを一定に抑える必要がありました。JavaScriptのコールスタックの深さを抑えることと、LuaのCスタック消費量を抑えること、共通点がありそうです。

というわけで、コルーチンをトランポリンすることで例外処理の際のCスタック消費量を抑える方法を編み出してみました。基本的な実装は次のようになります：

local function _handle(f)
  local c = coroutine.create(function()
      return "return", f()
  end)
  return coroutine.yield("handle", c)
end
local function _raise(x)
  error(x, 1)
end
local function _run(f)
  local c = coroutine.create(function()
      return "return", f()
  end)
  local stack = {c}
  local values = {}
  while #stack > 0 do
    local status, a, b = coroutine.resume(stack[#stack], table.unpack(values))
    if status then
      if a == "return" then
        table.remove(stack)
        values = {true, b}
      elseif a == "handle" then
        table.insert(stack, b)
        values = {}
      else
        error("unexpected result from the function: " .. tostring(a))
      end
    else
      table.remove(stack)
      if #stack > 0 then
        values = {false, a}
      else
        error(a)
      end
    end
  end
  return table.unpack(values)
end
_run(function()
  local success, result = _handle(function()
    return foo()
  end)
  if not success then
    -- resultは例外を表す値
    if result.tag == _Fail_tag then
      io.write(result.payload)
    else
      _raise(result, nil)
    end
  end
end)

エラー送出は従来の error を使っていますが、やろうと思えばそこも coroutine.yield でやりとりできます。ただ、Lua処理系自身が出すエラーも捕捉できた方が嬉しいかと思って error を活用する形にしました。

handleするたびにコルーチンを生成していると遅いので、高速化のためには「ある程度の段数は pcall を使って、深さが一定以上になったらコルーチンを使ってCスタックをリセットする」という工夫が有効です。これも末尾再帰のトランポリンと同じです。

ただ、コルーチンを例外処理に使ってしまうと、ユーザーコード側でのコルーチンの使用と相性が悪いかもしれません。LunarMLの「例外処理でCスタックを消費しないモード」ではユーザーがLuaのコルーチンを直接触るのを禁止して、コルーチンをラップしたワンショット限定継続を提供する、という方針がいいのかもしれません。

LunarMLでは --lua-stackless-handle オプションで「handleにコルーチンも併用する」モードが有効になります。まだ実験的です。名前もやっつけです。

次の目標

年始に掲げた目標的には、次は「REPLとインタープリター」か「Webで試せるようにする」か、という話になりそうです。標準ライブラリーの整備はぼちぼちやっていきます。

Luaで動かすLunarMLが結構遅かったので、LuaJIT対応も視野に入ってきます。現状のLunarMLはLua 5.3/5.4をターゲットとしていて、そのままではLuaJITで動かないのです。

CPSした後の最適化も実装したいです。JS-CPSバックエンドは非JITなLuaよりも遅いです。

おしゃれなロゴも欲しいです。

Successor MLの一環として、パターンマッチを強化したいです。また、パターンマッチのコンパイルのアルゴリズムをまともにすれば高速化に繋がるかもしれません。

まとめると、今後の目標は以下の感じです：

  • REPLとインタープリターを整備する
  • Webで試せるようにする
  • LuaJIT対応のコードを出力できるようにする
  • 最適化を実装する
  • おしゃれなロゴを用意する
  • パターンマッチをいい感じにする

「自分自身をコンパイルできるようにする」のが派手なマイルストーンすぎて残りの目標が地味に見えますが、今年の後半も着実にやっていきたいです。

LunarMLは以下のGitHubリポジトリーで開発しています。面白そうだと思っていただけましたらスターをお願いします。

このエントリーをはてなブックマークに追加

“LunarMLが自身をコンパイルできるようになった” に1件のフィードバックがあります

  1. ピンバック: LunarML進捗・2022年7月：LuaJIT対応など | 雑記帳

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です