A Program Looking in the Mirror

There is a tiny class of programs that seem, at first, to have been given an unfair advantage.

Run this one without opening it:

python3 lab/first_quine.py

It prints two lines. Now open the file. The two lines it printed are precisely the two lines in the file—including punctuation and the final newline.

How could a program know its own text?

Keep that question alive for a moment. A good puzzle should be allowed to be a puzzle before it becomes an explanation.

A note for Windows: commands in the course use python3. In PowerShell, use py instead. Where the course uses the Unix command cp, use your editor's Save As command or PowerShell's Copy-Item.

1. Draw the boundary

The program you ran is a quine. For this course, a quine obeys three rules:

It receives no source code as input.
It does not read its source file, inspect the process that launched it, or ask its environment for a copy.
Its output is exactly its source code, byte for byte.

The name comes from the philosopher Willard Van Orman Quine, whose work often visited self-reference. Douglas Hofstadter gave the programming puzzle its name in Gödel, Escher, Bach. The short bibliography in REFERENCES.md points outward when you want the history and theory in their less abbreviated forms.

Rules matter because loopholes are cheap. A program that opens __file__ and prints what it finds is interesting for other reasons, but it has stepped around our puzzle. An empty file raises another pub-table argument: it produces nothing, which is exactly its contents, but it teaches us nothing. We will ask our programs to do the honest work.

Keep: A quine does not discover its source. It reconstructs it.

Pause and predict

Before continuing, answer this in a sentence:

What information must be somewhere inside a program if the program is to print every character of itself?

Do not worry about getting it right. A prediction gives the next observation something to push against.

2. There is no hidden mirror

Most first guesses involve introspection: perhaps Python quietly exposes the current file, or perhaps print knows more than it admits.

But our specimen uses only a string, formatting, and print. There is no secret mirror. Instead, the program divides the job into two parts:

data: a description of the program's shape;
machinery: instructions that place a representation of that data back into the shape.

This is the turn. A quine does not need to contain two complete copies of itself. It needs one reusable description and a way to quote that description.

Try this in a Python prompt:

>>> word = "mirror\nlight"
>>> print(word)
mirror
light
>>> print(repr(word))
'mirror\nlight'

The first print shows the value of the string. The second shows a Python expression that could recreate that value. Quotes appear. The newline becomes the two visible characters \ and n.

Pause and predict

What will Python choose when the value itself contains a single quote? Make a prediction, then ask:

>>> print(repr("don't"))
"don't"

Python switched to double quotes so it would not need to escape the apostrophe. repr promises a usable representation of this string; it does not preserve how a programmer originally spelled the literal. Exact quines care about that choice. If the representation uses double quotes, the source must use them too.

That difference—between a value and a representation of the value—is almost the whole rabbit hole.

Keep: Source code can be data, and data can be rendered as source code.

3. Teach a string to leave a space for itself

Python's old-style string formatting has a useful placeholder:

shape = "The Python representation of the word is %r"
print(shape % "hello")

%r means: put the representation of this value here. The result is:

The Python representation of the word is 'hello'

Take three minutes before the reveal

Close lab/first_quine.py if it is still open. On paper or in a scratch file, start with only this:

s = SOMETHING
print(s % s)

SOMETHING must describe both lines, yet leave one %r-shaped opening for its own representation. Try to write it. A failed attempt is useful: circle the first character where its output stops matching its source.

Continue when you either have a candidate or can name the character that is giving you trouble.

Now imagine that shape is not an English sentence. Imagine that it describes a whole program, with one %r-shaped opening where the program's string must go.

We would like the finished program to have this form:

s = SOMETHING
print(s % s)

What must SOMETHING describe? Everything around it:

s = %r
print(s % s)

There is one nuisance. The formatting operation must save the second % for the program it is constructing. Inside a format string, %% produces one literal percent sign.

So the description becomes:

's = %r\nprint(s %% s)'

Put it in the opening. Reveal this only after making your own attempt:

Show the two-line quine

s = 's = %r\nprint(s %% s)'
print(s % s)

There it is. No oracle. No inspection. Just a template applied to its own representation.

The same value does two jobs. Read the two branches downward, then watch them meet again at the formatting operation:

                         one value: s
                         /          \
                        /            \
             use as template      represent as source
                      |                 |
                      v                 v
                "s = %r ..."         repr(s)
                      \                 /
                       \               /
                        +----- s % s --+
                               |
                               v
                        complete source
                               |
                              run
                               |
                               +------------> same source

The mechanism in slow motion

Piece	Job
`s`	holds the shape of the whole program
`%r`	inserts a quoted, escaped representation of `s`
`\n`	puts the second source line on a new line
`%%`	preserves the percent sign needed by that second line
`s % s`	applies the shape to its own description
`print`	adds the source file's final newline

Every mark has paid its fare.

Keep: The string holds the program with a hole; formatting fills the hole with the string itself.

4. Verify the claim

Human eyes forgive differences that computers do not. A missing newline, an extra space, or a changed quote means the output is not the source.

Ask the checker:

python3 tools/verify.py lab/first_quine.py

It runs the program, captures its output as bytes, reads the source as bytes, and compares the two. The checker establishes equality; it does not establish honesty. A file-reading impostor could pass, which is why the boundary we drew in lesson 1 still matters.

That distinction is useful beyond quines:

a test observes behavior;
an explanation accounts for how that behavior was produced.

We want both.

