IK.AM

@making's tech note

Brainf*ck => WebAssemblyおよびJVMバイトコードなコンパイラをJavaで書いた

🗃 {Programming/WebAssembly/Brainf*ck}
🏷 Java 🏷 WebAssembly 🏷 Brainf*ck 🏷 Wasm Workers Server 
🗓 Updated at 2023-07-18T08:02:21Z  🗓 Created at 2023-07-02T04:20:47Z   🌎 English Page

WebAssemblyの勉強のため、Brainf＊ckのコンパイラを書いてみました。

https://github.com/making/bfc

WebAssemblyのバイナリフォーマットを読む前に、同じスタックマシンであるJVMバイトコードのフォーマットの方が馴染みがあって書きやすいだろうと思い、 JVMバイトコードへの変換から先に実装しました。

ASMのようなライブラリは一切使用しておらずフルスクラッチで実装したので、GraalVMを使ってnative image化するのはとても簡単でした。

native binaryはbrewでインストールできます。

brew install making/tap/bfc

Macの場合はIntel用のバイナリしか用意していません。(Apple Silicon用に誰かビルドしてください...) → Apple Siliconに対応しました

GraalVMがインストールされていれば以下のコマンドでビルドできます。

git clone https://github.com/making/bfc
cd bfc
./mvnw package -Pnative
install target/bfc /usr/local/bin/

あるいは実行可能なjarファイルとしてもビルドできます。

./mvnw package
java -jar ~/git/bfc/target/bfc-*.jar --help

bfcの使い方

まずはBrainf＊ckファイルを用意します。

echo '++++++++[>+++++++++<-]>.<++++[>+++++++<-]>+.<>+++++++.<>.<>+++.<++++++[>-------------<-]>-.<+++++[>+++++++++++<-]>.<++++[>++++++<-]>.<>+++.<>------.<>--------.<++++++[>-----------<-]>-.<' > hello.bf

bfcはインタプリタとしても使えます。

$ bfc hello.bf 
Hello World!

JVMバイトコードにコンパイル。

$ bfc hello.bf -o hello.class
$ java hello
Hello World!
$ javap hello 
public class hello {
  public static void main(java.lang.String[]);
}

stackmap frameの理解が足りずバイトコードのバージョンは50.0(Java 1.6相当)です

$ file hello.class 
hello.class: compiled Java class data, version 50.0 (Java 1.6)

WebAssemblyにコンパイル。WASI preview1の標準入出力に対応しています。

$ bfc hello.bf -o hello.wasm
$ wasmtime hello.wasm
Hello World!

その他、Java、JavaScript、WAT (WebAssembly Text Format)にも変換できるので、こちらの方が何をおこなっているのか理解しやすいです。

$ bfc hello.bf -o hello.java 
$ java hello.java
Hello World!
$ cat hello.java
実行結果 
public class hello {

    public static void main(String[] args) {
        final int[] memory = new int[1024];
        int pointer = 0;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
    while (memory[pointer] != 0) {
        pointer += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        pointer += -1;
        memory[pointer] += -1;

    }
        pointer += 1;
        System.out.print((char) memory[pointer]);
        pointer += -1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
    while (memory[pointer] != 0) {
        pointer += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        pointer += -1;
        memory[pointer] += -1;

    }
        pointer += 1;
        memory[pointer] += 1;
        System.out.print((char) memory[pointer]);
        pointer += -1;
        pointer += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        System.out.print((char) memory[pointer]);
        pointer += -1;
        pointer += 1;
        System.out.print((char) memory[pointer]);
        pointer += -1;
        pointer += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        System.out.print((char) memory[pointer]);
        pointer += -1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
    while (memory[pointer] != 0) {
        pointer += 1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        pointer += -1;
        memory[pointer] += -1;

    }
        pointer += 1;
        memory[pointer] += -1;
        System.out.print((char) memory[pointer]);
        pointer += -1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
    while (memory[pointer] != 0) {
        pointer += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        pointer += -1;
        memory[pointer] += -1;

    }
        pointer += 1;
        System.out.print((char) memory[pointer]);
        pointer += -1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
    while (memory[pointer] != 0) {
        pointer += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        pointer += -1;
        memory[pointer] += -1;

    }
        pointer += 1;
        System.out.print((char) memory[pointer]);
        pointer += -1;
        pointer += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        System.out.print((char) memory[pointer]);
        pointer += -1;
        pointer += 1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        System.out.print((char) memory[pointer]);
        pointer += -1;
        pointer += 1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        System.out.print((char) memory[pointer]);
        pointer += -1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
        memory[pointer] += 1;
    while (memory[pointer] != 0) {
        pointer += 1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        memory[pointer] += -1;
        pointer += -1;
        memory[pointer] += -1;

    }
        pointer += 1;
        memory[pointer] += -1;
        System.out.print((char) memory[pointer]);
        pointer += -1;
    }
}

