🧠
Brainf**k講座(4) 条件分岐

2024/12/01に公開
初心者向け
esolang
Brainfuck
tech
 はじめに※本記事は、2016/7/11にHatenaBlogに投稿した記事を移行したものです

前回まででループを一通りマスターされたことと思われますBrainf**k講座、今回からは条件分岐、いわゆるif文の処理に入ります。実はループよりもif文の方が複雑なのですが、これを身に着ければ、大抵のコード ( Brainf**k向きの ) は書けるようになるはずです。


 講座一覧
Hello, BF!

導入およびシンプルなループによる数値生成

数値入力と簡単なループ

, による入力と数値解釈、簡単なループの実例

スライド型ループ

ループ継続の判断を行うセルの位置をずらしていくループ

条件分岐 (今回)

if文、if-else文相当の処理

条件分岐の多段化

switch文相当の処理

非破壊的条件分岐

条件変数を壊さない条件分岐

divmodアルゴリズムと数値出力

除算・剰余算のアルゴリズムと、それを利用した不定長の数値出力

BCD演算

10進数による任意長の数値の計算
※上記以外も含め、各記事はBrainf**kの記事一覧から辿ることができます

 実行環境
ideone

オンラインのIDE環境で、bffという処理系が使えます。この講座は基本的にこのbffに対応したものです。
[Brainf**kインタープリタ(http://azisava.sakura.ne.jp/js/bf/)

あじさんという方が作られたブラウザ上で動くインタプリタです。細かい挙動の調整や、途中のセルの状態のダンプができたり、重宝しています。

※オプションで「バッファの型」を「4バイト符号付き整数」、「標準入力の終端」を「-1」と設定すると、bffと同じ挙動になります。

 今回の話題
 条件分岐文字通り条件分岐、一般のプログラミング言語における、if文、if-else文相当の処理になります。Brainf**kの[]は、セルの値のゼロ、非ゼロによって挙動を変えますから、これがそのまま条件分岐に使えるわけですが、[]の中から出る時のことに留意する必要があります。

 if文ではまずif文です。条件変数として使うセルの値が 0,1 のみ ( もしくは、2,3 や 3,4 等、何か値を加工した結果0,1にできる場合 ) であれば、これは繰り返し回数1回のループと同等です。条件変数 C に対して、次のようなコードがそのまま if文になります。
C[- 処理 C]
しかしながら、条件変数が複数の値をとる場合、少し工夫する必要があります。値が 0 以外の正の値 ( -1等も内部的には正の数ですが、除外します ) の場合だけ処理を行う場合。[]に入ったら、即座に条件変数をクリアしてしまえば、繰り返し回数1回のループと同じことになります。コードとしては次のようになります。
C[[-] 処理 C]
[-]はその場のセルをただ0まで減らすだけの空ループで、正の値のセルをクリアするときに使われます ( 逆に負の値の場合は[+] )。

 if文の実例それでは、実際の問題に即して、if文のコードを見ていきたいと思います。
入力された数字 ( 9桁以内、改行は無し ) の中に含まれる 0 の個数を出力する。

※9桁以内としているのは、複数桁の数字の出力方法をまだやっていないからです
数字が 0 かどうか、が if文での処理に相当するわけですが、1つ注意があります。それは、[]の中に入る条件が「0以外の値の時」である以上、「0の時に特定の処理を行う」とするには if-else型になってしまうのです。

そこでここでは、「数字に関わらずカウントを増やし、0以外の場合はそこから減らす」と考えて if文での処理とします。Rubyで書くと次のようなコードです。
a=0
while c=$<.getc
  a+=1
  a-=1 if c!="0"
end
puts a
では、Brainf**kでのコードです。
** loop **
C,+[
 >A+
 <<T+++++++[->C-------<T]
 >C[[-]>A-<C]
C,+]
** convert an integer to a character code ( plus 48 ) **
C++++++[->A++++++++<C]
>A.
入力ループC,+[ ～ C,+]の中の処理の様子を図示すると、次のようになります。
if文に相当するのは>C[[-]>A-<C]の部分ですが、真の場合の分岐 ( 左側 ) と、偽の場合の分岐 ( 右側 ) の違いが見て取れます。

 if-else文では、続いてif-else文です。
if文の処理C[- 処理 C]やC[[-] 処理 C]をもう一度見てみます。そうすると、[]内に入った場合も、入らなかった場合も、完了後には C の値は 0 になっていますから、後からどちらだったのかを区別することができません。
そこで、予め if用のものと対になる else 用の条件変数を設けて置き、if節の[]に入った場合には else 用のをクリアするような処理で、if-elseを実現する方法が考えられます。
Rubyで書くと次のような処理です。
# ci,ce: if,elseそれぞれの条件変数
ce=true
if ci
  ci=ce=false
  # if の処理
end
if ce
  ce=false
  # else の処理
end
Brainf**kでは、次のような形式になります。
** IE : if elseそれぞれの条件変数 **
I>E+
E<I[[-]>E- ifの処理 <I]
I>E[- elseの処理 E]
このように、if-else文は、ある意味2つのif文の連結とも言えます。

 if-else文の実例それでは、先ほどの問題を少し変更して、if-else文を使ってみます。
入力された数字 ( 9桁以内、改行は無し ) の中に含まれる 0 の個数、それ以外の個数を1行ずつ出力する。
[]に入るのは非ゼロの時ですから、「それ以外」の方が if、0 の方が else になることに注意してください。
上で挙げた要領で、Rubyで書いてみると次のようになります。
azero=anonzero=0
while c=$<.getc
  celse=true
  if c!="0"
    celse=false
    anonzero+=1
  end
  if celse
    azero+=1
  end
end
puts azero,anonzero
Brainf**kでは次のようなコードになります。
** loop **
C,+[
 C>E+++++++[-<C------->E]
 E+
 E<C[[-]>E->>N+<<<C]
 C>E[->Z+<E]
E<C,+]
** make 2 character codes and newline **
C<T++++++[->C++>>Z+>N+[+++++++<]E<<T]>C--
C>>Z.<<C.>>>N.<<<C.
入力文字 C を if の条件変数として、その隣に else の条件変数 E を設けます。Z,Nはそれぞれゼロ、非ゼロ用のカウンタです。図示すると次のようになります。
左側が if を、右側が else を処理する場合の様子です。先ほどの if 文の例と比較して、Eに関連した処理が増えているのが見て取れます。

 まとめif文は繰り返し1回のループとして実装できる
条件変数が0,1以外の様々な正の値をとる場合も[-]でクリアすることで、繰り返し1回のループになる
if-else文は、if用の条件変数とelse用の条件変数を対にして用いる
if-else文は、else用条件変数を予めセットしておいて、ifの処理中にクリアする

#終わりに

これで条件分岐も使えるようになりました。しかし、複雑な条件分岐を効率的に実装するために、様々な変形バージョンがありますので、次からはそちらを説明していきたいと思います。
はじめに

講座一覧

実行環境

今回の話題

条件分岐

if文

if文の実例

if-else文

if-else文の実例

まとめ

Discussion
