BrainfuckでのHello World!
BrainfuckでHello World!を表示させるプログラムは、様々な場所で紹介されています。
ここでは、いくつか例を挙げて、そのプログラムを解説します。
Brainf*ckについて少し
Brainf*ckはコンパイラがなるべく小さくなるように設計されたプログラミング言語です。
詳しい歴史はさておき、Brainf*ckは、メモリの番地を指し示すポインタと、メモリの内部をいじくってプログラムをする言語です。
以下の図を見てください。
使用できる命令は、以下の8通りです。以下の通りなのですが、今はあまりこだわらずにさらっと読み進めてください。
- >：ポインタのインクリメント（次のメモリ番地へ移動する）
- <：ポインタのデクリメント（前のメモリ番地へ移動する）
- +：ポインタの指す値のインクリメント（現在のメモリ番地を1だけ増やす）
- -：ポインタの指す値のデクリメント（現在のメモリ番地を1だけ減らす）
- .：ポインタの指す値を出力する
- ,：ポインタの指す値に入力する
- [：ポインタの指す値が0のとき、対応する]の直後に移動する
- ]：ポインタの指す値が0でないとき、対応する[の直後へ移動する。
なお、以下でも途中で図解をいくつか使用します。
その時の見方は、上の図を参考にしてください。
脳死で文字を全部メモリへ格納する方法
頭を使わない方法です。まずはこちらをご覧ください。
++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++
>++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ +
>++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++
>++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++
>++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ +
>++++++++++ ++++++++++ ++++++++++ ++
>++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ +++++++
>++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ +
>++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++
>++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++
>++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++
>++++++++++ ++++++++++ ++++++++++ +++
>++++++++++
<<<<<<<<<<<<
.
>.
>.
>.
>.
>.
>.
>.
>.
>.
>.
>.
>.
このコードは、各文字のASCIIコードを順番にメモリへ格納し、順に表示しています。
ASCIIコード表などを調べればわかるのですが、「A」が65、「a」が97、空白が32、改行が10です。
そして「Hello World!」は[72, 101, 108, 108, 111, 32, 87, 111, 114, 108, 100, 33, 10]です。
一文字目は「H」ですから、対応するコードは72です。
起動時、ポインタはメモリ0番目を指し、すべてのメモリで初期値は0ですから、値を72回インクリメントすれば、0番目は72になります。
メモリの指す値をインクリメント（1だけ増やす）するには、「+」を用います。
見やすいように10区切りでスペースを入れていますから、上記コードで一行目が72を表していることが確認できると思います。なお、Brainf**kにおいて、意味をなす8種類の記号以外は無視されるので、任意に改行や空白を導入し、可読性を向上させることができます。
1行目で、メモリの状態は[72, 0, 0, ...]のようになっています。
次に表示すべきは「e」です。コードは101です。これをメモリの1番目を101にしましょう。
メモリを指すポインタをインクリメントするため、「>」を書き、続いてメモリのさす値を101回インクリメントするために「+」を101回記述します。
ここまでで、メモリの状態は[72, 101, 0, ...]のようになっています。
同様に「Hello World!」全てにおいてメモリに追加していき、最後に改行文字を入れてやります。
改行文字を含めて13文字分ありますから、ここまででメモリを13個使用しています。また、ポインタも12番目(ゼロベースなので)を示しているはずです。
順番に読みだして表示していくために、一度ポインタを0に戻します。
そのために12回、ポインタをデクリメント（1だけ減らす）するので、「<」を12回記述します。
そして最後はこれらをメモリを移動しながら（＝ポインタを移動させながら）読みだしていくだけですから、ポインタのインクリメント（>）と、メモリの指す内容を表示する「.」を13回記述します。
最後の表示部分は次のように置き換えることができます。
[
.
>
]
これは、ポインタの指す内容を表示し、ポインタをインクリメントした後、インクリメント先のポインタの指すメモリの内容が0でない場合は「[」へ戻るといった動作になります。
13個の文字を表示すると、ポインタは13番目（14文字目）を指すので、そこは初期値である0が入っており、ループから抜け出します。
同じ文字はメモリの内容を再利用する
「Hello World!」には「o」が2文字、「l」が3文字ありますから、メモリ内容を再利用しない手はありません。
同じ内容の変数を何度も宣言しないのと、理論上全く同じ考え方です。
++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++
>++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ +
>++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++
>++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ +
>++++++++++ ++++++++++ ++++++++++ ++
>++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ +++++++
>++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++
>++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++
>++++++++++ ++++++++++ ++++++++++ +++
>++++++++++
<<<<<<<<<
.
>.
>.
.
>.
>.
>.
<<.
>>>.
<<<<.
>>>>>.
>.
>.
ダブってる「l」と「o」のメモリ格納を辞め、その分ポインタを移動させることで対応しています。
表示部分の4行目に、ポインタのインクリメントがないですね。
ここで「Hello」の「l」の2回目を表示しています。
「World」の「o」の表示には、2つメモリをさかのぼって、「Hello」の「o」を読み出したり、メモリの効率利用が随所で見られます。
ところで、「Hello World!」は[72, 101, 108, 108, 111, 32, 87, 111, 114, 108, 100, 33, 10]でした。「Hello」の2文字目以降の[101, 108, 108, 111]の部分なんて、その場でインクリメントした方が良いと思いませんか？
実行時に文字を作る
予めメモリに全部の文字を打つのではなく、毎度文字を作ってやる方式をとるとこんな感じになります。
++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++ .
++++++++++ ++++++++++ +++++++++ .
+++++++ ..
+++ .
>++++++++++ ++++++++++ ++++++++++ ++ .
<---------- ---------- ---- .
++++++++++ ++++++++++ ++++ .
+++ .
------ .
-------- .
>+ .
---------- ---------- --- .
だいぶコンパクトですね。
空白とエクスクラメーションマークと改行に関しては、面倒なので別のメモリで作りましたので、実行時に変数のためにメモリは2バイトしか使用していません。
上記コードは、まず「H」である72を作り、「.」で表示します。
次に「e」である101まで101-72=29回インクリメントして、さらに表示します。
次の「l」までは108-101=7回のインクリメントでよく、これを2回表示します。
「o」までは111-108=3回インクリメントですね。
次の空白文字は32なので、79回もデクリメントしないといけないのは面倒なので、ポインタをインクリメントし、隣のメモリに移動し、32を作るため32回インクリメントを行い、これを表示します。
あとは、ポインタをデクリメントして0番地に戻して、「W」を作り、表示し、といったことを繰り返します。
一番冒頭のプログラムとは全く異なった見た目ですね。
同じ動作をするプログラムコードはたくさんあると言いますが、本当に多様だと感じさせられます。
倍数を使って程よくメモリを使う
Brainf**kの「[]」は、ポインタの指す値が0になるまでのループです。
これを使って、ある特定の倍数列を簡単に得ることができます。次のコードをご覧ください。
++++++++++
[
>+
>+++++
<<-
]
上記のコードの挙動はどうなるでしょうか。ここまで読んだあなたなら察しが付くかもしれません。
一先ず、次のGIFをゆっくりご覧ください。
はじめに1行目で0番地を10にインクリメントしています。
続くループは、1番地をプラス1、その隣の2番地をプラス5しています。
ポインタを0番地に戻し、値をデクリメントして、ループの継続判定「]」へと到達します。
0番地のみに着目すれば、10にインクリメントされたのち、ループで1ずつデクリメントされますから、ループは10回だけ行われ、0番地の値が0になったときにループを抜ける構造になっています。
その間の1番地と2番地はどうでしょうか。それぞれプラス1とプラス5を行うので、10回のループの合計で1番地は$1\times10=10$、2番地は$5\times10=50$となっています。
このようにして、簡単に倍数列を得ることができます。
これを利用してHello Worldしましょう。
++++++++++
[
>+++++++
>++++++++++
>+++++++++++
>+++
>+++++++++
>+
<<<<<<-
]
>++.
>+.
>--..
+++.
>++.
>---.
<<.
+++.
------.
<-.
>>+.
>>.
上記のようなコードは、Brainf*ckのHello World! でよく見かけるパターンです。
今回は、10の倍数で、[70, 100, 110, 30, 90, 10]をあらかじめ用意して起き、各文字に対して差分を都度インクリメント・デクリメントしています。
イメージとしては次のような感じになります。
上図において、段を降りるときにポインタをインクリメント、上がるときにデクリメントし、+2などであればその分だけポインタの指す値をインクリメントします。
今回は、10の倍数を用いましたが、9の倍数を用いているコードも見かけますね。
さいごに
以上、Brainf*ckでのHello World! をいくつか見てきました。いかがだったでしょうか。
このプログラミング言語は、チューリング完全の最低条件をすれすれでいくような言語なので、一見ふざけた言語に見えます。しかし、コンパイラを小さくするために可読性が犠牲にはなっていますが、決して読みにくいような記号選びではないでしょう。
といっても、私はこれ以上Brainをf*ckされたくないので、ここらでおさらばです。