JavascriptでBrainfuckのインタプリタを実装してみた。

こんにちは。最近週一で温泉に通ってます。 nagata（@handlename）です。

Brainfuckというちょっと汚い名前のプログラミング言語があることをご存じでしょうか? たった８種類の文字からなるスーパーミニマムな言語です。

その仕様はというと・・・

> ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。

< ポインタをデクリメントする。C言語の「ptr--;」に相当。

+ ポインタが指す値をインクリメントする。C言語の「(*ptr)++;」に相当。

- ポインタが指す値をデクリメントする。C言語の「(*ptr)--;」に相当。

. ポインタが指す値を出力する。C言語の「putchar(*ptr);」に相当。

, 1バイトを入力してポインタが指す値に代入する。C言語の「*ptr=getchar();」に相当。

[ ポインタが指す値が0なら、対応する ] の直後までジャンプする。C言語の「while(*ptr){」に相当。

] ポインタが指す値が0でないなら、対応する [ にジャンプする。C言語の「}」に相当。

http://ja.wikipedia.org/wiki/Brainfuck より

たったこれだけ。

この言語でHello, world!を出力する場合、こう書けます。

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

今回はこの言語のインタプリタをJavascriptで実装してみます。

とりあえずできたものを

必要最低限の機能しかない、簡易版です。なお、今回は~~面倒だった~~簡単のために、「,」（入力）の実装は省いています。

brainf*ck interpreter - jsdo.it - share JavaScript, HTML5 and CSS

※Wikipediaだけ見てがががっと書いたので、不完全な部分がありますが、そこは目をつぶらずにフォークして直してやってください。

どんな実装?

さてさて、普段JSを書かないので、思いつきでどんどん実装していきます。

準備

とりあえず、

ポインタと、
メモリと

を表す何かが必要になります。とりあえずメモリは配列で用意しておきましょう。

var pointer = 0;  // ポインタ。メモリのインデックス
var memory  = []; // メモリに見せかけた単なる配列

もうひとつ、ASCII文字が入った配列も用意しておきます。制御文字は文字列で代用。

>と<

> ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。

< ポインタをデクリメントする。C言語の「ptr--;」に相当。

http://ja.wikipedia.org/wiki/Brainfuck より

これは簡単ですね。先ほど用意したpointerを増減させるだけです。ほんとはポインタの範囲なんかを管理しないといけないんでしょうが、とりあえず省略。

pointer++; // >
pointer--; // <

おお、なんというシンプルさ・・・。この調子でどんどん書いていきます。

+と-

+ ポインタが指す値をインクリメントする。C言語の「(*ptr)++;」に相当。

- ポインタが指す値をデクリメントする。C言語の「(*ptr)--;」に相当。

http://ja.wikipedia.org/wiki/Brainfuck より

これも簡単ですね。

memory[pointer]++; // +;
memory[pointer]--; // -;

.（ピリオド）

. ポインタが指す値を出力する。C言語の「putchar(*ptr);」に相当。

http://ja.wikipedia.org/wiki/Brainfuck より

出力バッファにポインタが指すメモリ、が指す文字を追加します。

var output = '';
output += chars[memory[pointer]]; // .

,（カンマ）

, 1バイトを入力してポインタが指す値に代入する。C言語の「*ptr=getchar();」に相当。

http://ja.wikipedia.org/wiki/Brainfuck より

今回は実装を省きます。

[と]

[ ポインタが指す値が0なら、対応する ] の直後までジャンプする。C言語の「while(*ptr){」に相当。

] ポインタが指す値が0でないなら、対応する [ にジャンプする。C言語の「}」に相当。

http://ja.wikipedia.org/wiki/Brainfuck より

さて、一番やっかいな部分ですね。対応する括弧にジャンプするためには、その括弧がどこにあるかを知らなくてはなりません。ない頭をひねって括弧の対応を配列に格納する方法をとることにしました。

var input = '[++[++]+]';
braces[0] = 8;
braces[3] = 6;
braces[6] = 3;
braces[8] = 0;

こんな感じ。入力の0番目にある開き括弧が10番目にある閉じ括弧と対応する、という意味です。

2010/08/04 11:00 括弧の対応の例が間違っていたので修正しました。

この対応配列を作るために、入力要素を一度ループさせます。開き括弧が見つかったら、対応する閉じ括弧が見つかるまでスタックに、

開き括弧ならプッシュ
閉じ括弧ならポップ

していきます。スタックが０になったらそのときの括弧が対応する閉じ括弧というわけです。

var braces = [];
var brace_stack = [];

for(var i in input) {
    var command = input[i];

    if(command == '[') {
        var j = i;

        while(true) {
            // 対応する括弧が見つからなければエラー
            if(input.length <= j) {
                throw 'invalid brace pare';
            }

            // 開き括弧ならプッシュ、閉じ括弧ならポップ
            if(input[j] == '[') {
                brace_stack.push(1);
            }
            else if(input[j] == ']') {
                brace_stack.pop();
            }

            // 対応する括弧が見つかったら抜ける
            if(brace_stack.length == 0) {
                break;
            }

            ++j;
        }

        braces[i - 0] = j - 0;
        braces[j - 0] = i - 0;
    }
}

これで括弧が出てきたとき、入力のどの部分に飛べばいいのかがわかるようになりました。

出力

最後に全体を処理して出力です。いままで実装してきたコマンドをまとめます。

var output = '';

for(var i = 0; i < input.length; ++i) {
    var command = input[i];

    switch(command) {
      case '>': pointer++; break;
      case '<': pointer--; break;
      case '+': memory[pointer]++; break;
      case '-': memory[pointer]--; break;
      case '.': output += chars[memory[pointer]]; break;
      case '[': memory[pointer] == 0 && (i = braces[i] + 1); break;
      case ']': memory[pointer] != 0 && (i = braces[i]); break;
    }

    if(pointer < 0 || memory.length <= pointer) {
        throw 'pointer out of range (' + pointer + ')';
    }
}

こうして入力に対する出力が得られるわけです。やたー

例

冒頭の、「Hello, World!」はこんな感じです。 jsdo.it上のコードには、これが最初から入力されています。

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

もうちょっと短い例を見てみましょう。 0から9までの数字を出力する場合はこう書きます。

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

うん、わかりにくい。考えるのもいやになります。さすがBrainfuck。

おわり

今回、思いつきでBrainfuckのインタプリタを実装してみました。普段こういうことに頭を使わないので相当時間がかかりましたが（主に括弧の対応部分）。

実用性という意味では皆無ですが、勉強ついでに実装してみるのもいいかもしれません。

（ちなみに、Wikipediaさん曰く、Brainfuckのインタプリタは98バイトでつくれるそうです）

カヤックでは無駄な部分に情熱を注げる技術者を募集しています！