クワイン (プログラミング)

クワイン（英: Quine）は、コンピュータプログラムの一種で、自身のソースコードと完全に同じ文字列を出力するプログラムである。娯楽として、プログラマーが任意のプログラミング言語でのクワインを書いたり、最短クワインを書いたりすることがある。クワインをプログラムを出力するプログラムだと見なせば、クワインのプログラミングはメタプログラミングの一種である。

要件の直感的な説明からは、いくつかのチート的な解がある。例えば、入力をそのまま出力するだけのプログラム（Unixではcatというプログラムが利用される）の入力を、そのプログラムのソースファイルとするとか、いくつかのプログラミング言語（の処理系）は空のソースコードを受け取って、何も行わない、という動作をするので、それを利用する手もある。そのような空のプログラムがIOCCCで「規則のはなはだしい悪用」賞を受賞したこともある。以上のようなプログラムはいずれも通常、この問題を解いたものとはみなされない。

クワインという名称は、自己参照の研究について業績を残した哲学者ウィラード・ヴァン・オーマン・クワイン（1908-2000）に由来し、命名したのはダグラス・ホフスタッターでそれほど古いことではないため、古い文献では自己複製・自己再生成などといった表現で呼ばれていることがある。(プログラミング言語ではない)言語的には次の一文で表されるクワインのパラドックスと、同様の構造を持っている。

「『は、自身の引用を前置されると偽になる』は、自身の引用を前置されると偽になる」

歴史

クリーネの再帰定理から直接導かれる通り、任意の計算可能な文字列を出力できるプログラミング言語にはクワインが存在する。このようなクワインという発想が最初に見られたのは、Bratley, Paul and Jean Millo. "Computer Recreations; Self-Reproducing Automata", Software -- Practice & Experience, Vol. 2 (1972). pp. 397-400. doi:10.1002/spe.4380020411 であった。Bratley が自己複製プログラムに興味を持つようになったのは、エディンバラ大学の講師兼研究者 Hamish Dewar が Atlas Autocode で書いたプログラムを見たことがきっかけであった。そのプログラムは次の通りである。

%BEGIN
!THIS IS A SELF-REPRODUCING PROGRAM
%ROUTINESPEC R
R
PRINT SYMBOL(39)
R
PRINT SYMBOL(39)
NEWLINE
%CAPTION %END~
%CAPTION %ENDOFPROGRAM~
%ROUTINE R
%PRINTTEXT '
%BEGIN
!THIS IS A SELF-REPRODUCING PROGRAM
%ROUTINESPEC R
R
PRINT SYMBOL(39)
R
PRINT SYMBOL(39)
NEWLINE
%CAPTION %END~
%CAPTION %ENDOFPROGRAM~
%ROUTINE R
%PRINTTEXT '
%END
%ENDOFPROGRAM

例

あるプログラマがこれをナイーブに実装しようとしているとする。まず、ソースコードの中に直接自分自身のコードを文字列にして埋め込もうとするだろう。そしてしばらくして、ある種の「無限後退」に陥ってしまっていることに気付くことになる。自然言語の例で表現するなら、「私は、「私は、「私は、……と言おうとした」と言おうとした」と言おうとした」というような感じになるが、この『……』の部分が無限になってしまうのである。これをどのように回避するかがポイントである。

一般に、任意のプログラミング言語でクワインを書くには、プログラム内を以下の2つの部分に分ける。第一は、出力を実際に行うソースコード、第二は、コードを文字列として表したデータである（例えば、後述のC言語の例での progdata）。コードはデータを使ってコード部自身の出力もするが（データの内容が元々コード部をテキスト表現にしたものであるため、これが可能となる）、もっと単純にデータのテキスト表現も出力する。コードとデータをプログラム内で構成する方法は様々であるが、データ部の共通な特徴として、データはプログラム全体のある程度の部分を反映している。

C言語

C言語でのクワインの例を示す。ここでは、コードを文字列として格納しており、コード部と文字列自身の2回の出力を行う。

/* A simple quine (self-printing program), in standard C. */

/* Note: in designing this quine, we have tried to make the code clear
 * and readable, not concise and obscure as many quines are, so that
 * the general principle can be made clear at the expense of length.
 * In a nutshell: use the same data structure (called "progdata"
 * below) to output the program code (which it represents) and its own
 * textual representation. */

#include <stdio.h>

