Zenn
🧠

Brainf**k講座(6) 非破壊的条件分岐

2024/12/01に公開
初心者向け
esolang
Brainfuck
tech

はじめに

※本記事は、2016/7/13にHatenaBlogに投稿した記事を移行したものです
いよいよ今回で条件分岐の最後の話題になります。ここがある意味、Brainf**kの醍醐味なのではないかと思っている、非破壊的条件分岐のお話です。

講座一覧

  1. Hello, BF!
    導入およびシンプルなループによる数値生成
  2. 数値入力と簡単なループ
    , による入力と数値解釈、簡単なループの実例
  3. スライド型ループ
    ループ継続の判断を行うセルの位置をずらしていくループ
  4. 条件分岐
    if文、if-else文相当の処理
  5. 条件分岐の多段化
    switch文相当の処理
  6. 非破壊的条件分岐 (今回)
    条件変数を壊さない条件分岐
  7. divmodアルゴリズムと数値出力
    除算・剰余算のアルゴリズムと、それを利用した不定長の数値出力
  8. BCD演算
    10進数による任意長の数値の計算

※上記以外も含め、各記事はBrainf**kの記事一覧から辿ることができます

実行環境

  • ideone
    オンラインのIDE環境で、bffという処理系が使えます。この講座は基本的にこのbffに対応したものです。
  • Brainf**kインタープリタ
    あじさんという方が作られたブラウザ上で動くインタプリタです。細かい挙動の調整や、途中のセルの状態のダンプができたり、重宝しています。
    ※オプションで「バッファの型」を「4バイト符号付き整数」、「標準入力の終端」を「-1」と設定すると、bffと同じ挙動になります。

今回の話題

非破壊的条件分岐

さて、これまでに出てきた条件分岐は、いずれのパターンでも、最終的には条件変数を必ずクリアしていました。なぜかというと、それは条件変数を保持するセルで]から出るためで、更になぜかというと、分岐に入らなかった場合のセルの位置 ( 条件変数を保持するセル ) と、分岐に入った場合で位置を合わせ、のちの処理で齟齬が出ないようにするためです。

しかしながらそれでは、後で利用したいデータを条件変数とすることができなくなってしまいます。そこで、非破壊的な条件分岐を紹介します。

シンプルな解決策:条件変数のバックアップ

ただし、これまでのように条件変数をクリアしてしまう実装でも、特に問題ないようにすることは可能です。それは、条件変数のバックアップを取ることです。すなわち、次のような処理になります。

  • 条件変数をコピーし、評価用とバックアップ用に二重化する
  • 評価用の条件変数を使って条件分岐を行う ( 評価用のセルはクリアされる )
  • 残ったバックアップ用を元のセルに移動する

特に、前回の多段化した分岐を行う場合等、どうしても条件変数を壊していかないといけませんから、このような方法を採らざるを得ません。しかし、条件判断が「0か非0か」だけで済むのであれば、もっと別な方法があります。

本題:非同期的条件分岐

今回本題として取り上げるのは、非同期的な条件分岐です。「非同期」というのは何かというと、ifの処理で]から出る時に、[で入った位置と別の位置で出る、すなわち、ifの処理に進まなかった場合に位置がずれることを言っています。

別の位置で出る以上、条件変数をクリアする必要がありません。そのため、非破壊的な条件分岐に使えるということになります。

ただし、それだとif文が終わった時の位置が不定になってしまうため、そのままでは以降の処理に齟齬が出ます。そこで、( 特に処理がなくとも ) 必ず else の処理を設け、ずれを解消するようにします。

典型的には、次のようなコードが考えられます。

** memory layout: CEB **
E+<C
C[>E-    **ifの処理**  E]
CE?>[E-  **elseの処理**  E>B]B

Cが条件変数、Eがelse用条件変数、Bは位置調整用のブランク ( 値 0 の ) セルです。ifの処理の]の直後では、C,Eどちらのセルにいるか分かりませんが、elseの処理に入った時には明確にEにいます。そこでelseの処理から出る時に ( ifの処理を経由したらいるはずの ) B から出るようにすることで、最終的に位置を合わせます。図示すると次の通りです。

なお、このコードではelseの処理でEをクリアしていますが、elseの[]から出る時も位置がずれますので、実はクリアしなくても済みます。ということで、前回までで紹介した条件分岐ではEは明確にelse用の条件変数として使うものでしたが、非同期的なものでは、単に非ゼロなセルであれば流用できたりします。

また、上で紹介したバックアップを取る方法の場合だと、バックアップのためのセルが必要になりますが、この非同期的な方法の場合、位置を調整するためのブランクセルが必要になりますので、セルの配置に注意しましょう。

非同期的条件分岐の実例: FizzBuzzのFizzのみ

では、実例として、FizzBuzz…だと数字の出力がありますので、簡単のために「Fizzのみ」を挙げたいと思います。仕様は次の通りです。

  • 1～100に対して、3の倍数の時に“Fizz”、それ以外で“-”を出力する ( いずれも改行を入れる )

他の言語では剰余演算 ( % や mod 等 ) がありますが、それはまだやっていないので、3周期のカウンターを設けて対処したいと思います。Rubyで書くと次のようなコードになります。

c=2
100.times{
  if c!=0
    c-=1
    puts "-"
  else
    c=2
    puts "Fizz"
  end
}

これをBraif**kで書くと次のようになります。

** memory layout: NCEBn_hziF
*   nh: character code for newline and hyphen
*   Fiz: character code for F i z
*   N:  global counter
*   C:  3 cycle counter
*   E:  else condition var
*   B:  blank
**

** create character codes **
B+++++++[->n+>>h----->z++++++>i++++>F-[+++++++++++<]<n<B]
>n+++>>h+++>z+++
** set 100 to the global counter N
<<<<<<C++++++++++[-<N++++++++++>C]
** set 2 to C **
C++
<N[-
 >>E+
 <C[
  ** decrement C and print a hyphen **
  C->E->>>>h.<<n.<<E
 E]
 >CE?[E
  ** set 2 to C and print Fizz **
  E-<C++>>>>>>>>F.<i.<z..<<<n.<B
 B]B
 B<<<N
N]

“** decrement C and print a hyphen **”が if の処理、“** set 2 to C and print Fizz **”がelseの処理として、上で挙げたような if-else の構成になっています。

条件分岐の中で位置ずれが起きるとややこしくなりますが、落ち着いて if と else の動作をシミュレートすれば、大丈夫かと思います。

まとめ

  • 条件変数を保存して条件分岐したい場合、バックアップを取る方法と非同期的な方法がある
  • 非同期的な方法では、ifの処理に入るかどうかでセルの位置がずれる
  • 非同期的な方法では、elseの処理でずれた位置を調整する
  • バックアップを取る場合はバックアップ用のセルが、非同期的な方法では位置調整用のブランクセルが必要となる

終わりに

これで条件分岐も終わりとなりました。非同期的な条件分岐は少し難しいですが、簡潔で短いコードを書くためには避けられないところです。さて、次回からは実際の問題に対処するための幾つかの典型的な処理を紹介しようと思います。

Discussion