[C#] Brainfuckのインタプリタ実装方法

Brainfuck とは

• Brainfuck – Wikipedia

Brainfuck とは、難解プログラミング言語のひとつで、Brainfuckで書かれたソースコードは可読性が低く難解なものになります。

例えば "HelloWorld" と出力するためのソースコードは次のようになります。可読性・記述性が低く何をやっているのかわかりません。

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

一方コンパイラ(インタプリタ)のサイズは非常に小さくなるように設計されており、その実装も容易です。C#を使って、Brainfuckのインタプリタを実装してみます。

言語仕様

Brainfuck の言語仕様は次の通りです。Wkipediaからの引用です。

1. > ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。
2. < ポインタをデクリメントする。C言語の「ptr--;」に相当。
3. + ポインタが指す値をインクリメントする。C言語の「(*ptr)++;」に相当。
4. - ポインタが指す値をデクリメントする。C言語の「(*ptr)--;」に相当。
5. . ポインタが指す値を出力に書き出す。C言語の「putchar(*ptr);」に相当。
6. , 入力から1バイト読み込んで、ポインタが指す先に代入する。C言語の「*ptr=getchar();」に相当。
7. [ ポインタが指す値が0なら、対応する ] の直後にジャンプする。C言語の「while(*ptr){」に相当。
8. ] ポインタが指す値が0でないなら、対応する [ （の直後）にジャンプする。C言語の「}」に相当。

上記8つのコマンドしかありません。また、上記以外の文字はすべてコメントとして扱い無視することにします。

実装

class Brainfuck
{
    public int[] Memory { get; private set; }
    public int Pointer { get; private set; }
    public int Index { get; private set; }
    public string SourceCode { get; set; }

    public void Run(string sourceCode)
    {
        this.Memory = Enumerable.Repeat(0, 2048).ToArray();
        this.Pointer = 0;
        this.SourceCode = sourceCode;
        this.Index = 0;

        while (this.Index < this.SourceCode.Length)
        {
            // 現在のインデックスにあるコマンドを実行
            ExecCommand();
            this.Index++;
        }
    }

    private void ExecCommand()
    {
        var c = this.SourceCode[this.Index];

        switch (c)
        {
            case '>': // ポインタ加算
                this.Pointer++;
                break;
            case '<': // ポインタ減算
                this.Pointer--;
                break;
            case '+': // 値加算
                this.Memory[this.Pointer]++;
                break;
            case '-': // 値減算
                this.Memory[this.Pointer]--;
                break;
            case '.': // 出力
                var outputChar = (char)this.Memory[this.Pointer];
                Console.Write(outputChar);
                break;
            case ',': // 入力
                this.Memory[this.Pointer] = Console.Read();
                break;
            case '[': // ループ開始
                if (this.Memory[this.Pointer] == 0)
                {
                    // 値が0の時、ループを抜ける
                    var bracketCount = 1;
                    while (bracketCount > 0)
                    {
                        // 対応する括弧 ']' を探す。
                        // 途中に '[' が出てきたら見つける数を増やす
                        this.Index++;
                        if (this.SourceCode[this.Index] == '[') bracketCount++;
                        if (this.SourceCode[this.Index] == ']') bracketCount--;
                    }
                }
                break;
            case ']': // ループ終了
                if (this.Memory[this.Pointer] != 0)
                {
                    var bracketCount = 1;
                    while (bracketCount > 0)
                    {
                        // 対応する括弧 '[' を探す。
                        // 途中に ']' が出てきたら見つける数を増やす
                        this.Index--;
                        if (this.SourceCode[this.Index] == ']') bracketCount++;
                        if (this.SourceCode[this.Index] == '[') bracketCount--;
                    }
                }
                break;
            default:
                // その他の文字はコメント扱いで無視
                break;
        }
    }
}

ソースコードとインデックス

Run メソッドに Brainfuck のソースコードを渡すと、実行します。Index で実行するソースコードの文字位置を管理しています。ソースコード末尾に達するまで、ExecCommand メソッドで文字に対応した処理を実行します。実行後にインデックスを次の文字に進めます。

なお仕様に存在する8文字以外はすべて無視します。

メモリとポインタ

ポインタとポインタの指す値を管理するメモリ、それぞれ int, int型配列 で管理します。加算減算はそれぞれに対して実行します。

入力と出力

入力(,), 出力(.)は単純に実装します。ただメモリの値はint型となっているので、出力する前に文字に変換して出力します。

// 出力値を文字に変換
var outputChar = (char)this.Memory[this.Pointer];

ループ

メモリとポインタ、入出力処理は単純なので1行ずつで実装できますが、ループは少し複雑です。

[ xxx ] というコードの "xxx" の部分が繰り返し実行されます。繰り返し終了の条件はポインタの指す値が0かどうかです。

[ のコマンド実行時、ポインタの指す値が "0" ならループ処理を実行せず抜けます。つまり対応する ] までジャンプします。

] のコマンド実行時、ポインタの指す値が "0" ならループを抜けるのでそのまま次の文字の実行に移りますが、"0" 以外だとループ処理を繰り返すので、対応する [ (の次の文字)までジャンプします。( [ にジャンプしても "0" 以外なのでループ処理に入るので問題ないけど無駄)

対応する括弧

対応する [, ] ですが、直近の対応する括弧を探すとうまくいきません。[[]] や [[][]] といった2重のループも考慮に入れて、対応する括弧を探します。

上記コードでは探し方は開始終了ともに同じです。対応する ] を探している最中に、[ を見つけた場合、見つける閉じかっこ ] の数を増やします。対応するものが見つかると数(bracketCount)が0になっているので、そこで探索処理を終えます。

探索処理の後のインデックスは、[] の位置ですが、そのあとに次の文字にインデックスを進めるので、[] の次の文字が、次に実行されることになります。

動作確認

では、実行してみます。

var bf = new Brainfuck();
bf.Run(">++++++[<++++++++++>-]<++++."); // @

コンソールに "@" が出力されれば成功です。上に乗せた "HelloWorld" もいければだいたいOKでしょう。もう少し複雑なものも実行したいですが、自分でコードを書くのは大変です。書いてみるとパズルっぽくて楽しいのですが。

ハノイの塔を解いてくれるソースがあったのでそれを載せておきます。

• esoteric.sange.fi/brainfuck/bf-source/prog/hanoi.bf

66億回くらいの命令が内部で実行されるのでそれなりに重たいです。が、見ていると面白いです。試してみてください。

以上です。

参考URL

• Brainfuck – Wikipedia
• HaskellでBrainfuck – Qiita
• BrainFuckとは