Quine (computing)

From Wikipedia, the free encyclopedia

In computing, a quine is a program (a form of metaprogram) that produces its complete source code as its only output. For amusement, programmers sometimes attempt to develop the shortest possible quine in any given programming language.

Note that programs which take input are not considered quines. This would allow the source code to be fed to the program via keyboard input, opening the source file of the program, and similar mechanisms. Also, a quine which contains no code is ruled out as trivial; in many programming languages executing such a program will output the code (i.e. nothing). Such an empty program once won the "worst abuse of the rules" prize in the Obfuscated C contest.

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

1 History
2 Examples
3 Philosophical usage
4 See also
5 Further reading
6 External links

[edit] History

A quine exists in any programming language with the ability to output any computable string, as a direct consequence of Kleene's recursion theorem. The specific idea of quines 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

[edit] C

/* 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 (formated as per 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 in C\n      "
    "* code. */\n{\n    int i;\n\n    printf(\"    \\\"\");\n "
    "   for (i = 0; s[i]; i++) {\n        /* Certain c"
    "haracters are quoted. */\n        if (s[i] == '\\\\"
    "')\n            printf(\"\\\\\\\\\");\n        else if ("
    "s[i] == '\"')\n            printf(\"\\\\\\\"\");\n       "
    " else 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 "
    "follows is a string representation of the progra"
    "m code, from\n * beginning to end (formated as pe"
    "r quote() function, above), except\n * that the s"
    "tring _itself_ is coded as two consecutive '@'\n "
    "* characters. */\nconst char progdata[] =\n@@;\n\nin"
    "t main(void)\n     /* The program itself... */\n{\n"
    "    int i;\n\n    /* Print the program code, chara"
    "cter by character. */\n    for (i = 0; progdata[i"
    "]; i++) {\n        if (progdata[i] == '@' && prog"
    "data[i + 1] == '@')\n            /* We encounter "
    "two '@' 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\","
    " progdata[i]);  /* Print character. */\n    }\n   "
    " return 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;
}

[edit] Scheme (also correct Common Lisp)

   ((lambda (x)
           (list x (list (quote quote) x)))
       (quote
           (lambda (x)
               (list x (list (quote quote) x)))))

[edit] JavaScript

function a() { alert (a + "\na();"); }
a();

[edit] Philosophical usage

In the satirical dictionary The Philosophical Lexicon, the word was used in jest to mean "To deny resolutely the existence or importance of something real or significant." Since then, the word has been used seriously in many papers to denote the proposed elimination (or reduction) of a thing or concept.