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

クワイン（英: 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での例。改行を除けば僅か404バイトしかない。

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

参考文献

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

関連項目

• プログラミング (コンピュータ)
• 自己複製
• プログラミング言語一覧

外部リンク

• Self Printing Programs Explained in C (at go4expert.com)
• Tupper's Self-Referential Formula
• The Quine Page (by Gary P. Thompson)
• QuineProgram at the Portland Pattern Repository Wiki
• David Madore's Discussion of Quines
• JavaScript Quine Contest Entries
• 自己出力プログラムと自己参照プログラム