Quine (computing): Difference between revisions
Cyberbot II (talk | contribs) m Removing {{Blacklisted-links}}. No blacklisted links were found. (Peachy 2.0 (alpha 8)) |
Rescuing 2 sources and tagging 0 as dead. #IABot (v1.1) |
||
| Line 146: | Line 146: | ||
</source> |
</source> |
||
In [[Rust_(programming_language)|Rust]]: https://play.rust-lang.org/?gist=538739d5b3008dd6edbdc8e2022abb47 |
In [[Rust_(programming_language)|Rust]]: http://web.archive.org/web/20160508013652/https://play.rust-lang.org/?gist=538739d5b3008dd6edbdc8e2022abb47 |
||
<source lang="rust"> |
<source lang="rust"> |
||
fn main() { |
fn main() { |
||
| Line 440: | Line 440: | ||
==Further reading== |
==Further reading== |
||
*[[Douglas Hofstadter]]: ''[[Gödel, Escher, Bach: An Eternal Golden Braid]]'' |
*[[Douglas Hofstadter]]: ''[[Gödel, Escher, Bach: An Eternal Golden Braid]]'' |
||
*[[Ken Thompson]]: "[http://cm.bell-labs.com/who/ken/trust.html Reflections on Trusting Trust]" (''[[Communications of the ACM]]'', '''27'''(8):761-3) |
*[[Ken Thompson]]: "[http://web.archive.bibalex.org/web/20010702132817/http://cm.bell-labs.com/who/ken/trust.html Reflections on Trusting Trust]" (''[[Communications of the ACM]]'', '''27'''(8):761-3) |
||
==External links== |
==External links== |
||
Revision as of 15:22, 21 July 2016
 |
A quine is a non-empty 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 Turing complete programming language, 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.
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.
In some languages, particularly scripting languages, an empty source file is a fixed point of the language, being a valid program that produces no output.[a] Such an empty program, submitted as "the world's smallest self reproducing program", once won the "worst abuse of the rules" prize in the International Obfuscated C Code Contest.[1]
History
The idea of self-reproducing automata came from the dawn of computing, if not before. John von Neumann himself theorized about them. Later, Paul Bratley and Jean Millo's article "Computer Recreations: Self-Reproducing Automata" discussed them 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 "download source" requirement of the Affero General Public License is based on the idea of a quine.
Examples
A short non-cheating Quine in Perl.[3]
$_=q{print"\$_=q{$_};eval"};eval
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.
class Q{public static void main(String[]a){String f="class Q{public static void main(String[]a){String f=%c%s%1$c;System.out.printf(f,34,f);}}";System.out.printf(f,34,f);}}
The following short Java quine can be compiled at the command line - but it depends on the java VM version, it doesn't work with current JVMs. It makes use of multiple tricks of the Java language, and thus is much harder to read. However, it relies on the same principle of code repetition within string literals.
enum E{A;System s;String t="enum E{A;System s;String t=%c%s%1$c;{s.out.printf(t,34,t);s.exit(0);}}";{s.out.printf(t,34,t);s.exit(0);}}
The following example is in Javascool.
void main(){
String s1="void main(){";
String s2=" println(s1);\n println(\" String s1=\\\"\"+s1.replace(\"\\\\\",\"\\\\\\\\\").replace(\"\\n\",\"\\\\n\").replace(\"\\\"\",\"\\\\\\\"\")+\"\\\";\");\n println(\" String s2=\\\"\"+s2.replace(\"\\\\\",\"\\\\\\\\\").replace(\"\\n\",\"\\\\n\").replace(\"\\\"\",\"\\\\\\\"\")+\"\\\";\");\n println(s2);\n}";
println(s1);
println(" String s1=\""+s1.replace("\\","\\\\").replace("\n","\\n").replace("\"","\\\"")+"\";");
println(" String s2=\""+s2.replace("\\","\\\\").replace("\n","\\n").replace("\"","\\\"")+"\";");
println(s2);
}
The same idea is used in SQL quine:
SELECT REPLACE(REPLACE('SELECT REPLACE(REPLACE("$",CHAR(34),CHAR(39)),CHAR(36),"$") AS Quine',CHAR(34),CHAR(39)),CHAR(36),'SELECT REPLACE(REPLACE("$",CHAR(34),CHAR(39)),CHAR(36),"$") AS Quine') AS Quine
A very concise quine with the same basic structure can be written in Lua:
x = [["x = [" .. "[" .. x .. "]" .. "]\nprint(" .. x)]]
print("x = [" .. "[" .. x .. "]" .. "]\nprint(" .. x)
And in Python:
s = 's = %r\nprint(s%%s)'
print(s%s)
A JavaScript example:
Quine = function () {var str = arguments.callee.toString(); Quine = console.log(str.substring(52, 60) + str +
str.substring(32, 37) + str.substring(9, 11));}.call()
In R:
m<-"m<-0;cat(sub(0,deparse(m),m))";cat(sub(0,deparse(m),m))
In Rust: http://web.archive.org/web/20160508013652/https://play.rust-lang.org/?gist=538739d5b3008dd6edbdc8e2022abb47
fn main() {
let x = "fn main() {\n let x = ";
let y = "print!(\"{}{:?};\n let y = {:?};\n {}\", x, x, y, y)\n}\n";
print!("{}{:?};
let y = {:?};
{}", x, x, y, y)
}
In Go: http://play.golang.org/p/pVBds0oHrO
Quines can take advantage of eval. For example, this Ruby quine:
eval s="print 'eval s=';p s"
"Cheating" quines
Quines, per definition, cannot receive any form of input, including reading a file, which means a quine is considered to be "cheating" if it looks at its own source code. The following shell script is not a quine:
#!/bin/sh
# Invalid quine.
# Reading the executed file from disk is cheating.
cat $0
Nor this succinct use of the Shebang:
#!/bin/cat
The above also applies to this JavaScript code:
function a() {
document.write(a, "a()");
}
a()
In PHP:
<? highlight_file(__FILE__) ?>
A program in the joke language HQ9+ is a quine if and only if the source code consists only of zero or more '+' characters and a single 'Q' character (the 'Q' command prints a quine and '+' prints nothing):
++Q++++++Other questionable techniques include making use of compiler messages; for example, in the GW-BASIC environment, entering "Syntax Error" will cause the interpreter to respond with "Syntax Error". Ignoring the restriction that quines be non-empty, there are many examples of programming languages where an empty program is valid (such as C). Such programs generally do nothing, in effect, reproducing the program.
Ouroboros programs
The quine concept can be extended to multiple levels or recursion, originating what has been called[by whom?] "ouroboros programs", or quine-relays. This should not be confused with Multiquines.
Example
This Java program outputs the source for a C++ program that outputs the original Java code.
#include <iostream>
#include <string>
using namespace std;
int main(int argc, char* argv[])
{
char q = 34;
string l[] = {
" ",
"=============<<<<<<<< C++ Code >>>>>>>>=============",
"#include <iostream>",
"#include <string>",
"using namespace std;",
"",
"int main(int argc, char* argv[])",
"{",
" char q = 34;",
" string l[] = {",
" };",
" for(int i = 20; i <= 25; i++)",
" cout << l[i] << endl;",
" for(int i = 0; i <= 34; i++)",
" cout << l[0] + q + l[i] + q + ',' << endl;",
" for(int i = 26; i <= 34; 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 <= 9; 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 = 10; i <= 18; i++)",
" System.out.println(l[i]);",
" }",
"}",
};
for(int i = 20; i <= 25; i++)
cout << l[i] << endl;
for(int i = 0; i <= 34; i++)
cout << l[0] + q + l[i] + q + ',' << endl;
for(int i = 26; i <= 34; i++)
cout << l[i] << endl;
return 0;
}
public class Quine
{
public static void main(String[] args)
{
char q = 34;
String[] l = {
" ",
"=============<<<<<<<< C++ Code >>>>>>>>=============",
"#include <iostream>",
"#include <string>",
"using namespace std;",
"",
"int main(int argc, char* argv[])",
"{",
" char q = 34;",
" string l[] = {",
" };",
" for(int i = 20; i <= 25; i++)",
" cout << l[i] << endl;",
" for(int i = 0; i <= 34; i++)",
" cout << l[0] + q + l[i] + q + ',' << endl;",
" for(int i = 26; i <= 34; 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 <= 9; 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 = 10; i <= 18; i++))",
" System.out.println(l[i]);",
" }",
"}",
};
for(int i = 2; i <= 9; 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 = 10; i <= 18; i++)
System.out.println(l[i]);
}
}
Such programs have been produced with various cycle lengths:
- Haskell → Python → Ruby[4]
- Python → Bash → Perl[5]
- C → Haskell → Python → Perl[6]
- Haskell → Perl → Python → Ruby → C → Java[7]
- Ruby → Java → C# → Python[8]
- C → C++ → Ruby → Python → PHP → Perl[9]
- Ruby → Python → Perl → Lua → OCaml → Haskell → C → Java → Brainfuck → Whitespace → Unlambda[10]
- Ruby → Scala → Scheme → … → Rexx (100 programming languages)[11]
Multiquines
David Madore, creator of Unlambda, describes multiquines as follows:[12]
"A multiquine is a set of r different programs (in r different languages — without this condition we could take them all equal to a single quine), each of which is able to print any of the r programs (including itself) according to the command line argument it is passed. (Note that cheating is not allowed: the command line arguments must not be too long — passing the full text of a program is considered cheating)."
A multiquine consisting of 2 languages (or biquine) would be a program which:
- When run, is a quine in language X.
- When supplied with a user-defined command line argument, would print a second program in language Y.
- Given the second program in language Y, when run normally, would also be a quine in language Y.
- Given the second program in language Y, and supplied with a user-defined command line argument, would produce the original program in language X.
A biquine could then be seen as a set of two programs, both of which are able to print either of the two, depending on the command line argument supplied.
Theoretically, there is no limit on the number of languages in a multiquine, a 5-part multiquine (or pentaquine) has been produced with Python, Perl, C, NewLISP, and F#[13] and there is also a 25-language multiquine.[14]
Radiation-hardened
A radiation-hardened quine is a quine that can have any single character removed and still produce the original program with no missing character. Of necessity, such quines are much more convoluted than ordinary quines, as is seen by the following example in Ruby:[15]
eval='eval$q=%q(puts %q(10210/#{1 1 if 1==21}}/.i rescue##/
1 1"[13,213].max_by{|s|s.size}#"##").gsub(/\d/){["=\47eval$q=%q(#$q)#\47##\47
",:eval,:instance_,"||=9"][eval$&]}
exit)#'##'
instance_eval='eval$q=%q(puts %q(10210/#{1 1 if 1==21}}/.i rescue##/
1 1"[13,213].max_by{|s|s.size}#"##").gsub(/\d/){["=\47eval$q=%q(#$q)#\47##\47
",:eval,:instance_,"||=9"][eval$&]}
exit)#'##'
/#{eval eval if eval==instance_eval}}/.i rescue##/
eval eval"[eval||=9,instance_eval||=9].max_by{|s|s.size}#"##"
See also
Notes
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. doi:10.1002/spe.4380020411.
- ^ [1]
- ^ Dan Piponi (5 February 2008). "A Third Order Quine in Three Languages".
- ^ Bruce Ediger. "Ask and ye shall receive: Self-replicating program that goes through three generations, Python, Bash, Perl".
- ^ b.m. (1 February 2011). "multiquine". Archived from the original on 2013-04-15.
- ^ Dan Piponi (30 January 2011). "Quine Central".
- ^ Ruslan Ibragimov (20 April 2013). "Quine Ruby -> Java -> C# -> Python" (in Russian).
- ^ Shinichiro Hamaji (10 November 2007). "Quine by shinh (C C++ Ruby Python PHP Perl)". (this one is also a polyglot)
- ^ Ku-ma-me (22 September 2009). "Uroboros Programming With 11 Programming Languages".
- ^ Yusuke Endoh. "Quine Relay - An uroboros program with 100 programming languages".
- ^ David Madore. "Quines (self-replicating programs)".
- ^ Rijnard van Tonder. "Pentaquine - 5 part multiquine".
- ^ Lu Wang. "Quine Chameleon#Variants".
- ^ Yusuke Endoh. "Radiation-hardened Quine". Retrieved 2014-02-24.
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
- TiddlyWiki, a quine manifested as a wiki
- The Quine Page (by Gary P. Thompson)
- QuineProgram at the Portland Pattern Repository Wiki
- David Madore's Discussion of Quines
- Zip File Quine
- 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
- A Java Quine built straight from Kleene's fixed point theorem, composition and s-n-m
- A QR code quine
- Stylish, valid quine with syntax highlighting: A CSS-valid HTML quine
- "Quine palindrome": A web page that "is the same as its source, the same from left to right as from right to left, the same from top to bottom as from bottom to top."