--optimizeオプションをつけると生成されるコードが少し最適化されます。Javaで見るとわかりやすいです。

bfc hello.bf -o hello.java --optimize
cat hello.java
実行結果 
public class hello {

    public static void main(String[] args) {
        final int[] memory = new int[1024];
        int pointer = 0;
        memory[pointer] += 8;
    while (memory[pointer] != 0) {
        pointer += 1;
        memory[pointer] += 9;
        pointer += -1;
        memory[pointer] += -1;

    }
        pointer += 1;
        System.out.print((char) memory[pointer]);
        pointer += -1;
        memory[pointer] += 4;
    while (memory[pointer] != 0) {
        pointer += 1;
        memory[pointer] += 7;
        pointer += -1;
        memory[pointer] += -1;

    }
        pointer += 1;
        memory[pointer] += 1;
        System.out.print((char) memory[pointer]);
        pointer += 0;
        memory[pointer] += 7;
        System.out.print((char) memory[pointer]);
        pointer += 0;
        System.out.print((char) memory[pointer]);
        pointer += 0;
        memory[pointer] += 3;
        System.out.print((char) memory[pointer]);
        pointer += -1;
        memory[pointer] += 6;
    while (memory[pointer] != 0) {
        pointer += 1;
        memory[pointer] += -13;
        pointer += -1;
        memory[pointer] += -1;

    }
        pointer += 1;
        memory[pointer] += -1;
        System.out.print((char) memory[pointer]);
        pointer += -1;
        memory[pointer] += 5;
    while (memory[pointer] != 0) {
        pointer += 1;
        memory[pointer] += 11;
        pointer += -1;
        memory[pointer] += -1;

    }
        pointer += 1;
        System.out.print((char) memory[pointer]);
        pointer += -1;
        memory[pointer] += 4;
    while (memory[pointer] != 0) {
        pointer += 1;
        memory[pointer] += 6;
        pointer += -1;
        memory[pointer] += -1;

    }
        pointer += 1;
        System.out.print((char) memory[pointer]);
        pointer += 0;
        memory[pointer] += 3;
        System.out.print((char) memory[pointer]);
        pointer += 0;
        memory[pointer] += -6;
        System.out.print((char) memory[pointer]);
        pointer += 0;
        memory[pointer] += -8;
        System.out.print((char) memory[pointer]);
        pointer += -1;
        memory[pointer] += 6;
    while (memory[pointer] != 0) {
        pointer += 1;
        memory[pointer] += -11;
        pointer += -1;
        memory[pointer] += -1;

    }
        pointer += 1;
        memory[pointer] += -1;
        System.out.print((char) memory[pointer]);
        pointer += -1;
    }
}

このほかにも[-]のように"現在の値が0になるまでデクリメントするループ"を"直接0に設定する"ような最適化も入っています。

いくつかのサンプルファイルは https://github.com/making/bfc/tree/develop/examples においてあります。

定番FizzBuzzの例。WASMの場合。

$ curl -sL https://github.com/making/bfc/raw/develop/examples/fizzbuzz.bf | bfc - -o fizzbuzz.wasm
$ wasmtime fizzbuzz.wasm
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
22
23
Fizz
Buzz
26
Fizz
28
29
FizzBuzz
31
32
Fizz
34
Buzz
Fizz
37
38
Fizz
Buzz
41
Fizz
43
44
FizzBuzz
46
47
Fizz
49
Buzz
Fizz
52
53
Fizz
Buzz
56
Fizz
58
59
FizzBuzz
61
62
Fizz
64
Buzz
Fizz
67
68
Fizz
Buzz
71
Fizz
73
74
FizzBuzz
76
77
Fizz
79
Buzz
Fizz
82
83
Fizz
Buzz
86
Fizz
88
89
FizzBuzz
91
92
Fizz
94
Buzz
Fizz
97
98
Fizz
Buzz

JVMバイトコードでも同じように動作します。

$ curl -sL https://github.com/making/bfc/raw/develop/examples/fizzbuzz.bf | bfc - -o fizzbuzz.class
$ java fizzbuzz
1
2
.. (略) ..
Fizz
Buzz

