ブラウザで動く高速 Brainfuck 実行環境を作った

実物

https://yukikurage.github.io/brainf__k/

試しに Brainfuck のライブラリ群 の mandelbrot.b を実行してみると，自分の環境 (Ryzen 7 3700U / Firefox) では大体 3 秒前後でした．

Chromium 系のブラウザですと途中にコードの最適化が入って遅くなる傾向があります．(自分の環境では 10 秒前後)

今のところ観測範囲内でこれより速く，ブラウザ上かつ非同期で動くものは見つけられていません．もし見かけたらスーパーの値引きシステムでもっと高速化を頑張るので，コメント欄などに書き込んで頂けると幸いです

リポジトリ

https://github.com/yukikurage/brainf__k

仕組み

• 利用者に画面を提供する(インターフェース)
• 利用者が入力した文字列をトランスパイルする(トランスパイラ)
• トランスパイルされたコードを Web Worker で動かす(実行)

の 3 つのタスクに大まかに分かれています．それぞれ詳しく説明していきます

インターフェース

まず，アプリケーションのインターフェース，およびトランスパイラは PureScript で書かれています
DOM 操作には Halogen Hooks を用いました．これは PureScript 版の React Hooks のようなライブラリで，ロジックを含むアプリケーションが比較的簡単に書けます．
デザインには tailwind を用いました．tailwind は クラス名さえ決められる枠組みであれば導入できるので， Halogen のようなまともな UI フレームワークがないフレームワークにも入れる事ができて便利です．
コンポーネントは画面全体で 1 つです．トランスパイラの方に専念したかったのでこちらはかなり適当に書いています.

トランスパイラ

https://github.com/yukikurage/brainf__k/blob/master/src/Brainfk/System/Transpile.purs

トランスパイラはこのアプリケーションの肝です．入力されたコード，および標準入力から JavaScript のコードを生成します．
ここで大事なのが，コードの最適化です．

例えば

>>+++

というようなコードは愚直にトランスパイルすると

p++;
p++;
m[p]++;
m[p]++;
m[p]++;

でしょう．(ここでメモリがm，ポインタがpとします．)

が，このままでは非効率なので

p += 2;
m[p] += 3;

とすることができます．

さらに短くすると

m[p + 2] += 3;

となります．

このように，処理の一部をトランスパイラが肩代わりすることで，高効率なコードを生成します．

さて，最適化は大きく分けて

• 遅延評価(っぽいもの)
• ループ最適化

の 2 つの方針で行っています．それぞれ説明していきます．

遅延評価(っぽいもの)

まず，現在のポインタから操作対象へのポインタへのずれを表す Int 型の変数 pointer を用意します．初期値は 0 です．意味は後述します．

そして，String 型の transpiled 変数を用意し，これにトランスパイルされたコードを保存していくことにします．初期値は ""です．

さらに，変数操作を貯めておく連想配列 stack を用意します．

これの中身の状態を次のように書くとしましょう．

[key0: value0, key1: value1,...]

また，value へのアクセスを次のように書きます．

stack[2]

stack の初期値は [] です．

ここで，stack の key は Int 型， value は Operation Int 型です．
Operation a は自前で定義した型で，変数への操作を表す型です．定義は次のようになっています．

data Operation a = Set a | Add a

Setは変数への代入，Addは変数への値の追加を表しています．

例えば，Set 1 は変数に 1 を代入する事を表していて，Add 2 は変数に 2 を足し算する事を表しています．

操作の合成関数 appendOp を定義します．

appendOp _ (Set m) = Set m
appendOp (Add n) (Add m) = Add $ n + m
appendOp (Set n) (Add m) = Set $ n + m

appendOp x y は 操作 x をしてから操作 yをする操作を表します．例えば， appendOp (Set 2) (Add 3)はSet 5です．(変数に 2 を代入してから 3 を足すのは，5 を代入するのと同じ事であるため．)

stack の key は現在のポインタから操作対象のポインタへのずれを表しています．ここら辺は言葉だと分かりにくいので具体例を示します．

>>>++<-

をトランスパイルすることを考えます．まず，一文字目を読みます．>ポインタを右に 1 つずらす操作ですね．

いきなりトランスパイルはせず，そのかわりに，pointer をインクリメントします．

pointer == 1
stack == []
transpiled == ""

同様に続く 2 つでも pointer をインクリメントします．

pointer == 3
stack == []
transpiled == ""

このような操作をトランスパイラの状態から別のトランスパイラの状態への変換だと考えて，incr 1 と書きます．
今後，「>に対応する操作は incr 1」などというように書きます

次の + では，stack に 現在の pointer をキー，Add 1 を Value として追加します．

pointer == 3
stack == [3: Add 1]
transpiled == ""

