PythonでBrainf*ckを書いてみた

Brainf*ckとはなんぞや
Brainfuckは8つの命令しかない小規模なプログラミング言語です。

小規模なため、処理系と呼ばれるプログラムのコードを読み込み実行するプログラムを簡単に作る事が出来るので、
ちょっとしたプログラミングの練習にピッタリの題材です。

ちなみにpythonにも処理系があります。

pythonでプログラム( ほにゃらら.py)を解釈し、実行したり結果を出力しているアレが処理系です。

さすがにpythonの処理系は非常に難解であり、「よっしゃつくってみよー！」とはならないですが、
Brainf*ckでは結構簡単に作る事が出来ます。

Brainf*ckの仕様
brainfu*kの処理系は基本的に、読み込んだプログラムを保存するテープと値を保存するメモリーで構成されています。

テープは下の画像のように、プログラムを一文字ずつ保存しています。

図のa, b, cの部分に1文字ずつコードが保存されていきます。

このテープに対し、処理系は位置文字ずつ読み込んでいき、処理を行っていきます。

プログラムを作成する時、変数を保存する必要がありますよね。
Brainfuc*も変数をサポートしています。

処理系でメモリーを確保しておき、読み込んだコードに「変数保存してくれよ～」の様な命令
が記述された時、メモリーに対してアクセスを行います。

Brainf*ckの基本的な仕様は以上です。

このような単純な仕組みでC言語やpythonと同じ表現力を持つ（pythonで記述できるプログラムなら、brainf*ckでも記述可能）なんて凄いですよね。

ただ、処理系の仕組みが単純であると言う事はbrainf*ckのコードは非常に難解なものとなります。

次にBrainf*ckの言語仕様を見てみましょう。

Brainf*ckの言語仕様
先に述べたように、Brainf*ckには8つの命令しか有りません。パパっと見てみましょう。

1. > メモリポインタをインクリメントする
2. < メモリポインタをデクリメントする
3. + メモリポインタが指す値をインクリメントする
4. - メモリポインタが指す値をデクリメントする
5. . メモリポインタが指す値を出力する
6. , 入力から1byteのデータを読み込み、メモリポインタが指す値に代入する
7. [ メモリポインタが指す値が0なら、対応する]までプログラムカウンタを進める
8. ] メモリポインタが指す値が非0なら、対応する[までプログラムカウンタを戻す

>命令と<命令

色々新しい用語が出てきましたね。メモリポインタとは、現在読み書きしようとしているメモリの位置を示す値です。
ポインタと言っていますが、C言語のポインタとは違います。（用法は同じですけどネ）

イメージしづらいと思うので具体的な実装を例に説明すると、Brainf*ckの処理系におけるメモリーは配列実装します。
そして、その配列の要素にアクセスするインデックス( a[i] = 12 におけるi )がメモリポインターとなります。

インクリメントとは値を1だけ増加する事です。プログラムで書くと

i += 1

でしょうか。
デクリメントは逆に、値を1だけ減少する事です。

i -= 1

+命令と-命令
この2つの命令は非常に単純で、メモリポインター（配列の添字）が指す値をそれぞれ+1, -1するだけで実装できます。

#+命令
memory[memory_pointer] += 1
#-命令
memory[memory_pointer] -= 1

.命令と,命令
標準入力と標準出力です。こちらは使用する言語によって実装方法が大きく異る部分ですね。
Pythonだと両方共非常にシンプルに記述することが出来ます。

#.命令
print(chr(memory[pointer]), end="")
#,命令
memory[pointer] = int(input())

.命令は少し複雑そうに見えますね。外側のprint関数から見てみましょう。
print関数はchr()とend=""を引数に渡しています。後ろのend=""は見慣れない人も居るかもしれませんが、
print関数に対して「出力しても改行しないでね！」と教えてあげています。

chr()関数はmemory[pointer]を引数に渡しています。この関数は整数データをアスキーコードと捉え、文字に変換する関数です。
アスキーコードはざっくり言うと、様々な文字を数値に写像したものです。「a」なら97、「#」なら35と文字ごとに重複しない数値が割り当てられています。

,命令はmemory[pointer]に対し、入力したデータを整数値に変換し代入しています。

[命令と]命令
この2つの命令は割と厄介です。
まずざっくりとしたイメージとして[と]で囲まれた部分を繰返し実行します。
pythonでいうwhile文に近いですね。

[命令はメモリポインタが指し示す値が0ならば対応する]にジャンプすると言う命令でした。

ここで、メモリポインタが指し示す値をflagと一時的に名前をつけてあげます。

すると、この命令は

while flag != 0:
    #[と]で囲まれた部分の処理

となります。

また、]命令はメモリポインタが指す値が非0なら、対応する[までプログラムカウンタを戻すという命令でした。

この命令はwhile文の中に記述された命令を実行した後、flag != 0が成立するならば（whileから抜け出せなければ）whileの先頭に戻る
という命令です。

ループ命令は入れ子になっているとちょっとだけ処理が面倒くさいです。

これはループの入れ子を数える変数を別に用意してあげると解決できます。

Pythonで記述したBrainf*ckの処理系
処理系のコードは次の様になります。
スクリプトと同じ階層のディレクトリにbrainf*ckで記述されたプログラムを配置すると、処理されます。

file_path = "./brain_fuck_code.txt"

#メモリポインタ
pointer = 0

#プログラムカウンタ
program_counter = 0

#メモリ
memory = [0 for i in range(10000)]

#brainfuckのプログラム
tape = open(file_path,"r").read()

#コードの末尾までプログラムを処理する
while program_counter < len(tape):

    #プログラム・カウンタが指し示す文字を読み ">"ならメモリポインタをインクリメントする
    if tape[program_counter] == '>':
        pointer += 1

    #"<" メモリポインタをデクリメントする
    elif tape[program_counter] == '<':
        pointer -= 1

    #"." メモリポインタが指し示す先に格納された変数を処理系に表示
    elif tape[program_counter] == '.':
        print(chr(memory[pointer]), end="")

    #"+" メモリポインタが指し示す先に格納された変数をインクリメント
    elif tape[program_counter] == '+':
        memory[pointer] += 1

    #"-" メモリポインタが指し示す先に格納された変数をデクリメント
    elif tape[program_counter] == '-':
        memory[pointer] -= 1

    #"," 標準入力された値をメモリポインタが指し示す先に代入
    elif tape[program_counter] == ',':
        memory[pointer] = int(input())

    #"[" メモリポインタが指す値が0なら、対応する"]"までskip
    elif tape[program_counter] == '[':
        if memory[pointer] == 0:
            #nest構造をカウントする変数
            nest = 0
            while True:
                program_counter += 1
                if tape[program_counter] == '[':
                    nest += 1
                if tape[program_counter] == ']' and nest == 0:
                    break
                if tape[program_counter] == ']':
                    nest -= 1
    #"]" メモリポインタが指す値が非0なら、対応する"["までジャンプ
    elif tape[program_counter] == ']':
        if memory[pointer] != 0:
            #nest構造をカウントする変数
            nest = 0
            while True:
                program_counter -= 1
                if tape[program_counter] == ']':
                    nest += 1
                if tape[program_counter] == '[' and nest == 0:
                    break
                if tape[program_counter] == '[':
                    nest -= 1
                    
    #プログラム・カウンタをインクリメントする
    program_counter += 1

brainf*ckのサンプルプログラムは、ニコニコ大百科や様々なウェブサイトで公開されています。
Brainfuckとは (ブレインファックとは) [単語記事] - ニコニコ大百科