« DNS ラウンドロビンと高可用性 (High Availability) | メイン | Re: BF2JS opimizing compiler »

2006年06月30日

Brainf*ck で動的リスト

 Brainf*ck では、メモリアドレスを動的に指定することはできません。しかし、そのような制約があるからといって、リストを使用したプログラムを書ことができないわけではありません。

 Brainf*ck の場合、ちょうど C の文字列のように、要素列の前後にターミネータを置くことで動的リスト構造を表現することができます。でもそれだけじゃおもしろくないので、考えをもう一歩進めて、動的リストをイテレートできないか考えてみました。

 というわけで、以下が電車の中で書いたコードです。任意の長さの動的リストをイテレートして、その総和を表示します。

 この構造を利用して、バカソート等も実現可能です。イテレーション位置を表す数値をもうひとつ用意すれば、同時に2箇所の参照位置を管理することができるので、クイックソートもできますね (^^;

 みなさん、 Brainf*ck がいかにすばらしい言語であるか、お分かりいただけますでしょうか?

>>+>++>+++>>              0 0 1 2 3 0 {0} 0 
                          ^ ^       ^  ^  ^ 
                          | |       |  |  | 
                          | |       |  | temporary 
                          | |       | accumulator 
                          | |      list end marker 
                          | iterator marker 
                          | 
                         list start marker 

algorithm image: 
    0 0 1 2 3 0 0 0 
    0 1 0 2 3 0 0 0 
    0 1 0 2 3 0 1 0 
    0 1 2 0 3 0 1 0 
    0 1 2 0 3 0 3 0 
    0 1 2 3 0 0 3 0 
    0 1 2 3 0 0 6 0 
    0 0 1 2 3 0 6 0 


<<[<]>                   move cursor to leftmost value 

  [-<+>]<                move current value leftwards by one
  [ -                    accumulate (destructive) 
    >>[>]>+>+ 
    <<<[<]< 
  ] 
  >>[>]>> 
  [                      restore 
    - 
    <<<[<]< 
    + 
    >>[>]>> 
  ] 
  <<<[<]>                move cursor to next value 


<<[ [->+<] <]            move all values rightwards by one 

>>[>]>                   move cursor to accumulator 
>++++++[<++++++++>-]<    convert to asciii 
.                        print

投稿者 kazuho : 2006年06月30日 11:06 このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク

トラックバック

このエントリーのトラックバックURL:
http://labs.cybozu.co.jp/cgi-bin/mt-admin/mt-tbp.cgi/670