はじめに

anagol ( anarchy golf ) というコードゴルフサイトで最近出題された、“The B Programming Language”という問題、締め切りを過ぎましたが、Brainf**kで実装してみましたので、備忘録として解説を載せます。

問題

空白区切り、if,then,else,true,falseという単語で構成された行を評価し、行毎にtrueまたはfalseを出力していく、というものです。

各行は、必ず“true”“false”“if XXX then XXX else XXX”という形をしており、最後の形の XXX の部分は入れ子状に、また“true”“false”“if XXX then XXX else XXX”という形を…と、いくらでも入れ子にできるようになっています。

解法

ちょっと今回ゴルフ的な解き方は思いつかなかったのですが…。

単純には、正規表現パターン/if (true|false) then (true|false) else (true|false)を“true”または“false”に置き換えることを繰り返すことで、解くことができます。Perlで書くと例えば次のような。

#!perl -p
1 while s/if (true|false) then (true|false) else (true|false)/$1 eq "true" ? $2 : $3/e

しかし、Brainf**で解く場合に、どこにそのパターンがあるかをいちいち調べるのは大変です。なんとしても先頭から見る方法を考えねばなりません。

…そう考えると、実はスタックを活用することで先頭から順に評価して解けることが分かります。新たな if文が出てきたところで「未評価」ということでスタックにつみ、else節まで全部、“if XXX then XXX else XXX”の塊が出揃ったところで評価して“true”または“false”に置き換える ( 未評価部分を減らす ) ことを繰り返せば良いのです。

例えば、次のRubyのような実装が考えられます。

while gets
  tok=$_.scan(/\w+/)
  a=[] # a stack of if-then pairs
  loop do
    t=0
    skip=true
    case tok.shift
    when "if"
      a.push([]) # push a null pair to the stack
      skip=false
    when "true"
      t=1
    when "false"
      t=2
    else
      raise "not reached"
    end
    while t>0
      break !puts(%w(true false)[t-1]) unless a[-1]
      if !a[-1][0] # if clause
        a[-1][0],t=t,0
      elsif !a[-1][1] # then clause
        a[-1][1],t=t,0
      else # complete all of if-then-else clauses
        t=a[-1][1] if a[-1][0]==1
        a.pop
      end
    end and break
    tok.shift if skip # skip a "then" or "else" token
  end
end

これを元にBrainf**kでの実装を行いました。

実装

次がBrainf**k(314)のコメント付ソースです。

簡単に解説していきたいと思います。

メモリレイアウト

** memory layout **
* *itit~it_C
* *itit~it__m
* *itit~itfbs_c
*
* *: a sentinel ( minus 1 )
* i: stacked if(condition) clause ( 1 for true 2 for false )
* t: stacked then clause ( 1 for true 2 for false )
* C: the first character of "if" or "true" or "false"
* m: 4 minus (C plus 1) mod 4 
* f: temporary flag
* b: current true/false value ( 1 for true 2 for false )
* s: skip flag ( to skip "then" or "else" )
* c: continue flag

まず冒頭のコメントにあるメモリレイアウトですが、左端の番兵 ( -1 ) から右に、if(条件)節、then節のペアを並べたスタックを構成しています。
そして、左端で新たな入力を処理し、スタックを更新していく、という形をとっています。
なぜ else節がないかというと、else節が来た瞬間にスタックを更新してしまうので、スタックに積む必要がないからです。

ループ構成

*loop(line)*
->,+[
 *loop(token)*
 [
  (入力の解析)
  (スタック操作ループ)
 <<]
->,+]

まず、全体のループとしては行毎の処理になります。なので番兵を設定した直後に、行頭を読み込んでEOFでないかどうかを判断しています ( EOFが-1となる処理系を想定 )。

その内側はトークン毎のループです。トークンの先頭文字がある ( +1された状態で0でない ) ことが持続条件となっています。ループ自体が既に1文字入力された状態で開始されるため、ループの最後の方で次のトークンの先頭の読み込みを行うことになります。

入力の解析

  *analyze the first character ( mod 4 )*
  C[>[->>]<[>+++>]<<-]
  >>+<m-[-[-
    *t(true)*  >,,,[-]<b+>]>
   [*i(if)*    ,[-]>>>>c+<]<]>
  [ *f(false)* ,,,,[-]<b++>>]

