Title: How do you make quines and self-referential programs?


A Basic Strategy

A basic strategy for building a quine is to write a program in two phases as follows.

In the first phase, you first specify a special character or phrase such as !#%&. Next, you create a string variable str storing the value !#%&. Then, you substitute str's string value for the first occurrence of !#%& in str's string value. Finally, you print the result. See the following pseudo code:

1) String str = !#%&;
2) Substitute str for the first occurrence of !#%& in str;
3) print the result as output;

In the second phase, you take the code you wrote and substitute it for !#%&. See the result below:

1) String str = "String str = !#%&; Substitute str for the first occurrence of !#%& in str; print the result as output;";
2) Substitute str for the first occurrence of !#%& in str;
3) print the result as output;

The preceding pseudo code represents a valid quine. However, depending on the programming language, there are at least three issues that may come up.

(1) How do you appropriately handle quotation marks for string assignment?
(2) What about additional special characters?
(3) How do you display everything properly in the end?

A Simple Quine

We will discuss a simple quine that we made in HTML and JavaScript. View its code and run it here: A Simple Quine.

We first resolve issue (3) by making functions for safely displaying special characters and appropriately displaying spacing in HTML.

/* Safely replaces html special characters */
function htmlSafe(str)

/* Replaces newlines and tabs for proper display */
function htmlSpacing(str)

We resolve issues (1) and (2) by introducing encode and decode functions that safely convert special characters to and from strings of hexadecimal numbers. Actually, we only need to use the decode function.

/* Decodes a hex string */
function decode(hex)

Next, we do the string assignment as in phase 1, make the substitution, and print the result.

/* The hex encoding of the partial source code */
var hex = "!#%&";

/* This source code */
var src = decode(hex).replace("!#%&", hex); /* first occurrence only */

/* Safely prints the result */
document.write(htmlSpacing(htmlSafe(src)));

It's important to note that the replace function only replaces the first occurrence of !#%& with hex.

Finally, to get the quine, we proceed to phase 2 where we encode the phase 1 source code in hex using a tool such as String to Hex and update the string assignment:

/* The hex encoding of the partial source code */
var hex = "3c21444f435459504520..."; // and it goes on and on

A Simpler Quine

If you found the previous Quine to be a little too complicated, then you might want to take a look at: A Simpler Quine.

Implementing the Recursion Theorem

We can use the preceding two phase method to create a program that computes its own source code. But, can a program do anything more after it computes its own source code?

To refresh your memory, our version of the recursion theorem says that given any computable function G(x,y) there exists a source code e computing a function E such that E(n) = G(e,n) for all inputs n.

All we have to do to get the source code e is add code for computing the function G at the end of phase 1. Then, we proceed with phase 2 as normal.

We made a simple example where G(x,y) prints y and then prints x. Take a look at our example and make sure to view the code for the following function.

/* This program computes E such that E(str) = G(e,str) */
function G(x,y)

/* Evaluation */
G(src,userInput);

You could replace G(x,y)'s code with whatever you choose and then repeat phase 2. You could even make a program where you enter G's JavaScript code as input and it computes the corresponding self-referential program's code. We implemented such a program and you're welcome to test it here.

Feel free to share any interesting self-referential programs that you've made. :)



Go to: A connection between self-reference and Turing-completeness.

Back to Programs