Brainf*ckにおける非破壊if文と呼ばれるテクについて

この記事はBrainf*ck Advent Calendar 2019 12日目の記事です。

adventar.org

「非破壊if文」のお気持ち

そもそもif文って?

多分こんなやつのことです。

[**ifの処理**[-]]

ここで重要なのは、対応する[]でポインタの位置を同じにしておくことです。 でないと、if文の処理を行ったときと、そうでないときでポインタの位置が異なる、といった事態になります。 これの帳尻を合わせるのは面倒なので、対応する[]でポインタの位置は合わせておくことが基本だと思います。

よって、全ての処理が終わった後で、条件分岐に使われたセルの値は必ず0になっていることがコードより分かります。

でも、これだと条件分岐に使ったセルの値を再利用したい場合に困ってしまいます。

ナイーブな解決策

セルの値を事前にコピーしておくだけでいいです。 ほとんどの場合、これで済むと思います。

ただ、あるセルの値が0か否かを調べるためだけにセルの値をコピーするのは大袈裟な気がします。 また、(処理系による最適化が無ければ、)コピーする分の実行時間がかさむという欠点もあります。

非破壊if文を使う

さて、この問題を解決するのが非破壊if文です。 読んで字の如く、条件分岐に使うセルの値をコピーも破壊もせずにif文を書くテクニックです。

実はこのテクに関しては、分かりやすい記事がいくつかあるので、本記事ではいくつか例を挙げてお茶を濁そうと思います。

f:id:koikotya:20191212120356p:plain
ゆるせねえ(本当は私がこの記事を書くと決める前から書いてたらしい)

実装例

以下のいずれの方法でもメモリの配置は次のようになっています。

{x}{0}{0}

ポインタは0番地にある状態からスタートし、0番地の値xで条件分岐します。 1,2番地は0で初期化されています。

方法1

[>>+<**ifの処理**]
>[<]>-
[+**elseの処理**]

私がよく使うのはこれです。 後に示す方法の方が優れていそうですが、手に馴染んでいるのでこの方法を使っています。

方法2

>>+<<
[>**ifの処理**]
>[<]<

elseの場合の処理も入れようと思えば入ると思います。

参考:brainfuck 入門:非破壊 if - 三流プログラマの戯言

方法3

>+<
[>-**ifの処理**]>
[->**elseの処理**]

個人的にはこの方法が一番無駄がないと思います。

参考:Brainf**k講座(6) 非破壊的条件分岐 - ange1のブログ

まとめ

ほとんど役に立つことのないテクですが、プログラムを高速化したい、コードを短くしたいときには覚えておいて損のないテクだと思います。