Brainf**k講座(1) Hello, BF!
はじめに
Brainf**kは、命令が+-<>[],.のたった8種類という、超シンプルなプログラミング言語であり、初心者にも易しい ( はず!! 絶対! …多分 ) のですが、実用的な組み方の指針と言うのがなかなかなく、興味を持ってもとっつきにくいのではないかと感じています。
そこで、実際のコードを元に、どのように組んでいくのか、講座形式で紹介していきたいと思います。全部で8回の予定です。
講座一覧
- Hello, BF!
導入およびシンプルなループによる数値生成
今回の話題
まずはお約束ということで、“Hello, world!”ならぬ“Hello, BF!”を題材とした導入、シンプルなループによる数値生成を紹介したいと思います。
Brainf**kの実行モデル
コードの実行
Brainf**kのコードは、+-<>[],.の8種類の命令からなります。それ以外の文字はコメントとして無視されます。
実行時は、先頭からコードを1文字ずつ見ていって、その文字に対応する命令を実行していく、という形をとります。最後まで到達すると、そこで実行が終了します。
実行モデル
Brainf**kの実行環境は、数値を格納するための複数のセル ( 初期値 0 ) と、操作対象のセル ( 1つ ) の位置 ( ポインタ ) を管理しています。命令によって、セルの操作を行ったり、セルの位置を移動したりといったことを繰り返すことで、目的を果たすということです。
今回は、まず基本的な+-.と、そののち<>[]を紹介します。
Hello, BF!
naiveな実装
ではまずは、naiveな実装から見ていきます。セルの移動はさておき、セルの操作として+-,を使います。それぞれの機能としては、
+… セルの値を1増やす-… セルの値を1減らす.… セルの値を文字コードとする文字を出力する
ね? 簡単でしょう? ( 定型句 ) なので、“Hello, BF!”の各文字コードに対応する、72,101,108(2回),111,44,32,66,70,33 の数値を作って出力してあげれば、それで“Hello, BF!”の出来上がりです。
このようなコードになります。文字出力.毎に改行を入れていますが、改行もコメント扱いであって、特に入れても入れなくても動作に影響はありません。さて、+72個で H の文字コード72を作り.で出力、続いて+29個でセルの値を29増やし、e の文字コード101を作る、また、o の次の , については-67個でセルの値を67減らし…と、+-によって値を増減させています。
さあ! これであなたもBrainf**k使いの仲間入りです!
シンプルなループによる値生成
…そうは言っても、アルファベット1文字出力するために何十文字も+-を書いていたのでは気が滅入ります。そこで、シンプルなループによって、もっと短い文字数で値を生成 ( 増減 ) する方法を紹介します。
新しい命令の紹介
ここで、新たに<>[]を紹介します。機能としては次の通り。
<… セルを1つ左に移動する>… セルを1つ右に移動する[… 現在のセルの値を見て、非ゼロなら次の命令へ、ゼロなら対応する]の次の命令へ移る]… 現在のセルの値を見て、非ゼロなら対応する[の次の命令へ、ゼロなら次の命令へ移る
左や右と書いていますが、Brainf**kの実行環境が管理するセルは、1次元的な広がりを持つもので、それを左右の方向に伸びるものとして見做しています。…ちょうど記号とも合致しますので。
[]については、他の命令よりも複雑です。[と]は入れ子にすることもできますが、必ず同じ個数を使い、1対1に対応させる必要があります。これらの命令はセルの値によって挙動を変えるもので、すなわち条件分岐に使えるものです。これだけで、ループやif文等をこなせる優れものです。
ループの記述
では、これらの命令をつくってどのようにループを作るかを見ていきます。まずは先頭の H に対応する 72 を作るループです。
++++++++[->+++++++++<]
<>によってセルの移動を行っています。これによって、どのセルに移動したかが分かるように、セルに名前をつけてコードにもコメントとして表すようにします。以下では次のようにします。
A++++++++[A->B+++++++++<A]
2個のA,Bというセルを行ったり来たりして操作を行う様子は次の図のようになっています。
- 直前の
+によってAに8がセットされた状態で、[が実行される。非ゼロなので、[の次の処理に移る -でAを1減らし、>で1つ右のBに位置を変える+によって、Bが9増える<によって、1つ左のAに戻り、]では、依然Aが非ゼロのため、2. と同じ命令に移る- 再びAが1減り、Bに位置を変える
- Bが9増える
… - ( Aにセットされていた 8 に対応した ) 8回の繰り返しでBが72になった後、A が 0 の状態で
]が実行される - 今度は 0 なので、この部分の実行が完了する ( コードがこの先続いていれば、そちらに制御が移る )
ちょうど A を制御変数として、[]の中身によってBの加算を繰り返すループ構造になっており、8×9の計算がなされるわけです。ループ終了後、Aの値は0になり、代わりにBが72になっています。
この後、今度は101を作ろうと思えば、72から30増やして1減らせばよいわけです。その部分のコードは例えば次のようになります。
A+++++[A->B++++++<A]A>B-
このループによって、Bに5×6が加算され、そののち1減らされます。
大きな数を足し引きする部分をこのようなループに替えたコードは次のようになります。以前のコードより大分すっきりしているのが分かるかと思います。
複数の値を同時に作る
さて、ループによってコードが簡潔になりましたが、文字コードが大きく変化するところを1つのセルで管理するにはやや無駄が感じられます。
そこで、複数のセルに幾つか値を作っておいて、近い文字コードは同じセルを、大きく違う文字コードは別のセルを見るようにすれば良いのではないかと考えられます。この場合、ループの中の処理を、1つのセルではなく、複数のセルをまとめて変化させるようにすることで対応できます。サンプルとしては次のコードが挙げられます。
先ほどと同じようにループ部分の処理によるセルの値の遷移を図にすると、次のようになり、複数の値がループ毎に更新されているのが分かるかと思います。
今回のまとめ
- Brainf**kのコードは
+-<>,.[]の8種類の文字で構成されます。( その他の文字はコメント ) - Brainf**kは内部に1次元のセルを持っていて、そこでの値操作、位置変更によって目的を達成します
+-はセルの値を増減させます.はセルの値を文字コードとして出力します<>はセルの位置を移動します[]を使うことでループを組むことができます
おわりに
まずはBrainf**kで、一般的な“Hello, XX!”の組み方を説明しました。次はいよいよ最後の命令である,を紹介していきたいと思います。
