quine.bf
前の記事のコメント欄で shinh さんから私の投稿した Brainfuck の Quine が実は世界記録ではないかという指摘があったので一応メモ． 負数のメモリ番地は反則らしいので，投稿した 392B （改行除く，以下同様）ではなく shinh さんの書き直した 404B が最短となる． 以下に簡単な解説を示すが，以前までの記録であった（と思われる）410B のものも全く同じ構造をしている．
Brainfuck での Quine は，大まかに 3 つのパート A, B, C に分けられる． 具体的には，(A)「B+C」を表現するデータ列を生成， (B) A のデータ列から「A」自身を表現するデータ列への変換（同時に元のデータ列も複製）， (C) 作られたデータ列の出力処理（つまり「A+B+C」が出力される），という構成になっている． 最初に投稿した 587B のものでは，B の部分で，データ列への変換ではなくA 自身の出力をする処理をしていたため， 出力部が無駄に多くなってしまった…．
コードを書くにあたり，まず A でプログラム自身をどう表現するかを考える． 具体的な中身については B, C に依存するので， Brainfuck の命令に現れる「+(43)」「-(45)」「.(46)」「<(60)」「>(62)」「[(91)」「](93)」 （括弧内は ASCII 値）を短めのデータ列で表現することを考える． 1 つのメモリで1文字を表すのは無駄が多いので 2 つのメモリを使うことを考えると a[0]+16*a[1]+43 あたりが思いつく．
| 命令 | ASCII値 | a[0] | a[1] | コード上での表現 |
|---|---|---|---|---|
| + | 43 | 0 | 0 | >> |
| - | 45 | 2 | 0 | >++> |
| . | 46 | 3 | 0 | >+++> |
| 60 | 1 | 1 | >+>+ | |
| > | 62 | 3 | 1 | >+++>+ |
| [ | 91 | 0 | 3 | >>+++ |
| ] | 93 | 2 | 3 | >++>+++ |
次に，このデータ列からこのデータ自身の表現へ変換するパート B を考える． つまり，[3,1] というデータ列から「>+++>+」を出力する [3,1,0,0,0,0,0,0,3,1,0,0] （正順）というデータ列へ変換するコードである． 但し，元のデータ列も B と C を出力するデータとして必要な部分なので複製しながら上記のデータ列への変換を行わなければならない． なお，この変換の際に，便宜上 1 ずつ大きい値のデータ列として生成する．ここでいう「便宜」とは以下のような理由のためである．
- 各データが 0 でないため [>] や [<] によってデータの長さによらず自由に行き来ができて便利である．
- 各データの処理の前にループ停止条件（値が「-1」かどうか）を判定するために 1 を足す必要がある．
- >+>+++>++>+ +[[>>+[>]+>+[<]<-]>>[>]<+<+++[<]<<+]は [0,0,2,4,3,2, 1,1,4,2, 1,1,1,1,4,2, 1,1,1,1,1,1,4,2, 1,1,4,2] というデータを生成する． 逆順に処理されることを期待しているため，[4,2] が「>」を，[1,1] が「+」を出力することから， >+>+++>++>+ が出力され，これは元のコードの二行目そのものと成っている． この前に「-」を出力し，データ列が後半のコードを表現するものになっていればめでたく Quine ができあがる．
次に，データ列から出力するコード C について考える． 実はここが 410B から 404B になった要因らしい． まず，「-」を出力する必要があるため，以下のコードにより，データの右端に [3,1] をデータとして加えておく．
>>>[>]+++>+データ列の出力は基本的に a[0]+16*a[1]+43 に従うが，各データが 1 ずつ大きいことを考慮して (a[0]+1)+16*((a[1]+1)+1)+10 と考えれば，
[+[<++++++++++++++++>-]<++++++++++.<]が必要なコードとなる．[追記] (a[0]+1)+16*((a[1]+1)+2)-6 と考えると，
[++[<++++++++++++++++>-]<------.<]のように短くなる気がするが，「-」が多いためにこれを A にデータ列生成を埋め込む際に長くなってしまうので逆に損をすることになる．
ここで得られた B および C のコードをデータ列で表現することにより， A の部分が決定され，以下の 404B の Quineが完成する．
- >++>+++>+>+>+++>>>>>>>>>>>>>>>>>>>>>>+>+>++>+++>++>>+++ >+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+>+>>+++>>>>+++>>>+++ >+>>>>>>>++>+++>+++>+>>+++>+++>+>+++>+>+++>+>++>+++>>>+ >+>+>+>++>+++>+>+>>+++>>>>>>>+>+>>>+>+>++>+++>+++>+>>+++ >+++>+>+++>+>++>+++>++>>+>+>++>+++>+>+>>+++>>>+++>+>>>++ >+++>+++>+>>+++>>>+++>+>+++>+>>+++>>+++>> +[[>>+[>]+>+[<]<-]>>[>]<+<+++[<]<<+] >>>[>]+++>+ [+[<++++++++++++++++>-]<++++++++++.<]但し，上のコードに含まれる改行は全て取り除くものとする． ちなみに，このコードを生成する時に Ruby を使っていたりする．
hash = {
'+'=>'>>',
'-'=>'>++>',
'.'=>'>+++>',
'<'=>'>+>+',
'>'=>'>+++>+',
'['=>'>>+++',
']'=>'>++>+++',
}
code='+[[>>+[>]+>+[<]<-]>>[>]<+<+++[<]<<+]>>>[>]+++>+[+[<++++++++++++++++>-]<++++++++++.<]'
quine=code.reverse.gsub(/./){hash[$&]}
print '-'+quine+code
なお，負数のメモリ番地を許すと更に短くなるのは，「>」よりも「<」の方が短いデータ列で表現できるためで， 不等号記号が逆転されることにより，少ない数の「>」の出現で B や C を記述できるため， A に埋め込まれるデータ列を大幅に短縮することができる（392B）．
- <++<+++<+++<+<+++<<<<<<<<<<<<<<<<<<<<<<+++<+<++<+++<++<<+ <+<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<+++<+<<+++<<<<+++<<<+<+ <<<<<<<++<+++<+<+<<+++<+<+<+<+<+<+<++<+++<<<+++<+<+++<+<++ <+++<+++<+<<+++<<<+++<+<<<+++<+<++<+++<+<+<<+++<+<+<+<+<++ <+++<++<<+++<+<++<+++<+++<+<<+++<<<+<+<<<++<+++<+<+<<+++ <<<+<+<+<+<<+++<<+++<< +[[<<+[<]+<+[>]>-]<<[<]>+>+[>]>>+] <<<[<]+++<+ [+[>++++++++++++++++<-]>++++++++++.>]
