Quine (computer program)

from Wikipedia, the free encyclopedia

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

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

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

Construction of quines

Ask yourself

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

main() {
    print myself out.
}

Usually, C programs are compiled ; H. The runtime version of the program is available in machine language (representation as a sequence of bytes , stored in a so-called binary file), but its original representation is usually an ASCII- coded source text that is also stored in another file. The access to the own representation ( myself ) required for this approach to the implementation of a Quines would therefore be very complicated.

A Quine is also required to be completed.

  • It should do without access to external data, which also excludes access to your own source text file.
  • Similarly, the essential code in Quine should be present yourself why external functions are to be used sparingly, the library function a sign spend about is still permissible.

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

An interpreted programming language, such as Perl or Python , would in principle have an easier time, since the representation of the program to be executed required by the interpreter could also be made available to the same, but this is usually not supported, for example for security reasons or because the Designers of the language didn't want to go that far (for example because self-modifying code is rejected). Usually there is not much more reflection possible for the program than to learn its name and the names of its variables and functions from the runtime system.

Reflection therefore does not lead to a correct quine in most programming languages.

Code as data

Most programming languages ​​offer little help in representing programs appropriately internally and working with these representations:

  • analyze them ( parse ),
  • to generate 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 any mathematical functions.

In other words:

In many programming languages ​​there is no appropriate data type with corresponding operations for functions.

In C you can store a piece of program code in a string , but you can do little with it, because it is difficult to analyze and execute with the means of C. You then have to resort to complex marked structures and external libraries.

LISP is a positive example because this language represents source code in the algebraic data type list , which it mainly uses itself ( homoiconicity ).

Quination

The above has listed the difficulty a program has in asking for its own structure. Nevertheless, it must also be possible to realize a quine in C (see the explanations on the existence of quines in the theoretical part). The following technique is used for this:

If you cannot inquire about your own structure, you have to know it in advance.

You design the program in two parts, one called the code and one called the data. The data represent the code (or its textual form) and they are derived from the code in an algorithmic way (mostly using quotation marks, but sometimes in a slightly more complicated way). The code uses the data to output the code (which is easy because the data represents the code); then it uses the data to output the data (which is possible since the data is obtained in an algorithmic transformation).

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

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

Examples

language example Hints
Lisp 
((lambda (x)
  (list x (list (quote quote) x)))
 (quote
    (lambda (x)
      (list x (list (quote quote) x)))))
The only example that does not require a "String" data type
Go 
package main
import "fmt"
func main() {
	fmt.Printf("%s%c%s%c\n", s, 0x60, s, 0x60)
}
var s = `
package main
import "fmt"
func main {
	fmt.Printf("%s%c%s%c\n", s, 0x60, s, 0x60)
}
var s = `
Uses the ASCII coding of the grave accent
C. 
#include <stdio.h>
char*f="#include <stdio.h>%cchar*f=%c%s%c;main() {printf(f,10,34,f,34,10);}%c";main() {printf(f,10,34,f,34,10);}
Uses the ASCII coding of the quotation mark
Lua 
a="a=%c%s%c;io.write(string.format(a,34,a,34))";io.write(string.format(a,34,a,34))
Uses the ASCII coding of the quotation mark
Python 2 
a="a=%c%s%c;print a%%(34,a,34)";print a%(34,a,34)
Uses the ASCII coding of the quotation mark
Python 3 
a="a=%c%s%c;print(a%%(34,a,34))";print(a%(34,a,34))
Uses the ASCII coding of the quotation mark
Pearl 
$a='$a=%c%s%c;printf($a,39,$a,39,10);%c';printf($a,39,$a,39,10);
Uses the ASCII coding of the single quotation mark
Pearl 
$r='\'; $_=$r; s/([\\\'\\\\])/\\\\$1/g; print \'$r=\\\'\'.$_.$r;
'; $_=$r; s/([\'\\])/\\$1/g; print '$r=\''.$_.$r;
Independent of the character set
Perl6 
my $t="; say \"my \\\$t=\",\$t.perl,\$t"; say "my \$t=",$t.perl,$t
Ruby 
puts <<2*2,2
puts <<2*2,2
2
Independent of the character set
Ruby 
eval s=%q(puts"eval s=%q(#{s})")
Independent of the character set
Rust 
fn main() {
    let x = "fn main() {\n    let x = ";
    let y = "print!(\"{}{:?};\n    let y = {:?};\n    {}\", x, x, y, y)\n}\n";
    print!("{}{:?};
    let y = {:?};
    {}", x, x, y, y)
}
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 
class Q{public static void main(String[]a){String f=
"class Q{public static void main(String[]a){String f=%c%s%1$c;System.out.printf(f,34,f);}}";
System.out.printf(f,34,f);}}
Just one line
Kotlin 
fun main(args: Array<String>){val f="""fun main(args: Array<String>){val f="%s"%s"%s";System.out.printf(f,'"',f,'"')}""";System.out.printf(f,'"',f,'"')}
Only one line, regardless of the character set
JavaScript 
var x = '"'+"; alert('var x = '+x[9]+x[0]+x[9]+'+'+x+x);"; alert('var x = '+x[9]+x[0]+x[9]+'+'+x+x);
Sleep 
[{$s = ';print("[{\$s = ".chr(39).$s.chr(39).$s);}]';print("[{\$s = ".chr(39).$s.chr(39).$s);}]
PHP 
<?php printf($c = '<?php printf($c = %c%s%c, 39, $c, 39); ?>', 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=
'program Quine;{$APPTYPE CONSOLE}var x:String=;begin Insert(#39+x+#39,x,46);WriteLn(x);ReadLn;end.';
begin Insert(#39+x+#39,x,46);WriteLn(x);ReadLn;end.
without line breaks (would otherwise be too long for this table)

Theoretical background

The existence of quines is theoretically secured by the recursion theorem (also called Kleene's fixed point theorem ).

The reasoning goes roughly as follows:

  • The properties of programming languages ​​can be inferred from the results of computability theory , which analyzes very simple models of programs with mathematical precision.
  • Since all programs (more precisely: their finite source texts) can be counted, i.e. mapped bijectively to the natural numbers , in this model world it is sufficient to specify a natural number as a representation of a program. This number does the same thing as the source text, namely the selection of exactly the function that corresponds to the semantics of the program.
  • With the fixed point block it can be shown that there is a program with the number (with ), whose output (for all possible inputs ) is in turn the number . Thus, from the above lemma of the computability theory, this is exactly the equivalent of a program that outputs its own representation - a quines.

The statements from the computability theory for computable functions can easily be generalized to Turing machines and thus ultimately to any Turing-complete languages.

Quines are therefore not just the result of resourceful programmers who trick a programming language, it is rather a fundamental property of Turing-complete programming languages ​​that quines exist for them.

See also

literature

Web links

Individual evidence

  1. ↑ Craig S. Kaplan: The Search For Self-Documenting Code