[入門] 某超難読言語Brainf*ckに挑戦してみる

このコードわかる？

このコード、何をするコードかわかりますか？

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

...

...

...

実はこれは、 Brainf*ck というプログラミング言語で書かれたれっきとしたプログラムで、 "Hello World!" を出力するコードです。

Brainf*ckは上記のように 可読性がとんでもなく低い ため、非実用的な言語ですが、後述するように8つの文字だけで構成され、非常にシンプルであることから Code Golf（ある同じアルゴリズムをいかに短いコードで解くことができるかを競う、プログラミングコンテスト）などで使われることが多い言語です。

エディタを使ってみよう

Brainf*ckはHomebrewなどでローカル環境にインストールすることが可能です。

しかし、javascriptで動くオンラインエディタがありますので、練習するにはこれで十分かと思います。

こちらのエディタの「コード」と書かれた部分に冒頭のコードをコピペし、「実行」を押すと、右側の「標準出力」に "Hello World!" が出力されるのがわかります。

基本文法

Brainf*ckには8つのコマンドがあります。いや、 8つのコマンドしかありません という表現が正しいかもしれません。

言い換えると、コーディングのために使える文字はたった8種類です。それ以外の文字はすべて無視されます。

無視されることを利用して、コードコメントとしてプログラムの中に他の文字を入れることもできます。

例えば、

値を3増やす
+++
値を2減らす
--

のように記述しても、実際に実行されるプログラムは

+++--

となります。

コマンド一覧

以下がそのコマンドの全貌です。

コマンド	操作	C言語だと？
+	値をインクリメント	(*ptr)++
-	値をデクリメント	(*ptr)--
>	次のアドレスへ	ptr++
<	前のアドレスへ	ptr--
.	値を出力	putchar(*ptr)
,	値を入力	*ptr=getchar()
[	ループ開始	while(*ptr) {
]	ループ終了	}

C言語を知っている方はポインタを学習したことがあるはずです。ポインタの理解がある方ですと、上記の操作に対応を見れば何をしたいのか理解できるかと思います。

この記事では、ポインタが何かわかっていなくてもわかるように書いていますので、なんとなくポインタについても理解でき、一石二鳥になると幸いです。

文字の出力: Hello World!

前述の通り、Brainf*ckでは8つしか命令がありません。そのため、すべて「値を1増やす、1減らす」、といった操作を組み合わせて文字を構成します。また、文字もASCIIコードとして扱うので冒頭で紹介したHello Worldを出力するコードだけでもそれなりの分量になってしまうのです。

Hello World!すべてを出力するのは大変なので、今回はHelloに絞って出力してみましょう。

まずは愚直に出力してみます。以下が文字コードになりますので、Helloを出力したければ、
72 101 108 108 111
を出力すれば良いことになります。

	1	2	3	4	5	6	7	8	9	10	11	12	13
文字	A	B	C	D	E	F	G	H	I	J	K	L	M
10進	65	66	67	68	69	70	71	72	73	74	75	76	77
文字	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
10進	78	79	80	81	82	83	84	85	86	87	88	89	90
文字	a	b	c	d	e	f	g	h	i	j	k	l	m
10進	97	98	99	100	101	102	103	104	105	106	107	108	109
文字	n	o	p	q	r	s	t	u	v	w	x	y	z
10進	110	111	112	113	114	115	116	117	118	119	120	121	122

最初に、プログラムしていく際のメモリ空間を考えます。1つのアドレスにつき、1つの値(1byte)を保持することができます。
最初は愚直なプログラムを書くためにアドレスが1つしかないケースを考えます。1byteだけが保持できる変数が1つだけある、と言い換えることもできるでしょう。

初期状態はこうです。1番目のアドレスにはASCIIコードで 0 が入っています。

アドレス	1
文字
10進	0

操作としては、

1:Hの文字を作る
2:Hを出力する
3:eの文字を作る
4:eを出力する
5:lの文字を作る
6:lを出力する
7:lを出力する
8:oの文字を作る
9:oを出力する

となります。
これから行う操作は、感覚としてプログラミングというよりちょっと便利な電卓を叩いているような感覚だと個人的には思っています。

ステップ1-2: H

Hを出力するには、値を72回インクリメントすれば良いので、 + を72回打ちます。その後に、文字を出力させる . を打ちます。

Brainf*ckでは空白や改行は無視されるので、以下の例では回数がわかりやすいように適当なところで空白を入れています。

1:Hの文字を作る
+++++ +++++ +++++ +++++ 
+++++ +++++ +++++ +++++
+++++ +++++ +++++ +++++
+++++ +++++ ++
2:Hを出力する
.

ステップ3-4: e

1ステップが終わった時点で、メモリ空間はこのようになっています。

アドレス	1
文字	H
10進	72

次にeを出力します。上記のように、メモリにはHが入っています。ASCIIコードは 72 。次の文字であるeは 101 なので、 (101-72) で29回値をインクリメントすれば、アドレス1はeを示します。

3:eの文字を作る
+++++ +++++ +++++ +++++ 
+++++ ++++
4:eを出力する
.

ステップ5-7: l

3ステップ目が終わった時点で、メモリ空間はこのようになっています。

アドレス	1
文字	e
10進	101

同様に、lを出力します。lのASCIIコードは 108 なので、 7 だけインクリメントすればいいですね。これまでと比べて大分指が楽ですね。

5:lの文字を作る
+++++ ++
6:lを出力する
.

次の文字もlです。既にアドレス1にはlが入っているので、単純にもう一度出力を行うだけでOKです。

7:lを出力する
.

ステップ8-9: o

同様に、oは 111 なので、

8:oの文字を作る
+++
9:oを出力する
.

となります。
ここまでをまとめると、

