Quine (computing)

From Wikipedia, the free encyclopedia

You have new messages (last change).

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

Contents

[edit] History

A quine exists in any programming language which has 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

The idea behind this quine is to store a copy of the program code in a string, and use that to print out both the program code and the string.

main(a){a="main(a){a=%c%s%c;printf(a,34,a,34);}";printf(a,34,a,34);}

[edit] Scheme (also valid Common Lisp)

This quine works by feeding the program to itself, which then converts the data structure to source code.

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

[edit] JavaScript

In JavaScript you can get the source code for any function by converting it to a string:

function a() { document.write (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.

[edit] See also

[edit] Further reading

[edit] External links

Retrieved from "http://en.wikipedia.org../../../q/u/i/Quine_%28computing%29.html"