複雑なBrainf＊ckの例として使われるマンデルブロ集合の例。(こちらはJVMバイトコードだと動きません。stackmap frameに詳しい方、助けてください...)

$ curl -sL https://github.com/making/bfc/raw/develop/examples/mandelbrot.bf | bfc - -o mandelbrot.wasm
$ time wasmtime mandelbrot.wasm
image

--optimizeオプションをつけると実行時間が約37%短縮されました。

$ curl -sL https://github.com/making/bfc/raw/develop/examples/mandelbrot.bf | bfc - -o mandelbrot.wasm --optimize
$ time wasmtime mandelbrot.wasm
image

Wasm Workers Serverにデプロイ

bfcでコンパイルしたWASMはWASIに対応しているので、Brainf＊ckで書いたコードをWasm Workers ServerのWorkerとしてデプロイしてHTTPで公開できます🤯

mkdir app
echo '--[-->+++++<]>.+[---->+<]>+++.-[->+++<]>+.---.--[--->+<]>-.+[->+++<]>++.[->+++<]>-.[----->+<]>.[->+++++<]>.++[->++<]>.-[->+++++<]>++.+++++++..+++.[--->+<]>-----.---[->+++<]>.++++++++++.--[--->+<]>--.------.[->+++++<]>.+.++++++++++.----------.[----->++<]>-.+.+[->+++<]>++.--[--->+<]>-.+.--.+[-->+++++<]>.[----->+<]>.--------.--..----.----------.-[->+++<]>-.-.--[--->+<]>--.++++[->+++<]>.+[-->+<]>+++.--.-[--->++<]>.[----->+<]>.--[--->+<]>--.-----.+++++++++++.+++++++.++++[->+++<]>.-[->+++<]>.----------.[->+++<]>++.---.----.+++.+.+++++++++++++.+.+[-->+++++<]>.[----->+<]>.[--->++<]>-.+[---->+<]>+++.>+[--->++<]>++.[-->+<]>+.+[-->+++<]>++.[->+++++<]>++.+++++++++.---------.+++++++++++++.+++[->+++<]>++.--[--->+<]>-.+++[->+++<]>.-.[->+++<]>+.-[-->+++<]>.-----[->++<]>-.-[---->+<]>++++.[----->+<]>.[->+++++<]>.[-->+++++++<]>.-[->+++<]>-.--[--->+<]>--.------.+[----->++<]>+.-[----->++<]>-.--------.+++.-------.------.+++++++++++++.+.+[++>---<]>-.+[--->++<]>-.++++[->+++<]>.+++++++++++++.++++.+[->+++<]>.+++++++++++++.[--->+<]>----.>--[-->+++<]>.+[--->+<]>++.----------.[--->++<]>-.+++++++++++.--[-->+++++<]>.[----->+<]>.[--->++<]>-.++..' > index.bf
bfc index.bf -o app/index.wasm --optimize

生成したWASMのWorkerをwasmtimeで実行してみます。次のようなJSONが出力されます。

$ wasmtime app/index.wasm 
{"data":"Hello Wasm!","status":200,"base64":false,"headers":{"X-Generated-By":"wasm-workers-server"},"kv":{}}

Wasm Workers Serverのインストール

curl -fsSL https://workers.wasmlabs.dev/install | bash

appディレクトリをrootにして、Wasm Workers Serverを起動

$ wws app 
⚙️  Preparing the project from: app
⚙️  Loading routes from: app
⏳ Loading workers from 1 routes...
✅ Workers loaded in 11.09542ms.
    - http://127.0.0.1:8080/
      => app/index.wasm
🚀 Start serving requests at http://127.0.0.1:8080

HTTPでアクセス

$ curl -v http://127.0.0.1:8080
> GET / HTTP/1.1
> Host: 127.0.0.1:8080
> User-Agent: curl/7.88.1
> Accept: */*
> 
< HTTP/1.1 200 OK
< content-length: 11
< x-generated-by: wasm-workers-server
< content-type: text/html
< date: Sun, 02 Jul 2023 01:49:20 GMT
< 
Hello Wasm!

ちゃんと返りました。

WebAssemblyの勉強のため、Brainf＊ckのコンパイラを書いてみました。

学んだ順番としては

でした。結果的にはWASMの方がJVMよりも簡単でした。実装中はxxd、やjavap、wat2wasm、wasm2watを多用しました。

WASMの勉強には以下の本が役立ちました。

✒️️ Edit  ⏰ History  🗑 Delete