FACTOID # 11: Oklahoma has the highest rate of women in State or Federal correctional facilities.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Quine (computing)

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. RAM (Random Access Memory) Look up computing in Wiktionary, the free dictionary. ... A computer program is a collection of instructions that describe a task, or set of tasks, to be carried out by a computer. ... Metaprogramming is the writing of computer programs that write or manipulate other programs (or themselves) as their data or that do part of the work during compile time that is otherwise done at run time. ... Source code (commonly just source or code) is any series of statements written in some human-readable computer programming language. ... A programming language is an artificial language that can be used to control the behavior of a machine, particularly a computer. ...


Note that programs that 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 that 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. The International Obfuscated C Code Contest (abbr. ...


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." For people named Quine, see Quine (surname). ... ... Quines paradox is a paradox concerning truth values, attributed to W. V. O. Quine. ...

Contents

History

A quine exists in any programming language that 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: In computability theory Kleenes recursion theorem, first proved by Stephen Kleene in 1938, is a fundamental result about the application of computable functions to their own descriptions. ... Atlas Autocode (AA) was a programming language developed at Manchester University for the Atlas Computer. ... The University of Edinburgh (Scottish Gaelic: ), founded in 1582,[4] is a renowned centre for teaching and research in Edinburgh, Scotland. ...

 %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 

Examples

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 (e.g., progdata in the first C example below). 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 (e.g., quote() below) to print the textual representation of the data itself. There are many ways the code and the data can be organized together within the program (neither must be contiguous), but a common telltale sign of the data section is that it mirrors some part of the entire program. Source code (commonly just source or code) is any series of statements written in some human-readable computer programming language. ... For other uses, see Data (disambiguation). ...


An example in colloquial english would be:

 "quoted and followed by itself is a quine." quoted and followed by itself is a quine. 

(from http://spikeypillow.com/item/31)


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. C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ...

 /* 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 (formatted as per the 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. */nn/* Note: in designing this quine, " "we have tried to make the code clearn * and read" "able, not concise and obscure as many quines are" ", so thatn * 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 ownn * textual representation" ". */nn#include <stdio.h>nnvoid quote(const char " "*s)n /* This function takes a character stri" "ng s and prints then * textual representati" "on of s as it might appear formattedn * in " "C code. */n{n int i;nn printf(" "");n " " for (i=0; s[i]; ++i) {n /* Certain cha" "racters are quoted. */n if (s[i] == '')" "n printf("");n else if (s[" "i] == '"')n printf(""");n e" "lse if (s[i] == 'n')n printf("n");" "n /* Others are just printed as such. */n" " elsen printf("%c", s[i]);n " " /* Also insert occasional line breaks. */n " " if (i % 48 == 47)n printf(""" "n "");n }n printf(""");n}nn/* What fo" "llows is a string representation of the program " "code,n * from beginning to end (formatted as per" " the quote() functionn * above), except that the" " string _itself_ is coded as twon * consecutive " "'@' characters. */nconst char progdata[] =n@@;nn" "int main(void)n /* The program itself... */n" "{n int i;nn /* Print the program code, cha" "racter by character. */n for (i=0; progdata[i" "]; ++i) {n if (progdata[i] == '@' && prog" "data[i+1] == '@')n /* We encounter tw" "o '@' signs, so we must print the quotedn " " * form of the program code. */n {n " " quote(progdata); /* Quote all. */n" " i++; /* Skip second '" "@'. */n } elsen printf("%c", p" "rogdata[i]); /* Print character. */n }n r" "eturn 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; } 

An alternative approach in C would be to make use of the C pre-processor. For example:

 #include <stdio.h> int main(int argc, char** argv) { #define B(x) x; printf(" B(" #x ")n"); #define A(x) printf(" A(" #x ")n"); x; B(printf("#include <stdio.h>nint main(int argc, char** argv)n{n#define B(x) x; printf(" B(" #x ")n");n#define A(x) printf(" A(" #x ")n"); x;n")) A(printf("}n")) } 

Note that in the above, the line beginning with B(printf( would be one line; there is exactly one space between the string argv)n{n#define B(x) and the symbol x; it is broken as two lines so that it does not overflow the screen.


An even shorter approach in C avoids the preprocessor and instead exploits the printf function, passing a carefully-constructed string as both the format string and a substitution parameter. Note: 34 is the ASCII code for a double-quote character, and is used to avoid the need to quote the double-quotes in the string literal.

 int main() { char *s = "int main() { char *s = %c%s%c; printf(s, 34, s, 34); }"; printf(s, 34, s, 34); } 

Scheme (also valid Common Lisp)

This quine works by feeding the program to itself, which then converts the data structure to source code. Scheme is a multi-paradigm programming language. ... Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard X3. ...

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

JavaScript

In JavaScript you can get the source code for any function by converting it to a string: It has been suggested that Client-side JavaScript be merged into this article or section. ...

 window.onload = function() { document.body.appendChild(document.createTextNode(window.onload.toSource().replace(/.*?{(.*)}.*/, "window.onload = function() { $1 }"))); } 

See also

“Programming” redirects here. ... A self-interpreter (frequently called meta-circular interpreter or meta-interpreter) is a programming language interpreter written in the language it interprets. ... Self-replication is the process by which some things make copies of themselves. ... A simple form of machine self-replication The concept of self-replicating machines has been most notably advanced and examined by, Homer Jacobsen, Edward F. Moore, Freeman Dyson, John von Neumann and in more recent times notably K. Eric Drexler in his seminal book on nanotechnology, Engines of Creation. ... There are a lot of kinds of listing. ... In mathematical logic, Gödels diagonal lemma is a precise way of constructing self-referential statements. ... Obfuscated code is source code that is (usually intentionally) very hard to read and understand. ...

Further reading

Douglas Richard Hofstadter (born February 15, 1945 in New York, New York) is an American academic. ... Kenneth Thompson redirects here. ... Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery. ...

External links

  • Tupper's Self-Referential Formula
  • The Quine Page (by Gary P. Thompson)
  • QuineProgram at the Portland Pattern Repository Wiki
  • David Madore's Discussion of Quines
  • JavaScript Quine Contest Entries

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m