Brainfuckの基礎

当記事は以下の記事を参考としています。

そもそもPietって何

PietとはPiet Mondrianという抽象芸術家の作品からコンセプトを得た画像でコードを書く言語です。

色

Pietでは20色(命令18色+特殊2色)の色で書くことができます。
それ以外の色の場合は実装に依存します。

rgbのそれぞれの値がFFとC0の組み合わせ、FFと00の組み合わせ、C0と00の組み合わせの#C0C0C0を除く色がPietの命令で用いられる色です。

以下は#000000と#FFFFFFを除く色の話です。

`100`	`110`	`010`	`011`	`001`	`101`
`#FFC0C0`	`#FFFFC0`	`#C0FFC0`	`#C0FFFF`	`#C0C0FF`	`#FFC0FF`
`#FF0000`	`#FFFF00`	`#00FF00`	`#00FFFF`	`#0000FF`	`#FF00FF`
`#C00000`	`#C0C000`	`#00C000`	`#00C0C0`	`#0000C0`	`#C000C0`

例えば#FFC0C0と#FF0000と#C00000のような組み合わせは際立っている色が同じ100のパターンであるため同じ色相とみなされます。

#0000FFは#FF0000から見て右に4つずれているので色相が4段階変化しているとPietでは解釈されます。
また、この表の両端はPietの仕様上繋がっているので、#FFFF00は#FF00FFから見て右に2つずれているとみなし色相が2段階変化していると解釈します。

#00C0C0は#C0FFFFから見て下へ2つずれているので明度が2段階変化しているとPietでは解釈されます。
また、この表の上下端はPietの仕様上繋がっているので、#00FF00は#00C000から見て下に2つずれているとみなし明度が2段階変化していると解釈します。

以上を踏まえて#C000C0は#FFC0C0から見て色相は5段階変化、明度は2段階変化しているとみなせます。
Pietにおいては色相の変化と明度の変化でコマンドを定義します。
これは色そのものに絶対的な命令があるのではなく時間や場所によってその色の解釈が変化することを表します。

codel

Pietの命令は画素単位ではありません。
なぜなら画素単位で実行を行うとなるとコードを書く時に小さすぎて見えないからです。
だから、codelといった単位で解釈を行います。
codelは一般的には正方形です。

カラーブロック

カラーブロックとは白と黒を除く色のcodelの連続した塊を表します。
つまり中身に穴があったり別の色のカラーブロックが入っていても大丈夫です。
ちなみに白色のcodelは1つからなるカラーブロックとみなされます。
つまり白色のcodelがいくつ連続してもそれぞれは独立したカラーブロックです。

スタック

Pietではデータの記憶はstackで行います。
スタックに積むことができるのは整数ですが、文字を入出力する時には適当な手段で対応する文字が出力されたりするでしょう。
スタックは概念的には無限に積み上げられますが電子計算機の記憶は高々有限なので、十分な高さが積めるのであれば実装に依存します。

Codel Chooser(CC)と方向ポインタ(DP)

Codel Chooser(CC)

Codel Chooser(CC)とは進行方向のなかで最も端となるcodelが複数ある時、右側と左側どちらに分岐するかをインタプリタが判断する時に使用します。

この例では進行方向が右の時、CCによって、上側と下側に分岐します。

ただし、以下の例ではどちらのCCを取っても分岐は行われません。

その理由は右向きに進行方向に対して右端と言えるcodelがただ一つしかないからです。

このCCは、インタープリターが現在のCCでは進行不能と判断した場合に入れ替えられます。

そして同じ進行方向(DP)で二度以上入れ替えられることはありません。
なぜならその前に進行方向(DP)が変更されるからです。

方向ポインタ(DP)

方向ポインタとはカラーブロックをどの方向に解釈していくかというものです。
基本的にこれは、その方向で進行不能であると判断された時に、右下左上の順に切り替えられます。
ただし、上の次は右に切り替えられます。

