Quine (computing)


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:

See also

References

Further reading

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Quine — may refer to: * Willard Van Orman Quine American philosopher and logician * Robert Quine American guitarist * Quine (computing), a program that produces its source code as output * Quine (surname), people with the surname Quine * Quine–McCluskey… …   Wikipedia

  • Willard Van Orman Quine — Unreferenced|date=August 2007 Infobox Philosopher region = Western Philosophy era = 20th century philosophy color = #B0C4DE image caption = Willard Van Orman Quine name = Willard Van Orman Quine birth = birth date|mf=yes|1908|6|25 death = death… …   Wikipedia

  • Indirect self-reference — describes an object referring to itself indirectly .For example, define the function f such that f(x) = x(x) . Any function passed as an argument to f is invoked with itself as an argument, and thus in any use of that argument is indirectly… …   Wikipedia

  • Self-modifying code — In computer science, self modifying code is code that alters its own instructions, intentionally or otherwise, while it is executing.Self modifying code is quite straightforward to write when using assembly language (taking into account the CPU… …   Wikipedia

  • Self-interpreter — A self interpreter, or metainterpreter, is a programming language interpreter written in the language it interprets. An example would be a BASIC interpreter written in BASIC. Conceptually, self interpreters are closely related to self hosting… …   Wikipedia

  • Von Neumann universal constructor — John von Neumann s Universal Constructor is a self replicating machine in a cellular automata environment. It was designed in the 1940s, without the use of a computer. The fundamental details of the machine were published in von Neumann s book… …   Wikipedia

  • Function (mathematics) — f(x) redirects here. For the band, see f(x) (band). Graph of example function, In mathematics, a function associates one quantity, the a …   Wikipedia

  • Hilary Putnam — Infobox Philosopher region = Western Philosophy era = 20th century philosophy color = #B0C4DE name = Hilary Whitehall Putnam birth = July 31, 1926 flagicon|USA|size=20px Chicago, Illinois school tradition = Analytic main interests = Philosophy of …   Wikipedia

  • Combinatory logic — Not to be confused with combinational logic, a topic in digital electronics. Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It has more recently been… …   Wikipedia

  • language, philosophy of — Philosophical study of the nature and use of natural languages and the relations between language, language users, and the world. It encompasses the philosophical study of linguistic meaning (see semantics), the philosophical study of language… …   Universalium


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.