how to write a quine

main

how to write a quine

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.

How a Quine Works

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.

summary of how this machine works

And now, a summary of how this machine works:

someone presses the button, the machine starts

based on the plan, it produces a machine capable of producing anything based on the plan

it makes a copy of the plan

it inserts this copy of the plan into the machine it made

it gives the machine equipped with the plan to the person who pressed the button

I encourage you: stop here for a moment. Imagine all of this until you feel comfortable with it. Imagine it precisely, step by...