- Quine (computing)
-
A quine's output is exactly the same as its source code
A quine is a computer program which takes no input and produces a copy of its own source code as its only output. The standard terms for these programs in the computability theory and computer science literature are self-replicating programs, self-reproducing programs, and self-copying programs.
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.
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
History
The idea of self-reproducing programs first appeared in Paul Bratley and Jean Millo's article "Computer Recreations: Self-Reproducing Automata" in 1972.[2] 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
The name "quine" was coined by Douglas Hofstadter, in his popular science book Gödel, Escher, Bach: An Eternal Golden Braid, in the honor of philosopher Willard Van Orman Quine (1908–2000), who made an extensive study of indirect self-reference, and in particular for the following paradox-producing expression, known as Quine's paradox:
"Yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation.
Example
The following Java code demonstrates the basic structure of a quine.
public class Quine { public static void main( String[] args ) { char q = 34; // Quotation mark character String[] l = { // Array of source code "public class Quine", "{", " public static void main( String[] args )", " {", " char q = 34; // Quotation mark character", " String[] l = { // Array of source code", " ", " };", " for( int i = 0; i < 6; i++ ) // Print opening code", " System.out.println( l[i] );", " for( int i = 0; i < l.length; i++ ) // Print string array", " System.out.println( l[6] + q + l[i] + q + ',' );", " for( int i = 7; i < l.length; i++ ) // Print this code", " System.out.println( l[i] );", " }", "}", }; for( int i = 0; i < 6; i++ ) // Print opening code System.out.println( l[i] ); for( int i = 0; i < l.length; i++ ) // Print string array System.out.println( l[6] + q + l[i] + q + ',' ); for( int i = 7; i < l.length; i++ ) // Print this code System.out.println( l[i] ); } }
The source code contains a string array of itself, which is output twice, once inside quotation marks.
Multiquines
The quine concept can be extended to multiple levels or recursion, originating what has been called multiquines, or "ouroboros programs".
Example
This Java program outputs the source for a C++ program that outputs the original Java code.
#include <stdafx.h> #include <iostream> #include <string> using namespace std; int main(int argc, _TCHAR* argv[]) { char q = 34; string l[] = { " ", "=============<<<<<<<< C++ Code >>>>>>>>=============", "#include <stdafx.h>", "#include <iostream>", "#include <string>", "using namespace std;", "", "int main(int argc, _TCHAR* argv[])", "{", " char q = 34;", " string l[] = {", " };", " for( int i = 21; i <= 26; i++ )", " cout << l[i] << endl;", " for( int i = 0; i <= 35; i++ )", " cout << l[0] + q + l[i] + q + ',' << endl;", " for( int i = 27; i <= 35; i++ )", " cout << l[i] << endl;", " return 0;", "}", "=============<<<<<<<< Java Code >>>>>>>>=============", "public class Quine", "{", " public static void main( String[] args )", " {", " char q = 34;", " String[] l = {", " };", " for( int i = 2; i <= 10; i++ )", " System.out.println( l[i] );", " for( int i = 0; i < l.length; i++ )", " System.out.println( l[0] + q + l[i] + q + ',' );", " for( int i = 11; i <= 19; i++ )", " System.out.println( l[i] );", " }", "}", }; for( int i = 21; i <= 26; i++ ) cout << l[i] << endl; for( int i = 0; i <= 35; i++ ) cout << l[0] + q + l[i] + q + ',' << endl; for( int i = 27; i <= 35; i++ ) cout << l[i] << endl; return 0; }
public class Quine { public static void main( String[] args ) { char q = 34; String[] l = { " ", "=============<<<<<<<< C++ Code >>>>>>>>=============", "#include <stdafx.h>", "#include <iostream>", "#include <string>", "using namespace std;", "", "int main(int argc, _TCHAR* argv[])", "{", " char q = 34;", " string l[] = {", " };", " for( int i = 21; i <= 26; i++ )", " cout << l[i] << endl;", " for( int i = 0; i <= 35; i++ )", " cout << l[0] + q + l[i] + q + ',' << endl;", " for( int i = 27; i <= 35; i++ )", " cout << l[i] << endl;", " return 0;", "}", "=============<<<<<<<< Java Code >>>>>>>>=============", "public class Quine", "{", " public static void main( String[] args )", " {", " char q = 34;", " String[] l = {", " };", " for( int i = 2; i <= 10; i++ )", " System.out.println( l[i] );", " for( int i = 0; i < l.length; i++ )", " System.out.println( l[0] + q + l[i] + q + ',' );", " for( int i = 11; i <= 19; i++ )", " System.out.println( l[i] );", " }", "}", }; for( int i = 2; i <= 10; i++ ) System.out.println( l[i] ); for( int i = 0; i < l.length; i++ ) System.out.println( l[0] + q + l[i] + q + ',' ); for( int i = 11; i <= 19; i++ ) System.out.println( l[i] ); } }
Such programs have been produced with various cycle lengths:
- Haskell → Python → Ruby[3]
- Python → Bash → Perl[4]
- C → Haskell → Python → Perl[5]
- Haskell → Perl → Python → Ruby → C → Java[6]
- C → C++ → Ruby → Python → PHP → Perl[7]
- Ruby → Python → Perl → Lua → OCaml → Haskell → C → Java → Brainfuck → Whitespace → Unlambda[8]
See also
- Diagonal lemma
- Fixed point combinator
- Self-interpreter
- Self-replicating machine
- Self-replication
- Tupper's self-referential formula
- Programming Languages
- Grey goo
References
- ^ IOCCC 1994 Worst Abuse of the Rules
- ^ Bratley, Paul; Millo, Jean (1972). "Computer Recreations: Self-Reproducing Automata". Software Practice and Experience 2: 397–400.
- ^ Dan Piponi (5 February 2008). "A Third Order Quine in Three Languages". http://blog.sigfpe.com/2008/02/third-order-quine-in-three-languages.html.
- ^ Bruce Ediger. "Ask and ye shall receive: Self-replicating program that goes through three generations, Python, Bash, Perl". http://www.stratigery.com/source.html#Ouroboros.
- ^ b.m. (1 February 2011). "multiquine". http://hpaste.org/43501/multiquine.
- ^ Dan Piponi (30 January 2011). "Quine Central". http://blog.sigfpe.com/2011/01/quine-central.html.
- ^ Shinichiro Hamaji (10 November 2007). "Quine by shinh (C C++ Ruby Python PHP Perl)". http://golf.shinh.org/reveal.rb?Quine/shinh+%28C+C%2B%2B+Ruby+Python+PHP+Perl%29_1194650418&rb. (this one is also a polyglot)
- ^ Ku-ma-me (22 September 2009). "Uroboros Programming With 11 Programming Languages". http://asiajin.com/blog/2009/09/22/uroboros-programming-with-11-programming-languages/.
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)
External links
- The Quine Page (by Gary P. Thompson)
- QuineProgram at the Portland Pattern Repository Wiki
- David Madore's Discussion of Quines
- Zip Files All The Way Down
- An Introduction to Quines — in particular, quines using more than one language
- Quine Web Page: A standards-conforming HTML+JavaScript web page that shows its own source code
- An unusually short Quine that incorporates optical character recognition
Standard test items Television (test card) Computer programming Data compression 3D computer graphics Other Categories:- Source code
- Articles with example Lisp code
- Articles with example Scheme code
- Willard Van Orman Quine
Wikimedia Foundation. 2010.
