ニジボックスAdvent Calendar 2015 16日目の記事です。

BrainF*ckとは

BrainF*ckとは難解言語の一種で、下記の8つの実行可能な命令を持っている言語です。
1. > ポインタをインクリメントする
2. < ポインタをデクリメントする
3. + ポインタが指す値をインクリメントする
4. - ポインタが指す値をデクリメントする
5. . ポインタが指す値を出力する
6. , 入力から1バイト読み込んで、ポインタが指す先に代入する
7. [ ポインタが指す値が0なら対応する]の直後にジャンプする
8. ] ポインタが指す値が0以外なら対応する[の直後にジャンプする
以上Wikipedia先生から抜粋。

やたらとポインタと言う単語が出てきており、学生時代にC言語にいじめられた自分としては今すぐブラウザを閉じてお家へ帰りたいところではありますが、
折角なので、JavaScriptでBFのインタプリタを実装して、アドレスとその中の数値の動きを視覚的に見られるようにしてみましょう。

実装

まず実際の数値を入れる配列とその配列のキー(ポインタ)がどこかを示す変数が必要になります。
また、BFのソースコードのどこを読んでいるかを示すプログラムカウンタが必要です。
ブラウザから受け取るソースと出力用の変数も書いておきます。

var mem = [];
var ptr = 0;
var pc = 0;
var source = "input";
var result = "";

受取りの細かい部分は割愛して、BFの言語仕様を１つずつ実装していきます。
以下の処理をソースの読み込みが終わるまで繰り返します。

var c = source.substring(pc, pc+1);    //1文字取得
pc++;                                  //プログラムカウンタをインクリメント
switch(c){
}

簡単に実装できそうな値の加減算から

case '>':pt++; break;
case '<':pt--; break;
case '+':mem[pt]++; break;
case '-':mem[pt]--; break;

BFの出力はC言語でいうputcharと同じ動きのため、こちらもそのまま実装します。
入力はブラウザから行っているため実装しません。

case '.':result += String.fromCharCode(mem[pt]); break;

そして繰り返し処理につかうジャンプ命令を実装します。
処理自体は単純で、プログラムカウンタを増やし(減らし)ながら、対応するジャンプ命令を検知し、その時点のカウンタより1大きい数をプログラムカウンタに代入します。

この時に注意が必要なのは、ジャンプ命令のネストがあった場合に、単純に対応する命令を検知するだけでは正しく動作しないことです。

そのため、処理している命令と同種のジャンプ命令があった場合その数をカウントしておき、対応するジャンプ命令があった時にカウンタが0だったらループから抜けるようにします。

case '[':
    if(mem[pt] == 0){
        var count = 0;
        for(var i = pc; i < source.length; i++){
            if(source.substring(i, i + 1) == '['){
                count++;
            }
            if(source.substring(i, i + 1) == ']'){
                if(count == 0){
                    break;
                }
                count--;
            }
        }
        pc = i + 1;
    }
    break;
case ']':
    if(mem[pt] != 0){
        var count = 0;
        for(var i = pc - 2; i >= 0; i--){
            if(source.substring(i, i + 1) == ']'){
                count++;
            }
            if(source.substring(i, i + 1) == '['){
                if(count == 0){
                    break;
                }
        count--;
            }
        }
        pc = i;
    }
    break;

以上で一通りの機能実装が完了です。
あとはフロント側で見た目を整えたり、アドレスや数値の流れを追いやすいようにスリープやステップ実行を好みで付けてこうなりました。

Runボタンを押すことで緑色のプログラムカウンタがソース上を読み取っていき、出力命令があった場合はresultに出力されます。
また今どこのメモリを指しているかはピンクの網掛けで表しています。

途中経過。

無事、ハロワが表示されました。

終わりに

今回、本当はGCPのCloudVisionの記事を書くつもりだったのですが、Googleの審査が間に合わずファ〇ク！ファ〇ク！と言っていたらこのネタ記事が出来上がりました。
審査が通ったら、笑わせた福沢諭吉を認識するか遊んでみたいと思っています。

JavaScriptでBrainF*ckインタプリタを実装する

BrainF*ckとは

実装

終わりに