How to Write a Quine

The Allegory of the Machine

This is a text about how to write a quine, which is a program that prints its own source code without using introspection. I assume the reader has encountered quines before, maybe even tried to write one, and understands why they are difficult and interesting. The text consists of two parts: in the first, I explain through an allegory how it works, and in the second, I describe in detail how to write a quine.

Now I'll explain how one could build a machine that can create its own copy. Of course, the simplest way would be for the machine to look at itself, see how it's built, and build something identical. But could a machine be built that could create its own copy without introspection? First, I would build a machine that can create anything if it has a plan for it. One could say that such a machine is not really a machine until a plan is inserted into it, because if you turn it on, it does nothing, but that doesn't matter. It's still cool because you just need to insert a plan for a kayak, and you'll have a machine that builds kayaks; insert a plan for a wheelbarrow, and you'll have a machine that builds wheelbarrows, etc.

So, could we insert a plan of itself and get a machine that builds its own copy? There's one problem: what will be drawn on the plan where the plan holder is depicted? Will the holder be empty? If so, the machine built according to this plan won't be able to build anything (so it won't really be a copy of its parent, because the parent could build a descendant machine, but it can't). Or maybe the plan will show the exact plan of this machine? That's better, but what should be drawn on the plan within the plan where the holder is depicted? Unfortunately, there are two possibilities: either the holder on one of the plans will be empty, meaning the machine won't create its perfect copy, or we will never finish drawing this plan.

I encourage you: stop here for a moment. Imagine all this until you feel comfortable with it. Imagine a machine that can make anything if the plan for that thing is inserted into its plan holder. Imagine inserting a plan for a desk (car, frying pan, headphones, phone), pressing a button, and it makes it. Now imagine drawing a plan for this machine, inserting this plan into the plan holder, and turning on the machine. The parent machine produces a child machine; we turn on the child machine, and what happens then?

Now another thought experiment: we draw a plan for this machine, but this time the plan holder holds a plan for a desk, then we turn on the machine, the child machine pops out, we turn on the child machine, and what happens now?

And now another thought experiment: we draw a plan for this machine, but this time the plan holder shows the plan of this machine with an empty plan holder. Then we turn on the machine, the child machine pops out, we turn on the child machine... do you see what happens in your mind's eye?

But you can modify this machine to work a bit differently: to produce what's drawn on the plan and then to copy the plan, find the place marked "here" on the produced item, and insert the copy there. And on the plan, we will draw the exact plan of this machine, but with an empty holder marked "here". And now watch what happens when we turn on the machine: it will build its copy without any plan, copy the plan, and insert it into the holder. And this way, it created its exact copy.

