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

Brainf**k

はじめに

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

講座一覧

  1. Hello, BF!
    導入およびシンプルなループによる数値生成
  2. 数値入力と簡単なループ
    ,による入力と数値解釈、簡単なループの実例
  3. スライド型ループ
    ループ継続の判断を行うセルの位置をずらしていくループ
  4. 条件分岐
    if文、if-else文相当の処理

実行環境

  • 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,+]の中の処理の様子を図示すると、次のようになります。

f:id:ange1:20160707065656p:plain

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はそれぞれゼロ、非ゼロ用のカウンタです。図示すると次のようになります。

f:id:ange1:20160707080359p:plain

左側が if を、右側が else を処理する場合の様子です。先ほどの if 文の例と比較して、Eに関連した処理が増えているのが見て取れます。

まとめ

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

    終わりに

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