Brainfuck


[外]の表記がついた項目は外部ページへリンクしています。

言語仕様


BFの言語仕様を紹介していきます。

命令語はたったの8つ! ! 

BFを用いて実行できる命令は > < + - . , [ ] の8つしかありませんが、その命令の組み合わせで多様な処理ができます。命令語の解説は8つの命令語をご覧下さい。命令語の種類と動作領域は少ない(狭い)ですが他の言語と比べて劣っている理由にはなりません。理論上Cと同等の表現が可能と言われています。

チューリング完全である

チューリング・マシンという仮想計算機があるのですが、こいつは「0を書き込む」「1を書き込む」「左に移動」「右に移動」等のごく簡単な命令のみ実行できる仮想機械です。チューリング完全であるということはチューリング・マシンで実現できるあらゆるプログラムがその言語で組めるということです。BFはチューリング完全です。

命令語以外はコメント扱い?

プログラム中の「> < + - . , [ ]」以外の文字は、恐らく一般的なインタプリタでは無効文字として扱われる筈なのでコード中にコメントとして残しておいても問題ありません。一般的と言ったのはインタプリタの処理系によって無効文字の設定が左右されてしまうからです。私の使っている環境では無視されます。

★結論=インタプリタに依存します。

処理は配列とポインタを用いて実行される

BFにはメモリ上に30000byteのbyte型の配列一つと配列上の位置を示す一つのポインタが用意されています。配列の要素はすべてゼロで初期化され、ポインタの初期位置は配列の先頭になります。BFはこのポインタを移動させて対象の要素を変更する命令を組み合わせることでプログラムを作成します。

プログラム始動の状態を図にすると以下になる。

配列 01234567829999
配列の要素値 0000000000
ポインタ位置

上記表と言語仕様の刷り合わせを以下に示します。

  1. 配列は0〜29999の範囲の30000バイト配列
  2. 配列の要素値は0で初期化されている
  3. ポインタ位置は最初、配列の先頭にある

配列の要素値がとりうる値の範囲

配列に格納できる値の範囲は0から255までの1byte(8bit)の値をとり負の数はありません。初期値は0です。メモリの値が255の時に「+」を実行した場合は循環して0に戻り、メモリの値が0の時に「-」を実行した場合は255になります。

つまりプログラミングするときに、値を0の状態から255にしたい場合は「+」を255個記述しなくても「-」1個記述すれば実現できます。コーディングに役立つ情報なので覚えておきましょう。

ポインタが取り得る範囲

ポインタが0に位置するときに「<」が実行されメモリの負のアドレス(ポインタ < 0)に移動した場合、処理系として用意されている領域からポインタが脱してしまうのでプログラムの実行は中止されます。正のアドレスの限界に来た場合に「>」が実行された場合も同じだと思います。

でもご安心を。こうした問題は大概インタプリタ側で循環配列として対処されているはずなので、ユーザ側が気にする事項ではありません。つまりポインタが正負どちらにはみ出ても逆側の端に移動させて循環させれば、ポインタが範囲外に出ることがなくなるということです。

ちゃんとエラー処理するインタプリタもあるかもね。

★結論=インタプリタに依存します