計算機でもあるBrainfuck

Brainfuckは難解プログラミング言語として有名です。
Brainfuckソースを見ると、その奇抜な見た目に驚かされます。
そのソースやBrainfuckがどんなものかの説明は、例えば下のページが詳しいです。

前述のページの言語仕様を読むと、
「要素数30000の配列」や「インストラクションポインタ」、「データポインタ」と言ったキーワードが登場してきます。
言語仕様とは言っていますが、これらのキーワードが定義するところは、本質的に計算機の仕様になっています。
いわゆるハードウェアのスペックです。
「要素数30000の配列」は計算機のメモリそのものであるし、
「インストラクションポインタ」は計算機でよく出てくるプログラムカウンタ、
「データポインタ」は計算機のレジスタのようなものと見なせます。
つまりその仕様を見ると、本質的に計算機ともみなせるものになっています。
従ってBrainfuckを実装することは、最も単純な計算機のエミュレータを実装することと同じになります。
順に、Brainfuckの特徴や個別の要素を整理しながら、ぜひ実装してみましょう。

Brainfuckの計算機としてアーキテクチャを整理する

実装する前に、Brainfuckの計算機としてアーキテクチャを整理してみましょう。
Brainfuckの計算機としてアーキテクチャを見ると、現代的な計算機、いわゆるノイマン型のアーキテクチャと違いがあります。
それはプログラムとデータの格納先が区別されている点です。
そのようなアーキテクチャをハーバード・アーキテクチャと呼びます。
プログラムとデータがメモリでどのように扱われるか比べてみましょう。
簡単のためにここでは入出力は考えないものとします。

ノイマン型

ノイマン型ではプログラムとデータは、どちらもメモリ上に格納されています。

メモリ

+----------+----------+
| プログラム | データ    |
+----------+----------+

ハーバード・アーキテクチャ

ハーバード・アーキテクチャでは、プログラムはプログラム専用の領域がありそこに格納します。
メモリではデータだけを格納します。

そしてBrainfuckでは、プログラム領域とメモリのそれぞれを操作するために、
それぞれ用のポインタが用意されています。
プログラム領域にはインストラクションポインタ、メモリにはデータポインタが用意されています。

インストラクションポインタは、次に実行されるプログラム領域の位置を指します。
データポインタはデータの操作対象となる位置を指します。

プログラム領域

  | インストラクションポインタ
  V
+----------+
| プログラム |
+----------+

メモリ

  | データポインタ
  V
+----------+
| データ    |
+----------+

まとめると、Brainfuckのアーキテクチャには、4つの構成要素がありました。
プログラム領域、メモリ、インストラクションポインタ、データポインタです。

Brainfuckのアーキテクチャを実装してみる

アーキテクチャが整理できたので、それをここではJava言語で実装してみたいと思います。
4つの構成要素を変数で表してみます。

//  アーキテクチャ
int instructionPointer;
String programArea;
int dataPointer;
byte[] memory;

Brainfuckの状態遷移を考える

Brainfuckの実行を分析すると、3つの状態を遷移することが見て取れます。
次の3つです。

初期状態→動作状態→停止状態

初期状態は動作状態へ移れる条件を満たすように、アーキテクチャが初期化された状態です。
動作状態はアーキテクチャの状況を使って、計算を実行している状態です。
停止状態は、動作状態が実行を継続する条件を満たせなくなると、遷移する状態です。

それぞれの状態について、詳しく見ていきましょう。

初期状態

初期状態とは、アーキテクチャが初期化された状態です。
Brainfuckを計算機とするならば、電源を入れた直後の状態にあたります。
アーキテクチャの整理で、Brainfuckは4つの構成要素があることが分かりました。
それぞれについて、初期化された状態がどうなるか考えてみましょう。

プログラム領域

Brainfuckは実行を始めるとすぐにプログラム実行することから、
プログラム領域にはプログラムがあることが初期状態であると考えられます。

メモリ

メモリは全て0になっていなければなりません。

インストラクションポインタ

インストラクションポインタは0になっていなければなりません。

データポインタ

データポインタは0になっていなければなりません。

Brainfuckの初期状態を実装してみる

初期状態について考えた結果を実装してみましょう。
プログラム領域には初期状態でプログラムがある前提なので、とりあえずプログラムを直に書きました。
これは起動パラメータやファイルから、プログラムが読み込めた方がいいですが、
まずは簡単のためにこのままにしましょう。
その他の3つの構成要素は、どれも単純に0で初期化しています。

//  初期化
instructionPointer = 0;
programArea = "++++++[>++++++[>+<-]<-]>>.-.";
dataPointer = 0;
memory = new byte[30000];

動作状態と停止状態

初期状態が整理できたところで、動作状態と、その状態から停止状態にどう移るかを考えてみましょう。

停止判定

