TechFULの中の人

TechFULスタッフ・エンジニアによる技術ブログ。IT関連のことやTechFULコーディングバトルの超難問の深掘り・解説などを毎週更新

クワインの書き方【自分自身を表示するプログラム】

自身のソースコードと完全に同じ文字列を出力するプログラムは Quine (クワイン) と呼ばれます。

Quine は単純に書けるものではありません。 例えば Python3 で print 関数から Quine を書き始めようとすると、引数に渡すべき文字列は自身のソースコードなので "print( から始まり、その括弧の中身も "print( ... と永遠に続いてしまいます。

# Quine を print から書き始めようとするとキリがない
print("print(\"print(\\\" ... ")

このように単純には書くことのできない Quine ですが、定石さえ知っていれば下図のような Quine を作れます。

謹賀新年Quineの実行結果スクリーンショット
謹賀新年Quineの実行結果

これは私が作った、Ruby 言語によるアスキーアート Quine です。 本稿の投稿時期はお正月でしたので、それにちなんで「謹賀新年」を表示しています。 このアスキーアートRuby で実行すれば、全く同じアスキーアートのコードが出力されます。試してみてください。

以下にテキストのソースコードを貼っておきます。

     eval$s=        %w(      $s=               %(
                    eva      l$s              =%w             (#{$s})*"");k
                ahdiealkbayeizytgakdi     elaheyeiwoaiekya    w=         %q
  (x2uoz7p55x6h 3b8gn7zxvnkrmvw4k1xvj         zyn      c9u    pa         gh
                    rro      jog            v34        ilc    qd         ol
                    dsx      9yb        c2bs7     i85qfb8     xnb194hb9tdrz
     dcwul72    k8wjkh2paie00fbxbds40    8c
                ps       gko       nm         twaqk8znuogjbsjuncsqqn24
                ou       ha3       ot         3g                    hx
     n5cx2ux    vwax1hxow8tpyamjokj7y         rzmd32sbr9mnuymtbg9dio0d
                         cg5                  z9                    pg
                  gfoa8twzvq0hfyig            nmre3mdynwh3tnp2sebbshaz
   p3692r0uysm           1td                  cj                    qz
   7m       17    ms2bn6g79j5yo118            6gvgv33t4uwjegg7oywc7sd8
   o3       de           jr9
   2y       67 2ic5jl1u00xco5se6575two           2cvj0b0     6ixwmi3
   xi2rh0kikjv 7jobzwpc0bjzhckm4lenkbh         e3zlqs            gqj4ffd
                                         u4ynjyn                     n6amuj

         eg                        y               v
         1n                     i1fcu             c2d
    p82z6fqhc7no9          cc373f                lhu
      sr     0e       fx9bdj                    2xglct3eq7sxljn4shtw54sp
       2     x        ut0                      hd3        du3
       fz   9a        szz                    b74          6no
  g2c8e1rtajenxmn4)   .to_i(36);f=->(n     ){$    s.      sli
         ce           !(0     0,n         )}      ;h,wi=37,76;puts;h.
   times{|i|line=St   rin     g.n                 ew      ();
        wi.t          ime     s{|                 j|      if(
      kahdiealk       bay     eiz                 yt      gak
      di el  ahe      ye      iwo       aiekyaw[wi*i+j]==0);line<<32.chr;el
     se  ;l   in     e<<      f[1                         ];e
    nd   ;}    ;l    in       e.r                         str
  ip!    ;l         in        e<<                         ';'
 if      (i       +1=         =h)                         ;pu
         ts     (li           ne)                         })*
                                                          "";

QuineソースコードとQuine実行結果の diff をとった図。
両者は同一であることが示された。

Quine 自体が社会の役に立つことは期待しにくいですが、プログラマの遊びとしては面白いものだと思います。 本稿では Quine を書いてみたいプログラマ向けに Quine の書き方を紹介します。 説明には Python3 をメインに用いますが、Quine を書く手法は他の多くの言語にも通用します。

Quine らしくない Quine

もしかしたら、読者の中には「自身のファイルを読み込んでそれを表示すればいいじゃないか」と考える人もいるかもしれません。 例えば Python3 だと以下のようなプログラムが考えられます。

with open(__file__) as f:
    print(f.read())

確かに上記のようなプログラムは自分自身を出力しますが、簡単すぎます。 そこで、以降は 外部からの入力をしない というルールのもとで Quine を書くことにします。

他にも 0 バイトのスクリプトも Quine と解釈できますが、ここでの紹介に留めておきます。

Quine の考え方

ソースコードの先頭を print にすると手詰まりになることは冒頭で示しました。 print から書き始める方針をやめて、「自身のソースコード文字列をプログラム内で構築して出力する」方針で進めると成功します。

以下、Python3 で Quine を作るときの考え方を示します。

1. おもむろに以下のようなコードを書く
s = ""; print(s)

以降、変数 sソースコード文字列を表すために使っていきます。 この時点ではまだ Quine ではありません。

2. s の中身を埋めてみる

変数 sソースコード文字列を表すのでした。 1.のソースコードs = ""; print(s) なので、それを変数 s の値にすればよいです。
すると文字列の中に再び s = "" が登場するのですが、このダブルクォートの中身は ... という文字列で誤魔化しておきます。

s = "s = \"...\"; print(s)"; print(s)
3. ...ソースコード (= s) を埋め込む

2.で誤魔化した ... の部分を解決したいです。 ... はもともとソースコード文字列になる予定のものでした。 変数 sソースコード文字列を表すので、... の部分には s を埋め込めば良いことになります。

そのために文字列の置換を行います。 s.replace('...', s, 1) とすることで、 s 中の ...s の値に置換した文字列を生成できます。 第3引数の 1 は置換回数の上限です。

s = "s = \"...\"; print(s.replace('...', s, 1))"; print(s.replace('...', s, 1))

上記のプログラムを実行すると、以下が出力されます。 ほとんど元のプログラムと一致しており、Quine らしくなりました。

s = "s = "..."; print(s.replace('...', s, 1))"; print(s.replace('...', s, 1))

しかし s = "s = "...." の部分でダブルクォートのエスケープが足りていません。

4. s の値を適切にエスケープして埋め込めば完成

ダブルクォートをエスケープするために s.replace('"', '\\"') する方法が思いつきますが、この方法はいろいろと厳しいです 1

Python3 にはエスケープに利用できる便利な組み込み関数として repr があります。 ※ 文字列をエスケープする専用の関数ではありません。

repr について repr() の引数に文字列を渡すと、インタプリタが解釈したときにもとの文字列になる文字列が生成されます。

# repr の結果例
print(repr("hoge\n"))           #=> 'hoge\n'
print(repr("'"))                #=> "'"
print(repr('\''))               #=> "'"
print(repr('"..." \'hoge\n\'')) #=> '"..." \'hoge\n\''
print(repr("\"...\" 'hoge\n'")) #=> '"..." \'hoge\n\''

3.のプログラムの replace の第2引数を s から repr(s) に変えて、s = \"...\"s = ... に変えてあげれば完成です。

s = "s = ...; print(s.replace('...', repr(s), 1))"; print(s.replace('...', repr(s), 1))

よりシンプルな Quine

先ほどの Quine は文字列の中と実際のコードとで重複があります。 文字列をプログラムとして実行する機能を有している言語ならば、重複なしにより簡単に書けます。

Python3 の exec 関数は引数の文字列をプログラムの文として実行します。 exec を利用すると、下記のような Quine ができます。

s = 'print(f"s = {repr(s)}; exec(s)")'; exec(s)

print の中身は f-string (フォーマット済み文字列リテラル) です。 f-string を使うと、波括弧内の式の値を埋め込んだ文字列を生成できます。

C言語で Quine

先ほどのように、ソースコードを表す文字列 s を用意して、s の中に s を埋め込んだ文字列を表示する 方法は多くの言語に適用できます。

C言語でそのアプローチを使って Quine を実装してみます。 C言語には文字列置換やエスケープをする関数は標準では用意されていません。 しかし文字列を実際に置換せずとも、置換した結果さえ表示できれば良いので、s を先頭から1文字ずつ出力して、 ... の部分では代わりにダブルクォートと s を出力するようにすれば可能です。

下記にC言語による Quine の例を示します。
※読みやすさのために改行やインデントを入れています。

変数 s の中身において、 ...@ 1文字で表し、改行文字は $ で表しています。 エスケープは極力避けたいので、文字リテラルを用いずに、対応するASCIIコードの整数リテラルを用いています。 C言語では連続する文字列リテラルは連結されることを利用して、s の値は複数行に分けています (読みやすさのため)。

#include <stdio.h>
const char *s =
"#include <stdio.h>$"
"const char *s = @; "
"int main() {"
    "for (const char *p = s; *p; ++p) {"
        "if (*p == 64) {"
            "putchar(34);"
            "fputs(s, stdout);"
            "putchar(34);"
        "} else if (*p == 36) {"
            "putchar(10);"
        "} else {"
            "putchar(*p);"
        "}"
    "}"
    "return 0;"
"}";
int main() {
    for (const char *p = s; *p; ++p) { // s を1文字ずつ走査
        if (*p == 64) {         // *p == '\n' なら s の値をダブルクォートで囲んで表示
            putchar(34);
            fputs(s, stdout);
            putchar(34);
        } else if (*p == 36) {  // *p == '$' なら改行
            putchar(10);
        } else {                // そうでなければ *p を表示
            putchar(*p);
        }
    }
    return 0;
}

上記のプログラムを正式な Quine にするために改行とインデントとコメントを頑張って取り除いても良いですが、そのような必要はありません。 このプログラムをコンパイルして実行すれば、所望の Quine プログラムが得られます。

実行して得られる出力は以下のとおりです。

#include <stdio.h>
const char *s = "#include <stdio.h>$const char *s = @; int main() {for (const char *p = s; *p; ++p) {if (*p == 64) {putchar(34);fputs(s, stdout);putchar(34);} else if (*p == 36) {putchar(10);} else {putchar(*p);}}return 0;}"; int main() {for (const char *p = s; *p; ++p) {if (*p == 64) {putchar(34);fputs(s, stdout);putchar(34);} else if (*p == 36) {putchar(10);} else {putchar(*p);}}return 0;}

ちなみにマクロ機能を利用すれば、以下のように重複を少なくできます。

#define Q(prog) const char *s = #prog; prog
Q(int main() { __builtin_printf("#define Q(prog) const char *s = #prog; prog\nQ(%s)\n", s); })

上記プログラムについて簡単に解説すると、

  • #define マクロ内では文字列化演算子 # を利用している。 #prog とすることでその部分は prog を表す文字列リテラルとして展開される。
  • printf ではなくコンパイラ組み込みの __builtin_printf を使うことで stdio.h のインクルードを不要にしている (インクルードせずに printf してもできるが、コンパイラから警告されてしまう)。

終わりに

言語によってはさらにいろいろな Quine の書き方があり面白いです。 本稿で紹介していないテクニックがまだありますが、ここで終わりたいと思います。

より詳しく知りたい方は参考文献の方をご覧いただくと良いかと思います。

参考文献

  • 遠藤 侑介『あなたの知らない超絶技巧プログラミングの世界』(技術評論社,2015)
  • 遠藤 侑介『Rubyによる超絶技巧プログラミング』(情報処理学会,2012)

  1. すると今度は replace の引数そのもののダブルクォートをエスケープする必要があります。文字 " はASCIIコードで10進数の 34 、文字 \ は10進数の 92 であることを利用すると、s.replace(chr(34), chr(92) + chr(34)) と書くことができますが、 s の値の中の4つのダブルクォートのうち1つ目と4つ目はエスケープしてはいけないので面倒です。