Quine (computing)

Last updated
A quine's output is exactly the same as its source code (the syntax highlighting demonstrated by the text editor in the upper half of the image does not affect the output of the quine). Java implementation of a quine program.png
A quine's output is exactly the same as its source code (the syntax highlighting demonstrated by the text editor in the upper half of the image does not affect the output of the quine).

A quine is a computer program that 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".

Contents

A quine is a fixed point of an execution environment, when that environment is viewed as a function transforming programs into their outputs. 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.

Name

The name "quine" was coined by Douglas Hofstadter, in his popular science book Gödel, Escher, Bach , in 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.

History

The idea of self-reproducing automata came from the dawn of computing, if not before. John von Neumann theorized about them in the 1940s. Later, Paul Bratley and Jean Millo's article "Computer Recreations: Self-Reproducing Automata" discussed them in 1972. [1] 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.

The "download source" requirement of the GNU Affero General Public License is based on the idea of a quine. [2]

Examples

Constructive quines

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. 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, to print the textual representation of the data itself.

Here are three small examples in Python 3:

# Example A. chr(39) == "'".a='a = {}{}{}; print(a.format(chr(39), a, chr(39)))';print(a.format(chr(39),a,chr(39)))
# Example B. chr(39) == "'".b='b = %s%s%s; print(b %% (chr(39), b, chr(39)))';print(b%(chr(39),b,chr(39)))
# Example C. %r will quote automatically.c='c = %r; print(c %% c)';print(c%c)

The following Java code demonstrates the basic structure of a quine.