Experiment: disturb the balance

Duplicate the quine so the original remains a reliable specimen. Use your editor's Save As command, or on macOS and Linux run:

cp lab/first_quine.py my_quine.py

Make one change at a time and run the verifier after each:

Rename s to mirror on only the second line.
Restore it, then remove one % from %%.
Restore it, then replace both source lines with these. The file itself should still end with a newline.
```
s = "s = %r\nprint(s %% s, end='')"
print(s % s, end='')
```
Restore it, then add a comment to the end of the file.

Before running each version, predict the failure. A syntax error, a formatting error, and an almost-correct output are different clues.

When you are ready, compare your explanations with answers/README.md.

5. Rebuild one without looking

The difference between recognizing an idea and owning it is whether you can reconstruct it after the page is closed.

Open lab/unfinished_quine.py. Replace its contents with a genuine quine, but do not copy first_quine.py. Begin with only this skeleton:

text = ?
print(? )

Work backward:

What should the final printing expression do?
What must text contain for that expression to print both source lines?
Where must a representation of text be inserted?
Which characters inside text need to survive one round of formatting?

Then check your work:

python3 tools/verify.py lab/unfinished_quine.py

If you get stuck, use the hints in answers/README.md one at a time.

One small extension

Rename every identifier and retain exact equality. This sounds cosmetic, but it forces you to find every place where the program describes its own machinery.

The goal is not brevity. It is being able to predict where every changed character must be represented.

Keep: Understanding is the ability to rebuild, vary, and repair.

6. Different languages, same turn

The Python example leans on repr, which conveniently produces valid Python string syntax. Other languages provide different machinery, but the division of labor remains recognizable.

Pause and predict

Before opening either specimen, ask what service must replace Python's repr. JavaScript has a string representation close at hand. C does not. Predict which version will need to mention quotation marks and newlines explicitly.

If Node.js is installed:

node gallery/javascript.js
python3 tools/verify.py gallery/javascript.js

JavaScript's specimen uses %j: Node's formatter converts the supplied string to JSON, whose quoted string syntax works for this program.

If a C compiler is installed:

python3 tools/verify.py gallery/c.c

C offers no built-in repr. The specimen explicitly inserts character codes for newline (10) and quotation mark (34). It is less graceful, but the same two jobs are visible: keep a shape, then place a quoted version of the shape inside itself.

The gallery is not a contest for the shortest incantation. Tiny quines often compress away the explanation. Here, another language is valuable only when it makes the shared structure easier to see.

7. The rabbit hole widens

We can now say what the first surprise was hiding.

A fixed point

Think of “run this source and capture its output” as an operation on program text. Most programs are moved somewhere else by that operation: their output does not resemble their source. A quine is left in place.

run-and-capture(Q) = Q

It is a fixed point of that operation. This vocabulary lets the little program sit beside fixed-point ideas in logic, mathematics, and semantics without claiming that all those subjects are identical.

Diagonalization

The move s % s applies a description to itself. Logic uses related diagonal moves to construct statements that refer, indirectly and precisely, to their own descriptions. Quines are a friendly mechanical model of that maneuver. They are not a proof of Gödel's incompleteness theorems, but they exercise one of the same mental muscles.

The recursion theorem

Kleene's second recursion theorem says, roughly, that programs in a sufficiently expressive system can be constructed to make use of their own descriptions. A plain quine is the hello-world example. More general constructions can know their descriptions and then do something other than merely print them. The references include both the original mathematical source and a modern, program-shaped route into the idea.

Replication and trust

Computer viruses and worms reproduce, but they are not automatically quines: they interact with hosts, files, networks, and altered copies. Self-hosting compilers compile their own implementations, but need not print their source. These systems are cousins, not synonyms. The family resemblance is a system carrying enough structure to recreate or transform a description of itself.

That resemblance has serious consequences. Ken Thompson's classic lecture “Reflections on Trusting Trust” shows how self-reproduction in a compiler can preserve behavior that is absent from the visible source. The parlor trick has become a question about what evidence we trust.

8. Look back at the first question

How could a program know its own text?

It did not know its text in the way a file reader would. It carried a partial description, plus a general operation for turning that description into a complete one. The apparent circle was built from two ordinary, non-circular steps:

represent a value as source;
insert that representation into a source-shaped template.

The result refers to itself because we deliberately feed the template its own description.

You have reached the useful end of the course when the original program is no longer magic, but has not become dull. That is a fine place to leave a rabbit hole: solid ground under your feet, and much more tunnel ahead.

A final challenge ladder

Take these one at a time. Verify each rung before climbing to the next.

Annotate it. Add the comment # hello, future reader and make the comment part of the quine's output.
Give it a third line. Build a three-line quine whose middle line assigns the completed source to a second variable.
Make a descendant. Write maker.py, a program that is not a quine but prints the source of a different program that is. Then run:
```
python3 maker.py > child.py
python3 tools/verify.py child.py
python3 tools/verify.py maker.py
```
The child should pass and the maker should fail. You have changed the relation from “prints itself” to “prints something that prints itself.”

The hints and compact solutions are in answers/README.md.

Continue, if curiosity insists

Read gallery/README.md and annotate the JavaScript and C specimens.
Try a quine in a language you use every day.
Follow the deliberately short path through REFERENCES.md.

Then close the examples and build the two-line program once more.

Built from COURSE.md. The course and its specimens are available from the source repository under the MIT License.