この時、一つのカラーブロックで全てのCCとDPの組み合わせ(全8通り)を試しても、インタープリターが現在のカラーブロックに留まり続けたら、それ以上の変化はないと判断され、プログラムは終了します。

白カラーブロック

白のカラーブロックは1つのcodelからなります。
そして、白色から命令のカラーブロックに移動した場合でもその命令は実行されません。
また、他の色のカラーブロックに一度も入らずに二度以上同じ白カラーブロックを同じ進行方向で通過した場合、プログラムは終了します。

端と黒のブロック

黒のブロックや端は進行不能な領域です。
インタープリターが進行不能な領域に進もうとするとCCをかえ、それでも進行が不能であればDPをかえます。
これを最大8回繰り返し、それでもいかなる方向にも進行ができない場合、プログラムは終了します。

コマンド

スタックがないなどの要因で実行ができない場合はその実行は無視されます。

色相変化/明度変化	変化なし	1段階変化	2段階変化
変化なし	none	push	pop
1段階変化	add(`+`)	sub(`-`)	mul(`×`)
2段階変化	div(`/`)	mod(`%`)	not
3段階変化	greater(`>`)	pointer	switch
4段階変化	dup	roll	in(number)
5段階変化	in(char)	out(number)	out(char)

二項演算子は現在スタックに積まれている値を2つ取り出し、後に取り出された[演算子]先に取り出された値を結果として返します。
例えばスタックが1,2,3,4,5と積まれていた場合にmodなどをおこなうと、5%4の計算が行われます。
ただし、modは必ずスタックから先に取り出された数の符号に等しくなります。
つまり-1 mod 3 = 2であり、-4 mod -3 = -1
また、greaterはtrueでは1をfalseでは0を結果として返します。
notはスタックから一つ値を取り出し、0なら1を、それ以外なら0を結果として返します。
結果として返された値はスタックの一番上に積まれます。

pushは現在いるカラーブロックの隣接する同色のcodelの数をサイズとしてスタックに積みます。
popは現在スタックに積まれている値を1つ取り出し、破棄します。

pointerは現在スタックに積まれている値を取り出し、その数だけDPを時計回りに回転させます。
もし取り出された数が負の数なら半時計周りに回ります。
switchは現在スタックに積まれている値を取り出し、その数だけCCを切り替えます。
もし取り出された数が負の数なら回数の絶対値だけ切り替えます。

dupは現在スタックに積まれている値を1つ取り出し、その値を2つスタックに積みます。

outは現在スタックに積まれている値を1つ取り出し、適当な形式で表示します。
numberは値をそのまま10進数の整数として表示します。
charは値に対応するUnicodeの文字を表示します。

inは適当な形式で入力された値をスタックに積みます。
numberは入力された値をそのまま10進数の整数として解釈され、その値が積まれます。
charは入力された文字に対応するUnicodeの値が整数として積まれます。

rollは少し複雑な命令です。
rollはスタックから順に値を2つ取り出します。
最初に取り出した値は回転数、二つ目に取り出した値は深さです。
まずは下の例を見てみましょう。

#stack
|01|02|03|04|05|03|02|
↓roll
|01|02|04|05|03|

この例では、最初にスタックから取り出される02が回転数、次にスタックから取り出される03が深さとなります。
深さとはスタックの最上位からどこまでを回転の有効範囲にするかを表します。
今回は深さが03なので、|03|04|05|が回転の対象となります。
そして1回転の定義ですが、回転させる範囲に関して、最上位スタックを最下位に、そしてそれ以外のスタックは繰り上げといった感じです。
例えば|03|04|05|を一回転させると|05|03|04|です。
そして、今回は02回の回転なので、|03|04|05|に先程の動作を二回適応します。
そうすると|04|05|03|となります。
なお、負の回転数が入った場合は逆回転します。

Pietの基本