1:Hの文字を作る
+++++ +++++ +++++ +++++ 
+++++ +++++ +++++ +++++
+++++ +++++ +++++ +++++
+++++ +++++ ++
2:Hを出力する
.
3:eの文字を作る
+++++ +++++ +++++ +++++ 
+++++ ++++
4:eを出力する
.
5:lの文字を作る
+++++ ++
6:lを出力する
.
7:lを出力する
.
8:oの文字を作る
+++
9:oを出力する
.

となります。このコードを前述のエディタに貼り付けると、無事「Hello」が出力されます。

今回は文字の並びとしてすべてASCIIコードがインクリメントになりましたが、例えばoの次にlを出力したければ、値のデクリメントを利用し、 ---. とすれば Hellol と出力されることが確認できます。

ここまで +-. の3コマンドだけを使ってプログラムを書いてきました。
先程のコードからコマンドだけを取り出して書いてみると、

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.
+++++++++++++++++++++++++++++.+++++++..+++.

となり、 116bytes です。これを毎回手打ちするのは少し面倒ですよね。次は、これをもうちょっと短くしてみましょう。

ループしてみる

短くするためには、 ループ を学ぶ必要があります。

ループは [] を使って表現できます。ここでまず、先程1byteしか表現できなかったアドレスを2bytesまで表現できるように変更します。初期状態はこうです。

アドレス	1	2
文字
10進	0	0
今いるアドレス	○

今度はアドレス空間の移動を伴うので、わかりやすさのためにその時点でいるアドレスに○を付けてみました。

Hは72bytesですが、72は 9 * 8 で計算できます。この計算を上記のアドレス空間上で表現してあげます。
9 * 8は、「9回インクリメントする作業を8回連続で行う」と考えることができます。

ステップ1: ループカウンタに8をセット

ここで、メモリ上のアドレスに役割を与えてあげます。

• アドレス1をループカウンタ
• アドレス2を解を保持する変数

とします。

まず、ループカウンタに8回同じ操作を行うために8を入れていきます。

step1

ループカウンタ準備
+++++ +++

この時点でのアドレス空間は以下の通り。

アドレス	1(カウンタ)	2(解)
10進	8	0
今いるアドレス	○

ステップ2: 解に9を追加

解に1度目のループで、9を追加します。

step2

アドレス2に移動
>
解に9を追加
+++++ ++++

アドレス	1(カウンタ)	2(解)
10進	8	9
今いるアドレス		○

ステップ3: ループカウンタを減らす

次に、カウンタ1に戻り、ループカウンタを減らします。

step3

アドレス1に移動
<
ループカウンタを減らす
-

アドレス	1(カウンタ)	2(解)
10進	7	9
今いるアドレス	○

ステップ4: ループにする

この後、step2をもう一度行うと、解が18になりますよね。

アドレス	1(カウンタ)	2(解)
10進	7	18
今いるアドレス		○

お気づきかとは思いますが、このまま「解に9を追加する」という作業を合計8回繰り返すと、アドレス2の解が72になります。

すなわち、ステップ２，ステップ３の操作を何度も繰り返せばいいのです。これをBrainf*ckで表現すると、以下のようになります。

step4

[
  アドレス2に移動
  >
  解に9を追加
  +++++ ++++
  アドレス1に移動
  <
  ループカウンタを減らす
  -
]

記事の最初の方のC言語との対応を見ていただくと、他のプログラミング言語を触ったことがある方にはわかりやすいのではないでしょうか？

C言語で書くと

while(*ptr) {
  ptr++;
  (*ptr)++; (*ptr)++; (*ptr)++; (*ptr)++; (*ptr)++; (*ptr)++; (*ptr)++; (*ptr)++; (*ptr)++;
  ptr--;
  (*ptr)--;
}

Brainf*ckにはループの条件式を書く部分がありません。Brainf*ckでは、条件式の代わりに「ループの終端 ] の時点でいるアドレスが0だったらループを終える」というルールになっています。

すなわち、ループを繰り返し、アドレス空間が以下のようになれば、ループ終了です。

アドレス	1(カウンタ)	2(解)
文字		H
10進	0	72
今いるアドレス	○

ステップ5: Hを出力

最後に、Hを出力します。ループが終わった後のアドレス位置は1なので、解の場所に移動し、値を出力します。

step5

アドレス2に移動
>
値を出力
.

アドレス	1(カウンタ)	2(解)
文字		H
10進	0	72
今いるアドレス		○

コードの全貌は以下の通り。

ループカウンタ準備
+++++ +++
[
  アドレス2に移動
  >
  解に9を追加
  +++++ ++++
  アドレス1に移動
  <
  ループカウンタを減らす
  -
]
アドレス2に移動
>
値を出力
.

これにより、Hを出力するコードは

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.

の73bytesから

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

24bytesに削減されました。

"Hello" も 116 -> 67bytes に削減することに成功です！

これでループと、アドレス空間の使い方がわかったのではないでしょうか。
複雑なコードを書こうとすると、もっと多数のアドレス空間を利用することになります。頭の中でアドレス空間の現在の状態をイメージしながらコードを書いていくと速く書けるようになるでしょう。暗算でそろばんを使う感覚に近いかもしれません（私自身はそろばんの経験は浅いので熟達した方にツッコまれるかもしれませんが・・・）

実は冒頭の "Hello World!" のプログラムは、二重ループや複数のアドレスを駆使して短い文字で実現されています。（プログラム自体はWikipediaより）

同様に、「足し算」や「条件分岐」もここまで表現してきた文字で実現可能です。
いつか記事の続きを書こうと思いますが、どうやって実現できるか、考えてみるのも面白いでしょう。

参考

こちらの動画が大変わかりやすいです！