This is a text about how to write a quine (https://en.wikipedia.org/wiki/Quine_%28computing%29), 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.
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[:6] + 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[:6] + 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[:6] + repr(string) + string[11:]; print(string)'; string=string[:6] + 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[:6] + repr(string) + string[11:]; print(string)'; string=string[:6] + 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:
text='text=here!; print(text)'; print(text)
And I changed it to this:
text='text=here!; print(text)'; text=text[:6] + text + text[11:]; print(text)
One might think that instead of splitting the text into two parts — one up to the sixth 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 I can modify the program to escape like repr does. It’s easier to do the latter. Hmm, actually very easy. I don’t need to do anything: the above text that my program printed already has the quotes escaped as repr does. It is the quine I wanted to write.
So the quine using find and replace looks like this:
text="text=here!; text=text.replace('ereh'[::-1], repr(text)); print(text)"; text=text.replace('ereh'[::-1], repr(text)); print(text)
When I run it, I get this output:
text="text=here!; text=text.replace('ereh'[::-1], repr(text)); print(text)"; text=text.replace('ereh'[::-1], repr(text)); print(text)
And now one more variation: I will write a quine in Python using find and replace without using the convenient repr function. I’ll start from the point where I had this program:
string='string=here!; string=string.replace(\'ereh\'[::-1], string); print(string)'; string=string.replace('ereh'[::-1], string); print(string)
As you might remember, its output looked like this:
string=string=here!; string=string.replace('ereh'[::-1], string); print(string); string=string.replace('ereh'[::-1], string); print(string)
As you can see and might remember, it’s almost a quine. All that’s left is to make the string inserted in place of the word here! be changed into a string literal: meaning it needs to be enclosed in quotes, and all special characters within it need to be escaped.
I’ll start by enclosing it in quotes:
string='string=here!; string=string.replace(\'ereh\'[::-1], string); print(string)'; string=string.replace('ereh'[::-1], '\'' + string + '\''); print(string)
Since I added a piece of code to the program, I need to add the same piece of code to the string literal containing the program source. But because I will add this piece in the literal, I need to escape the quotes and backslashes within it. Like this:
string='string=here!; string=string.replace(\'ereh\'[::-1], \'\\\'\' + string + \'\\\'\'); print(string)'; string=string.replace('ereh'[::-1], '\'' + string + '\''); print(string)
Alright. I enclosed the inserted string in quotes, now I’ll escape all the quotes within it:
string='string=here!; string=string.replace(\'ereh\'[::-1], \'\\\'\' + string + \'\\\'\'); print(string)'; string=string.replace('ereh'[::-1], '\'' + string.replace('\'', '\\\'') + '\''); print(string)
Since I added a piece of code to the program, I need to add the same piece of code to the string literal containing the program source. But because I will add this piece in the literal, I need to escape the quotes and backslashes within it. Like this:
string='string=here!; string=string.replace(\'ereh\'[::-1], \'\\\'\' + string.replace(\'\\\'\', \'\\\\\\\'\') + \'\\\'\'); print(string)'; string=string.replace('ereh'[::-1], '\'' + string.replace('\'', '\\\'') + '\''); print(string)
Alright. I enclosed the inserted string in quotes, escaped all the quotes within it, now I’ll escape all the backslashes within it:
string='string=here!; string=string.replace(\'ereh\'[::-1], \'\\\'\' + string.replace(\'\\\'\', \'\\\\\\\'\') + \'\\\'\'); print(string)'; string=string.replace('ereh'[::-1], '\'' + string.replace('\'', '\\\'').replace('\\', '\\\\') + '\''); print(string)
Since I added a piece of code to the program, I need to add the same piece of code to the string literal containing the program source. But because I will add this piece in the literal, I need to escape the quotes and backslashes within it. Like this:
string='string=here!; string=string.replace(\'ereh\'[::-1], \'\\\'\' + string.replace(\'\\\'\', \'\\\\\\\'\').replace(\'\\\\\', \'\\\\\\\\\') + \'\\\'\'); print(string)'; string=string.replace('ereh'[::-1], '\'' + string.replace('\'', '\\\'').replace('\\', '\\\\') + '\''); print(string)
Alright. This should be a working quine. I’ll check if it works. I run it and see that the output is:
string='string=here!; string=string.replace(\\'ereh\\'[::-1], \\'\\\\'\\' + string.replace(\\'\\\\'\\', \\'\\\\\\\\'\\').replace(\\'\\\\\\', \\'\\\\\\\\\\') + \\'\\\\'\\'); print(string)'; string=string.replace('ereh'[::-1], '\'' + string.replace('\'', '\\\'').replace('\\', '\\\\') + '\''); print(string)
Look closely. Do you see that it didn’t produce what it was supposed to? Do you see that the result of this program is different from the source of this program? Do you see that it’s not even syntactically correct Python code? Something went wrong.
If you’re tough, sit down now and think about where we made a mistake and why this quine doesn’t work. Try to fix it yourself.
There is one thing done wrong in this quine. When escaping the string, you need to escape the backslashes first, and only then escape the quotes. So I need to swap the order of the two replace methods, like this:
string='string=here!; string=string.replace(\'ereh\'[::-1], \'\\\'\' + string.replace(\'\\\\\', \'\\\\\\\\\').replace(\'\\\'\', \'\\\\\\\'\') + \'\\\'\'); print(string)'; string=string.replace('ereh'[::-1], '\'' + string.replace('\\', '\\\\').replace('\'', '\\\'') + '\''); print(string)
I’ll try running this program now. I see that its output looks like this:
string='string=here!; string=string.replace(\'ereh\'[::-1], \'\\\'\' + string.replace(\'\\\\\', \'\\\\\\\\\').replace(\'\\\'\', \'\\\\\\\'\') + \'\\\'\'); print(string)'; string=string.replace('ereh'[::-1], '\'' + string.replace('\\', '\\\\').replace('\'', '\\\'') + '\''); print(string)
Phew, it works. But it wasn’t easy, was it? That’s why remember my advice: when writing a quine, avoid using quotes. Once you start escaping them, you’ll never get out of the loop. At this point, I stop writing the text and go out for a sleigh ride.
Now I will write a quine in JavaScript. This time, I will explain less than I did when writing in Python — because I assume you already understand how quines work.
I am writing a program that displays a program that displays anything:
var text='var text=here!; alert(text)'; alert(text)
Between creating the text and displaying it, I insert this text in place of the word here!:
var text='var text=here!; alert(text)'; text = text.substring(0, 10) + text + text.substring(15, text.length); alert(text)
I surround the inserted text with quotes, but without using quotes (to avoid escaping):
var text='var text=here!; alert(text)'; text = text.substring(0, 10) + String.fromCharCode(39) + text + String.fromCharCode(39) + text.substring(15, text.length); alert(text)
Since I added some code to the program, I add the same code to the text literal with the source of the program:
var text='var text=here!; text = text.substring(0, 10) + String.fromCharCode(39) + text + String.fromCharCode(39) + text.substring(15, text.length); alert(text)'; text = text.substring(0, 10) + String.fromCharCode(39) + text + String.fromCharCode(39) + text.substring(15, text.length); alert(text)
And done. This is a complete quine.
Alright, so how would one write a quine in Excel (or any other spreadsheet)? It won't be easy since we can't store a string in a variable to use it later, but it is possible. Let's see.
What I'm going to write now, I'll start with a simple Python quine, a bit — but not much — different from those I’ve discussed before. This will be a quine that inserts the literal of the string into the string by find and replace (using the Python method replace), but without using quotes (to avoid the escaping nightmare).
Here's the template for a program that prints a string:
string=here!; print(string)
Here's the program that prints the template for a program that prints a string:
string='string=here!; print(string)'; print(string)
You could also say that it's the template for a program that prints a program that prints a string — it’s the same thing.
Now I want to modify this outer program so that before displaying the string, it performs a find and replace — replacing the placeholder here! with the literal of that string. But, as we remember, it’s worth doing this in such a way that we don’t use quotes in the find and replace command. But how to write the word here! without using quotes? Maybe instead of the word here! we use some other placeholder that’s easy to write without using quotes? For example, the character #, which can be written as chr(35)? So, I write it like this:
string='string=#; print(string)'; string=string.replace(chr(35), repr(string)); print(string)
Since I changed the program, I also need to change the string literal with the program source:
string='string=#; string=string.replace(chr(35), repr(string)); print(string)'; string=string.replace(chr(35), repr(string)); print(string)
And now I have a quine.
Okay. Now, using this quine as an example, I want to tell you a different recipe for making a quine. A bit different, a bit not. Different because it consists of different steps, but not different because it leads to the same goal, producing the same quine. Here’s the recipe:
Write a template for a program that takes a string, does find and replace in it by inserting the literal of that string in place of the placeholder, and then prints the result:
string=somerestring; string=string.replace(chr(35), repr(string)); print(string)
Remember this program template. I'll call it the program template.
Write the literal source of this program template somewhere:
'string=somerestring; string=string.replace(chr(35), repr(string)); print(string)'
Now, in this literal, where the string to be operated on should be, put the placeholder:
'string=#; string=string.replace(chr(35), repr(string)); print(string)'
Remember this literal. I'll call it the literal.
And now take the program template and where the string goes, insert the literal (in the code below, I've highlighted the inserted literal in blue so you can see what's happening):
string='string=#; string=string.replace(chr(35), repr(string)); print(string)'; string=string.replace(chr(35), repr(string)); print(string)
And that is the quine we were supposed to write.
Now I'll summarize this new recipe for writing a quine:
This recipe is — as I remind you — equivalent to the previously discussed recipe (meaning it produces the same quines). It has the drawback that — in my opinion — it’s harder to understand how it works. It has the advantage that — in my opinion — it’s easier to use to write a quine in difficult situations.
And now I'll use this recipe to write a quine in Excel. More precisely: I’ll write it in Libre Office, but what I write should also work in Excel.
First, I'll write a formula template that takes a string, does find and replace in it by inserting the literal of that string in place of the placeholder, and then prints the result. I'll need to use the SUBSTITUTE function, which is used like this:
=SUBSTITUTE(string-where-replacement-happens, find-what, replace-with-what)
In the third argument, we need — as we remember — the literal of the first argument. This involves two problems: how (in the third argument) to change the given string into a literal and how to write the same string as in the first argument in the third argument.
Changing a string into a string literal is easy. If it doesn't contain special characters (and, as we remember, we don't want them because it will become a nightmare), just surround it with quotes. Like this:
=CHAR(34)&somestring&CHAR(34)
For example:
=CHAR(34)&"Romania"&CHAR(34)
And saying that the third argument should be the same string as in the first argument is also easy. Just write the same string in the third argument as in the first. Like this:
=SUBSTITUTE(somestring,"someplaceholder",thesamestring)
For example:
=SUBSTITUTE("QUIX XXX QUIX","XXX","QUIX XXX QUIX")
I combine both techniques and now I have a formula template that takes a string, does find and replace in place of the placeholder by inserting the literal of that string, and then prints the result. Here it is:
=SUBSTITUTE(somestring,CHAR(35),CHAR(34)&somestring&CHAR(34))
I'll remember this formula template because I'll need it in the future. I'll call it the formula template.
Here's an example of using this formula template:
=SUBSTITUTE("quix # quix",CHAR(35),CHAR(34)&"quix # quix"&CHAR(34))
So, I have completed the first step of the plan. Now I’ll complete the second step, which says: write down the literal source of this formula template. So, I write down this string:
"=SUBSTITUTE(somestring,CHAR(35),CHAR(34)&somestring&CHAR(34))"
Now I'll complete the third step of the plan, which says: now, in this literal, where the string to be operated on should be, put the placeholder. Here you go:
"=SUBSTITUTE(#,CHAR(35),CHAR(34)&#&CHAR(34))"
Remember this literal. I'll call it the literal.
And now I do the last step of the plan. I'll take the formula template and where the string goes, I’ll insert the literal. It turns out like this (I've highlighted the literal in blue to make it easier to see what's happening):
=SUBSTITUTE("=SUBSTITUTE(#,CHAR(35),CHAR(34)&#&CHAR(34))",CHAR(35),CHAR(34)&"=SUBSTITUTE(#,CHAR(35),CHAR(34)&#&CHAR(34))"&CHAR(34))
And that's the quine. I tested it in Libre Office, and it works. It should also work in Excel.