トークンの先頭文字の解析です。諸所の事情により、“if”,“true”,“false”だけ ( “then”,“else”は考慮しなくてよい ) なので、先頭文字コードの mod 4 ( 実際には 4-(文字コード+1)mod 4 ) で判断します。

mod については、BFのアルゴリズム集にあるdivmod で、商をカウントしないようにしても良いのですが、こちらの方がより短く実装できます。

いずれの場合でも、トークンの残りの読み飛ばしを行います。加えて、true,false の場合は、bの位置に対応する値 ( 1 or 2 ) をセットして次に使いますが、if の場合は代わりに、スタックを伸長する ( 空の値を積む ) ためポインタ右に移動します。

スタック操作ループ

  <<b[>s[-]<
   (スタック操作)
   (出力)
  <<<b]
  * *itit_!__c or *itit_!s__ or nothing *
  * skip "then" or "else" and input the first character of the next token *
  >s[->>c,,,,,<<]>>c[[-]<<<<,,+>>]

true/false を読み込んだ場合は、スタック更新のループになります。なぜループにしているかというと、if-then-else全て揃う毎にスタックをどんどん縮めていく必要があるからです。
ループの持続条件は、最新の true/false の値 b ( 1,2 ) です。

ループの最初にsをクリアしているのは、スタックを縮める前にセットした前のsが残らないように、です。このsは、true/falseを読み込んでループを抜けた後に“then”,“else”を読み飛ばすかどうかの制御に使われます ( 空白も入れて同じ5文字なのでまとめて扱える )。入力文字の判定時にthen/elseを考慮する必要がなかったのは、ここで読み飛ばしてしまうからです。
なお、前に if を読み込んでcが設定された場合、あるいはsが設定されてthen/elseを読み飛ばした場合は、次の文字を読み込んで、トークンのループの最初に戻ります。

スタック操作

   <f+<+[-<i[>t[
      * move b ( the newest "else" clause ) as the new b *
      <i-[->t[-]>f->b[-<<+>>]b<]>>
      * move the newest "then" clause as the new b *
      [f->b[-]>]<<f * *itit_b! ]>
     * fill the "then" clause *
     [f->[-<<+>>]>>] * *itit_b_! or *itit___! * ]>>
    * fill the "if(condition)" clause *
    [f->[-<<<+>>>]>>>>] * *itit_b___! or *itit_____! or itiT_____! *
   <<<s+>]

いよいよ核心のスタック操作の部分です。

これは、番兵によってスタックが空でないと判定された場合の分岐です ( 空の場合は出力に移る )。

これは粗く3種類、細かくは4種類の分岐になっていて、

スタックの最後のif(i),then(t)の値がある
if-then-else揃ったのでスタックを縮小
- thenの値がtrue(1)
  thenの値を新たなbとして使う
- thenの値がfalse(2)
  elseに相当する今のbを、そのまま次のbとして使う
スタックの最後のifの値はあるが、thenの値がない
- bの値をtにセットする
スタックの最後のifの値がない
- bの値をiにセットする

なお、多重分岐の場合は、最終的にポインタの場所の辻褄を合わせる必要がありますので、各分岐でどこに出るか、色々気を遣っています。コメント中の ! が、各ケースでの現在地を表しています。

また、この分岐はいずれにせよ true/false を読み込んだ場合のものなので、次の then/else を読み飛ばすための s をセットします。

出力

   >f[*print*
    +++++[-<<++<+<+++<++++[+++++++++++++++>]>]
    >-[*false* -<<-<.<+.<.<+.>>>-.>>]<+
    [  *true* -<<<<<++.--.+++.>>>-.>]
    ,.[[-]<] * a newline from stdin *
   ] * *itit_bs_! or null *

最後に出力処理です。これはスタックが空の ( 番兵に到達した ) 場合の分岐になります。文字データは、最初に true,false の全文字分 ( 文字コードが近い文字は同一地点を共用 ) を用意し、最後に残ったbの値に従って、true または false を出力します。
改行については、次の入力がそれになるはずなので、入力から流用しています。出力後は今後の憂いを絶つため、全てのデータをクリアしておきます。

終わりに

一見シンプルでありながらなかなか効率的に組むには頭をひねらないといけない、良問だと思います。

ange1のブログ

The B Programming LanguageのBrainf**k実装 ( anagol )