brainfuck入門

date: 2015-04-09

cの知識のみ仮定し、基本的な部分のみ解説する。

仕様

基本的な仕様や命令はBrainfuck #Brainfuckの言語仕様 - Wikipediaに任せる。

また、可搬性の問題には触れないこととする。参考: http://en.wikipedia.org/wiki/Brainfuck#Portability_issues

例

+
[
    .
    +
]

は、1cellが8bitの整数の処理系のとき、

char a = 0;

++a;
while (a) {
    putchar(a);
    ++a;
}

と読め、1から255を文字として出力する。

変数

[,]の前後でdata pointerを変化させない限り、任意個の変数が自由に使えるものと考えてよい。この条件はむやみに破るべきではなく、実際この文章中ではすべて成立している。しかし破らないと書けないプログラムも存在する。

基本命令

定数の加算は足したい数だけ+を並べればよい。減算も同様。

0の代入は[-]と書く。これはcで書くと、

while (a) {
    --a;
}

定数の代入は、0を代入した後に定数を加算すればよい。

for文

while (*p) {
    ...
}

の形のwhile文は自明に書ける。それを用いて、

for (; *p != 0; --(*p)) {
    ...
}

が書ける。loopの内部でpも*pも変更されない時、これは*p回の繰り返しを表す。ただし変数*pは消費され0になる。brainfuckで書くと[ {A} -]。

変数間の値の移動操作

変数から変数への代入や加算は少し工夫が要る。

まず、

for (; 0 < a; --a) {
    ++b;
}

のように書くことで、

b += a;
a = 0;

相当の操作ができる。brainfuckでは[>+<-]となる。

さらに、簡単に加算先を増やすことができ、

b += a;
c += a;
a = 0;

相当の操作ができる。brainfuckでは[>+>+<<-]。

また、これらの前に加算先に0を代入することで、変数値の(代入元を破壊しながらの)代入が可能になる。

以上を用いて普通の代入が行える。

b = a;
c = a;
a = 0;

a = c;
c = 0;

のように、別な変数cを仲介とすることで、b = a;の形の代入となる。

これをbrainfuckに直すと、>[-]>[-]<< [>+>+<<-] >>[<<+>>-]<<のようになる。

乗算

定数倍は加算の延長で扱える。[>+++<-]のように書くことで定数倍しながらの(破壊的)加算ができ、あとは同様にすればよい。

変数どうしの乗算は加算代入演算を用い、

for (; 0 < a; --a) {
    c += b;
}

のようにする。

brainfuckで直に書くと[>[>+>+<<-]>>[<<+>>-]<<<-](p[2] == 0,p[3] == 0のときp[2] = p[0] * p[1])などとなる。

if文

if (a) {
    ...
}

は、

while (a) {
    ...
    a = 0;
}

で表せる。ただしaは消費される。[ {A} [-]]といった形となる。

さらに、

if (a) {
    ...
} else {
    ...
}

は、

b = 1;
while (a) {
    ...
    a = b = 0;
}
while (b) {
    ...
    b = 0;
}

で表現できる。a,bは消費される。

よってp[1]を仲介としてp[0]で分岐するif文は>+<[ {THEN} [-]>-<]>[< {ELSE} >-]<となる。ただし、p[0]は消費され、p[1]は0であり、{THEN}, {ELSE}はp, p[1]を保存するとする。なおこのとき、if文の前後、{THEN}, {ELSE}の直前の各時点でpの値は共通となる。

p[0]の初期化の位置などは都合で適当に前後させたり{THEN}と融合させるとよい。

論理演算

if文より作れる。

比較

等値判定は減算から簡単に作ることができる。

大小の比較は多少複雑で、

c = 0;
for (; b != 0; --b) {
    if (! a) {
        c = 1;
    }
    a += 1;
}

とする。これは

c = a < b;
a -= b;
b = 0;

と同じであり、上の議論によりbrainfuckで書き表せる。

<=, >, >=は<を用いて作れる。

除算

c = 0;
while (b <= a) {
    c += 1;
    a -= b;
}

とすると、

c = a / b;
a = a % b;
b = 0;

となる。

他

以上までを理解すればbrainfuckを実用的に使えるようになります。例えば競技プログラミングの簡単な問題解くとかです。

ただしこの記事の範囲では決め打ちされた量のメモリ上の操作にしか言及していない、つまりメモリを動的に確保できる機構がありません。したがって、ここで書いた内容のみを用いても書けないプログラムがあることには注意が必要です。
例えば任意の大きさの自然数を2つ受けとってその和を出力するプログラムは書けません。stackとかlistとかそういうのがまだだめです。

他の日本語のよい資料としては実用Brainf*ckプログラミングがあります。

brainfuck入門

追記: 2016年 8月 24日水曜日 21:28:38 JST

最近書かれた丁寧な資料として、Brainf**k講座(1) Hello, BF! - ange1のブログがあります。全8回。

再帰的な計算までの技法に関する解説記事は(基本的な事項であるにも関わらず)まだなさそうなので誰か書いて教えてください。適当な計算の教科書に載っている気もするけど。