void quote(const char *s)
     /* This function takes a character string s and prints the
      * textual representation of s as it might appear formatted
      * in C code. */
{
    int i;

    printf("    \"");
    for (i=0; s[i]; ++i) {
        /* Certain characters are quoted. */
        if (s[i] == '\\')
            printf("\\\\");
        else if (s[i] == '"')
            printf("\\\"");
        else if (s[i] == '\n')
            printf("\\n");
        /* Others are just printed as such. */
        else
            printf("%c", s[i]);
        /* Also insert occasional line breaks. */
        if (i % 48 == 47)
            printf("\"\n    \"");
    }
    printf("\"");
}

/* What follows is a string representation of the program code,
 * from beginning to end (formatted as per the quote() function
 * above), except that the string _itself_ is coded as two
 * consecutive '@' characters. */
const char progdata[] =
    "/* A simple quine (self-printing program), in st"
    "andard C. */\n\n/* Note: in designing this quine, "
    "we have tried to make the code clear\n * and read"
    "able, not concise and obscure as many quines are"
    ", so that\n * the general principle can be made c"
    "lear at the expense of length.\n * In a nutshell:"
    " use the same data structure (called \"progdata\"\n"
    " * below) to output the program code (which it r"
    "epresents) and its own\n * textual representation"
    ". */\n\n#include <stdio.h>\n\nvoid quote(const char "
    "*s)\n     /* This function takes a character stri"
    "ng s and prints the\n      * textual representati"
    "on of s as it might appear formatted\n      * in "
    "C code. */\n{\n    int i;\n\n    printf(\"    \\\"\");\n "
    "   for (i=0; s[i]; ++i) {\n        /* Certain cha"
    "racters are quoted. */\n        if (s[i] == '\\\\')"
    "\n            printf(\"\\\\\\\\\");\n        else if (s["
    "i] == '\"')\n            printf(\"\\\\\\\"\");\n        e"
    "lse if (s[i] == '\\n')\n            printf(\"\\\\n\");"
    "\n        /* Others are just printed as such. */\n"
    "        else\n            printf(\"%c\", s[i]);\n   "
    "     /* Also insert occasional line breaks. */\n "
    "       if (i % 48 == 47)\n            printf(\"\\\"\\"
    "n    \\\"\");\n    }\n    printf(\"\\\"\");\n}\n\n/* What fo"
    "llows is a string representation of the program "
    "code,\n * from beginning to end (formatted as per"
    " the quote() function\n * above), except that the"
    " string _itself_ is coded as two\n * consecutive "
    "'@' characters. */\nconst char progdata[] =\n@@;\n\n"
    "int main(void)\n     /* The program itself... */\n"
    "{\n    int i;\n\n    /* Print the program code, cha"
    "racter by character. */\n    for (i=0; progdata[i"
    "]; ++i) {\n        if (progdata[i] == '@' && prog"
    "data[i+1] == '@')\n            /* We encounter tw"
    "o '@' signs, so we must print the quoted\n       "
    "      * form of the program code. */\n        {\n "
    "           quote(progdata);    /* Quote all. */\n"
    "            i++;                /* Skip second '"
    "@'. */\n        } else\n            printf(\"%c\", p"
    "rogdata[i]);  /* Print character. */\n    }\n    r"
    "eturn 0;\n}\n";

int main(void)
     /* The program itself... */
{
    int i;

    /* Print the program code, character by character. */
    for (i=0; progdata[i]; ++i) {
        if (progdata[i] == '@' && progdata[i+1] == '@')
            /* We encounter two '@' signs, so we must print the quoted
             * form of the program code. */
        {
            quote(progdata);    /* Quote all. */
            i++;                /* Skip second '@'. */
        } else
            printf("%c", progdata[i]);  /* Print character. */
    }
    return 0;
}

もう1つの例は、C のプリプロセッサを使ったものである。

