
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
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...
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 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.
The name "quine" was coined by
Douglas Hofstadter
Douglas Richard Hofstadter (born February 15, 1945) is an American scholar of cognitive science, physics, and comparative literature whose research includes concepts such as the sense of self in relation to the external world, consciousness, an ...
, in his popular science book ''
Gödel, Escher, Bach
''Gödel, Escher, Bach: an Eternal Golden Braid'', also known as ''GEB'', is a 1979 book by Douglas Hofstadter.
By exploring common themes in the lives and works of logician Kurt Gödel, artist M. C. Escher, and composer Johann Sebastian Bach, t ...
'', 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
Paul may refer to:
*Paul (given name), a given name (includes a list of people with that name)
*Paul (surname), a list of people
People
Christianity
*Paul the Apostle (AD c.5–c.64/65), also known as Saul of Tarsus or Saint Paul, early Chris ...
and Jean Millo's article "Computer Recreations: Self-Reproducing Automata" discussed them in 1972.
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
Hamish is a Scottish masculine given name. It is the anglicized form of the vocative case of the Gaelic name ''Seamus'' or ''Sheumais''. It is therefore, the equivalent of James.
People Given name
* Hamish Bennett, retired New Zealand crickete ...
.
The "download source" requirement of the
Affero General Public License is based on the idea of a quine.
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
In communications and information processing, code is a system of rules to convert information—such as a letter, word, sound, image, or gesture—into another form, sometimes shortened or secret, for communication through a communication ...
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. Note that chr(39) "'".
a = 'a = ; print(a.format(chr(39), a, chr(39)))'; print(a.format(chr(39), a, chr(39)))
# Example B. Note that chr(39) "'".
b = 'b = %s%s%s; print(b %% (chr(39), b, chr(39)))'; print(b % (chr(39), b, chr(39)))
# Example C. Note that %r will quote automatically.
c = 'c = %r; print(c %% c)'; print(c % c)
The following
Java code demonstrates the basic structure of a quine.
public class Quine
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.
Thanks to ne
text blocksfeature in Java 15 (or newer), a more readable and simpler version is possible:
public class Quine
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:
eval s="print 'eval s=';p s"
Lua
Lua or LUA may refer to:
Science and technology
* Lua (programming language)
* Latvia University of Agriculture
* Last universal ancestor, in evolution
Ethnicity and language
* Lua people, of Laos
* Lawa people, of Thailand sometimes referred t ...
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. 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. The program was not actually compiled, but used
cp
to copy the file into another file, which could be executed to print nothing.
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
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
#include
using namespace std;
int main(int argc, char* argv[])
public class Quine
Such programs have been produced with various cycle lengths:
*
Haskell →
Python →
Ruby
*
Python →
Bash →
Perl
*
C →
Haskell →
Python →
Perl
*
Haskell →
Perl →
Python →
Ruby →
C →
Java
*
Ruby →
Java →
C# →
Python
*
C →
C++ →
Ruby →
Python →
PHP →
Perl
*
Ruby →
Python →
Perl →
Lua
Lua or LUA may refer to:
Science and technology
* Lua (programming language)
* Latvia University of Agriculture
* Last universal ancestor, in evolution
Ethnicity and language
* Lua people, of Laos
* Lawa people, of Thailand sometimes referred t ...
→
OCaml
OCaml ( , formerly Objective Caml) is a general-purpose programming language, general-purpose, multi-paradigm programming language which extends the Caml dialect of ML (programming language), ML with object-oriented programming, object-oriented ...
→
Haskell →
C →
Java →
Brainfuck →
Whitespace
White space or whitespace may refer to:
Technology
* Whitespace characters, characters in computing that represent horizontal or vertical space
* White spaces (radio), allocated but locally unused radio frequencies
* TV White Space Database, a mec ...
→
Unlambda
*
Ruby →
Scala →
Scheme →
Scilab
Scilab is a free and open-source, cross-platform numerical computational package and a high-level, numerically oriented programming language. It can be used for signal processing, statistical analysis, image enhancement, fluid dynamics simulat ...
→
Shell (bash) →
S-Lang
The S-Lang programming library is a software library for Unix, Windows, VMS, OS/2, and Mac OS X. It provides routines for embedding an interpreter for the S-Lang scripting language, and components to facilitate the creation of text-based applic ...
→
Smalltalk
Smalltalk is an object-oriented, dynamically typed reflective programming language. It was designed and created in part for educational use, specifically for constructionist learning, at the Learning Research Group (LRG) of Xerox PARC by Alan Ka ...
→
Squirrel3 →
Standard ML
Standard ML (SML) is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of the ...
→ ... →
Rexx
Rexx (Restructured Extended Executor) is a programming language that can be interpreted or compiled. It was developed at IBM by Mike Cowlishaw. It is a structured, high-level programming language designed for ease of learning and reading. ...
(128 (and formerly 50) programming languages)
* Web application →
C (web application source code consists of
HTML,
JavaScript, and
CSS
Cascading Style Sheets (CSS) is a style sheet language used for describing the presentation of a document written in a markup language such as HTML or XML (including XML dialects such as SVG, MathML or XHTML). CSS is a cornerstone techno ...
)
Multiquines
David Madore, creator of
Unlambda, describes multiquines as follows:
"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. (Note that 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:
* When run, is a quine in language X.
* When supplied with a user-defined command line argument, would print a second program in language Y.
* Given the second program in language Y, when run normally, would also be a quine in language Y.
* Given the second program in language Y, and supplied with a user-defined command line argument, would produce the original program in language X.
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#
and there is also a 25-language multiquine.
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:
eval='eval$q=%q(puts %q(10210/#}/.i rescue##/
1 1" 3,213max_by#"##").gsub(/\d/)
exit)#'##'
instance_eval='eval$q=%q(puts %q(10210/#}/.i rescue##/
1 1" 3,213max_by#"##").gsub(/\d/)
exit)#'##'
/#}/.i rescue##/
eval eval" , =9,instance_eval, , =9max_by#"##"
See also
*
Diagonal lemma
*
Droste effect
The Droste effect (), known in art as an example of ''mise en abyme'', is the effect of a picture recursively appearing within itself, in a place where a similar picture would realistically be expected to appear. This produces a loop which in ...
*
Fixed point combinator
*
Self-modifying code
*
Self-interpreter
*
Self-replicating machine
*
Self-replication
*
Self-relocation
In computer programming, a self-relocating program is a program that relocates its own address-dependent instructions and data when run, and is therefore capable of being loaded into memory at any address. In many cases, self-relocating code is ...
*
TiddlyWiki
*
Tupper's self-referential formula
*
Programming languages
*
Quine's paradox
Notes
References
Further reading
*
Douglas Hofstadter
Douglas Richard Hofstadter (born February 15, 1945) is an American scholar of cognitive science, physics, and comparative literature whose research includes concepts such as the sense of self in relation to the external world, consciousness, an ...
: ''
Gödel, Escher, Bach: An Eternal Golden Braid''
*
Ken Thompson:
Reflections on Trusting Trust (''
Communications of the ACM'', 27(8):761-3)
External links
TiddlyWiki, a quine manifested as a wikiA Brief Guide to Self-Referential ProgramsQuineProgram at the Portland Pattern Repository WikiZip File QuineAn Introduction to Quines — in particular, quines using more than one language*
ttps://no-gravity.github.io/html-quine/ HTML Quine: An HTML page that only uses HTML and CSS to show its own source codebr>
Quine Challenge for Tom's JavaScript Machine with a series of interactive hints
A Java Quine built straight from Kleene's fixed point theorem, composition and s-n-mA QR code quine
{{DEFAULTSORT:Quine (Computing)
Source code
Articles with example C code
Willard Van Orman Quine
Test items in computer languages
Computer programming folklore
Self-replication