まず始めに動作状態からどうしたら停止するか考えましょう。
動かす以上は安全に停止したいですね。
当たり前ですが、動作状態ではプログラムを実行します。
これを停止の視点から言い換えると、動作状態は実行するプログラムが尽きたら停止するとなりますね。
それを実装に落とすために、実行するプログラムが尽きたらというのを具体的にすると、
インストラクションポインタの指す位置に、次に実行されるプログラムが無いときになります。
インストラクションポインタとは何でしたっけ？
次に実行されるプログラム領域の位置を指すものですね。
どうやら安全に停止しそうです。

動作状態

動作状態を細かく見ていきましょう。
参考に、WikipediaのCPUのページ、動作の節(以降ではWikipediaと省略)を読むと、

CPUでは、フェッチ、デコード、実行という3つのステップがほぼ必ず存在する。」

とあります。
エミュレータの端くれとして、Brainfuckでも同じようになるはずではないでしょうか。
Brainfuckでその3つのステップが、どうなるか考えてみましょう。

フェッチ

Wikipediaでは、

フェッチとは、実行すべき命令（ある数値または数値の並び）をプログラムの置かれたメモリから取り出すこと

とあります。
さて、アーキテクチャの整理で触れたように、Brainfuckはプログラムはメモリではなく、
プログラム領域に置かれます。
Brainfuckでのフェッチは、プログラム領域から、インストラクションポインタの指す位置のプログラムを
取り出すことなるでしょうか。
例えば、下のようプログラムがあって、インストラクションポインタが3だったら、
その位置にある"["が、取り出されます。

    | :インストラクションポインタ = 3
    V
"+++[>+<-]" :プログラム

デコード

同じくWikipediaでは、

デコードでは、命令をCPUにとって意味のある形式に分割する。

とあります。
Brainfuckのプログラムを見てみると、命令はどれも1文字です。2文字や3文字はありません。
フェッチで取り出した1文字は、意味のある形式に分割されていると見なせるものです。
となると、Brainfuckではデコードは要りませんね。

実行

またまたWikipediaでは、

このステップでは、CPUの多くの部分が接続され（たとえばマルチプレクサを切り替えるなどして）指定された操作を実行する。

とあります。
Brainfuckで考えると単純に命令を実行することに当たるでしょう。

順にプログラムを実行する

個々の動作について詳しく見ました。
今度はどのように動作を、順に実行させるか考えましょう。
順にプログラムを実行するには、フェッチが順にプログラムを取り出す必要があります。
そのためには、インストラクションポインタの指す位置が、順に進んでいかなければなりません。
順にプログラムを実行するには、フェッチの後にどこかでインストラクションポインタを進めます。

Brainfuckの動作を実装してみる

さて、ここまで見てきた、停止判定、フェッチ、実行、インストラクションポインタを進めることを、
実装してみましょう。
実行については後ほど、詳しく見て実装することにして、ここではコメント文として置いておきます。
まだ何の実行もできないわけですが、何となく実装全体の骨組みは整いましたね。

//  動作
while(programArea.length() > instructionPointer) {

    // フェッチ
    char command = programArea.charAt(instructionPointer);

    // ここに実行を実装する予定

    ++instructionPointer;
}

命令の実装

実行を実装するために、命令を見ていきましょう。
Brainfuckの命令は次の8つだけです。

<>+-.,[]

命令を大別すると、データポインタ制御、データ操作、入出力、条件分岐に分けられます。
簡単な命令から順に検討し、実装していきましょう。

データポインタ制御、"<", ">"

"<"と">"はそれぞれデータポインタを減らしたり、増やしたりするものです。
実装で書くと下のようになります。
これは文章で書くより実装の方が簡単ですね。

//  "<"はデータポインタを減らす
--dataPointer;

//  ">"はデータポインタを増やす
++dataPointer;

"<"と">"の見た目についてちょっと余談。
図のようにメモリが左から右に続いていると想像します。

メモリ

  | データポインタ
  V
+----------+
| データ    |
+----------+

すると、"<"はデータポインタを左に動かす、">"はデータポインタが右に動かすことになり、
その見た目とも一致しますね。

データ操作、"+", "-"

"+"と"-"はそれぞれ、データポインタが指す位置のデータを、減らしたり増やしたりするものです。
実装で書くと下のようになります。
これも実装の方が視覚的に分かりやすいかも知れません。

//  "+"はデータポインタが指す位置のデータを増やす
++memory[dataPointer];

//  "-"はデータポインタが指す位置のデータを増やす
--memory[dataPointer];

入出力、".", ","

"."はデータポインタが指す位置のデータを、出力します。
","はデータポインタが指す位置へ、データを入力します。

入力や出力は、Brainfuckを実装する言語によるところが大きいです。
Javaでの一例として下のように書きました。

//  出力
System.out.print((char) memory[dataPointer]);

//  入力
memory[dataPointer] = (byte) System.in.read();

条件分岐、"[", "]"

"[", "]"は主に繰り返し処理を書くのに使います。
"["はデータポインタが指す位置のデータが0なら、対応する"]"へ飛びます。
"]"はデータポインタが指す位置のデータが0でないなら、対応する"["へ飛びます。
その説明だけでは、繰り返し処理になることが分かり辛そうなので、プログラムの例をちょっと見てみましょう。

