Zenn
Open13

Brainfuckの処理系

Rust
Brainfuck
hotate29hotate29

普通に実行するだけだと面白くないので、Brainfuckのコードに最適化をかけてみたい。Brainfuckのコードは定形ループがいくつかあるので、それを高レベルな命令に変換する感じ。

最適化する際は、コードを木構造ぽい感じにすると扱いやすそう。枝を切って付け替えるだけの簡単なお仕事。

最近ハマっているRustで書く。

hotate29hotate29

命令

  • PtrIncrement(usize)
  • PtrDecrement(usize)
  • Add(u8)
  • AddTo(usize)
  • AddToRev(usize)
  • Sub(u8)
  • SubTo(usize)
  • SubToRev(usize)
  • MulAdd(usize,u8)
  • MulAddRev(usize,u8)
  • Copy(usize)
  • CopyRev(usize)
  • ZeroSet
  • Input
  • Output

enumで持つ

*Rev系は、対応する命令に符号付き整数を持たせると不要になるけど、キャストが面倒くさい。（とりあえず実装してみる？）

hotate29hotate29

最適化

中間表記

コードを木構造ぽく持つ。

[+.]-.
を
root
|-while
| |-[Add, Output]
|-[Sub, Output]

のように解釈する（雑）。

ループを普通の命令列に変えるのがほとんどなので、命令列を直接触るのはあまり考えていない。

Pass？

最適化処理のトレイトをユニット構造体に実装する。

再帰関数で木構造を辿りながら、いろんな最適化パターンに当てはめて最適化していく。

条件

ループを命令列に変換する最適化が基本になる。

最適化出来るループと、出来ないループがあるのでそれを判定しないといけない。現時点での判定条件は

  • ループ開始時と終了時のポインターの位置が同じ（[->+<]のような）
  • ループ開始時にポインターが指している値が終了時には0になる（上記と同じようなコード）
  • IOが無い

の3つを満たすと、最適化をする。

hotate29hotate29

出力

Cにトランスコンパイル。（文字列を繋げるだけ）

LLVMを触ってみたいけど、しばらく先になりそう。

実行

インタープリンターを用意する。先述の木構造を再帰関数で処理するのは遅いので、命令の配列に直して実行する。"今どこを実行しているか"の数値を動かしながら実行する、よくあるアレ。

先述の形式で実行すると、ステップ実行の実装が比較的楽？

メソッドを呼び出したら1ステップという感じが素直だけど、イテレーターにした方が良い？（()じゃなくてメモリの参照と実行地点を返すと（brainfuckコードの）デバッグが楽になりそう）

hotate29hotate29

メモリ上の値と定数のenumにしたら色々楽なんじゃないか説。

enum Value {
    Const(u8),
    Memory(isize),
}
hotate29hotate29

>+++++++++[-<++++++++>]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>++++++++[<++++>-]<+.[-]++++++++++.