Quine: Self replicating computer programs

Darshan A SDarshan A S
8 min read

A Quine, (/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, in his popular science book Gödel, Escher, Bach, in honour of the philosopher 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!

data = "???"
print(data)

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!

data = "???"
print('data =', data); print(data)

Output:

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!

data = "print('data =', data); print(data)"
print('data =', data); print(data)

Output:

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!

data = "print('data =', data); print(data)"
print('data =', repr(data)); print(data)

Output:

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!

data = "print('data =', repr(data)); print(data)"
print('data =', repr(data)); print(data)

Output:

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, 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 in his Turing Award acceptance speech, 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!

_='_=%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!

d = '???'
print(d)

Output:

???

Step 2

Let's add the entire source code from previous step into d.

Python Input: Try it online!

d = 'd = ???\nprint(d)'
print(d)

Output:

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:

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!

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

Output:

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!

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

Output:

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 ;

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 _

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

Get rid of all the spaces.

Python: Try it online!

_='_=%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!

  File "quine.py", line 1
    File "quine.py", line 1
    ^
IndentationError: unexpected indent

Some more Quines

Ruby: Try it online!

s="s=%p;puts s%%s";puts s%s

Lua: Try it online!

s="s=%qprint(s:format(s))"print(s:format(s))

Perl 5: Try it online!

$s=q($s=q(%s);printf($s,$s););printf($s,$s);

JavaScript: Try it online!

s="s=%j;console.log(s,s)";console.log(s,s)

C: Try it online!

main(s){printf(s="main(s){printf(s=%c%s%1$c,34,s);}",34,s);}

Java: Try it online!

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!

fn main(){print!("fn main(){{print!({0:?},{0:?})}}","fn main(){{print!({0:?},{0:?})}}")}

HQ9+: Try pasting it Online

Wiki page of HQ9+ language

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:

3
Subscribe to my newsletter

Read articles from Darshan A S directly inside your inbox. Subscribe to the newsletter, and don't miss out.

self-repquinednaPython

Written by

Darshan A S
Darshan A S

Tricking rocks into thinking, at Google.