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

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

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

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

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

1. 歴史
-----

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

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

2. 例
----

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

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

2.1. C言語
--------

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

/* A simple quine , 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  and its own
textual representation. */
include void quote /* 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  { /* Certain characters are quoted. */ if  printf; else if  printf; else if  printf; /* Others are just printed as such. */ else printf; /* Also insert occasional line breaks. */ if  printf("\"

\"");} printf; }

/* What follows is a string representation of the program code,

from beginning to end  function
above), except that the string _itself_ is coded as two
consecutive '@' characters. */const char progdata[] = "/* A simple quine , in st" "andard C. */

/* Note: in designing this quine, " "we have tried to make the code clear

* and read""able, not concise and obscure as many quines are" ", so that

* the general principle can be made c""lear at the expense of length.

* In a nutshell:"" use the same data structure  to output the program code  and its own

* textual representation"". */

include void quote

/* This function takes a character stri""ng s and prints the

* textual representati""on of s as it might appear formatted

* in ""C code. */ {

int i; printf; "" for  {

/* Certain cha""racters are quoted. */

if ""

printf; else if 

printf; e""lse if 

printf;" "

/* Others are just printed as such. */" " else

printf; "" /* Also insert occasional line breaks. */

"" if 

printf;

} printf;}

/* What fo" "llows is a string representation of the program " "code,

* from beginning to end  function

* above), except that the"" string _itself_ is coded as two

* consecutive ""'@' characters. */ const char progdata[] = @@;

" "int main

/* The program itself... */" "{

int i; /* Print the program code, cha""racter by character. */

for  {

if 

/* We encounter tw""o '@' signs, so we must print the quoted

"" * form of the program code. */

{ "" quote; /* Quote all. */ " " i++; /* Skip second '" "@'. */

} else printf; /* Print character. */

} r""eturn 0; } ";

int main /* The program itself... */ { int i;

/* Print the program code, character by character. */ for  { if  /* We encounter two '@' signs, so we must print the quoted

form of the program code. */{ quote; /* Quote all. */ i++; /* Skip second '@'. */ } else printf; /* Print character. */ } return 0; }<WtXmlEndTag />

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

include int main {

define B x; printf");

define A printf"); x; B {

define Bx; printf\ \");

define A printf\\"); x; ")) A) }<WtXmlEndTag />

この例では、B {

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

int main { char *s = "int main { char *s = %c%s%c; printf; }"; printf; }

2.2. Scheme
-----------

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

 )) ' )))

2.3. MS-Office VBA
------------------

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

i="&chr:?mid;i;mid:i="&chr:?mid;i;mid:<WtXmlEndTag />

2.4. Haskell
------------

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

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

<WtXmlEndTag />

2.5. Brainfuck
--------------

Brainfuckでの例。改行を除けば僅か404バイトしかない。 - >++>+++>+>+>+++>>>>>>>>>>>>>>>>>>>>>>+>+>++>+++>++>>+++ >+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+>+>>+++>>>>+++>>>+++ >+>>>>>>>++>+++>+++>+>>+++>+++>+>+++>+>+++>+>++>+++>>>+ >+>+>+>++>+++>+>+>>+++>>>>>>>+>+>>>+>+>++>+++>+++>+>>+++ >+++>+>+++>+>++>+++>++>>+>+>++>+++>+>+>>+++>>>+++>+>>>++ >+++>+++>+>>+++>>>+++>+>+++>+>>+++>>+++>> +[[>>+[>]+>+[<]<-]>>[>]<+<+++[<]<<+] >>>[>]+++>+ [+[<++++++++++++++++>-]<++++++++++.<]

2.6. HQ9+
---------

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

2.7. Python3系
-------------

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

3. 脚注
-----

4. 参考文献
-------

ダグラス・ホフスタッター: 『ゲーデル、エッシャー、バッハ - あるいは不思議の環』
ケン・トンプソン: "[1]" :761-3)

5. 関連項目
-------

プログラミング 
自己複製
Polyglot 
プログラミング言語一覧

6. 外部リンク
--------

[2] in C 
[3]
[4]
[5]
[6]
[7]
[8]