クワイン (プログラミング)
クワイン (プログラミング)の最新ニュースをまとめて検索!
クワイン(英: Quine)は、コンピュータプログラムにおけるメタプログラミングの一形態であり、自身の完全なソースコードだけを出力するプログラムである。娯楽として、プログラマが任意のプログラミング言語での最短クワインを書くことがある。
入力を受け付けるプログラムは、クワインとは見なされない。入力が許容されるなら、単にキーボードからソースコードを入力するだけで実現してしまうし、そのプログラムのソースファイルを入力とするなどしても実現できる。実行コードを含まないクワインも自明であるとして除外される。多くのプログラミング言語では、実行コードのないプログラムはコードを明らかに出力可能(何もないので、何も出力しないでもクワインと主張できる)である。そのような空のプログラムがIOCCC(国際邪悪なCコードコンテスト)で「規則のはなはだしい悪用」賞を受賞したことがある。
クワインという名称は、間接自己参照の研究についても業績を残した哲学者ウィラード・ヴァン・オーマン・クワイン(1908-2000)に由来する。他にも、次の一文で表されるクワインのパラドックスにも名を残している。
- 「『自身の引用を前置されると偽になる』は、自身の引用を前置されると偽になる」
目次 |
[編集] 歴史
クリーネの再帰定理から直接導かれる通り、任意の計算可能な文字列を出力できるプログラミング言語にはクワインが存在する。このようなクワインという発想が最初に見られたのは、Bratley, Paul and Jean Millo. "Computer Recreations; Self-Reproducing Automata", Software -- Practice & Experience, Vol. 2 (1972). pp. 397-400. であった。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):
[編集] 関連項目
[編集] 参考文献
- ダグラス・ホフスタッター: 『ゲーデル、エッシャー、バッハ - あるいは不思議の環』
- ケン・トンプソン: "Reflections on Trusting Trust" (Communications of the ACM, 27(8):761-3)
[編集] 外部リンク
最終更新 2009年11月19日 (木) 01:17 (日時は個人設定で未設定ならばUTC)。
【クワイン (プログラミング)】変更履歴

