**Scheme を WebAssembly にコンパイル**

Bob – Python と C++ で実装された Scheme 実装スイート

私の最古のオープンソースプロジェクトの一つ、Bob は数か月前に 15 歳を迎えました。

Bob は Python で書かれた Scheme 実装群です。インタプリタ・コンパイラ・仮想マシン（VM）が含まれています。
その頃は CPython の内部実装を改造していたので、CPython スタイルのバイトコード VM がどのように動作するかを理解したかったため、R5RS Scheme 用にゼロからこうした VM を構築する実験として Bob を始めました。

その後、Python のランタイムサポート（組み込み GC など）が無い低レベル言語でこれらのマシンがどのように作られるかを学ぶため、C++ VM をスイートに追加しました。C++ VM は独自の mark‑and‑sweep GC を実装しています。

数年間ほとんどメンテナンスだけ（主に見た目の変更、GitHub への移行、Python 3 用アップデート）をしていた後、休暇直前に Bob を再訪する必要性を感じました。そこで新しいコンパイラを追加しました：Scheme → WebAssembly。

---

目的

1. 高レベル言語である Scheme を WebAssembly に低下させる実験
   「Let's Build a Compiler」プロジェクトは通常、C レベルの toy 言語を対象にしています。Scheme は組み込みデータ構造・レキシカルクロージャ・GC が備わっているため、より難易度が高いです。

2. WASM GC 拡張機能 [1] を実務的に体験
   

   wasm-wat-samples

   リポジトリのサンプルはあったものの、実際のプロジェクトで適用したかったためです。

---

概要

Bob の新しい構成要素は右側の垂直パス：

WasmCompiler

クラスが解析済み Scheme 式を WebAssembly テキストにまで低下させ、そこからバイナリへコンパイルして標準 WASM ツールで実行できるようにします [2]。

主な特徴

• WASM GC を使って Scheme オブジェクトを表現
  すべての値を参照（

  ref

  ）でボックス化・ラップすれば、基盤となる WASM ランタイムがメモリ管理を行います。

• Scheme オブジェクトの主要な表現

;; PAIR は cons cell の car と cdr を保持する。
(type $PAIR (struct (field (mut (ref null eq))) (field (mut (ref null eq)))))

;; BOOL は Scheme 真偽値。0 → false、非 0 → true。
(type $BOOL (struct (field i32)))

;; SYMBOL は Scheme シンボル。線形メモリ上のオフセットと長さを保持する。
(type $SYMBOL (struct (field i32) (field i32)))

$PAIR

が特に興味深い点は、フィールドが任意のオブジェクト（

ref null eq

）を含められることです。

ref.test

命令で参照の実行時型をクエリできます。

• 数値 は

  i31

  型で表現されます。これは整数を参照内にボックス化せずに格納し、1 ビット差異で本物の参照と区別します。専用の数値型は不要です。

• シンボル は文字列として手動で保持します。WASM には組み込み文字列サポートがないためです。コンパイラは線形メモリにシンボル文字列を書き込み、

  $SYMBOL

  にオフセットと長さを保存します。これにより同一シンボルのインターリングも効率的に行えます。

例:

;; シンボル用線形メモリ
(data (i32.const 2048) "foo")
(data (i32.const 2051) "bar")

;; シンボル値を構築
(struct.new $SYMBOL (i32.const 2051) (i32.const 3))

---

write

の実装

組み込みの

write

関数は、リストやシンボルなど任意の Scheme 値の再帰的表現を出力する必要があります。

• ホストへ委譲すると、ホストは WASM GC 参照にアクセスできないため問題があります。
• 別言語（例：C）から低下させても WASM GC オブジェクトの表現が難しいです。

したがって

write

を WebAssembly テキスト内で直接実装し、AI のヘルプを得てボイラープレートを書きました。インポートされるホスト関数は 2 つだけです：

(import "env" "write_char" (func $write_char (param i32)))
(import "env" "write_i32"  (func $write_i32  (param i32)))

例えば、標準 Scheme 表記（

#t

/

#f

）で真偽値を出力するには：

(func $emit_bool (param $b (ref $BOOL))
  (call $emit (i32.const 35)) ;; '#'
  (if (i32.eqz (struct.get $BOOL 0 (local.get $b)))
      (then (call $emit (i32.const 102))) ;; 'f'
      (else (call $emit (i32.const 116)))) ;; 't'
)

ほとんどの出力には最低レベルの

write_char

を使用し、整数のエミッションは

write_i32

に委ねます。

---

結論

このプロジェクトは非常に楽しく、実際の WebAssembly コード生成について多くを学びました。

WasmCompiler

のソースは十分にドキュメント化されています。総計 1 000 行を超えるコード（[4]）で、その半分以上が最小限の Scheme 実装に必要な組み込み型と関数を実装する WASM テキストスニペットです。

---

参考文献

[1] The GC proposal – 2023 年 10 月に公式に WASM スペックに追加。
[2] Bob ではテキストからバイナリへの変換に

bytecodealliance/wasm-tools

を使用し、Node.js がバイナリを実行します（将来的には Python バインディングが Wasmtime の WASM GC をサポートするかもしれません）。
[3] 2048 はシンボル格納のためにコンパイラが選んだ任意オフセットです。WASM の複数メモリ機能を使えば別線形メモリを用いることも可能です。
[4] 1 000 行は

WasmCompiler

クラスのみの計で、他のコンポーネント（パーサ・レキサ・共有 Scheme 表現）は含まれていません。

ぜひ

WasmCompiler

のソースコードを覗いてみてください。