#include <stdio.h>
int main(int argc, char** argv)
{
#define B(x) x; printf("  B(" #x ")\n");
#define A(x) printf("  A(" #x ")\n"); x;
  B(printf("#include <stdio.h>\nint main(int argc, char** argv)\n{\n#define B(x) 
    x; printf(\"  B(\" #x \")\\n\");\n#define A(x) printf(\"  A(\" #x \")\\n\"); x;\n"))
  A(printf("}\n"))
}

この例では、B(printf( で始まる行は次の行と繋がっている（見やすくするため2行で表示した）。argv)\n{\n#define B(x) と x; の間には空白が1つある。

プロプロセッサを使わずに、printf 関数を利用して注意深く書式文字列と置換パラメータを配置することで、さらに短いプログラムを書くこともできる。以下の例で、34 というのはダブルクオート文字のASCIIコードであり、文字列リテラル内のダブルクオートを引用する必要を防ぐために使われている。

int main() { char *s = "int main() { char *s = %c%s%c; printf(s, 34, s, 34); }"; printf(s, 34, s, 34); }

Scheme

Schemeでの例。Common Lisp としても妥当な例となっている。このクワインではプログラム自身を入力とし、データ構造からソースコードへの変換が行われる。

((lambda (x) (list x (list 'quote x)))
 '(lambda (x) (list x (list 'quote x))))

MS-Office VBA（マクロ）

MS-Office VBA（マクロ）の例。イミディエイトウィンドウに直接入力可能なこの軽い遊びの例は、故意による可読性低下・冗長な装飾を含み、コードが前後同形になっている。

:i="&chr(34):?mid(i,34);i;mid(i,1,34):i="&chr(34):?mid(i,34);i;mid(i,1,34):

Haskell

Haskellでの例。Haskellには値をその表現に変換するshow関数が備わっているため簡単に実装できる。

main = putStrLn $ q ++ show q where q = "main = putStrLn $ q ++ show q where q = "

Brainfuck

Brainfuckでの例^[1]。改行を除けば僅か404バイトしかない。

-
>++>+++>+>+>+++>>>>>>>>>>>>>>>>>>>>>>+>+>++>+++>++>>+++
>+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+>+>>+++>>>>+++>>>+++
>+>>>>>>>++>+++>+++>+>>+++>+++>+>+++>+>+++>+>++>+++>>>+
>+>+>+>++>+++>+>+>>+++>>>>>>>+>+>>>+>+>++>+++>+++>+>>+++
>+++>+>+++>+>++>+++>++>>+>+>++>+++>+>+>>+++>>>+++>+>>>++
>+++>+++>+>>+++>>>+++>+>+++>+>>+++>>+++>>
+[[>>+[>]+>+[<]<-]>>[>]<+<+++[<]<<+]
>>>[>]+++>+
[+[<++++++++++++++++>-]<++++++++++.<]

HQ9+

HQ9+での例。HQ9+自体にクワインのプログラムが備わっているため、1文字でクワインを実現可能である。

Python3系

Pythonでの例。reprを用いてオブジェクトを返す処理を組み込むことにより、比較的単純に実現可能。

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

脚注

[脚注の使い方]

^ “quine.bf - λx.x K S K ＠はてな”. はてなダイアリー 2018年7月12日閲覧。

参考文献

ダグラス・ホフスタッター: 『ゲーデル、エッシャー、バッハ - あるいは不思議の環』
ケン・トンプソン: "Reflections on Trusting Trust" (Communications of the ACM, 27(8):761-3)

外部リンク

[1] “quine.bf - λx.x K S K ＠はてな”. はてなダイアリー 2018年7月12日閲覧。

[1]

表話編歴標準テストアイテム
パングラムリファレンス実装健全性テストスタンダード・テスト画像（英語版）
人工知能	中国語の部屋チューリングテスト
テレビ（テストパターン）	SMPTEカラーバーインディアンヘッドテストカード（英語版）テストカードF（英語版）フィリップス PM5544（英語版）
プログラミング言語	Hello world クワイン TPKアルゴリズム Man or boy テスト（英語版） Just another Perl ハッカー（英語版）
データ圧縮	カルガリーコーパス（英語版）カンタベリーコーパス（英語版）
3Dコンピュータグラフィックス	コーネルボックススタンフォードバニースタンフォードドラゴン（英語版）ユタ・ティーポット
機械学習	ImageNet MNISTデータベース一覧（英語版）
タイポグラフィ	etaoin shrdlu Hamburgevons Lorem ipsum The quick brown fox jumps over the lazy dog
その他	EICARテストファイル GTUBE ハーバードセンテンス（英語版）レナ北風と太陽トムズ・ダイナー（英語版） SMPTEユニバーサルリーダーユーリオンシェイクダウン Acid3 本日は晴天なり USAFパターン（英語版） 3DBenchy

歴史

例

C言語