読者です 読者をやめる 読者になる 読者になる

Quine いろいろ

Program

Quine の難しい点はたぶん、

  • 自分自身を出力しようとして永久に書き終わらないよギャース
  • クォート文字列中にクォート文字を入れられないよギャース

という2点じゃないかなぁと思います。前者は変数を使えば簡単です。後者はクォート文字をエンコードできるようにしてやる、っていうのがまぁ基本的な考えかたではないかと思いますが、これは色々方法があります。一般的な作り方としては以下とかがすごくわかりやすかったです。

http://d.hatena.ne.jp/KeisukeNakano/20070814/1187070401

format 系

多くの言語で手軽に書ける…と思う。 %s で自分自身を出力できる && クォート文字列は %c で、っていうのが基本的な発想。 Ruby だと、

printf a="printf a=%c%s%c,34,a,34",34,a,34

とかが基本形。いくつか短くする方法があって、まずは2つ目の %c を %1$c にしてやる方法。 Ruby は %1$c 無いので、 C とかで、 (追記: 普通にあるとのこと。すいません http://znz.s1.xrea.com/t/?date=20081112#p01)

int main(a){printf(a="int main(a){printf(a=%c%s%1$c,34,a);}",34,a);}

などと。 Ruby には %p っていう Quine のために生まれたフォーマット形式があって(inspectした結果が入る)、それを使うと、

printf a="printf a=%p,a",a

とかなり短くなります。

eval

eval は他の Quine とのあわせ技で便利。

eval a="printf'eval a=%p',a"

これだとさっきの printf より長くてイマイチ…という感じしか無いわけですが、ポイントは printf や ,a の部分が一回しか出現していないこと。 Quine は普通出力関係のコードは2回書かないといけないわけですが、 eval を使うと1回にできちゃう。 Pyramid Quine なんかでデコーダが長くなってしまう場合に良いようです。

あと同じ話なんですが、これはつまり、

eval a="***;printf'eval a=%p',a"

の *** の部分に a を破壊したり出力をしない範囲でなら何を書いても Quine になる、というのは面白いかなぁと思います。

このテクニックは eval があるのに加えて、クォート文字が2種類ある言語だといい感じです。

ヒアドキュメント

クォートを開始する文字列がクォート内にあっても大丈夫なリテラルがある言語は割と簡単に、

puts (a=<<E),a,"E"
puts (a=<<E),a,"E"
E

などとして作れます。2つ目の <<E で終わっちゃわないのがポイント。あとヒアドキュメントが1行の途中で来ても平然とその後に式書けるんですよーという。文字列のかけ算があると縮む。ついでに "E" を :E にしてやって、

puts <<E*2,:E
puts <<E*2,:E
E

などなど。

%Q{} やら %{}

ヒアドキュメントと似た感じで書けます。

a=%{print "a=%{",a,"}
",a}
print "a=%{",a,"}
",a

これも } で文字列が終わっちゃわないのがポイント。これは割と素直な形なので、ちょっと Quine 作る時のコツというか私のやりかたみたいなのをご紹介…まず、

a=%{hoge}

などと深く考えずデータ部分を書きます。 hoge が a に入ります。次に、今書いたものを出力するプログラムを書きます。

a=%{hoge}
print "a=%{",a,"}"

何も難しくはないと思います。これで出力は

> ruby quine.rb
a=%{hoge}

という感じです。次に2行目を1行目の中にコピペします。

a=%{print "a=%{",a,"}"}
print "a=%{",a,"}"

出力は、

> ruby quine.rb
a=%{print "a=%{",a,"}"}

となりました。1行目はいい感じです。ここからは、2行目に加えたコードは1行目の文字列内にも同時に加えていくと良いです。まず2行目にうつるために、改行とか加えてみます。

a=%{print "a=%{",a,"}
"}
print "a=%{",a,"}
"

実行すると、

> ruby quine.rb
a=%{print "a=%{",a,"}
"}

うまくいっています。改行の次は2行目を出力したいわけですが、2行目は変数 a に入っているはずなので、 ,a を加えてやれば、

a=%{print "a=%{",a,"}
",a}
print "a=%{",a,"}
",a

という最初のコードになりました。

join

クォート文字列をつっこむ方法として、 join も使えるよねーというような。ほとんど kik さんのコードのまんまです。

a=';print ["a=",a,a].join("%c"%39)';print ["a=",a,a].join("%c"%39)

自分のコードを取り出す

関数のコードを取り出せる言語とかがあったりします。例えば JavaScript や Io 。 JavaScript で書くと、

a=function () {
    print("a=" + a.toString() + ";\na();");
};
a();

などと。イメージとしては eval に近い感じかなぁと思います。 SpiderMonkey(smjs) に依存してます。

この方法は SiroKuro さんとこ で見てなるほどなぁと感動しました。

自力デコード

他にも色々方法はあったと思うのですが、気の効いた方法が無い言語でも、最終手段として自力でデコーダを書けば、必ず Quine が書けます。エンコード方法は自由なのですが、ありがちなのはたぶん文字コードに1を足しておいたデータを持っておいて、 Quine の中でそのデータを出力した後でデコーダで出力するような。

a='qvut!#b>(#,b,#(#<b/fbdi`czuf|}d}qvud!d.2~'
puts "a='"+a+"'";a.each_byte{|c|putc c-1}

こういうヤツ。 puts でデータ部分を出力するところと、 each_byte でデコードする部分を先に書いておいて、その後でエンコードされた文字列を生成すると良いです。

Brainfuck とかそいう言語だとこういう感じでやるしかないわけですが、デコーダの形式は自由なので、腕の見せどころという感があります。例えば 私が 164MB かけて書いた quine.grass を 1525B で書いたりする子がいるわけです。

エンコード方法の工夫の例としては、 JavaScript は URL の unescape が組み込みで入っているので、それを利用して、

a="print('a=%22'+a+'%22;'+unescape(a));";print('a="'+a+'";'+unescape(a));

など。

自分を読み込む

論外な方法として自分をファイルとして読みこむというのがあります。まぁそれは不粋だろうという感じしかしませんが、機械語なんかだとメモリ空間に自身のコードがロードされているので、それを出力するだけでいい、っていうのはまぁ面白いかと思います。 Befunge なんかも自分のロードされた空間をメモリとして読めるので比較的簡単に作れるなど。

あと、 PHP という言語はご存じの通り Quine に最適化して設計された言語であるため、

a

などという1バイトのコードが Quine になってしまったりします。さすがですね。

追記 from id:yshl さん

http://d.hatena.ne.jp/yshl/20081102#1225609290

PostScript の Quine 短い。

文字列をプログラム中に書くような…は Ruby でも、

a="print'a=';p a;print a"
print'a=';p a;print a

などとできますが、出力部分が分断されてしまうのがイマイチな感じだったり。思うにスタック言語は式書いときゃ明示的に代入することなくスタックに置けるってのは強みですねえ。

あと m4 はアレたぶん turing 完全じゃないですよね…(自信ない)

=> コメントいただきましたが、 m4 完璧に turing 完全でした! FizzBuzz書けたし

追記: C 言語のマクロ

これも %p や p の類型かなと思います。

The Quine Page の、

http://www.nyx.net/~gthompso/self_c.txt

にあった、以下のようなコード。

#define q(k)main(){puts(#k"\nq("#k")");}
q(#define q(k)main(){puts(#k"\nq("#k")");})

#k でうまいことトークンを文字列化しちゃっています。なるほどなぁ。

他にも

なんかよくあるのがあった気がします。なんか面白いのがあったら教えていただけると嬉しいです。

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h