前回紹介した自作Brainfuck系言語の「INSTEP」を使って、Quineを書く話
・Quineってなんや
自身のソースコードと完全に同じ文字列を出力するプログラムのこと。Wikipediaを参照されたし。ただし、入力を受け取るものや空文字列はQuineとはみなさない。
・Quineを書く一般的方針
一般的な話をする。抽象的すぎるが。
Quineは大きく分けて2つの部分(A、Bとする)に分けられる。
- Aは、Bそのものの文字列である。
- Bは、A+B (= 自身のソースコード)を出力するプログラムである。
ここで気を付けたいのは、Bは、Aに全く依存してはいけないということである。なぜなら、AはBに依存しているので、無限ループになってしまうからである。
つまり、Bは、Aだけから「Aそのものの文字列」を生成しなければいけない。
(なるほどわからん)
・実際に書いていきたい
前回紹介したINSTEPは、本家Brainfuckの , 以外の命令を使えるので、本家BrainfuckでQuineならINSTEPでも当然Quineになる。しかしそれだと面白くないので、今回はINSTEPで追加した左ビットシフト・右ビットシフト命令 ^・v を使うという条件で書いてみる。
・方針
A部分には、データ領域にB部分の文字列データを書き込むプログラムを記述する。今回は単純に文字コードをそのまま書き込むようにする。例えば、ソースコード上の文字+を表現するために、文字コード43 = 101011をデータ領域に書き込む。すなわち、A部分では+^^+^^+^+> と書くことになる。
B部分では、データ領域に書き込まれた情報からA部分を表すデータを錬成する。たとえばデータ領域に43があったら、それを+^^+^^+^+>に変換する機構を書くことになる。具体的な処理としては、下位ビットから順に値が1か0かを判別し、1なら +^ を、0なら ^のみを書き込むという形になる。
・B部分からつくってイク
B部分のソースコードはこうなる。
>>>>>>-<<<<<<
[
[>>+>+>+>+<<<<<-]
+^^^
[
>>>v^
[-<->]
<[>>[>]+^^+^^+^+[<]<-]
>>v
[
[>]+^^+^+^+^+^[<]
>[<<<+>>>-]
]
<<<
[>+>+>+<<<-]
<-
]
>>>>>[>]+^+^+^+^+^[<]
<<<<<
]
>>>>>>[>]<+
[-.<+]<[.<]
1行目の>>>>>>-<<<<<<は、A領域とB領域の境界の値として-1を設定する。間に5バイトの空白を入れるのは、ここが今から説明する作業を行う領域になるからだ。
以降、図を使って説明していくことにする。例えば、A領域の右端のデータが43だったとすると、現時点でのデータ領域は図のようになる。↓pはデータポインタを表す。また、便宜上、図中で左からnバイト目を{n}と書く。例えばここでは{7} = -1である。
3行目の[>>+>+>+>+<<<<<-]で、{1}のデータを{3}～{6}の4か所にコピーする。Brainfuckの命令は破壊的な変更をするので、大量にコピーを取っておく必要がある。
4行目の+^^^で、{1}の値を8に設定する。これはカウンターとしてはたらき、何ビット目を処理しているかを示す。
6行目の>>>v^で、{4}の下位1ビットが切り捨てられる。
7行目の[-<->]で、{3}から{4}を減算する。
8行目の<[>>[>]+^^+^^+^+[<]<-]で、もし減算の結果が1だった場合(= 元のデータの下位1ビットが1だった場合)には、右端まで行って43を書き込んで戻って来る。
9行目の>>vで、{5}を右ビットシフトする。その結果が0でない場合は、右端まで行って94を書き込んで戻って来る。
戻ってきたら、12行目の>[<<<+>>>-]で{5}の値を{2}に移す。
15行目の[>+>+>+<<<-]で、{2}の値を{3}～{5}にコピーする。そして、16行目の<-で、{1}のカウンターの値を1減らす。
ここまででループが1周したので、カウンターが0になるまで計8回、同じこと(6~16行目)を繰り返す。ループが終わると、18行目の>>>>>[>]+^+^+^+^+^[<]で右端に62を書き込んで戻って来る。
これで1バイト分の処理が完了したので、あとはデータ領域の端に到達するまでひたすらに同じこと(3~19行目)を繰り返す。
そして最終的には、A領域とB領域の境界の-1を挟んで 右側にはA部分を表すデータが、左側にはB部分を表すデータが書き込まれた状態になる。ただし、A領域の右端から読み取ったデータをB領域の左端から書き込んでいるので、B領域のデータは右から順に書き出していく必要がある。で、A領域も右端から書き出せるように書き込むA部分のデータ順を逆順にしてやると、B領域からA領域まで一気に書き出せるようになる。
というわけで、21行目の>>>>>>[>]<+でデータ領域の右端まで移動し、22行目の[-.<+]<[.<]で書き出していけばB部分のプログラムは終わりである。
・A部分をつくろう
方針のところで述べたように、B部分のソースコードのそれぞれの文字を、その文字コードを入力する命令に置き換えることでA部分が完成する。また前述の通りA部分のデータを逆順にして格納する必要がある。
B部分の文字数はざっと170字といったところなので手作業で出来ないこともないのだろうが、こういう単純な作業は自動化したほうが楽でいい。Python3を使った。
import re
rawcode="""
>>>>>>-<<<<<<
[
[>>+>+>+>+<<<<<-]
+^^^
[
>>>v^
[-<->]
<[>>[>]+^^+^^+^+[<]<-]
>>v
[
[>]+^^+^+^+^+^[<]
>[<<<+>>>-]
]
<<<
[>+>+>+<<<-]
<-
]
>>>>>[>]+^+^+^+^+^[<]
<<<<<
]
>>>>>>[>]<+
[-.<+]<[.<]
"""
purified=re.sub(r"[^]^v<>+.[-]","",rawcode)
rev=purified[::-1]
token=["+","-",".","<",">","[","]","^","v"]
repl=[
"+^^+^^+^+",
"+^^+^+^^+",
"+^^+^+^+^",
"+^+^+^+^^",
"+^+^+^+^+^",
"+^^+^+^^+^+",
"+^^+^+^+^^+",
"+^^+^+^+^+^",
"+^+^+^^+^+^"
]
res=""
for c in rev:
for i in range(9):
if token[i]==c:
res+=(">"+repl[i])
print(res)
28行目でRegexを使って関係ない文字を全部無視している。30行目でスライスを使って文字列をひっくり返し、あとはforで各文字に対して置換するだけである。
出来上がったA部分はこちら。
>+^^+^+^+^^+>+^+^+^+^^>+^^+^+^+^>+^^+^+^^+^+>+^+^+^+^^>+^^+^+^+^^+>+^^+^^+^+>+^+^+^+^^>+^^+^+^+^>+^^+^+^^+>+^^+^+^^+^+>+^^+^^+^+>+^+^+^+^^>+^^+^+^+^^+>+^+^+^+^+^>+^^+^+^^+^+>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^^+^+^+^^+>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^^+^+^+^^+>+^+^+^+^^>+^^+^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^^+>+^+^+^+^+^>+^^+^+^^+^+>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^^+^+^+^^+>+^^+^+^^+>+^+^+^+^^>+^^+^+^+^^+>+^^+^+^^+>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^^+^^+^+>+^+^+^+^+^>+^^+^^+^+>+^+^+^+^+^>+^^+^^+^+>+^+^+^+^+^>+^^+^+^^+^+>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^^+^+^+^^+>+^^+^+^+^^+>+^^+^+^^+>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^^+^^+^+>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^^+^+^^+^+>+^+^+^+^+^>+^^+^+^+^^+>+^+^+^+^^>+^^+^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^^+>+^+^+^+^+^>+^^+^+^^+^+>+^^+^+^^+^+>+^+^+^^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^^+^+^+^^+>+^^+^+^^+>+^+^+^+^^>+^^+^+^+^^+>+^+^+^+^^>+^^+^+^^+^+>+^^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^^+>+^+^+^+^+^>+^^+^+^^+^+>+^+^+^+^+^>+^+^+^+^+^>+^^+^+^^+^+>+^+^+^+^^>+^^+^+^+^^+>+^+^+^+^+^>+^^+^+^^+>+^+^+^+^^>+^^+^+^^+>+^^+^+^^+^+>+^^+^+^+^+^>+^+^+^^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^^+^+^^+^+>+^^+^+^+^+^>+^^+^+^+^+^>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^^+>+^^+^+^^+>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^^+^^+^+>+^+^+^+^+^>+^^+^^+^+>+^+^+^+^+^>+^^+^^+^+>+^+^+^+^+^>+^^+^^+^+>+^+^+^+^+^>+^+^+^+^+^>+^^+^+^^+^+>+^^+^+^^+^+>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^^+^+^^+>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^
実に1843文字である。ﾋｴ~ｯ。
これとさっきのB部分をそのままつなぐと、晴れてQuineとなる。
>+^^+^+^+^^+>+^+^+^+^^>+^^+^+^+^>+^^+^+^^+^+>+^+^+^+^^>+^^+^+^+^^+>+^^+^^+^+>+^+^+^+^^>+^^+^+^+^>+^^+^+^^+>+^^+^+^^+^+>+^^+^^+^+>+^+^+^+^^>+^^+^+^+^^+>+^+^+^+^+^>+^^+^+^^+^+>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^^+^+^+^^+>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^^+^+^+^^+>+^+^+^+^^>+^^+^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^^+>+^+^+^+^+^>+^^+^+^^+^+>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^^+^+^+^^+>+^^+^+^^+>+^+^+^+^^>+^^+^+^+^^+>+^^+^+^^+>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^^+^^+^+>+^+^+^+^+^>+^^+^^+^+>+^+^+^+^+^>+^^+^^+^+>+^+^+^+^+^>+^^+^+^^+^+>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^^+^+^+^^+>+^^+^+^+^^+>+^^+^+^^+>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^^+^^+^+>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^^+^+^^+^+>+^+^+^+^+^>+^^+^+^+^^+>+^+^+^+^^>+^^+^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^^+>+^+^+^+^+^>+^^+^+^^+^+>+^^+^+^^+^+>+^+^+^^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^^+^+^+^^+>+^^+^+^^+>+^+^+^+^^>+^^+^+^+^^+>+^+^+^+^^>+^^+^+^^+^+>+^^+^^+^+>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^+^>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^^+>+^+^+^+^+^>+^^+^+^^+^+>+^+^+^+^+^>+^+^+^+^+^>+^^+^+^^+^+>+^+^+^+^^>+^^+^+^+^^+>+^+^+^+^+^>+^^+^+^^+>+^+^+^+^^>+^^+^+^^+>+^^+^+^^+^+>+^^+^+^+^+^>+^+^+^^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^^+^+^^+^+>+^^+^+^+^+^>+^^+^+^+^+^>+^^+^+^+^+^>+^^+^^+^+>+^^+^+^+^^+>+^^+^+^^+>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^^+^^+^+>+^+^+^+^+^>+^^+^^+^+>+^+^+^+^+^>+^^+^^+^+>+^+^+^+^+^>+^^+^^+^+>+^+^+^+^+^>+^+^+^+^+^>+^^+^+^^+^+>+^^+^+^^+^+>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^+^+^+^^>+^^+^+^^+>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>+^+^+^+^+^>>>>>>-<<<<<<[[>>+>+>+>+<<<<<-]+^^^[>>>v^[-<->]<[>>[>]+^^+^^+^+[<]<-]>>v[[>]+^^+^+^+^+^[<]>[<<<+>>>-]]<<<[>+>+>+<<<-]<-]>>>>>[>]+^+^+^+^+^[<]<<<<<]>>>>>>[>]<+[-.<+]<[.<]
実に2012文字のQuineの完成である。
もっと短くできるという方は挑戦してみてください。