BrainfuckにBrainをHackされた男(Brainfuck入門)

December 05, 2018 (Last Modified: December 04, 2018)

この記事は、OIT Advent Calendar 2018の5日目の記事です。
Twitterで行ったアンケートで最も票が多かったBrainfuckについての記事になります。

Brainfuckとは

Brainfuck（ブレインファック）は難解プログラミング言語のひとつ。なお名称に卑語が含まれるため、Brainf*ckなどと表記されることがある。
開発者Urban Müllerがコンパイラがなるべく小さくなる言語として考案した。実際、Müllerが開発したコンパイラのサイズはわずか123バイト、インタプリタは98バイトであった。
Brainfuckプログラムは非常に可読性・記述性が低いため実用性は期待できないが、チューリング完全である。その簡潔さから多くの派生言語を生み出すこととなった。
引用:wikipediaより

Brainfuckの魅力

言語仕様が簡単
メモリが無限ならチューリング完全な言語なので、基本的にどんなプログラムも書ける
ポインタの理解が深まる(諸説ある)
コードが顔文字みたいで可愛い(構文以外の文字列は無視される)
,(>,<) = = = = \[> - <-]/ .
一発芸できる
AtCoderで使える

Brainfuckの言語仕様

> ポインタを１進める。C言語なら ++ptr;
< ポインタを１戻す。C言語なら --prt;
+ ポインタの指す要素の値を１増やす。C言語なら ++(*ptr);
- ポインタの指す要素の値を１減らす C言語なら --(*ptr);
. ポインタの指す要素の値を外に出力。C言語なら putchar(*ptr);
, 外から値を入力して、ポインタの指す場所へ入れる。C言語なら *ptr = getchar();
[ ポインタの指す要素の値が 0 だったら対応する次の ] までジャンプ。C言語なら while(*ptr){
] 対応する前の [ までジャンプ。C言語なら }

Brainfuckに必要なもの

