Zenn
Open10

LunarMLのWasmGCバックエンド検討メモ

WebAssembly
WebAssembly
だめぽだめぽ

目標

LunarMLからWasmGC (WebAssembly with GC proposal) 向けのコードを出力したい。

すでにJavaScriptバックエンドはあるが、それに比べて期待したい点は、読み込みと実行が高速であることである。つまり、

  • WasmはバイナリーなのでパースがJavaScriptよりも高速だと期待される。
  • Wasmにはi64やf32があるのでそういうのを多用するコードは高速化する可能性がある。

LunarMLをLuaやJavaScriptにコンパイルしたものは正直言って遅い。WasmGCにコンパイルすることでもう少し高速な「LunarMLでコンパイルされたLunarML」を得られると良い。

また、JavaScriptよりは低レベル（例：ネストした関数、無名レコードがない）なので、この先バイトコードやネイティブコードを出力する際の足がかりになるかもしれない。

要検討：

  • 限定継続をサポートするかどうか。現状のJavaScriptバックエンドのように、継続をサポートするモードとしないモードに分けるか。
だめぽだめぽ

Wasmのツールチェイン

テキスト形式（WAT）からバイナリー形式に変換する作業を外部ツールに任せたり、あるいは自分で出力したバイナリーを逆アセンブルするのを外部ツールでできると良い。出力したコードの最適化もできると良い。

数学関数とかをどうするか。システムとのやり取りも。自分でゼロから組むのは大変なので、出来合いのlibcを使いたい（少なくとも当初は）。

リファレンス実装があるとバリデーションとかで便利。

だめぽだめぽ

情報源・記事

だめぽだめぽ

型の表現

Standard MLの型をWasmGCの型にどうやって対応させるか。

関数（クロージャー）

C言語で書くなら

struct Closure {
    void *(*code)(struct Closure *, void *);
    void *payload[]; // 実際の内容はクロージャーごとに異なる
};

みたいな感じにする。

;; WAT形式
;; コメントはセミコロン2つで始める
(type $funccode (func (param $closure anyref) (result anyref)))
(type $closure (sub (struct (field $code (ref $funccode)))))
;; subtypeを作れる型はsubでマークする。しなかったら暗黙にsub final扱いになる。

;; i32型のfree variableとして$aを持つ関数
(type $someclosure (sub final (struct (field $code (ref $funccode)) (field $a i32))))
;; subtypeを作る際はsupertypeのフィールドを再び列挙する

datatype

ペイロードがないやつはタグのみの i32（i31?）として表現すれば良い。選択肢が1個のみのやつはHaskellの newtype あるいは unit と同様に表現すれば良い。

一般の場合は、例えば 'a option なら以下のようにする：

(type $option (sub (struct (field $tag i32))))
(type $option.NONE (sub final $option (struct (field $tag i32))))
(type $option.SOME (sub final $option (struct (field $tag i32) (field $payload anyref))))

レコード

Standard MLのレコードは構造的なので、低レベル言語にコンパイルする際は何らかの工夫が必要となる。

まず、フィールド名は辞書順にソートすることによってタプルにできる（脱糖）。タプルをどう表現するか。

最も簡単なのは、anyref の配列にすることであるが、int * int みたいなやつも要素をボックス化することになって効率が悪そう。

フィールドの一部が単相的になっている場合はそういうstructを使うようにすると効率的かもしれない。Java風に書けば

interface tuple3 {
    Object get0();
    Object get1();
    Object get2();
    /* プリミティブ型に対して
      int get0_i32();
      long get0_i64();
      float get0_f32();
      double get0_f64();
     みたいなやつも用意した方がいいかもしれない */
}
final class tuple_i32_f64_anyref implements tuple3 {
    int a;
    double b;
    Object c;
    // getの実装は省略
}

みたいな感じ。interfaceみたいなことをやりたいのでvtableを用意する。

(type $tuple3-getter (func (param $tuple3-vtable) (result anyref)))
(type $tuple3-vtable (struct (field (ref $tuple3-getter)) (field (ref $tuple3-getter)) (field (ref $tuple3-getter))))
(type $tuple3 (sub (struct (field $vtable (ref $tuple3-vtable)))))
(type $tuple3-i32-f64-anyref (sub final $tuple3 (struct (field $vtable (ref $tuple3-vtable)) (field i32) (field f64) (field anyref))))

datatypeのペイロードとして現れるレコードはstructにした方が良いのかもしれない。

だめぽだめぽ

必要な作業

  • 中間言語の後の方まで型情報を残す。現状はCPS変換の段階で削ぎ落としている。
  • closure conversion

最適化の案（後回しにする）：

  • レコードを具体的なstructに変換できる場合はそうする
    • 類似の変換：option→nullable、レコード→struct、vector→mono vector、array→mono array、関数→タプルを受け取る関数を複数引数に変換する
  • 具体的な型がわかっている場合にunboxする
  • 多相的な関数が単相的に使われる場合は特殊化する
    • MLはlet多相でカジュアルに多相関数が発生するが、全部ボックス化すると効率が悪そう。
だめぽだめぽ

多相の表現

最初は全部ボックス化して anyref にする。

ボックス化する必要のないやつ：

  • unit→null
  • bool, char, int8, int16, word8, word16→i31
    • Int31 を導入する余地があるのかもしれない。
だめぽだめぽ

WasmGCの簡単な例

i32 をボックス化するだけの関数と、ボックス化された値を取り出す関数を書いてみる。

(module
(type $boxed-i32 (struct (field i32)))

(func (export "make")
  (param $i i32)
  (result (ref $boxed-i32))
  (struct.new $boxed-i32 (local.get $i))
)
(func (export "get")
  (param $o (ref $boxed-i32))
  (result i32)
  (struct.get $boxed-i32 0 (local.get $o))
)
)

$ wasm-as --enable-gc --enable-reference-types test.wat

呼び出し側：

import { readFileSync } from "node:fs";
const wasmBuffer = readFileSync("test.wasm");
const wasmModule = await WebAssembly.instantiate(wasmBuffer);
const { make, get } = wasmModule.instance.exports;
const o = make(42);
console.log(o, get(o));

$ deno run --allow-read run.mjs
[Object: null prototype] {} 42