JavaでBrainf*ckを実装してみた！

1000speakers1:5のhackathonタイムでBrainf*ckが盛り上がっていた。
これまでは記号ばっかりの変なプログラムだな、としか思っていなかった。

Brainf*ckで「A」を出力させるコードはこんな感じ。

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

でもちゃんと調べてみると、仕様がコンパクトで、みんなが遊んでいる理由がわかった。これは面白い。
Brainf*ckの仕様は、Wikipediaによるとこんな感じ。

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

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

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

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

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

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

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

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

Brainfuck - Wikipedia

C言語の勉強したからちゃんと意味がわかる！
Javaで実装するので、以下のように仕様を読み替えた。

ポインタ→配列のインデックス
ポインタの指す値→配列の要素

配列がary[i]という感じだったら

ポインタ→ i
ポインタの指す値→ ary[i]

という感じ。
そんなわけで、僕のなかではこんな仕様になった。

> インデックスをインクリメントする。 i++;
< インデックスをデクリメントする。 i--;
+ インデックスが指す配列の要素をインクリメントする。 ary[i]++;
- インデックスが指す配列の要素をデクリメントする。 ary[i]--;
. インデックスが指す配列の要素を出力する。 System.out.println( (char)ary[i] );
, 1バイトを入力してインデックスが指す配列の要素に代入する。 ary[i] = System.in.read();
[ インデックスが指す配列の要素が0なら、対応する ] までジャンプする。0以外ならそのまま処理を進める。
] インデックスが指す配列の要素が0でないなら、対応する [ にジャンプする。0ならそのまま処理を進める。

><+-.,までは順調に実装できたのだが、 [ ] で詰まる。
ジャンプする、というのがなんのことだがわからなかったのだ。
ジャンプしないときは、普通に処理を進めるということが、うまく理解できていなかった。
わからなかったので、いろいろとカンニングした。

bfi.rb Brainfuck の Ruby 実装 - TokuLog!

けっきょくここのRubyのコードをJavaに置き換えただけになってしまった…。

Brainf*ckプログラミング入門という感じで、コードがいろいろあって分かりやすい。

BrainFuck ダイナマイツ

AppletでBrainf*ckが実行できて、実行中のメモリの操作もわかってすごい！
これを見れば内部でどんなふうに動いているのかわかる。

ちなみにネストしたループの動作が、未だによくわかっていない。
ちゃんと1ステップずつ追えばわかりそうなものだけど、1ステップずつ追ってもよくわからない。
そもそも、ネストしたループのBrainf*ckのコードが上手く書けない。困った困った。
また気が向いたとき調べよう。

そんなこんなで、実装したコードは以下の通り。
ちゃんとクラスを分けたほうがかっこいいけど、blogに載せるのが面倒なので1クラスにした。
デバッグ用に使ってたprintもそのままだし、変数名や、メソッド名や、細かい部分に突っ込みどころはたくさんあるが、とりあえず HelloWold や FizzBuzz は動いた。

FizzBuzzのコードは以下を参考にさせていただいた。

brainf*ckでFizzBuzz - Mi manca qualche giovedi`?

import java.io.IOException;

public class BrainFuck {

  public static void main(String args[]) {
    // print A
    brainFuck("++++++++[>++++++++<-]>+.");
    // print HelloWorld
    brainFuck("++++++++[>+++++++++<-]>.<+++++[>++++++<-]>-.<++[>+++<-]>+..+"
            + "++.<++++++[>----<-]>.<++++++[>++++<-]>.+++.------.--------.");
    // print FizzBuzz
    brainFuck("++++++[->++++> >+>+>-<<<<<]>[<++++> >+++>++++> >+++>+++++>++"
            + "+++> > > > > >++> >++<<<<<<<<<<<<<<-]<++++>+++>-->+++>-> >--"
            + "->++> > >+++++[->++>++<<]<<<<<<<<<<[->-[> > > > > > >]>[<+++"
            + ">.>.> > > >..> > >+<]<<<<<-[> > > >]>[<+++++>.>.>..> > >+<]>"
            + " > > >+<-[<<<]<[[-<<+> >]> > >+>+<<<<<<[-> >+>+>-<<<<]<]>>[["
            + "-]<]>[> > >[>.<<.<<<]<[.<<<<]>]>.<<<<<<<<<<<]");
  }

  public static void brainFuck(String codeStr) {
    boolean debug = false;

    int[] mem = new int[1024];
    char[] code = codeStr.toCharArray();
    int pointer = 0;
    int counter = 0;

    while (counter < code.length) {
      if (debug)
        System.out.println("char:" + code[counter] + " count:"
            + counter + " pointer:" + pointer + " value:"
            + mem[pointer]);
      switch (code[counter]) {
      case '+':
        mem[pointer] += 1;
        break;
      case '-':
        mem[pointer] -= 1;
        break;
      case '.':
        System.out.print((char) mem[pointer]);
        break;
      case ',':
        try {
          mem[pointer] = System.in.read();
        } catch (IOException e) {
          e.printStackTrace();
        }
        break;
      case '>':
        pointer += 1;
        break;
      case '<':
        pointer -= 1;
        break;
      case '[':
        if (mem[pointer] == 0) {
          counter += 1;
          int l = 0;
          while (l > 0 || code[counter] != ']') {
            if (debug)
              System.out.println("char:" + code[counter]
                  + " count:" + counter + " pointer:"
                  + pointer + " value:" + mem[pointer]);
            if (code[counter] == '[') {
              l += 1;
            } else if (code[counter] == ']') {
              l -= 1;
            }
            counter += 1;
          }
        }
        break;
      case ']':
        if(mem[pointer] != 0){
          int l = 0;
          counter -= 1;
          while (l > 0 || code[counter] != '[') {
            if (debug)
              System.out.println("char:" + code[counter] + " count:"
                  + counter + " pointer:" + pointer + " value:"
                  + mem[pointer]);
            if (code[counter] == ']') {
              l += 1;
            } else if (code[counter] == '[') {
              l -= 1;
            }
            counter -= 1;
          }
        }
        break;
      }
      counter++;
    }
    System.out.println("");
  }
}

これで僕も言語処理系を実装しました！と言える！
上記コードは main を入れても 97行だ。短い！
FizzBuzzくらいすぐに書けるよ、というひとはBrainf*ckの実装をしてみると楽しいと思う。
なによりあの記号の集合がプログラムとして動くと楽しい！

＜追記＞
] の場合の処理で、バグ(？)があったので修正。
下の条件がなかった。

        if(mem[pointer] != 0){

counter -= 1 が whileの外にもあった(2箇所記載されていた)ので削除した。
とりあえずFizzBuzzが動くことは確認した。

techlog

JavaでBrainf*ckを実装してみた！

参考URL

関連エントリ