Brainfuckのwasmターゲットコンパイラを書いてwasmとWASIに入門

19 min read読了の目安(約17600字

はじめに

WebAssembly(以下wasm)の勉強のために、Brainfuckのソースコードをwasmに変換するコンパイラを書きました。本稿はその解説記事になります。ソースコードはこちらにおいてあります。

生成したwasmバイナリはWasmtimeWasmerなどのランタイムから実行できます。この記事では扱いませんが、追加でJSを書けばブラウザでも実行できると思います[1]。ちなみに実装言語はRustです。

背景

ご存知の方も多いと思いますが、Brainfuckはたった8つの命令からなるプログラミング言語です。人間が読み書きするのは面倒ですが、命令の少なさゆえ処理系を書くのは比較的ちょろいです。今回はwasmの勉強が目的なのでおあつらえ向きと言えます。

ただ、wasmにコンパイルする場合には1つ問題があります。Brainfuckは入出力を扱う必要があり、コマンドラインならば標準入出力がそれに当たります。しかし、wasm自体の主な機能は数値演算で、標準入出力を含むOSの機能を使うための仕組みがないのです。

詳しくは後述しますが、wasmとその実行環境(ホスト環境とも呼ばれます)は関数を相互に受け渡しできるので、OSの機能もそれを通して渡してあげればwasmから使うことができます。ただ、各実装が好き勝手なインターフェースで書いてしまうと、ホスト環境とwasmプログラムが密に結合しかねず、wasmプログラムの可搬性が下がってしまいます。

そこで提案されたのがWASI(WebAssembly System Interface)です。WASIはwasmプログラムからOSの機能を使うための決まりごとのようなものです。WASIに従ってwasmを作れば、WASIに対応する全てのホスト環境で実行することができるのです[2]。上で紹介したWasmtimeやWasmerはWASIランタイムの1つです。

WASIはブラウザ外でのwasm利用を推し進めるために提案された仕様です。ブラウザ外wasmは今後どんどん広まると予想されるので、ここでWASIに対応したコンパイラを書いて勉強しておけば波に乗っていけるかも知れません。

本稿の構成

そんなこんなでコンパイラを書いたので、「WASI準拠のwasmコードの作りかた」の理解をこの記事の目標にしたいと思います。以下に本稿の構成を示しておきます。

  • コンパイラの大まかな構成
  • 実装に必要な範囲でのwasmの基礎
  • WASI対応コードの説明
  • Brainfuckの各命令とそれに対応するwasmコードの説明
  • 実行例

wasmとWASIがメインコンテンツなのでそこが一番分厚くなります。Brainfuckに興味が無い場合はそこだけ読むことも可能です。そして、以下の内容は扱いません

  • ブラウザでの実行方法
  • Rustで書いたコンパイラのソースコードの解説
  • Brainfuck命令の最適化

ブラウザの話は冒頭でも書いた通りで、今回はコマンドラインで使えるwasm(WASI)ランタイムでの実行を前提としています。また、命令の少なさに甘えて素朴に文字列として書き出すだけの雑実装にしたので、コンパイラのコード生成部分には大した工夫はありません。最後のBrainfuckの最適化についてですが、今回の実装は筆者が以前こちらの記事を参考にして書いたJITコンパイラからコードを流用しています。つまり、最適化の詳細はそこに書いてあるのでそっちを参照してねということです。例外として、「連続した同じ命令を1つにまとめる」最適化は一言で説明すれば済むのでさらっと言及します。

それでは本題に移りましょう。

コンパイラの構成

このコンパイラは、Brainfuckプログラムのファイルを入力としてWebAssemblyのバイナリコードをファイル出力するプログラムです。WebAssemblyにはバイナリ形式とそれに対応するテキスト形式(以下wat)があります。ブラウザで実行するAPIが提供されているのは前者ですが、バイナリなので人間が読み書きするにはかなりつらいです。一方、後者は機械語に対するアセンブリのような位置づけのフォーマットで、見た目はほとんどS式なので普通に手書きできる程度には人間に優しいものです。今回は自前で実装するのはwatに生成するところまでにして、バイナリ形式への変換は別のライブラリに任せましょう。公式ツールであるwabtのRustバインディングを使います。

したがって、以下で説明するwasmコードは全てwatです。

watの基礎

この節では、WASIにたどり着くことを目標にwatの基本事項について確認していきます。

なるべくSelf-Containedになるよう努めた結果、記述が肥大化しそうになったため、随所で不自然に説明を省略することでスリム化を図りました。より詳しく知りたい場合はMDNの記事公式ドキュメントなどを参照して下さい。

これからwatコードを見つつ説明していきますが、それに先立って簡易的な実行環境を紹介しておきましょう。次のNode.jsスクリプトは、watファイルをwabtでバイナリに変換してからコンパイルするものです。

run_wat.js
const { readFile } = require("fs/promises");
const wabt = require("wabt");

const importObject = {};

async function main() {
    const wabtMod = await wabt();
    const sourcePath = process.argv[2];
    const source = await readFile(sourcePath, 'utf-8');
    const wasmModule = wabtMod.parseWat(sourcePath, source);
    const { buffer } = wasmModule.toBinary({});
    const module = await WebAssembly.compile(Buffer.from(buffer));
    const instance = await WebAssembly.instantiate(module, importObject);
}

main()

npm i wabtで依存を入れてからnode run_wat.js path/to/wat/fileを実行して下さい。実はこのスプリクトでは何も起こらないのですが、読み込んだwatファイルに不具合があればコンパイルエラーで教えてくれます。importObjectも空で宣言していますが、これは後で使うときに説明します。

module

さて、wasmプログラムはモジュールから構成されています。

(module) ;; これはコメント

わざわざ宣言文が用意されているので複数宣言できそうな気がしてしまいますが、現在の仕様では1プログラムにつき1モジュールのようです。これは何も定義していない空のモジュールですが正しいwatなので、先程のrun_wat.jsに渡せば正常終了するはずです。

モジュール内には様々なコンポーネントを配置できますが、今回必要なのはfunc, global, memory, export, importの5つです。一番重要なのは命令を記述するためのfuncなのでまずはそこから見ていきましょう。

module宣言は必須ですが、これから挙げるコード例では断りなしに省略することがあります。予めご了承下さい。

func

宣言

$fという名前で関数を宣言してみましょう。

(module
    (func $f)
)

名前はオプショナルなので単に(func)とも書けます。名前を付けなくても宣言順に0始まりの添え字が割り当てられるので、参照する際には添え字も使えます(呼び出しについては後述)。

引数を受け取りたい場合は宣言を次のように変更します。

(func $f (param i32) (param i32))

これでi32型の値を2つ引数として受け取る関数を定義できました。

呼び出し

これを他の関数から呼び出すときは次のように書きます。

(func $f (param i32) (param i32))
(func $g
    i32.const 1
    i32.const 2
    call $f ;; `call 0`でもよい
)

wasmはスタックマシンなので、スタックにオペランドをプッシュしておき、それをポップして演算を呼び出していきます。上の例ではi32の12を引数として$fを呼び出しています。

自分はこう書いた方がスタックマシンっぽくて好きなのですが[3]、S式っぽく次のようにも書けます。

(call $f (i32.const 1) (i32.const 2))

「ではどうやって$fの中で引数を使うのか?」という疑問が浮かぶと思いますが、実は今回必要となるのは引数を取る関数の宣言方法だけなのでなんと説明しません。知りたい場合は冒頭で挙げた参考文献をあたって下さい。

数値演算

これは1 + 2を実行する関数です。

(func
    ;; (i32.add (i32.const 1) (i32.const 2))でもよい
    i32.const 1
    i32.const 2
    i32.add
    drop
)

i32.addはスタックから2つ値をポップして、それらを足し合わせた結果をスタックに積む演算です。最後のdropはスタックの最上位を破棄する命令です。スタックに値があると関数の戻り値として解釈されますが、この関数は戻り値がないことになっているためエラーになります。戻り値を設定することもできますが、やはり今回は必要ないのでスルーします。

もちろんi32.add以外にも基本的なi32演算は揃っていますが、他の演算については必要になったときに紹介していくことにしてglobalコンポーネントの説明に移ります。

global

グローバル変数を定義するの用います。

(global $g (mut i32) (i32.const 1))
(func
    global.get $g ;; `global.get 0`も可
    i32.const 2
    i32.add
    drop
)

これも1 + 2を実行して捨てるコードです。ここでは関数で説明したのと同じやり方で、グローバル変数に名前$gを割り当てています。名前を付けなくても添え字でアクセスできるのも同様です。mut i32は変更可能なi32型の値であることを表し、i32.const 1は初期値が1であることを示しています。

次のコードはこのグローバル変数を2に変更するものです。

(func
    i32.const 2
    global.set $g
)

memory

メモリを初期化するためのセクションです。メモリは1バイトずつ格納する単なる一次元配列で、宣言時に最小のページ数を指定します。1ページは64KiBです。

(module
    (memory 1)
)

こうすると1ページのメモリを確保できます。関数と同様、0始まりのインデックスが振られており名前を付けることも可能ですが、現在の仕様では1モジュールにつき1インスタンスしか作れないので名前を付けてもあまり意味はありません[4]

中身は全て0で初期化されており、メモリへの値の保存は関数の中で行います[5]。メモリのオフセット0の位置に1を格納してみましょう。

(func
    ;; (i32.store8 (i32.const 0) (i32.const 1))でも可
    i32.const 0
    i32.const 1
    i32.store8
)

ストア命令には注意が必要です。i32型のストア命令にはi32.store8, i32.store16, i32.storeの3種類があり、使う命令を間違えると意図しない書き込みが行われてしまいます。これらは第一引数のi32値をオフセットとして、それぞれ8ビット、16ビット、32ビットを書き込む命令です。例えば今のメモリの状態がこんな風になっているとします。

番地 値(1バイト)
0 0
1 10
2 20
3 30

この状態で次のような命令を実行するとどうなるでしょうか。

i32.const 0
i32.const 1
i32.store

第一引数はあくまでオフセットなので、0から初めて32ビットを書き込むことになります。1を32ビットの二進数で書くと00000000000000000000000000000001なので、実行後の状態はこうなります。

番地
0 1
1 0
2 0
3 0

1, 2, 3番目のセルが0で上書きされています。n番目のセルだけに8ビット範囲の整数を書き込みたい場合はi32.store8を使います。

メモリからの読み込みについても同様の注意が必要です。i32.load命令は第一引数のオフセット値から32ビットを読み込むので、

番地
0 0
1 10
2 20
3 30

の状態で(i32.load (i32.const 0))を実行するとスタックの一番上には504629760が積まれます。(30 << 24) + (20 << 16) + (10 << 8) + 0と等しいですね。よって、ちょうど0番目のセルのバイトだけを読んでスタックに積みたい場合はこう書かねばなりません。

;; (i32.load8_u (i32.const 0))でもよい
i32.const 0
i32.load8_u

_uというサフィックスは符号なし整数として読み込むという意味です。符号ありとして読み込む場合はi32.load8_sを使いますがやはり今回は使いません。

命令に関する説明は以上になります。実際にはループやifなどの制御構文も使うのですが、それらはWASIの説明には不要なのでコンパイラの生成コードとまとめて説明します。

exportとimport

先程も述べたように、wasmコードとそれを実行するホスト環境はfuncmemoryの受け渡しができます。exportはwasmからホスト環境へ渡すための文です。

add.watというファイルを作り、1 + 2を実行して捨てるだけの関数をmainという名前でエクスポートしてみましょう。

add.wat
(module
    ;; (func (export "main")とまとめることもできる
    (func
        i32.const 1
        i32.const 2
        i32.add
        drop
    )
    (export "main" (func 0))
)

そしてrun_wat.jsmain関数の最後の行にinstance.exports.main()という式を付け足します。

run_wat.js
const { readFile } = require("fs/promises");
const wabt = require("wabt");

const importObject = {};

async function main() {
    const wabtMod = await wabt();
    const sourcePath = process.argv[2];
    const source = await readFile(sourcePath, 'utf-8');
    const wasmModule = wabtMod.parseWat(sourcePath, source);
    const { buffer } = wasmModule.toBinary({});
    const module = await WebAssembly.compile(Buffer.from(buffer));
    const instance = await WebAssembly.instantiate(module, importObject);
    instance.exports.main() // +
}

main()

instance.exportsでwasmからエクスポートされたコンポーネントにアクセスできます。今回はmain関数だけですね。スタックに積んで捨てるだけの関数なので何も起こりませんが正常終了します。これをinstance.exports.hoge()と変えて実行すればエラーになります。エクスポートしていない名前のプロパティはundefinedになるからです。

こんな何も起こらない関数を実行しても全く面白くないですよね。エクスポートした関数に戻り値があればもうちょっとわかりやすい結果が出せるのですが、戻り値の説明をしないという縛りを自らに科したためそれはできません。

そこでimportを紹介します。importを使えば、wasmプログラムが使える関数をホスト環境から渡すことができます。またrun_wat.jsをいじりましょう。

run_wat.js
const importObject = {
    console: {log: console.log}
};

空オブジェクトだったimportObjectを修正しました。これはwasm側から見ると、consoleモジュールのlogという名前にconsole.logが割り当てられたことになります。これをWebAssembly.instantiateに渡せばconsole.logがwasmから参照できます。add.watも変更しましょう。

add.wat
(module
    (import "console" "log" (func $log (param i32))) ;; +
    (func (export "main")
        i32.const 1
        i32.const 2
        i32.add
        call $log
    )
)

importの宣言によってimportObjectで渡したconsole.log$logという名前で参照できるようになりました。これをrun_wat.jsに渡して実行すると3と出力されるはずです。

WASI

前節ではwasmの命令の基礎と、exportimportを通してホスト環境とやり取りする方法を学びました。これで準備が整ったので、WASIの説明に移りたいと思います。

繰り返しになりますが、WASIはOSの機能をwasmから使うための決まりごとです。先程の例では、JavaScriptのconsole.logをインポートしてwasmから使えるようにしました。しかし、consoleモジュールのlogという名前でインポートすることを決めたのは筆者です。それでは第三者がこのプログラムを使いたい場合に不便です。

そこでWASIです。WASIはwasmからのexportとホスト環境からのimportの約束事を定めています。まずwasmプログラムからはエントリーポイントとして_startという名前で関数を、memoryという名前でメモリインスタンスをエクスポートすることが求められます[6]

wasi.wat
(module
    (memory (export "memory") 1)
    (func (export "_start"))
)

このwatコードはWasmerで実行できます。雑にwasi.watという名前で保存してwasmer run wasi.watと叩けば正常終了するはずです。

今度はホスト環境からのインポートです。WasmerやWasmtimeは勝手にインポートオブジェクトを渡してくれているのでwasm側にimport宣言を書いてあげます。

wasi.wat
(module
    (import "wasi_snapshot_preview1" "fd_write" (func $fd_write (param i32 i32 i32 i32) (result i32)))
    (memory (export "memory") 1)
    (func (export "_start"))
)

wasi_snapshot_preview1fd_writeはWASIが定めたモジュールと関数です。fd_writeはファイル書き込みのための関数です。試しに標準出力に0と書き込んでみましょう。なお、ここの説明はWasmtimeのチュートリアルを参考にしています。

wasi.wat
(module
    (import "wasi_snapshot_preview1" "fd_write" (func $fd_write (param i32 i32 i32 i32) (result i32)))
    (memory (export "memory") 1)
    (func (export "_start")
        ;; 文字0のコードポイントをメモリの8番目に格納
        (i32.store8 (i32.const 8) (i32.const 48))

        ;; iov。出力するデータのポインタを指定。今回は8番目
        (i32.store (i32.const 0) (i32.const 8))
        ;; iov。出力する文字列の長さ。今回は1
        (i32.store (i32.const 4) (i32.const 1))

        (call $fd_write
            (i32.const 1) ;; file descriptor
            (i32.const 0) ;; iov配列のポインタ
            (i32.const 1) ;; iovの長さ
            (i32.const 20) ;; 書き込んだバイトの長さを格納するメモリのオフセット
        )
        drop
    )
)

fd_writeの第一引数はファイルディスクリプタの番号です。今回は標準出力なので1になります。第2、第3引数には出力するバイトの情報を表すiovというデータ構造の情報を渡します。iovは配列として渡すので、そのベースポインタと長さを指定して下さい。iovは次のように解釈される8バイトのデータ構造です。

  • 最初の4バイトは出力するデータの入ったメモリのオフセット
  • 続く4バイトは出力するバイト数

今回は文字0のコードポイントである48をメモリの8番目に格納しているので、8を最初の4バイトに入れて、長さ1を続く4バイトに保存しています。iov配列の始まりはメモリの0番地にしたので第2引数に0を渡し、iovは1つしかないので第3引数は1になります。最後の引数には書き込まれたバイト数をfd_writeが保存するためのメモリオフセットを渡します。今回はどこでもよいので適当に決めました。

このコードを先ほどと同じようにWasmerで実行するとコンソールに0が出力されるはずです。Wasmtimeでも同様に実行できます[7]。これでWASIランタイムで実行可能なwatコードが完成しました。

標準入力もほぼ同じAPIで使えるので、ここではコメントを添えたコードの引用だけにとどめます。echo a | wasmer run wasi.watで実行してみて下さい。

wasi.wat
(module
    (import "wasi_snapshot_preview1" "fd_read" (func $fd_read (param i32 i32 i32 i32) (result i32)))
    (import "wasi_snapshot_preview1" "fd_write" (func $fd_write (param i32 i32 i32 i32) (result i32)))
    (memory (export "memory") 1)
    (func (export "_start")
        ;; iov。ファイルから読み込んだバイトを格納するメモリオフセットの指定
        (i32.store (i32.const 4) (i32.const 0))
        ;; iov。読み込むバイト数を指定
        (i32.store (i32.const 8) (i32.const 1))

        (call $fd_read
            (i32.const 0) ;; 標準入力
            (i32.const 4) ;; iov
            (i32.const 1) ;; iov長さ
            (i32.const 20)
        )
        drop

        (i32.store8 (i32.const 4) (i32.const 0))
        (i32.store8 (i32.const 8) (i32.const 1))

        (call $fd_write
            (i32.const 1)
            (i32.const 4)
            (i32.const 1)
            (i32.const 20)
        )
        drop
    )
)

Brainfuckをwatに変換する

ここまでで学んだ知識を駆使すればコンパイラが書けます。まずBrainfuckの仕様をWikipediaから引用します。

処理系は次の要素から成る: Brainfuckプログラム、インストラクションポインタ(プログラム中のある文字を指す)、少なくとも30000個の要素を持つバイトの配列(各要素はゼロで初期化される)、データポインタ(前述の配列のどれかの要素を指す。最も左の要素を指すよう初期化される)、入力と出力の2つのバイトストリーム。
Brainfuckプログラムは、以下の8個の実行可能な命令から成る(他の文字は無視され、読み飛ばされる)。

> ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。
< ポインタをデクリメントする。C言語の「ptr--;」に相当。
+ ポインタが指す値をインクリメントする。C言語の「(*ptr)++;」に相当。
- ポインタが指す値をデクリメントする。C言語の「(*ptr)--;」に相当。
. ポインタが指す値を出力に書き出す。C言語の「putchar(*ptr);」に相当。
, 入力から1バイト読み込んで、ポインタが指す先に代入する。C言語の「*ptr=getchar();」に相当。
[ ポインタが指す値が0なら、対応する ] の直後にジャンプする。C言語の「while(*ptr){」に相当。
] ポインタが指す値が0でないなら、対応する [ (の直後)にジャンプする。C言語の「}」に相当。

例として12345という文字列を出力するBrainfuckプログラムを載せておきます。//以下はコメントの気持ちで書いてます。Brainfuckにはコメント機能などありませんが、無関係な文字は全て無視されるので、以下のプログラムは文法的に正しいBrainfuckプログラムです。

++++++++ ++++++++ ++++++++ ++++++++ ++++++++ ++++++++ // ポインタ0の値を48にする。ASCIIでは0
>+++++ // ポインタ1の値を5に。ループ用
[<+.>-] // ポインタ1が0になるまでポインタ0の値に1を加算して出力

さて、命令以外の要件を見ておきます。「30000個の要素を持つバイトの配列(各要素はゼロで初期化される)」は1ページのメモリインスタンスを作れば足りそうです。「データポインタ」は可変のグローバル変数に格納しましょう。「入力と出力の2つのバイトストリーム」には標準入出力を使います。

以上を踏まえると生成コードの雛形はこんな感じになるでしょう。メモリの0 ...11番目は標準入出力のために使うので、データポインタの初期値は12にしました。

(module
    (import "wasi_snapshot_preview1" "fd_read" (func $fd_read (param i32 i32 i32 i32) (result i32)))
    (import "wasi_snapshot_preview1" "fd_write" (func $fd_write (param i32 i32 i32 i32) (result i32)))

    (memory (export "memory") 1)
    (global $index (mut i32) (i32.const 12)) ;; データポインタ
    (func (export "_start"))
)

それでは命令をwatに変換していきましょう。

>, <

ポインタのインクリメントとデクリメントは、データポインタを保持するグローバル変数を増減することで実現できます[8]

global.get $index
i32.const 1
i32.add ;; デクリメント時には`i32.sub`
global.set $index

現在のデータポインタに1を足してグローバル変数に再保存するだけです。デクリメントの場合はi32.addの代わりにi32.subを使います。

>>>のように命令が連続する場合、1つずつこの一連の命令を呼び出すより2行目のi32.constに命令数を指定することで1つにまとめてあげる方が効率的です。筆者が書いたコンパイラも、連続するポインタとデータのインクリメント・デクリメントの命令は1つにまとめています。

+, -

ポインタの指すデータのインクリメントとデクリメントは、まずデータポインタをスタックに積み、それをオフセットにしてメモリから読み込んだ値に対して加減算します。その結果をデータポインタの指すメモリ領域に保存し直して完了です。

;; 保存用に一個積んでおく
global.get $index

(i32.load8_u (global.get $index))
i32.const 1
i32.add ;; デクリメント時には`i32.sub`

;; 最初に積んだポインタに対しストア
i32.store8

., ,

標準入出力には前節で説明したfd_read, fd_writeを使います。データの読み書きの対象が現在のポインタの指す値になる以外は上で載せたコード例とほとんど同じです。

;; `.`
;; 書き込むバイトが保存されている場所を現在のポインタに指定
(i32.store (i32.const 0) (global.get $index))
;; 標準出力に書き込むバイト数。1バイト
(i32.store (i32.const 4) (i32.const 1))

(call $fd_write
    (i32.const 1)
    (i32.const 0)
    (i32.const 1)
    (i32.const 8) ;; Brainfuckのデータ領域とかぶらない場所を指定
)
drop

;; `,`
;; 標準入力から受け取ったデータを書き込む領域に現在のポインタを指定
(i32.store (i32.const 0) (global.get $index))
;; 標準入力から受け取るバイト数。1バイト
(i32.store (i32.const 4) (i32.const 1))

(call $fd_read
    (i32.const 0)
    (i32.const 0)
    (i32.const 1)
    (i32.const 8)
)
drop

[, ]

最後はループです。ここでは説明を先送りにしたloopifを使います。

これは落とし穴なんですが、loopは実際にはただのラベルです[9]loopと対応するendの間はブロックとして扱われますが、そのブロックの終わりが来たら自動的にloopまで戻る、ということにはなりません

loop $l
    i32.const 1
    drop
end
i32.const 2 ;; endの後そのまま実行される
drop

endの代わりに丸括弧でくくることもできます。

(loop $l
    i32.const 1
    drop
)

br命令を使うとこれをloopのブロックで無限ループが作れます。loopも例の如く宣言時に付けた名前か、連番で付けられるラベルのインデックスで参照できます。br $nameで指定したラベルにジャンプします。

loop $l
    i32.const 1
    drop
    br $l
end
i32.const 2 ;; 永遠に実行されない
drop

このloopifを組み合わせればBrainfuckの[]を再現できます。ifはスタックからポップした値が0以外ならそのまま次の命令を実行し、0ならば対応するendまでジャンプします。

(i32.load8_u (i32.const 0))
if ;; メモリの0番目が0なら対応するendへ
    i32.const 1
    drop
end

この挙動はBrainfuckの[とまるで同じですね。なので、対応する]に出会ったときに戻ってくるためのloopを宣言してifを入れるだけの簡単なお仕事になります。

(loop $loop_0)
    (i32.load8_u (global.get $index)) ;; 現在のポインタの値を積む
    if ;; 0ならendまで飛ぶ
        ;; `[`と対応する`]`の間の命令が入る
        (br $loop_0) ;; 対応する`[`にジャンプ
    end ;; ifのend
end ;; loopのend

ただし2点だけ注意があります。まずloopのラベルです。[]は入れ子になりうるので、]に出会ったときに対応する[loopラベルを覚えている必要があります。上のコード例では$loop_0という固定値にしていますが、実際には[と出会う度に発行したユニークなインデックスをラベルとし、スタックのようなデータ構造に保持しておき(wasmのスタックではありません)、]に出会ったらポップして使えばよいでしょう。

また、]の仕様では「ポインタが指す値が0でないなら」ジャンプする、とありますがここでは問答無用でジャンプしています。[のときに行う現在のポインタの値のチェックで代用できるからです。]のときにチェックしても問題はないのですが、ジャンプしてしまった方が実行速度が向上しました。

実際には他にも命令の最適化を施していますが、以上のように変換していけば最低限動くwasmコードが生成できるはずです。実行してみましょう。

実行

リポジトリにはBrainfuckのコードも入れておきました。Rustの処理系とWasmerかWasmtimeがあればクローンするだけで試すことが可能です。

cargo run bf-example/mandelbrot.bf
wasmer run mandelbrot.wasm

生成したwasmをそのまま実行すると結構遅いですが、Wasmerにnativeコンパイルしてもらえばかなり速くなります。

wasmer compile --native --llvm -o mandelbrot.so mandelbrot.wasm
wasmer run ./mandelbrot.so

それでは皆さんよいwasmライフを!

脚注
  1. 標準入力の扱いが若干面倒かもしれません ↩︎

  2. Software Design 2021年3月号のwasm特集にも解説があります ↩︎

  3. あとコード生成するときに楽です ↩︎

  4. 将来的には複数宣言できるかもしれません https://webassembly.github.io/spec/core/syntax/modules.html#memories ↩︎

  5. 実際にはdataを使って格納することも可能 https://webassembly.github.io/spec/core/syntax/modules.html#data-segments ↩︎

  6. WASIはwasmのモジュールを「コマンド」と「リアクター」の二種類に分けており、_startはコマンドの仕様です。リアクターが何者なのかは正直よくわかりません。 https://github.com/WebAssembly/WASI/blob/main/design/application-abi.md ↩︎

  7. もちろん自分で書いたfd_writeの実装を与えることもできます https://fits.hatenablog.com/entry/2020/04/29/210734 ↩︎

  8. セルのオーバーフロー時の挙動は定義されていないようです https://roodni.hatenablog.com/entry/2019/12/09/232114 ↩︎

  9. こちらも参照 https://qiita.com/blackenedgold/items/704141afbfafef0df254 ↩︎