次の + でも同様の操作を行うのですが，この操作の際に同じキーを持った値が stack にすでに存在するなら，appendOp で合成します．

pointer == 3
stack == [3: appendOp (Add 1) (Add 1)] == [3: Add 2]
transpiled == ""

このような操作を， add 3 (Add 1) と書きます．すなわち，+ に対応する操作は add pointer (Add 1) です．

次の < に対応する操作は incr -1，続く - に対応する操作は add pointer (Add -1) です．

最終的にトランスパイラの状態は次のようになります．

pointer == 2
stack == [3: Add 2, 2: Add (-1)]
transpiled == ""

さて，トランスパイルされたコードtranspiledは次のようになっています．

そう，今回は変数への操作のみでそれらを使用しなかったので，トランスパイルされたコードはこれで良いのです．

次は元の brainfuck コードの最後で出力をしてみます．

>>>++<-.

追加する前のトランスパイラの最終状態は

pointer == 2
stack == [3: Add 2, 2: Add (-1)]
transpiled == ""

です．まず，これをこのように変換します．

pointer == 2
stack == [3: Add 2]
transpiled == "m[p+2]+=-1;"

stack の 2 を削除して，transpiled に対応する操作を書き込んでいます．

このうち， transpiled に書き込むような操作を write "m[p+2]+=-1;" などというように書きます．

また，stack から値を削除するような動作は delete 2 などというように書きましょう．

そうすると，この一連の操作は write "m[p+2]+=-1;" してから delete 2 する，と書けます．このような操作を複数まとめたものを次のように書きましょう．

use 2:
  write "m[p+2]+=-1;"
  delete 2

これで，今後 use 2 と書けば， write "m[p+2]--;" してから delete 2 する，という意味になります．use の一般化した定義も載せておきましょう．

use n:
  write "m[p+${n}]+=${stack[n]};"
  delete n

文字列に変数を埋め込むのを ${n} と書いています．

さらにアウトプットのため，渡された文字を出力する関数 f に中身を渡すコードを追加します．(ここで f の中身は気にする必要はありません．)

write "f(m[p+2]);"

一般化すると

write "f(m[p+${pointer}]);"

最終的な . に対応する操作は次のようになります．

use pointer
write "f(m[p+${pointer}]);"

これらの操作を状態

pointer == 2
stack == [3: Add 2, 2: Add (-1)]
transpiled == ""

に適用すると

pointer == 2
stack == [3: Add 2]
transpiled == "m[p+2]+=-1;f(m[p+2]);"

となります．最終的なトランスパイル結果は "m[p+2]+=-1;f(m[p+2]);" です．ちゃんと動きそうですね！

同様に , に対応する操作は

use pointer
write "m[p+${pointer}]=i[x];x++;"

です (ここで， i は input 文字列，x はそのインデックスを表していますが，あまり本質ではないので気にしなくてよいです．)

まとめ

それぞれのコマンドに対応する操作一覧です

• >

  incr 1
  

• <

  incr -1
  

• +

  add pointer (Add 1)
  

• -

  add pointer (Add -1)
  

• .

  use pointer
  write "f(m[p+${pointer}]);"
  

• ,

  use pointer
  write "m[p+${pointer}]=i[x];x++;"
  

ここで

use n:
  write "m[p+${n}]+=${stack[n]};"
  delete n

ループが無ければこれで期待された最適化がされたコードが transpiled に吐かれます．

ループ最適化

長くなってきたので次回
一つ予告しておくとループの種類によって 4 種類 の場合分けをしています．大変でした．

実行

ここは軽く流したいと思います．
まず，なんやかんやしてトランスパイルされたコードを次のような形式の文字列にします．

self.addEventListener(
  "message",
  () => {
    let p = 0;
    let m = new Uint8Array(30000);
    let i = "";
    let x = 0;
    let f = postMessage;

    // ここからトランスパイル結果
    m[p + 2] += -1;
    f(m[p + 2]);
    // ここまで

    f("f");
  },
  false
);

この文字列を Blob にして URL を生成して Worker に渡し， あとは postMessage をすれば勝手に走ってくれます．便利な時代だ……．

const workerUrl = URL.createObjectURL(new Blob(["...さっきの文字列..."]));
const worker = new Worker(workerUrl);
worker.postMessage("");

非同期処理などはイベントを追加して頑張っています．例えば出力を順次更新するためにこうしています．

let output = "";
worker.addEventListener(
  "message",
  (e) => {
    if (e.data !== "f") {
      try {
        output += String.fromCodePoint(e.data);
      } catch (e) {
        worker.terminate();
        URL.revokeObjectURL(workerUrl);
      }
    }
  },
  false
);

いかが

でしたか

ループ最適化については時間があったら書きます．