Openstack Summit Tokyoに行ってきた。
ATC(Active Technical Contributor)としてOpenstack Summitに参加してきました。
自分が行ったのは、簡単なドキュメントのFixで、微力ではありますがOpenstackに貢献できてうれしく思います。
magnum projectの動向などは別記事で書いていきたいと思います。
Brainf**kのHello Worldを読む
Brainf**kとは
はてなキーワードによると以下のようである。
Urban Müllerが開発した難解プログラミング言語。「fuck」の言葉が卑猥であるため、しばしば「Brainf**k」「BF」などとも表記される。以下の8つのコマンドのみから成り、それでいてチューリング完全な計算が可能である。
仕様が極めて簡単なので処理系を小さくすることができ、オリジナルの実装では処理系が240バイトに収まった。
ざっくり書くと、Brainf**kの記述は
- ポインタの移動(>,<)
- ポインタの示すデータの増減(+,-)
- ポインタの示すデータの表示(.)
- 繰り返しの制御([,])
によって行われる。
特にポインタに関する知識がない場合、これだけだと理解できないはずなので、以下に説明をしていく。
Hello Worldを読む
+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-. ------------.<++++++++.--------.+++.------.--------.>+.
これだけでは何の処理が行われているか全くわからない。
前提知識としてはASCIIコードの存在があるが、ここではアルファベットや記号がある特定の数字と対応していて、数字を使って示すことができることを把握していればいいだろう。
たとえばAと対応する数字は10進数で65、16進数で0x41である。これらはASCII文字コード : IT用語辞典などで調べることができる。
ポインタについて
Brainf*ckを理解するためには、まずポインタについて理解する必要がある。
非常に簡単に説明すると、ポインタは変数に対応する場所を示すものである。
ポインタを動かすと、ポインタが示す変数が変わることで別の変数に対して操作を行うことができる。
詳しくは以下で説明していく。
ポインタの示すデータの増減
まず最初の部分であるが、
+++++++++
[00][00][00][00][00] ^
ポインタの位置は、初期状態では一番先頭にある。そのためポインタの示す変数に対して「+」、すなわちインクリメントすると、
[01][00][00][00][00] ^
[02][00][00][00][00] ^
このように一番最初のポインタが示した変数の中身がインクリメント(1つ加算)される。
「-」も「+」同様にポインタが示す値がデクリメント(1つ減算)される。
最終的には、「+」を9回行うので
[09][00][00][00][00] ^
となる。
ポインタの移動
「[」「]」は「]」の時点でポインタが示す変数が0になるまで繰り返しを行う。(これについては後述)
[>++++++++>+++++++++++>+++++<<<-]
「>」はポインタが示す場所をインクリメント(1つ大きく)させる。ポインタが示す場所は、
[09][00][00][00][00] ^
へ移動する。
「+」を8回行うので
[09][08][00][00][00] ^
同様の要領で「>」し「+」を行うと
[09][08][0b][00][00] ^
[09][08][0b][05][00] ^
「<」を3回行うので
[09][08][0b][05][00] ^
その後「-」でデクリメント(1つ引く)ので以下の通りになる。
[08][08][0b][05][00] ^
繰り返しの制御
「]」はポインタの示す変数の値が0でなければ対応する「[」にジャンプすることを示している。
この場合、ポインタが示す変数の値は「08」であるため、処理は対応する「[」へジャンプする。
[>++++++++>+++++++++++>+++++<<<-] ^
したがって、この一連の流れがもう一度行われることになる。
これらが繰り返されていくと最終的には以下のようになる。
[00][48][63][2d][00] ^
「[」はポインタの示す変数の値が0であれば対応する「]」にジャンプすることを示している。この時点はポインタが示す値0であるので、
[>++++++++>+++++++++++>+++++<<<-]>. ^
へジャンプし、その次にある処理へ進むことになる。
ポインタの示すデータの表示
その後は「>.」なので「>」でポインタは一つ右に移動
「.」でポインタが示した値を表示するので、
[00][48][63][2d][00] ^
「48」はASCIIコード表において「H」に対応している。そのため画面にはHが表示される。
(これより先はその繰り返しなので省略)
Brainf**ck 自体の説明が長くなってしまったので、インタープリタを作った話はまた後日書きます。