よみとばしポイント
限界派遣SESのみなさんお疲れ様です。私も限界派遣SESです。
ひとりアドカレ15日目です。
TuringCompleteをやってからずっとやりたかったBrainf**kインタプリタを作成していこうと思います。
なお、この記事は前の記事を読んだりTuringCompleteをプレイすると理解できる気がします。
筆者はこんなクソ記事読むより購入して遊ぶことをオススメします。
Brainf**kとは？
Brainf**k(以下BF)は、2004年にUrban Müllerによって作成された、最小のチューリング完全言語です。
BFは、8つの命令のみで構成されています。
| 命令 | 意味 |
|---|---|
+ |
ポインタが指す値をインクリメントする |
- |
ポインタが指す値をデクリメントする |
> |
ポインタをインクリメントする |
< |
ポインタをデクリメントする |
[ |
ポインタが指す値が0なら、対応する]の直後 |
] |
ポインタが指す値が0でないなら、対応する[の直後 |
, |
標準入力から1バイト読み込み、ポインタが指す先に書き込む |
. |
ポインタが指す値を標準出力する |
これによってHello Worldを出力するBFプログラムは以下のようになります。
>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]
>++++++++[<++++>-] <.>+++++++++++[<++++++++>-]<-.--------.+++
.------.--------.[-]>++++++++[<++++>- ]<+.[-]++++++++++.
見ても読めませんね。
TuringCompleteでBFインタプリタを作成する
まず、インタプリタを作る前にいくつかの課題があります。
ベースとなるCPU
ベースとなるCPUはレベルFUNCTIONS終了時点で作成しているCPUをベースに使用しています。
そのため、スタックやメモリが搭載されたCPUを使用しています。
これだけだと、ファイル読み込みや出力表示などの機能がないため、それらを追加していきます。
ファイル読み込み
TuringCompleteのサンドボックスモードではFile Loaderを使ってファイルを読み込むことができます。
File Loaderを配置すると、ファイルを選択するダイアログが表示されるので実行するファイルを選択します。
ConsoleとLink Componentsで接続することで、BFファイルの中を確認することができます。
今回は上記のHello Worldプログラムを設定しています。
また、今回はファイルIOのことをあんまり考えていなかったので、レジスタ5番を廃止して、ファイルIOのカーソルの位置を管理するようにしました。
データ取得の際もINPUTの部分から読み込むようになっているため、CPUがBF専用みたいになってしまっています。
しかし、BFを実行できるので実質TuringCompleteですね？
出力の表示
先ほどConsoleはファイルの中身を確認するために使用しましたが、出力を表示するためにも使用できます。
出力用のRAMを用意し、Consoleと接続します。
また出力されるたびに、Counterインクリメントして、メモリアドレスをインクリメントするようにしました。
プログラムの実装
このBFインタプリタを作る上でレジスタは固定の役割をもたせるようにしています。
| レジスタ | 機能 |
|---|---|
| REG0 | BFのメモリアドレスの管理 |
| REG1 | BFの命令の管理 |
| REG2 | ループの開始アドレス |
| REG3 | メモリアドレスの値 |
| REG4 | メモリアドレスの値のインクリメント |
また、BFの命令に対応する値を定数として設定しています。
| 定数名 | 命令 |
|---|---|
| ptr_inc | > |
| ptr_dec | < |
| inc | + |
| dec | - |
| out | . |
| loop_s | [ |
| loop_e | ] |
| main_end | EOF |
上記を基にBFの命令を実装していきます。
メインループ
まずはBFの命令を実行するメインループを作成します。
const ptr_inc 62
const ptr_dec 60
const inc 43
const dec 45
const out 46
const loop_s 91
const loop_e 93
const main_end 0
label MAIN_LOOP
ORi INPUT 0 REG1
IF_EQi REG1 ptr_inc ptr_increment
IF_EQi REG1 ptr_dec ptr_decrement
IF_EQi REG1 inc increment
IF_EQi REG1 dec decrement
IF_EQi REG1 out output
IF_EQi REG1 loop_s loop_start
IF_EQi REG1 loop_e loop_end
IF_NOT_EQi REG1 main_end MAIN_LOOP
label STOP
IF_EQ REG0 REG0 STOP
constというのはこのゲームにおいての定数値を表します。
それぞれの命令に対応する値を設定しています。
IF_EQi REG1 ptr_inc ptr_incrementという命令がありますが、これはREG1の値とptr_incの値が等しい場合、ptr_incrementのラベルにジャンプするという命令です。
また、IF_NOT_EQi REG1 main_end MAIN_LOOPという命令がありますが、これはREG1の値とmain_endの値が等しくない場合、MAIN_LOOPのラベルにジャンプするという命令です。
これにより、空文字が入力されるまでBFの命令を実行することができます。
TypeScriptで書くと以下のようなイメージです。
実際には関数ではなく、ジャンプ命令なので関数呼び出し後はメインループの先頭に戻るようになります。
const ptr_inc = 62;
const ptr_dec = 60;
const inc = 43;
const dec = 45;
const out = 46;
const loop_vs = 91;
const loop_e = 93;
const main_end = 0;
while (true) {
const input_value = input();
switch (input_value) {
case ptr_inc:
ptr_increment();
break;
case ptr_dec:
ptr_decrement();
break;
case inc:
increment();
break;
case dec:
decrement();
break;
case out:
output();
break;
case loop_vs:
loop_start();
break;
case loop_e:
loop_end();
break;
case main_end:
break; // メインループを終了
default:
continue; // 未定義の命令はスキップ
}
}
ポインタのインクリメント
次に、>に対応するptr_incrementを実装します。
label ptr_increment
ADDi REG0 1 REG0
IF_EQ REG0 REG0 MAIN_LOOP
labelは先程のメインループでの呼び出し先になります。
ADDi REG0 1 REG0という命令は、REG0の値に1を加算し、REG0に代入するという命令です。
また、IF_EQ REG0 REG0 MAIN_LOOPという命令は、REG0の値とREG0の値が等しい場合、MAIN_LOOPのラベルにジャンプするという命令です。
これは常にTrueとなるため、純粋なJUMP命令と同じですが、JUMP命令はこのCPUには存在しないため、このような形で実装しています。
ポインタのデクリメント
ほとんどptr_incrementと同じですが、<に対応するptr_decrementを実装します。
label ptr_decrement
SUBi REG0 1 REG0
IF_EQ REG0 REG0 MAIN_LOOP
違うのは、SUBi REG0 1 REG0という命令で、REG0の値から1を減算し、REG0に代入するという命令です。
メモリのインクリメント
+に対応するincrementを実装します。
label increment
LOAD_MEM 0 REG0 REG3
ADDi REG3 1 REG4
SAVE_MEM REG0 REG4 0
IF_EQ REG0 REG0 MAIN_LOOP
まず、LOAD_MEM 0 REG0 REG3という命令は、REG0の値をメモリアドレスREG3から読み込み、REG3に代入するという命令です。
0の位置は利用されていないため、ダミーの値を入れています。(私のCPUの実装では0以外だとバグが発生する)
次に、ADDi REG3 1 REG4という命令は、REG3の値に1を加算し、REG4に代入するという命令です。
最後に、SAVE_MEM REG0 REG4 0という命令は、REG4の値をメモリアドレスREG0に書き込むという命令です。
ここでも最後の0はダミーの値です。
メモリのデクリメント
-に対応するdecrementを実装します。
label decrement
LOAD_MEM 0 REG0 REG3
SUBi REG3 1 REG4
SAVE_MEM REG0 REG4 0
IF_EQ REG0 REG0 MAIN_LOOP
先ほどと実装はほとんど一緒で、ADDiの部分がSUBiに変わっているだけです。
出力
.に対応するoutputを実装します。
label output
LOAD_MEM 0 REG0 REG3
OR REG3 REG3 OUTPUT
IF_EQ REG0 REG0 MAIN_LOOP
OR REG3 REG3 OUTPUTという命令は、REG3の値をOUTPUTに書き込むという命令です。
OUTPUTはConsoleに接続されているため、Consoleに書き込むことができます。
ループの開始
[に対応するloop_startを実装します。
label loop_start
OR REG5 REG5 REG2
IF_EQ REG0 REG0 MAIN_LOOP
OR REG5 REG5 REG2という命令は、REG5の値をREG2に書き込むという命令です。
REG5はレジスタではないですね。
REG5はファイルIOのカーソルの位置を管理するために使用しています。
ループの終了
]に対応するloop_endを実装します。
label loop_end
LOAD_MEM 0 REG0 REG3
IF_EQi REG3 0 MAIN_LOOP
ADDi REG2 0 REG5
IF_EQ REG0 REG0 MAIN_LOOP
LOAD_MEM 0 REG0 REG3という命令は、REG0の値をメモリアドレスREG3から読み込み、REG3に代入するという命令です。
次に、IF_EQi REG3 0 MAIN_LOOPという命令は、REG3の値と0が等しい場合、MAIN_LOOPのラベルにジャンプするという命令です。
これにより、[ ]の中身が0の場合、[ ]の外にジャンプすることができます。
ただし、この実装では多重ループには対応していません。
もし、多重ループに対応する場合はスタックにループの開始アドレスを積むなどの実装が必要です。
実行してみる
実際にBFのHello Worldプログラムを実行します。
といってもスクショだけなので、イマイチ伝わらないですね。
ConsoleにHello Worldが表示されているのがわかります。
実行Tickはゲーム内で9.5Kとなっています。
やはり、BFはステップ数が多いですね。
ゆっくり実行するモードだと、BFのWeb実行ツールなどを眺めてる気分になれます。
コンパイラも作りたかった
今回はインタプリタを作成しましたが、コンパイラも作成したかったですね。
今回作成したインタプリタは、BFの命令を1つずつ実行しているため実行のステップが多くなってしまいます。
これは、コンパイラが直接機械語に変換されるため、単純な命令の組み合わせに変換されるためです。
簡単にいうと「>はどういう意味？」とコンピュータは毎回考えずに、「ポインタのインプリメント」というような単純な命令を与えるだけにするようにします。
これを人間に適用しようとすると、「すべこべ考えずに言われたことだけやっておけ！」という主張になります。
まるでコンパイラはパワハラ上司ですね。
また、コンパイラは最適化を行うことができるため、実行速度も向上します。
これもBFを例に出しますが、例えばBFコードでは+の文字列が非常に多く連続して登場することがあります。
つまり、+の命令を連続で実行するのではなく、+の命令をまとめて実行することで、実行速度を向上させることができます。
いわゆるランレングス圧縮のようなものですね。
+++++は+5として扱うことで、+の命令を5回実行するよりも効率的になります。
これ以外にも様々な最適化が可能ですが、コンパイラはインタプリタを作るよりも難易度が高いため、今回は諦めました。
まとめ
今回はBFインタプリタを作成しました。
実はツッコミどころとして標準入力が実装されていませんが、使ってる人みたこないので省略しています。
TuringCompleteでTuringCompleteな言語を実行することが出来て満足です。
それでは。
参考にしたもの