1. Introduction

The name "quine" was coined by Douglas Hofstadter, in his popular science book Gödel, Escher, Bach: An Eternal Golden Braid, in the 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.

Concretely, the term "quine" is referred to a computer program which takes no input and produces a copy of its own source code as its only output. First appeared in Paul Bratley and Jean Millo's article "Computer Recreations: Self-Reproducing Automata" in 1972, the idea of quine is fascinating due to its self-reproducing feature. For amusement, programmers sometimes attempt to develop the shortest possible quine in any given programming language. Moreover, problems based on the idea of quine are popular in various code golf, which is a type of recreational computer programming competition in which participants strive to achieve the shortest possible code that implements a certain algorithm.

There are many theoretical results for quine. For example, it is possible to implement quine in any Turing complete programming language, as a direct consequence of Kleene's recursion theorem. However, this article focuses more on quines' implementation.

In some languages, quines are quite easy to be implemented, since in some languages, an empty program is a quine. 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. Another possible way to achieve self-reproducing is to use file operations to read its source code and print, which seems a bit cheating. All these kinds of trival cases are omitted in this article.

This article shows an easy, general, and elegant way to implement quines in C with preprocessing which not only have short length, but can easily do general purpose computations as well. The techniques in this article are widely used in various code golf.

The remainder of the article is organized as follows. In section 2, the preprocessing techniques used in this article are described. Section 3 shows how to implement quines.

2. The C Preprocessing

One of the major use of the preprocessor in C is to define macros, which is also used to implement quines in this article. A macro definition is usually of the following form:

#define MACRO_NAME(arg1, arg2, ...) [code to expand to]

For instance, a simple macro for multiplication might look like this:

#define MULT(x, y) (x)*(y)

After MULT is defined, one can write MULT(4, 2+3) and the preprocessor expands it to (4)*(2+3).

Besides macro itself, the stringize or number-sign operator # is also used in this article, which can convert a macro parameter into a string constant. For instance, with the following macro

#define hello(a) printf("Hello " #a)

One can write hello(Kai) and the preprocessor expands it to printf("Hello " "Kai").

Now, it is high time for us to define the magic operator using macro and stringize operator:

#define Q(x)char*s=#x;x

It is easy to see how does the magic operator work with an example, which will be given in the next section.

3. Quine Implementation

With the magic operator, A simple quine can be implemented as follows:

#define Q(x)char*s=#x;x
Q(main(){printf("#define Q(x)char*s=#x;x\nQ(%s)",s);})

Now, let us analyse the above quine. After expanding the macro, the code becomes:

char*s="main(){printf(\"#define Q(x)char*s=#x;x\nQ(%s)\",s);}";main(){printf("#define Q(x)char*s=#x;x\nQ(%s)",s);}

It can be seen that the variable s is a pointer pointing to the string of the code which is written as the parameter of macro Q(), that is, main(){printf("#define Q(x)char*s=#x;x\nQ(%s)",s);}, which is also the code after the definition of s for actual execution. Therefore, with s, in order to achieve self reproduceing, only #define Q(x)char*s=#x;x and Q() should be rewritten in printf() for output; the string of the other code can just be represented by s.

In fact, the approach described above is a general way for quine implementation, which can be seen by considering the following framework:

#define Q(x)char*s=#x;x
Q( {A} main(){ {B} printf("#define Q(x)char*s=#x;x\nQ(%s)",s); {C} } {D} )

In the framework, {A}, {B}, {C}, and {D} can be replaced by any legal code in C, and the feature of self reproducing still holds (In particular, if there exist other variables with identifier s, s should be replaced by some unused identifier).

With the approach with only a few modifications, we can go even further: implementing more general quines. For example, implement a general quine that outputs all its characters in the odd position when the user inputs "o" and outputs all its characters in the even position when the user inputs "e"; implement a general quine A that can output a general quine B, which can again output the general quine A, forming a "quine loop". As it is not difficult to implement both of them, here the solutions are not given, and these two problems are left for readers who are interested in the topic.

References

  1. http://en.wikipedia.org/wiki/Quine_(computing)
  2. http://en.wikipedia.org/wiki/Code_golf
  3. http://www.cprogramming.com/tutorial/cpreprocessor.html
  4. http://www.tutorialspoint.com/cprogramming/c_preprocessors.htm