++[-]

最初の"++"で繰り返す回数を作ります。"++"なので2になります。
"[]"の中の"-"が、作った繰り返す回数を減らしていくので、
"[]"の中を繰り返す最中に、2がやがて0になります。
0になると"]"が、対応する括弧へ飛ばなくなるので、繰り返しが終わります。
注意したいところは、繰り返しが入れ子のときです。
入れ子の例です。

++[[-]]

この入れ子を考慮して、対応する角括弧を飛べる実装を考えてみましょう。
例えば、"["に対応する"]"を捜査する場合を考えます。
"["の後に"]"は来るわけですから、順にinstructionPointerを増やしていって、
対応がないかさがします。
このとき、角括弧に出会った数を増減しながら、最終的に0になるように目指します。
増減は"["に出会ったら数を増やし、"]"に出会ったら数を減らします。
0になったら、対応のバランスが取れたという意味になるわけです。
"]"の対応括弧の場合は逆を行います。

  //  "["はデータポインタが指す位置のデータが0なら、対応する"]"へ飛びます。
  if(memory[dataPointer] == 0) {
      //  出会った角括弧の数
      int count = 1;
      while(count > 0) {
          ++instructionPointer;
          if(programArea.charAt(instructionPointer) == '[') {
              ++count;
          }
          else if(programArea.charAt(instructionPointer) == ']') {
              --count;
          }
      }                
  }

  //  "]"はデータポインタが指す位置のデータが0でないなら、対応する"["へ飛びます。
  if(memory[dataPointer] != 0) {
      //  出会った角括弧の数
      int count = 1;
      while(count > 0) {
          --instructionPointer;
          if(programArea.charAt(instructionPointer) == '[') {
              --count;
          }
          else if(programArea.charAt(instructionPointer) == ']') {
              ++count;
          }
      }                
  }

全てをまとめる

命令も全て実装できたので、今までものを全てまとめてみましょう。
とりあえずの例として、"$#"が出力されるBrainfuckプログラムを書きました。
プログラムは、6回繰り返しの二重ループになっているので、6x6=36を作っています。
ASCII Code 36に当たるのが、"$"なので、最初の出力コマンド、"."で"$"が出力されるわけです。
その後すぐに36から1を引き35になります。ASCII Code 35は"#"で、それをまた"."で出力します。
main()メソッドにthrows IOExceptionがついているのは、System.in.read()の影響です。

import java.io.IOException;

public class Brainfuck {

    public static void main(String[] args) throws IOException {

        //  アーキテクチャ
        int instructionPointer;
        String programArea;
        int dataPointer;
        byte[] memory;

        //  初期化
        instructionPointer = 0;
        programArea = "++++++[>++++++[>+<-]<-]>>.-.";
        dataPointer = 0;
        memory = new byte[30000];

        //  動作
        while(programArea.length() > instructionPointer) {

            // フェッチ
            char command = programArea.charAt(instructionPointer);

            // 実行
            switch (command) {
            case '<':
                //  "<"はデータポインタを減らす
                --dataPointer;
                break;
            case '>':
                //  ">"はデータポインタを増やす
                ++dataPointer;
                break;
            case '+':
                //  "+"はデータポインタが指す位置のデータを増やす
                ++memory[dataPointer];
                break;
            case '-':
                //  "-"はデータポインタが指す位置のデータを増やす
                --memory[dataPointer];
                break;
            case '.':
                //  出力
                System.out.print((char) memory[dataPointer]);
                break;
            case ',':
                //  入力
                memory[dataPointer] = (byte) System.in.read();
                break;
            case '[':
                //  "["はデータポインタが指す位置のデータが0なら、対応する"]"へ飛びます。
                if(memory[dataPointer] == 0) {
                    //  出会った角括弧の数
                    int count = 1;
                    while(count > 0) {
                        ++instructionPointer;
                        if(programArea.charAt(instructionPointer) == '[') {
                            ++count;
                        }
                        else if(programArea.charAt(instructionPointer) == ']') {
                            --count;
                        }
                    }                
                }
                break;
            case ']':
                //  "]"はデータポインタが指す位置のデータが0でないなら、対応する"["へ飛びます。
                if(memory[dataPointer] != 0) {
                    //  出会った角括弧の数
                    int count = 1;
                    while(count > 0) {
                        --instructionPointer;
                        if(programArea.charAt(instructionPointer) == '[') {
                            --count;
                        }
                        else if(programArea.charAt(instructionPointer) == ']') {
                            ++count;
                        }
                    }                
                }
                break;
            }

            ++instructionPointer;
        }
    }
}

謝辞

本稿は7shiさんをはじめ、研究会の仲間に検討して頂きました。
ありがとうございます。

おまけ

参考に、Brainfuckの動作が視覚的に分かりやすいような実装を作りました。
http://quwahara.github.io/VisualBrainfuckJs/index.html