If at this point you feel like I'm cheating because making a copy of the plan is a kind of introspection, if you are upset that I didn't clearly define which actions are forbidden introspection and which ones, like copying the plan, are not, then push those thoughts away. This whole story about the machine is not an independent puzzle. It doesn't even have to make perfect sense. It only serves to help you understand better why the quine I'll write in a moment is built the way it is and how it works. This comparison to such a machine helped me a lot with understanding the quine (the one I'll write shortly), so I'm sharing this story with you.

Let’s pay attention to one detail which is insignificant for the machine but will be important when I actually write the quine. This machine, after producing the machine, cannot immediately give it to the person who pressed the button - it has to hold it for a moment to insert a copy of the plan.

And now, a summary of how this machine works: I encourage you: stop here for a moment. Imagine all of this until you feel comfortable with it. Imagine it precisely, step by step, properly, visually, how this machine works, how it produces the child-machine, how it copies the plan, how it inserts the copy into the child-machine, how we start the child-machine, what this child-machine does, how we then start the grandchild-machine... and so on.

Writing a Simple Quine in Python

And now I will write a quine - a program that displays itself (without using introspection).

First, I will write a simple quine in Python to show you how to write a quine, and then I will write a few variations in Python and other languages to show what problems might arise and how to solve them.

First, note that a program displaying itself is a special case of a program that displays something. So I will start by writing a program that displays something. In Python, the simplest way to do this is:

print()

This is a program that can display anything - you just need to insert that anything into the parentheses. As long as you don't insert anything, this program is useless (like a machine without a plan), but when, for example, I insert the word Poland into these parentheses, I get a program that displays the word Poland:

print('Poland')

Next, note that a program displaying itself is a program that displays a program that displays itself. And this, in turn, is a special case of a program that displays a program that displays something. So let's write a program that displays a program that displays something. In Python, the simplest way to do this is:

print('print()')

This is a program that creates a program that can display anything - you just need to insert that anything into the parentheses. It is like a machine that produces a machine that can produce anything, given a plan. As long as nothing is inserted into these parentheses, this program is useless (like a machine producing a machine not equipped with a plan), but when, for example, I insert the word Poland into these parentheses, I get a program displaying a program displaying the word Poland:

print('print("Poland")')

Let's compare this again with the machines I wrote about in the first part. The program print() is like a machine that can make anything, given a plan for that anything. The notation 'print()' is like the plan for this machine. The program print('print()') is like a machine capable of making anything if given a plan, which has in its plan holder the plan of a machine that can make anything if given a plan, whose plan holder is empty. And the program print('print("Poland")') is like a machine capable of making anything if given a plan, which has in its plan holder the plan of a machine that can make anything if given a plan, which has in its plan holder the plan of the word Poland.

Note that this is not a program that prints its own source - though it is a program that prints the source of a program similar to itself, so we are quite close.

Now we need to perform a maneuver similar to what we did with the machines in the first part. Remember how in the plan of the child-machine I wrote here in the plan holder? Well, now I will do something similar. Watch:

print('print(here)')

Do you remember how I modified the machine so that before returning the child-machine, it would place a copy of the plan it was made from in its container? Now I will do something similar: I will modify this program so that after creating the string but before displaying it, it places a copy of this string in the spot marked with the word here. For now, this is not easy to do because creating the string and displaying it is done in one command, so there is no time to make this substitution. So, I will separate the creation of the string from its display in this program:

string='print(here)'; print(string)

But wait - since I changed the program, I should also change the string literal with the program source so that the parent creates a child similar to itself (do you understand? In analogy with the machine, I would say: when we change the machine, we also have to change the machine's plan so that the parent-machine creates a child-machine similar to itself):

string='string=here; print(string)'; print(string)

As you can see, I marked the modified fragment in blue. I will sometimes do this in the rest of the article as well.

Now I add a command to the program that inserts a copy of this string in place of the word here before displaying it:

string='string=here; print(string)'; string=string[:7] + string + string[11:]; print(string)

Notice that I do this substitution not by finding the string here (that is, not by the find and replace method, not by the Python method replace), but by slicing this string at a given place. I do it this way because it will be the easiest. Later I will show you what would happen if I tried to do it differently.

I run this program and see if it works well. Here is the result of its operation:

string=string=here; print(string); print(string)

Not bad, but there are still two things to fix. First, the string inserted in place of the word here should be enclosed in quotation marks. There is a built-in function in Python for this, repr. So I use it:

string='string=here; print(string)'; string=string[:7] + repr(string) + string[11:]; print(string)

I run this program and see if it works well. I see that now its output looks like this:

string='string=here; print(string)'; print(string)

Good, the quotation marks appeared. Now the second thing. Since I changed the program (because I added code that inserts what is needed in place of the string here), I also need to change the string literal with the program source. So I change the program to this:

string='string=here; string=string[:7] + repr(string) + string[11:]; print(string)'; string=string[:7] + repr(string) + string[11:]; print(string)

I run this program and see if it works well. I see that its output is this:

string='string=here; string=string[:7] + repr(string) + string[11:]; print(string)'; string=string[:7] + repr(string) + string[11:]; print(string)

Success! The quine works!

When you think about how this quine works, it’s worth comparing it to the machine-making machine I wrote about in the first part. There is only one difficulty: in the case of machines, the difference between the machine and the machine's plan is stark. In the case of programs, the difference between the text and its literal is subtle.

So once again, I’ll summarize in three steps how I wrote this simple quine in Python - because the same steps can be used to write quines in other languages:

1. Write a program that prints a placeholder.
2. Modify it so that instead of printing the placeholder, it prints the program text with the placeholder replaced by a copy of that text.
3. Adjust the program source inside the string to match the final program.

Variations and Problems

One might think that instead of splitting the text into two parts - one up to the seventh character and the other from the eleventh character - and inserting what is needed between them, it would be simpler to use find and replace, i.e., use the replace method. So I’ll give it a try. I add the replacement command both to the program and to the program's source literal:

text='text=here; text=text.replace(\'here\', text); print(text)'; text=text.replace('here', text); print(text)

I run this program and see that something went wrong. The output looks like this:

text=text=here; text=text.replace('here', text); print(text); text=text.replace('text=here; text=text.replace('here', text); print(text)', text); print(text)

The program didn’t work as it should because in the text literal, the word here appears twice: once where it marks the place where something needs to be inserted, and a second time where in the find and replace command we specify what fragment of the text we’re looking for. Only the first occurrence of the word here should be replaced, not the second.

This problem can be solved in several ways. For example, in the find and replace command, we could try to refer to here without using the word here. For example, like this:

text='text=here; text=text.replace(\'HERE\'.lower(), text); print(text)'; text=text.replace('HERE'.lower(), text); print(text)

or like this:

text='text=here; text=text.replace(\'ereh\'[::-1], text); print(text)'; text=text.replace('ereh'[::-1], text); print(text)

I run this program to see how it works. I see this output:

text=text=here; text=text.replace('ereh'[::-1], text); print(text); text=text.replace('ereh'[::-1], text); print(text)

Not bad. Now we just need to change the inserted text into a text literal: surround it with quotes and escape any special characters (for example, the quotes around 'ereh'). Fortunately, Python has a built-in function repr for this (but imagine how much work this would be if we were doing it in JavaScript and didn’t have such a function):

text='text=here; text=text.replace(\'ereh\'[::-1], repr(text)); print(text)'; text=text.replace('ereh'[::-1], repr(text)); print(text)

I run this program. I see this output:

text="text=here; text=text.replace('ereh'[::-1], repr(text)); print(text)"; text=text.replace('ereh'[::-1], repr(text)); print(text)

Well, almost perfect. Almost the same result. Only when the repr function converted the program source text into a text literal, it approached the problem of escaping single quotes around 'ereh' differently than I did: instead of escaping them, it surrounded the text with double quotes. If I want the program’s output to be exactly the same as its source (not just similar with respect to quotes), I need to either make the repr function escape like I do, or