Quine (computing)
From Wikipedia, the free encyclopedia
In computing, a quine is a computer program which produces a copy of its own source code as its only output.
A quine is a fixed point of an execution environment, when the execution environment is viewed as a function. Quines are possible in any programming language that has the ability to output any computable string, as a direct consequence of Kleene's recursion theorem. For amusement, programmers sometimes attempt to develop the shortest possible quine in any given programming language.
Quines are named after philosopher Willard Van Orman Quine (1908–2000), who made an extensive study of indirect self-reference. He coined, among others, the following paradox-producing expression, known as Quine's paradox:
"Yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation.
A quine takes no input. Allowing input would permit the source code to be fed to the program via the keyboard, opening the source file of the program, and similar mechanisms.
In some languages, an empty source file is a fixed point of the language, producing no output. Such an empty program, submitted as "the world's smallest self reproducing program", once won the "worst abuse of the rules" prize in the Obfuscated C contest.[1]
Contents |
[edit] History
The idea of self-reproducing programs first appeared in Bratley, Paul and Jean Millo. "Computer Recreations; Self-Reproducing Automata", Software -- Practice & Experience, Vol. 2 (1972). pp. 397-400. Bratley first became interested in self-reproducing programs after seeing the first known such program written in Atlas Autocode at Edinburgh in the 1960s by the University of Edinburgh lecturer and researcher Hamish Dewar. This program appears below:
%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
[edit] Examples
In general, the method used to create a quine in any programming language is to have, within the program, two pieces: (a) code used to do the actual printing and (b) data that represents the textual form of the code (e.g., progdata in the first C example below). The code functions by using the data to print the code (which makes sense since the data represents the textual form of the code), but it also uses the data, processed in a simple way (e.g., quote() below) to print the textual representation of the data itself. There are many ways the code and the data can be organized together within the program (neither must be contiguous), but a common telltale sign of the data section is that it mirrors some part of the entire program.
An example in colloquial English would be:
"quoted and followed by itself is a quine." quoted and followed by itself is a quine.
(from http://spikeypillow.com/item/31)
[edit] C
The idea behind this quine is to store a copy of the program code in a string, and use that to print out both the program code and the string.
/* 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; }
An alternative approach in C would be to make use of the C pre-processor. For example:
#include <stdio.h> int main(int argc, char** argv) { /* This macro B will expand to its argument, followed by a printf command that prints the macro invocation as a literal string */ #define B(x) x; printf(" B(" #x ")\n"); /* This macro A will expand to a printf command that prints the macro invocation, followed by the macro argument itself. */ #define A(x) printf(" A(" #x ")\n"); x; /* Now we call B on the text of the program up to this point. It will execute the command, and then cause itself to be printed. */ B(printf("#include <stdio.h>\n\nint main(int argc, char** argv)\n{\n/* This macro B will expand to its argument, followed by a printf\n command that prints the macro invocation as a literal string */\n#define B(x) x; printf(\" B(\" #x \")\\n\");\n\n/* This macro A will expand to a printf command that prints the\n macro invocation, followed by the macro argument itself. */\n#define A(x) printf(\" A(\" #x \")\\n\"); x;\n\n/* Now we call B on the text of the program\n up to this point. It will execute the command, and then cause\n itself to be printed. */\n")) A(printf("/* Lastly, we call A on a command to print the remainder of the program;\n it will cause itself to be printed, and then execute the command. */\n}\n")) /* Lastly, we call A on a command to print the remainder of the program; it will cause itself to be printed, and then execute the command. */ }
Note that in the above, the line beginning with B(printf( would be one line; there is exactly one space between the end of each line and the beginning of the next, but it is broken into multiple lines so that it does not overflow the screen. Likewise, the line beginning A(printf( has been broken into multiple lines.
After eliminating comments, the essence of this method is:
#define B(x) int main(){x; puts("B(" #x ")");} B(puts("#define B(x) int main(){x; puts(\"B(\" #x \")\");}"))
An even shorter, classic,[2] approach in C instead exploits the ability of the printf function to use a format string, passing a carefully-constructed string as both the format string and a substitution parameter. Note: 34 is the ASCII code for a double-quote character, and is used to avoid the need to quote the double-quotes in the string literal.
main() { char *s="main() { char *s=%c%s%c; printf(s,34,s,34); }"; printf(s,34,s,34); }
This program uses the printf function without including its corresponding header (#include <stdio.h>), which can result in undefined behavior. Also, the return type declaration for main has been left off to reduce the length of the program.
[edit] Scheme (also valid Common Lisp)
This quine works by feeding the program to itself, which then converts the data structure to source code.
((lambda (x) (list x (list 'quote x))) '(lambda (x) (list x (list 'quote x))))
[edit] See also
[edit] References
[edit] Further reading
- Douglas Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid
- Ken Thompson: "Reflections on Trusting Trust" (Communications of the ACM, 27(8):761-3)
