Beyond the Source Code: Quines and Self-Replication
Ability to Recreate One’s Self
The “Beyond the Source Code” series of posts will explore source code beyond its use as a set of instructions that direct a process or set of processes. We will dive in topics such as readability, metaprogramming, quines, and many other topics that look at source code in a different light. The motivation for this series comes from the idea of making source code work for developers, rather than the developers having to work against the source code.
In the previous article we dove into readability and understanding of source code, with a focus on self-documenting code, comments, and documentation automation.
In this post, we will be exploring quines and self-replication. Quines are curious little programs that perform a single function — taking no input and only outputting a copy of themselves. They are an interesting topic of computer science as they have both philosophical and biological underpinnings. To understand quines, let’s take a step back and look at the concept of self-replicating programs and machines.
A World I Fear
A world I fear is one in which the following two statements hold true:
- The artificial intelligence (AI) singularity has happened, or the point when artificial intelligence matches that of humans.
- 3D printers who are capable of the above intelligence, and have the capability of producing other 3D printers.
If these two statements were to be true, we would have self-aware machines capable of producing other self-aware machines, similar to human reproduction. Even worse, human reproduction requires the interaction between two individuals, while a self-replicating and self-aware 3D printer could be completely autonomous and independent. A self-replicating machine would create a far-greater rate of exponential population growth than the rate at which humans reproduce since a single machine could recreate infinite number of copies. Couple this with machine-to-machine communication networks capable of high-speed throughput, massive amounts of data available on the internet, and our reliance on machines and you have a recipe for disaster.
Luckily, machines don’t hold a candle to human intelligence (yet) and 3D printers are still relatively simplistic in their capabilities.
Self-Reproduction
Self-reproducing machines and programs have been theorized since the beginning of computer science and programming. John Von Neumann in the 1940s, without the use of a computer, designed the first known example of self-reproducing automata. Automata are programs or machines that act independently based on a set of internal rules and external stimuli. The word “automata” comes from the Greek word αὐτόματα, meaning “self-making.”
This first example is known as Von Neumann’s “Universal Constructor.”
The Universal Constructor utilized the concept of cellular automata, which are grid-like maps of independent automata, or cells, that have a finite number of states and interact with each other. Capable of reproducing itself ad infinitum, the Universal Constructor had three components that lends to its reproductive behavior:
- A description for the machine, that defines a program capable of self-replication.
- The “Universal Constructor” itself that can read any description and construct the program it defines.
- A “Universal Copy” machine that is able to copy any description that it reads
Given these components, it can be seen how the recursive self-reproducing behavior is created. A program is created with all of the above components, it’s description is copied using the Universal Copier, and the Universal Constructor reads the description copy and builds another one. Rinse and repeat, and you end up with an army of self-reproducing cellular automata capable of producing their own armies of cellular automata. Scary to think, these self-reproducing programs were designed in the 1940s, 44 years before the release of the first Terminator and the idea of Skynet. Even more so, a few years before the first digital computer, the ENIAC.
Interested to read more about the Universal Constructor? Here is a paper on it.
Quines
Quines operate in the same context of self-reproducing automata, but are quite simpler. Similar to the three components that a Universal Constructor is comprised of, a Quine is made up of a program capable of outputting data (a Constructor and Copier of sorts), and a representation of the source code as data (the Description). Quines have a strict rule of not reading a copy of its own source code or requiring any input, and any quine that does so is known as a “cheating quine.” An example of a quine in Python (3.X) can be seen below:
_='_=%r;print (_%%_)';print (_%_)Notice the information density and size of this program — not a single smidgen of syntax goes to waste. Yet, this program does something philosophically remarkable. It is able to self-replicate and indirectly reference itself.
Quines are a wonderful study into the world of metaprogramming, and what source code is capable of beyond being an instruction set for a process. Given the challenge of optimizing information density, programmers will often compete in a style of programming known as “code golf” to create the shortest possible quines with the least amount of code. These compact lilliputian programs carry much more weight from a theoretical perspective than they do in purpose and looks.
The idea of being able to recreate self-replicating behavior in the smallest form possible is analogous to concepts in biology and “meaning of life” philosophical studies. Biologists have studied microscopic organisms capable of reproduction to understand life at the smallest scales, and philosophers continuously research the far corners of logic and understanding to understand the purpose of life. In fact, the concept of Quines was not discovered by a computer scientist, but derived from the work of a philosopher.
Willard Van Orman Quine
Willard Van Orman Quine was an American philosopher in the 20th century best known for his work in logic and set theory. His work on the idea of “indirect self-reference” is essentially recursion from a philosophical point of view, or an object referring to itself indirectly. Quine demonstrated indirect self-reference with the following paradox:
“yields falsehood when preceded by its quotation” yields falsehood when preceded by its quotation.
This became known as Quine’s paradox, and is the reason for the curious little programs’ name and origin.
An easier to understand example of indirect self-reference can be seen in the following sentence from this Wikipedia page.
"Is a sentence fragment" is a sentence fragment.
- The quoted sentence itself is a sentence fragment.
- The self-reference identifies the preceding quotation as a sentence fragment.
- The full sentence itself is grammatically and syntactically correct in the English language.
Isn’t it interesting how source code can go beyond the concepts of computer science and programming, and be used as reflections on philosophy and logic?
Taking the idea of self-replicating or self-referencing behavior, how can this be seen in computer programs today?
Worms
We started off this article with a musing about a scary topic (end of the world caused by machines), so lets end with another one. A worm is a type of malware that seeks to infect as many computers as possible through self-replication. Often targeting a weak host on a network, a worm will then use its first host to spread to others in the same network. Due to the exponential growth that programs are capable of achieving when undergoing self-replication, worms are extremely dangerous and will usually damage entire networks rather than a single machine.
An interesting example of a self-replicating worm is the Stuxnet worm of 2010. Designed to target industrial control systems (SCADA, supervisory control and data acquisition systems), Stuxnet is the likely culprit for causing a lot of damage to Iran’s nuclear program. As a worm, Stuxnet was capable of infinite replication to targeted host systems, and was therefore extremely difficult to stop and quarantine. Starting from an engineer’s computer, the worm quickly spread through centrifuges and industrial equipment, continuously replicating and causing damage along the way.
The concepts first visited in this article of machine takeovers and program replication start to become very real when worms are specifically designed to target industrial equipment and factory controls. This is where the line between the virtual and physical worlds really start to become blurred, when self-replicating non-tangible programs start to wreak havoc on physical world systems.
Let’s hope that self-replicating programs and behavior stay confined to the seemingly benign world of quines and universal constructors for years to come.