ASCIIコード表(表、変換器)
紙とペン
エディタ([]のハイライトは必須)
コンパイラorインタプリタ(http://moon.kmc.gr.jp/~prime/brainf_ck/env/)

Brainfuckの考え方

長い配列をイメージする(各要素は0で初期化される)
出力したい文字のASCIIを配列内で作成して出力する
主な配列への操作

番地の移動( < >)
値の変更(+ -)
値の入力(,)

Brainfuck入門の準備

以降のサンプルはすべて説明用に小さい値を利用します。実際のコードでは出力はASCIIコードなのでもっと大きな値になります。

紹介するコードはあくまで一例なので他の実装方法もあります。

ループ

3回のループを実装する場合

+++[->処理<]

要素の初期化

0になるまで-するループで実装

[-]

要素の移動

隣の番地に移動して要素を+する。前の番地に戻って要素を0になるまで-する。

[>+<-]

0番地の2を1番地へ移動する例

足し算

要素の移動と同じコードになる。(要素の移動は０との足し算)

[>+<-]

2 + 4の例

引き算

1番地-0番地を1番地へ入れるコード。足し算と同じことをするだけ(引くだけ)。

[>-<-]

4 - 2の例

値のコピー

意外と重要。Brainfuckでコードを書くと、ほとんどの操作が破棄的操作になる。

値を使いまわしたいことはよくあるので、値のコピーを行う必要がある。

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

0番地の値を1番地と2番地にコピーする。

[>+>+<<-]

次のループで2番地の値を0番地に移動する。

[<<+>>-]

定数の掛け算

0番地に++で2をセットする。1番地に++する処理を0番地が0になるまで繰り返す。(2*2の処理)

++[->++<]

2 * 2の例

これを応用して"H"のASCIIコードに対応する72(8*9)を出力するコードは以下のようになる。

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

掛け算を使わずに"Hello World!“の一文字目"H"を出力する場合、0x48回(72)回+を記述しなければならない。

“Hello World!“を出力する場合……考えたくもないですね。

掛け算

足し算と値のコピーを組み合わせることで実装できる。

0番地 * 1番地の結果を2番地に入れる。

0番地が0になるまで{1番地の値を2番地に足す。0番地の値を1減らす}を繰り返す。

[> 1番地へ移動
[>+>+<<-]>>[<<+>>-]　ここで値のコピーをしてる
<<<-]　0番地に戻って-1する

1 * 2の例

条件分岐

Brainfuckにif文は存在しない。whileを応用して作る。

・一番簡単なif文

0番地が0でなければ処理を実行する。[-]で0番地は初期化されるので処理は一回しか実行されない。

処理の最後は0番地へ戻る必要がある。

[処理[-]]

・else文

0番地が0でなければ処理1を、0なら処理2を実行

処理1は0番地へ、処理2は1番地に戻る必要がある。

+<[処理1>-<[-]]>[処理2-]

・大小の比較

A:0番地、B:1番地、C:2番地、D:3番地

http://d.hatena.ne.jp/yurupo/20120508/1338630601

# if(A>B){～}
>[>+>+<<-]>[<+>-]<<            # D=B;
[>>+>>+<<<<-]>>>>[<<<<+>>>>-]< # C=A;
[<                             # while(D){
  [>]>[[-]+<+>>>]<<<           #   if(!C)C++,D=1;
  ->-                          #   C--,D--;
]<                             # }          CとDのどちらが先に0になるかで判定。
[[-]<<～>>]<<                  # if(C){C=0;～}

# if(A<B){～}
[>>+>+<<<-]>>[<<+>>-]<         # C=B;
[>+>>+<<<-]>>>[<<<+>>>-]<      # D=A;  数値を逆にしただけ。
[<                             # while(D){
  [>]>[[-]+<+>>>]<<<           #   if(!C)C++,D=1;
  ->-                          #   C--,D--;
]<                             # }
[[-]<<～>>]<<                   # if(C){C=0;～}

割り算

https://www.slideshare.net/KMC_JP/brainfck

0番地÷1番地の商を6番地に、あまりを7番地に入れる。(2~5番地は一時変数)

0番地 >= 1番地である間、{0番地から1番地を引き、6番地に加える}という作業を繰り返し、0番地<1番地になったら0番地を7番地に入れる。

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

こんな感じで簡単な処理でも実装はとてもめんどくさいです。ここまで理解すれば、AtCoder-ABCのAレベルなら解けるはず。

Brainfuck入門

手始めにHello World!

コードは以下の様になります。

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

まず最初に"Hello World!“をASCIIに変換します。

Hello World!　→　48 65 6c 6c 6f 20 57 6f 72 6c 64 21(Hex)

→　72 101 108 108 111 32 87 111 114 108 100 33(Decimal)

あとは、各文字に対応する文字コードを作ってやればいいわけです。

H : 9 * 8 = 72 => 0x48

e : 9 * 3 + 72 + 2 = 101 => 0x65

l : 101 + 7 = 108 => 0x6c

l : 108 => 0x6c

o : 108 + 3 = 111 => 0x6f

' ‘: 111 - 8 * 9 - 7 = 32 => 0x20

W : 32 + 9 * 6 + 1 = 87 => 0x57

o : 87 + 9 * 2 + 6 = 111 => 0x6f

r : 111 + 3 = 114 => 0x72

l : 114 - 6 = 108 => 0x6c

d : 108 - 8 = 100 => 0x64

! : 100 - 9 * 7 - 4 = 33 => 0x21

これが理解できればどんな文字列でも出力できるので一発芸ができますね。

入力と処理 (AtCoder111-A)

入力をもとに処理する問題の例題です。

入力の各桁を1なら9、9なら1で出力する問題。

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

入力は必ず3桁なのでとりあえず3回ループするために3を0番地に作る。
2番地に100を作る。(10 * 10)
1番地に数値を入力。
2番地 - 1番地を行う。(100 - 49 or 100 - 57)
2番地 + 6を行う。(51 + 6 = 57 => 0x39 => “9” or 43 + 6 = 49 => 0x31 => “1”)
2番地を0で初期化する。
0番地に戻る。

Brainfuckをさらに学びたい人向け

一発芸だけしたい人向け

まとめ

ざっくりとしたBrainfuckの解説記事を書いてみました。ちゃんと記事を読んでいただければ、今までネタでしかなかったBrainfuckのコードがネタじゃなくなると思います。
(メモリレベルで操作を考えると、普段どれだけ高級な言語を使っているかが身に染みてわかりますね….)

普通のプログラミングとは考え方がかなり異なるのでパズルを解いてるような感覚で楽しいですね。

言語の実用性に関してですが基本的にはありません。

極稀にBrainfuckが真価を発揮する競プロ問題もあるとかないとかなので、頭の片隅にでも入れておくと活躍する場面が来るかもしれないです。

あとはコードの難読化くらいですね。

Brainfuckがどんな言語なのか雰囲気だけでも伝わっていれば幸いです。

目次