Quine: Self replicating computer programs
Tags: quine, dna, selfrep, python
Published: 2024-07-12 04:14:29

A _[Quine](https://dev.to/darshan-as/quine-self-replicating-computer-programs-1c5g)_, (/_kwi:n_/ pronounced Kwine) is a self-replicating computer program, a digital life if you will. It takes no input and prints a copy of its own source code.

This may sound impossible, trivial, or completely uninteresting, depending on your temper and your knowledge of computer science. Trust me, it is not only not impossible, by the end of this post you'll have written your first Quine in Python.

The name "Quine" was coined by [Douglas Hofstadter](https://en.wikipedia.org/wiki/Douglas_Hofstadter), in his popular science book _[Gödel, Escher, Bach](https://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach)_, in honour of the philosopher [Willard Van Orman Quine](https://en.wikipedia.org/wiki/Willard_Van_Orman_Quine) (1908-2000), who made an extensive study of indirect self-reference, and in particular for the following paradox-producing expression, known as Quine's paradox:

> "Yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation.

The easiest way to write a Quine, of course, is to read the source file on the disk and print its contents. That may be done, but it is considered cheating; besides, the program might not know where the source file is, it may have access to only the compiled data, or the programming language may simply forbid that sort of operation.

---

## Your first Quine
Before we start,

> "If you have never done this, I urge you to try it on your own. The discovery of how to do it is a revelation that far surpasses any benefit obtained by being told how to do it."
> – Ken Thompson

That said, below is a step-by-step guide to writing your first Quine in Python:

Let's start with 2 pieces in our program.
- A variable to hold the string representation of the source code; call this the _Data_ part.
- A print statement to output the variable; call this the _Code_ part.

If we are to take an analogy with cellular biology (thanks to Douglas Hofstadter, again), think of a Quine as a cell with its own DNA. What I have called the _data_ would be the DNA, and the _code_ would be the rest of the cell. The cell is able to create a new cell using the DNA, and this involves, among other things, replicating the DNA itself. So the DNA (the data) contains all the necessary information for the replication, but without the cell (the code), or at least some other code to make the data live, it is a useless, inert, piece of data.

#### Step 1
Let's have a variable to store the _data_ part. And since we don't know the final source code yet, let's use `???` as a placeholder. Print statements will read the `data` to replicate itself, thereby acting as the _code_ part.
#
Python Input: [Try it online!](https://tio.run/##K6gsycjPM/7/PyWxJFHBVkHJ3t5eiaugKDOvRAMkpPn/PwA)
```python
data = "???"
print(data)
```
Output:
```python
# Output
???
```

Not quite what we're looking for, is it?

#### Step 2
We can't just print the contents of the `data` variable. We need to print the very act of declaring the variable itself. Let's add another `print` statement to do just that.

Python Input: [Try it online!](https://tio.run/##K6gsycjPM/7/PyWxJFHBVkHJ3t5eiaugKDOvREMdIqauowBiaForQITBnP//AQ)
```python
data = "???"
print('data =', data); print(data)
```
Output:
```python
data = ???
???
```

Sweet. It's starting to look structurally similar. But we still have those pesky `???` marks.

#### Step 3
Notice that the second line of output is `???`, which corresponds to the part of the source code we initially didn't know how to fill. This means, we can replace `???` to whatever the second line of source code becomes.

Python Input: [Try it online!](https://tio.run/##K6gsycjPM/7/PyWxJFHBVkGpoCgzr0RDHcJV11EAMTStFSDCYI4SF2E1//8DAA)
```python
data = "print('data =', data); print(data)"
print('data =', data); print(data)
```
Output:
```python
data = print('data =', data); print(data)
print('data =', data); print(data)
```

Almost there! But we seem to be missing the double quotes in line 1.

#### Step 4
In Python
- `str('hi')` outputs `hi`
- `repr('hi')` outputs `"hi"`, with quotes!

That's exactly what we need. Let's wrap `data` in the second line with `repr` to get those quotes.

Python Input: [Try it online!](https://tio.run/##K6gsycjPM/7/PyWxJFHBVkGpoCgzr0RDHcJV11EAMTStFSDCYI4SF7qaotSCIogcqsr//wE)
```python
data = "print('data =', data); print(data)"
print('data =', repr(data)); print(data)
```
Output:
```python
data = "print('data =', data); print(data)"
print('data =', data); print(data)
```

Yay! Line 1 in the source and output are an exact match.
But in doing so, we altered line 2 of the source!

#### Step 5
We can fix this by setting the value of the `data` variable to the updated _code_ part.

Python Input: [Try it online!](https://tio.run/##K6gsycjPM/7/PyWxJFHBVkGpoCgzr0RDHcJV11EoSi0o0gDxNDWtFSCSYJ4SF7Eq//8HAA)
```python
data = "print('data =', repr(data)); print(data)"
print('data =', repr(data)); print(data)
```
Output:
```python
data = "print('data =', repr(data)); print(data)"
print('data =', repr(data)); print(data)
```

Viola! There you have it. A valid Quine!

---

Although I've picked Python here, it's purely due to personal familiarity and brevity, there's nothing special about it. Quines are a general consequence of the so-called [Kleene's Fixed-Point theorem](https://en.wikipedia.org/wiki/Kleene%27s_recursion_theorem), which essentially means that a Quine (in fact, infinitely many) can be written in any Turing-complete programming language.

Almost all programming languages you've heard or used so far are Turing complete.
No, not HTML and CSS, they are not programming languages, let alone Turing-complete. Get over it.

One word of warning: this code/data distinction in Quines is pleasant and often helpful. It is not, however, completely valid in all circumstances

---

## Shortest Quine
In 1983, [Ken Thompson](https://en.wikipedia.org/wiki/Ken_Thompson) in his Turing Award acceptance speech, [Reflections on Trusting Trust](https://fermatslibrary.com/s/reflections-on-trusting-trust), presented the persistent compiler backdoor attack now known as the _Thompson hack_ or _Trusting trust attack_.
Although the paper itself is widely considered a seminal computer security work in its own right, he also made a peculiar statement about Quines.

>”In college, before video games, we would amuse ourselves by posing programming exercises. One of the favorites was to write the shortest self-reproducing program. Since this is an exercise divorced from reality, the usual vehicle was FORTRAN. Actually, FORTRAN was the language of choice for the same reason that three-legged races are popular.“
>– Ken Thompson

I claim no knowledge whatsoever of FORTRAN. So, here's the shortest Quine in Python:

Python:  [Try it online!](https://tio.run/##K6gsycjPM/7/P95WPd5Wtci6oCgzr0QjXlU1XlMdzonX/P8fAA)
```python
_='_=%r;print(_%%_)';print(_%_)
```

Looks esoteric, doesn't it? But don't let the compactness fool you. Let's decipher how we could have arrived at the shortest one ourselves.

#### Step 1
Let's start with

Python Input:  [Try it online!](https://tio.run/##K6gsycjPM/7/P0XBVkHd3t5enaugKDOvRCNF8/9/AA)
```Python
d = '???'
print(d)
```
Output:
```Python
???
```
#### Step 2
Let's add the entire source code from previous step into `d`.

Python Input: [Try it online!](https://tio.run/##K6gsycjPM/7/P0XBVkEdRNjb28fkFRRl5pVopGiqc8FY//8DAA)
```Python
d = 'd = ???\nprint(d)'
print(d)
```
Output:
```Python
d = ???
print(d)
```

If you noticed the output. We just want to replace `???` with the exact value of variable `d` and we are done!

#### Step 3
There's a nifty trick in Python to do this. The `str(d)` and `repr(d)` have a shortcut symbol of `%s` and `%r` respectively, and can be used like below:
```Python
print('Bruce Wayne is %s' % 'Batman') # outputs: Bruce Wayne is Batman
print('Bruce Wayne is %r' % 'Batman') # outputs: Bruce Wayne is 'Batman'
```

Using that, replace `???` with `%r` and substitute `d` onto itself in line 2.

Python Input: [Try it online!](https://tio.run/##K6gsycjPM/7/P0XBVkEdRKgWxeQVFGXmlWikaKpzQVkKqgopmv//AwA)
```Python
d = 'd = %r\nprint(d)'
print(d % d)
```
Output:
```Python
d = 'd = %r\nprint(d)'
print(d)
```

So close! We are just missing the `% d` in the second line.

#### Step 4
Let's add that `% d` in line 1 of the source.
But hold on `% d` would make Python look for a second value to be replaced.
To tell Python not to, we have to escape the `%` symbol. This can be done by adding another `%` in front.

Python Input: [Try it online!](https://tio.run/##K6gsycjPM/7/P0XBVkEdRKgWxeQVFGXmlWikKKiqKqRoqnPBuUDe//8A)
```Python
d = 'd = %r\nprint(d %% d)'
print(d % d)
```
Output:
```Python
d = 'd = %r\nprint(d %% d)'
print(d % d)
```

This is a valid Quine!

#### Step 5
Now, to make it short. Let's get rid of the newline character and combine both lines using `;`
```Python
d = 'd = %r;print(d %% d)';print(d % d)
```

Variables can start with underscores. A single underscore is in and of itself a valid variable. Let's replace `d` with `_`

```Python
_ = '_ = %r;print(_ %% _)';print(_ % _)
```

Get rid of all the spaces. 

Python: [Try it online!](https://tio.run/##K6gsycjPM/7/P95WPd5Wtci6oCgzr0QjXlU1XlMdzonX/P8fAA)
```Python
_='_=%r;print(_%%_)';print(_%_)
```
There you have it. The shortest Quine.

---

Here's an interesting one: An Error-Quine in Python. The source code is an error-like text that throws the exact error when executed.
The only difference being the output now goes to _stderr_ instead of _stdout_.

Python:  [Try it online!](https://tio.run/##K6gsycjPM/7/X0HBLTMnVUEpOT8lVa8kM19JRyEnMy9VwZBLQQG/XByXZ15Kal5JIlAmz7WoKL/ISqE0L7WiIDW5JDVFIRMs@f8/AA)
```python
  File "quine.py", line 1
    File "quine.py", line 1
    ^
IndentationError: unexpected indent
```

---

## Some more Quines

Ruby: [Try it online!](https://tio.run/##KypNqvz/v9hWqdhWtcC6oLSkWKFYVbVYCcYs5vr/HwA)
```Ruby
s="s=%p;puts s%%s";puts s%s
```

Lua: [Try it online!](https://tio.run/##yylN/P@/2Fap2Fa1sKAoM69Eo9gqLb8oNxHI0NRUwhTi@v8fAA)
```Lua
s="s=%qprint(s:format(s))"print(s:format(s))
```

Perl 5: [Try it online!](https://tio.run/##K0gtyjH9/1@l2LZQA0yoFmtaFxRl5pWkAfk6KkAeOp/r/38A)
```Perl
$s=q($s=q(%s);printf($s,$s););printf($s,$s);
```

JavaScript: [Try it online!](https://tio.run/##y0osSyxOLsosKNHNy09J/f@/2Fap2FY1yzo5P684PydVLyc/XaNYp1hTCUOE6/9/AA)
```JavaScript
s="s=%j;console.log(s,s)";console.log(s,s)
```

C: [Try it online!](https://tio.run/##S9ZNT07@/z83MTNPo1izuqAoM68kTaPYVglDRDVZtVjVUCVZx9hEp1jTulYJxvj/HwA)
```C
main(s){printf(s="main(s){printf(s=%c%s%1$c,34,s);}",34,s);}
```

Java: [Try it online!](https://tio.run/##y0osS9TNSsn@/z85J7G4WCGwuqA0KSczWaG4JLEESJXlZ6Yo5CZm5mkElxRl5qVHxyZqVkOYCsW2SuRoUk1WLVY1VEm2Dq4sLknN1csvLdErAMqVpGkU6xib6BRrWtfWKuGV5fr/HwA)
```Java
class Q{public static void main(String[]a){String s="class Q{public static void main(String[]a){String s=%c%s%1$c;System.out.printf(s,34,s);}}";System.out.printf(s,34,s);}}
```

Rust: [Try it online!](https://tio.run/##KyotLvn/Py1PITcxM09Ds7qgKDOvRFFDCSECE6o2sLKv1QGTmrW1SjqElWjW/v8PAA)
```Rust
fn main(){print!("fn main(){{print!({0:?},{0:?})}}","fn main(){{print!({0:?},{0:?})}}")}
```

HQ9+: [Try pasting it Online](https://hci.mkps.app/)
[Wiki page of HQ9+ language](https://esolangs.org/wiki/HQ9%2B)
```HQ9+
q
```

Quines are a fascinating topic and an art in their own right.
We'll go more in-depth and explore topics like **Intron**, **QuineRelay**, **MultiQuine**, and much more in the follow-up posts.

Stay tuned!

---

Sources and references:
- [Quine (computing)](https://en.wikipedia.org/wiki/Quine_(computing)), wiki page.
- [Quine: Self replicating computer programs](https://dev.to/darshan-as/quine-self-replicating-computer-programs-1c5g), self-referencing blog.
- [Self-replicating Python code | Quine](https://www.youtube.com/watch?v=a-zEbokJAgY), Youtube video by Lex Fridman.
- [Reflections on Trusting Trust](https://www.cs.cmu.edu/~rdriley/487/papers/Thompson_1984_ReflectionsonTrustingTrust.pdf), paper by Ken Thompson.
- [Gödel, Escher, Bach: An Eternal Golden Braid](https://www.goodreads.com/book/show/24113.G_del_Escher_Bach), book by Douglas R. Hofstadter.
- [Quines (self-replicating programs)](http://www.madore.org/~david/computers/quine.html), blog by David Madore.
- [The Quine Page](https://www.nyx.net/~gthompso/quine.htm), blog by Gary P. Thompson II.
- [Quine Programs](https://cs.lmu.edu/~ray/notes/quineprograms/), blog by Ray Toal.