Quine (computing)

A Quine is a computer program that writes a copy of itself (usually its source code ) as output. It thus is a form of self-reference.

Hackers and geeks see it as a sporting challenge to create the smallest possible Quine in programming languages ​​of their choice (see IOCCC ).

Quine's are named after the logician and philosopher Willard Van Orman Quine.

Construction of Quine's

Ask yourself

A Quine could be written in a C - like pseudo - code as

Main () {      print myself out. } Usually C programs are translated, that is, the run-time version of the program is in machine language before (representation as a sequence of bytes, stored in a so-called binary file ), but its original Repräsention is usually an ASCII -encoded source, the tends to be stored in another file. The need for this approach to implement a Quine's access to its own representation ( myself ) would be very complicated.

Next one calls for a Quine that it is complete.

• It is to do without access to external data, while also addressing the access to its own source code file is excluded.
• Likewise, should even be present basic code in Quine system, and external functions are to be used only sparingly, the library function to output a sign about is still permissible.

Few languages ​​support self-reference (reflection ) in the form that a program of this language has access to its own representation.

An interpreted programming language, such as Perl or Python, it would in principle be easier, as you could also make the selfsame available the required by the interpreter representation of the program to be executed, but usually that is not supported, for example, for security reasons, or because the designer of the language did not want to go so far ( for example, because self-modifying code is rejected ). In most cases the program is not much more reflection is possible there than to learn his name and the names of its variables and functions from the runtime system.

Therefore, reflection does not result in most programming to a correct Quine.

Code as data

Most programming languages ​​provide little help, appropriately internally to represent programs and to work with these representations:

• To analyze it ( parsing ),
• To create new programs from existing representations (composition) and in particular
• Execute the represented program (application ).

A well-known application example would be a function plotter, which is a program for plotting the graphs of arbitrary mathematical functions.

In other words:

For functions are available in many programming languages ​​do not provide adequate data type of certain operations.

In C, you can put some code in a string, but you can start by little, because this is the means of C only consuming to analyze and execute. One must then resort to complex verpointerten structures and external libraries.

A positive example would be LISP, because here the program code can be represented as a list and manipulated very easily.

Quinierung

The above statements have difficulty listed that has a program if it wants to ask its own structure. However, it should also be possible in C to implement a Quine (see the remarks on the existence of Quine's theory in part). The following technique is used:

If you can not poll its own structure, you have to know from the outset.

We designed the program in two parts, one which is called the code, and one, called the data. The data represent the code (or its text form), and they are derived in an algorithmic way from the code (usually by quotation marks were set, but sometimes even a slightly more complicated way ). The code uses the data to output the code (which is easy because the data represent the code ); He then uses the data to output the data (which is possible because the data are concerned in an algorithmic transformation).

As stated above, this is in some languages ​​easier and more difficult in others, for example depending on whether functions are first class citizens of the language or not.

In the strict sense Quine should be independent of the character set, and the source code should be issued, including all line breaks exactly again.

( ( lambda ( x)    (list x (list ( quote quote ) x )))   ( quote      ( lambda ( x)        (list x (list ( quote quote ) x)) ))) C char * f = " char * f = % c % s % c; main () { printf (f, 34, f, 34,10 );} % c "; main () { printf (f, 34, f, 34,10 );} Uses ASCII encoding of the quotation Lua a = " a = % c % s % c; io.write ( string.format (a, 34 a, 34) )"; io.write ( string.format (a, 34 a, 34) ) Uses ASCII encoding of the quotation Python 2 a = " a = % c % s % c; print a% % (34, a, 34 )"; print a% (34, a, 34) Uses ASCII encoding of the quotation Python 3 a = " a = % c % s % c; print ( a% % (34, a, 34) )"; print ( a% (34, a, 34) ) Uses ASCII encoding of the quotation Perl $ a = '$ a = % c % s % c; printf ($ a, 39, $ a, 39,10 ); % c'; printf ($ a, 39, $ a, 39,10 ); Uses ASCII encoding of the quotation Perl $ r = ' \'; $ _ = $ r; s / ( [\ \ \ '\ \ \ \] ) / \ \ \ \ $ 1 / g; print \ '$ r = \ \ \ ' \ '$ _ $ r. .; '; $ _ = $ r; s / ( [\ ' \ \] ) / \ \ $ 1 / g; print ' $ r = \ '' $ _ $ r. .; Regardless of the character set Ruby puts << 2 * 2,2 puts << 2 * 2,2 2 Regardless of the character set Ruby eval s = % q ( puts " eval s = % q (# {s }) " ) Regardless of the character set C # using System; class Quine { static string f = " using System; class Quine { { static string f = {1 } {0 } {1 }; static void Main () { { Console.Write ( f, f, Convert.ToChar (34 ) );} }} }"; static void Main () { Console.Write ( f, f, Convert.ToChar (34 ) );} } Java public class q { static String s = " public class q { 1} static String s = {3 } {0 } {3 }; public static void main (String [] a ) { 1} System.out.println ( java.text.MessageFormat.format (s, s, '' { 1} '','' {2 }'', '' { 3 }'' ) ); {2 } {2 } "; public static void main (String [] a ) { System.out.println ( java.text.MessageFormat.format (s, s, '{', '} ', ' " ')); }} Sleep [{ $ s = '; print (" [{ \ $ s =" chr ( 39 ) $ s.chr (39 ) $ s. .. );} ] '; print (" [{ \ $ s =". chr ( 39 ) $ s.chr (39 ) $ s); .. }] PHP $ vEngu = 96; printf ($ c = '$ vEngu =% s; printf ( $ c = % c % s % c, $ vEngu, 39, $ c, 39); ', $ vEngu, 39, $ c, 39); Pascal const a = ', begin write ( ^ # ^ / ^ ^ 3 ^ 4 ^ ' ^ ​​^ } # 39, a, # 39, a.! ) end. '; begin write ( ^ # ^ / ^ ^ ^ 3. 4 ^ `^! ^} # 39, a, # 39, a) end. uses escape sequences Delphi program Quine; {$ APPTYPE CONSOLE } var x: String = ' Quine program; {$ APPTYPE CONSOLE } var x: String =; begin Insert ( # 39 # 39 x, x, 46); WriteLn (x); ReadLn; end. '; begin Insert ( # 39 # 39 x, x, 46); WriteLn (x); ReadLn; end. without line breaks ( would be too long for this table ) Theoretical background

The existence of Quine's theory is by the Rekursionssatz (also called fixed point theorem of Kleene ) backed up.

Coarse runs the argument like this:

• One can infer the properties of programming languages ​​by results of computability theory, which analyzes very simple models of programs with mathematical accuracy.
• As you all programs (more precisely, their finite source code ) to count, so it can bijective map onto the natural numbers, in this model world the specification of a natural number as a representation of a program is sufficient. This number does the same as the source text, ie to select exactly the function that corresponds to the semantics of the program.
• With the fixed point theorem can be shown that it (also) is a program with the number, the output ( for all possible inputs ) in turn is the number. Thus, this is from the above lemma computability theory exactly the equivalent of a program that prints its own representation - a Quine.

The statements from the computability theory of computable functions can be easily on Turing machines and ultimately generalize to arbitrary Turing complete languages.

Quine therefore are not only the result of random resourceful programmers who outsmart a programming language, it is rather a fundamental property of Turing - complete programming languages ​​that they exist for Quine.