publicclassQuine{publicstaticvoidmain(String[]args){charq=34;// Quotation mark characterString[]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(inti=0;i<6;i++)// Print opening codeSystem.out.println(l[i]);for(inti=0;i<l.length;i++)// Print string arraySystem.out.println(l[6]+q+l[i]+q+',');for(inti=7;i<l.length;i++)// Print this codeSystem.out.println(l[i]);}}

The source code contains a string array of itself, which is output twice, once inside quotation marks.

This code was adapted from an original post from c2.com, where the author, Jason Wilson, posted it as a minimalistic version of a Quine, without Java comments. [3]

Thanks to new text blocks feature in Java 15 (or newer), a more readable and simpler version is possible: [4] 

publicclassQuine{publicstaticvoidmain(String[]args){StringtextBlockQuotes=newString(newchar[]{'"','"','"'});charnewLine=10;Stringsource="""public class Quine { public static void main(String[] args) {  String textBlockQuotes = new String(new char[]{'"', '"', '"'});  char newLine = 10;  String source = %s;  System.out.print(source.formatted(textBlockQuotes + newLine + source + textBlockQuotes)); }}""";System.out.print(source.formatted(textBlockQuotes+newLine+source+textBlockQuotes));}}

Eval quines

Some programming languages have the ability to evaluate a string as a program. Quines can take advantage of this feature. For example, this Ruby quine:

evals="print 'eval s=';p s"

Lua can do:

s="print(string.format('s=%c%s%c; load(s)()',34,s,34))";load(s)()

In Python 3.8:

exec(s:='print("exec(s:=%r)"%s)')

"Cheating" quines

Self-evaluation

In many functional languages, including Scheme and other Lisps, and interactive languages such as APL, numbers are self-evaluating. In TI-BASIC, if the last line of a program returns a value, the returned value is displayed on the screen. Therefore, in such languages a program consisting of only a single digit results in a 1-byte quine. Since such code does not construct itself, this is often considered cheating.

1


In some languages, particularly scripting languages but also C, an empty source file is a fixed point of the language, being a valid program that produces no output. [lower-alpha 1] 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. [5] The program was not actually compiled, but used cp to copy the file into another file, which could be executed to print nothing. [6]

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".

Source code inspection

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

A shorter variant, exploiting the behaviour of shebang directives:

#!/bin/cat

Empty quines

In some programming languages, an empty source file is a valid program that produces no output. Calling such an empty file a quine is often considered cheating.

Ouroboros programs

The quine concept can be extended to multiple levels of recursion, giving rise to "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>usingnamespacestd;intmain(intargc,char*argv[]){charq=34;stringl[]={"    ","=============<<<<<<<< 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(inti=20;i<=25;i++)cout<<l[i]<<endl;for(inti=0;i<=34;i++)cout<<l[0]+q+l[i]+q+','<<endl;for(inti=26;i<=34;i++)cout<<l[i]<<endl;return0;}
publicclassQuine{publicstaticvoidmain(String[]args){charq=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(inti=2;i<=9;i++)System.out.println(l[i]);for(inti=0;i<l.length;i++)System.out.println(l[0]+q+l[i]+q+',');for(inti=10;i<=18;i++)System.out.println(l[i]);}}

Such programs have been produced with various cycle lengths:

Multiquines

David Madore, creator of Unlambda, describes multiquines as follows: [16]

"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. (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:

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# [17] and there is also a 25-language multiquine. [18]

Polyglot

Similar to, but unlike a multiquine, a polyglot program is a computer program or script written in a valid form of multiple programming languages or file formats by combining their syntax. A polyglot program is not required to have a self-reproducing quality, although a polyglot program can also be a quine in one or more of its possible ways to execute.

Unlike quines and multiquines, polyglot programs are not guaranteed to exist between arbitrary sets of languages as a result of Kleene's recursion theorem, because they rely on the interplay between the syntaxes, and not a provable property that one can always be embedded within another.

Radiation-hardened

A radiation-hardened quine is a quine that can have any single character removed and still produces 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: [19] 

eval='eval$q=%q(puts %q(10210/#{11if1==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/#{11if1==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)#'##'/#{evalevalifeval==instance_eval}}/.irescue##/evaleval"[eval||=9,instance_eval||=9].max_by{|s|s.size}#"##"

Automatic generation

Using relational programming techniques, it is possible to generate quines automatically by transforming the interpreter (or equivalently, the compiler and runtime) of a language into a relational program, and then solving for a fixed point. [20]

See also

Notes

  1. ↑ Examples include Bash, Perl, and Python

Related Research Articles

In computer programming, lazy initialization is the tactic of delaying the creation of an object, the calculation of a value, or some other expensive process until the first time it is needed. It is a kind of lazy evaluation that refers specifically to the instantiation of objects or other resources.

In object-oriented programming, the decorator pattern is a design pattern that allows behavior to be added to an individual object, dynamically, without affecting the behavior of other instances of the same class. The decorator pattern is often useful for adhering to the Single Responsibility Principle, as it allows functionality to be divided between classes with unique areas of concern as well as to the Open-Closed Principle, by allowing the functionality of a class to be extended without being modified. Decorator use can be more efficient than subclassing, because an object's behavior can be augmented without defining an entirely new object.

A string literal or anonymous string is a literal for a string value in the source code of a computer program. Modern programming languages commonly use a quoted sequence of characters, formally "bracketed delimiters", as in x = "foo", where "foo" is a string literal with value foo. Methods such as escape sequences can be used to avoid the problem of delimiter collision and allow the delimiters to be embedded in a string. There are many alternate notations for specifying string literals especially in complicated cases. The exact notation depends on the programming language in question. Nevertheless, there are general guidelines that most modern programming languages follow.

In mathematics and computer science, a higher-order function (HOF) is a function that does at least one of the following:

In computer science, primitive data types are a set of basic data types from which all other data types are constructed. Specifically it often refers to the limited set of data representations in use by a particular processor, which all compiled programs must use. Most processors support a similar set of primitive data types, although the specific representations vary. More generally, "primitive data types" may refer to the standard data types built into a programming language. Data types which are not primitive are referred to as derived or composite.

In computing, type introspection is the ability of a program to examine the type or properties of an object at runtime. Some programming languages possess this capability.

Metaprogramming is a programming technique in which computer programs have the ability to treat other programs as their data. It means that a program can be designed to read, generate, analyse or transform other programs, and even modify itself while running. In some cases, this allows programmers to minimize the number of lines of code to express a solution, in turn reducing development time. It also allows programs a greater flexibility to efficiently handle new situations without recompilation.

In computer programming, a function object is a construct allowing an object to be invoked or called as if it were an ordinary function, usually with the same syntax. In some languages, particularly C++, function objects are often called functors.

In computer science, a generator is a routine that can be used to control the iteration behaviour of a loop. All generators are also iterators. A generator is very similar to a function that returns an array, in that a generator has parameters, can be called, and generates a sequence of values. However, instead of building an array containing all the values and returning them all at once, a generator yields the values one at a time, which requires less memory and allows the caller to get started processing the first few values immediately. In short, a generator looks like a function but behaves like an iterator.

<span class="mw-page-title-main">Foreach loop</span> Control flow statement for traversing items in a collection

In computer programming, foreach loop is a control flow statement for traversing items in a collection. foreach is usually used in place of a standard for loop statement. Unlike other for loop constructs, however, foreach loops usually maintain no explicit counter: they essentially say "do this to everything in this set", rather than "do this x times". This avoids potential off-by-one errors and makes code simpler to read. In object-oriented languages, an iterator, even if implicit, is often used as the means of traversal.

In computer programming, a callback or callback function is any reference to executable code that is passed as an argument to another piece of code; that code is expected to call back (execute) the callback function as part of its job. This execution may be immediate as in a synchronous callback, or it might happen at a later point in time as in an asynchronous callback. They are also called blocking and non-blocking.

<span class="mw-page-title-main">Method overriding</span> Language feature in object-oriented programming

Method overriding, in object-oriented programming, is a language feature that allows a subclass or child class to provide a specific implementation of a method that is already provided by one of its superclasses or parent classes. In addition to providing data-driven algorithm-determined parameters across virtual network interfaces, it also allows for a specific type of polymorphism (subtyping). The implementation in the subclass overrides (replaces) the implementation in the superclass by providing a method that has same name, same parameters or signature, and same return type as the method in the parent class. The version of a method that is executed will be determined by the object that is used to invoke it. If an object of a parent class is used to invoke the method, then the version in the parent class will be executed, but if an object of the subclass is used to invoke the method, then the version in the child class will be executed. This helps in preventing problems associated with differential relay analytics which would otherwise rely on a framework in which method overriding might be obviated. Some languages allow a programmer to prevent a method from being overridden.

In computer programming, an entry point is the place in a program where the execution of a program begins, and where the program has access to command line arguments.

In mathematics and in computer programming, a variadic function is a function of indefinite arity, i.e., one which accepts a variable number of arguments. Support for variadic functions differs widely among programming languages.

String functions are used in computer programming languages to manipulate a string or query information about a string.

In number theory, a narcissistic number in a given number base is a number that is the sum of its own digits each raised to the power of the number of digits.

In computer programming, an anonymous function is a function definition that is not bound to an identifier. Anonymous functions are often arguments being passed to higher-order functions or used for constructing the result of a higher-order function that needs to return a function. If the function is only used once, or a limited number of times, an anonymous function may be syntactically lighter than using a named function. Anonymous functions are ubiquitous in functional programming languages and other languages with first-class functions, where they fulfil the same role for the function type as literals do for other data types.

In computer programming, variable shadowing occurs when a variable declared within a certain scope has the same name as a variable declared in an outer scope. At the level of identifiers, this is known as name masking. This outer variable is said to be shadowed by the inner variable, while the inner identifier is said to mask the outer identifier. This can lead to confusion, as it may be unclear which variable subsequent uses of the shadowed variable name refer to, which depends on the name resolution rules of the language.

Different command-line argument parsing methods are used by different programming languages to parse command-line arguments.

In computer programming, string interpolation is the process of evaluating a string literal containing one or more placeholders, yielding a result in which the placeholders are replaced with their corresponding values. It is a form of simple template processing or, in formal terms, a form of quasi-quotation. The placeholder may be a variable name, or in some languages an arbitrary expression, in either case evaluated in the current context.

References

  1. ↑ Bratley, Paul; Millo, Jean (1972). "Computer Recreations: Self-Reproducing Automata". Software: Practice and Experience. 2 (4): 397–400. doi:10.1002/spe.4380020411. S2CID   222194376.
  2. ↑ Kuhn, Bradley M. (November 21, 2007). "stet and AGPLv3". Software Freedom Law Center. Archived from the original on March 15, 2008. Retrieved June 14, 2008.
  3. ↑ "Quine Program". wiki.c2.com.
  4. ↑ "Simple Java quine, self replicating (Self copying) Java code, with text blocks. This code can be run with Java 15+ or Java 13+ with special flags. License is public domain, no rights reserved".
  5. ↑ "IOCCC 1994 Worst Abuse of the Rules". Archived from the original on 12 November 2020.
  6. ↑ "Makefile". IOCCC.org. Archived from the original on 23 April 2019. Retrieved 4 April 2019.
  7. ↑ Dan Piponi (5 February 2008). "A Third Order Quine in Three Languages".
  8. ↑ Bruce Ediger. "Ask and ye shall receive: Self-replicating program that goes through three generations, Python, Bash, Perl". Archived from the original on 2011-02-23. Retrieved 2011-03-17.
  9. ↑ b.m. (1 February 2011). "multiquine". Archived from the original on 2013-04-15.
  10. ↑ Dan Piponi (30 January 2011). "Quine Central".
  11. ↑ Ruslan Ibragimov (20 April 2013). "Quine Ruby -> Java -> C# -> Python" (in Russian). Archived from the original on 4 March 2016. Retrieved 20 April 2013.
  12. ↑ Shinichiro Hamaji (10 November 2007). "Quine by shinh (C C++ Ruby Python PHP Perl)". (this one is also a polyglot)
  13. ↑ Ku-ma-me (22 September 2009). "Uroboros Programming With 11 Programming Languages". Archived from the original on 29 August 2011. Retrieved 17 March 2011.
  14. ↑ Yusuke Endoh (2 November 2021). "Quine Relay - An uroboros program with 100+ programming languages". GitHub .
  15. ↑ Michael Wehar (10 November 2019). "C Prints JavaScript".
  16. ↑ David Madore. "Quines (self-replicating programs)".
  17. ↑ Rijnard van Tonder (14 January 2020). "Pentaquine - 5 part multiquine". GitHub .
  18. ↑ Lu Wang (21 May 2021). "Quine Chameleon#Variants". GitHub .
  19. ↑ Yusuke Endoh. "Radiation-hardened Quine". GitHub . Retrieved 2014-02-24.
  20. ↑ Byrd, William E.; Holk, Eric; Friedman, Daniel P. (2012-09-09). "miniKanren, live and untagged: quine generation via relational interpreters (programming pearl)" (PDF). Proceedings of the 2012 Annual Workshop on Scheme and Functional Programming. Scheme '12. New York, NY, USA: Association for Computing Machinery: 8–29. doi:10.1145/2661103.2661105. ISBN   978-1-4503-1895-2.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.