Introduction

I want to show you a simple way to construct a quine. I’ll demonstrate using side-by-side Python, Java, and F# implementations. The approach is easily generalized to other languages.

After that, we’ll lightly refactor the first version of the quine, and then use the refactored version to prove Turing’s 1936 result that no algorithm can solve the halting problem.

What is a quine?

Here are two ways to define a quine.

If you have never written a quine, it can be a challenge. But it’s easy if you know the trick. I’m going to show you a four step recipe for writing your own quine. This will set the stage for an producing a readily understood explanation of one of the great results in computer science.

The code will appear on the right, where there are three tabs, one each for Python, Java, and F#. I hope it will be apparant that I’m doing the same thing in all three cases, modulo the different syntaxes.

Step 1

public class quine {
    public static void main(String[] args) {
        char q = (char) 34;
        String[] lines = {
        };
        for (int i = 0; i < 0; i++) {
            System.out.println(lines[i]);
        }
        for (int i = 0; i < 0; i++) {
            System.out.println(lines[i]);
        }
        for (int i = 0; i < 0; i++) {
            System.out.println(lines[i]);
        }
    }
}
q = chr(34)
lines = [
]
for k in range(0,0):
    print(lines[k])
for k in range(0,0):
    print(lines[k])
for k in range(0,0):
    print(lines[k])
let q = string(char 34)
let semicol = string(char 59)
let blank = string(char 32)
let lines = 
 [
 ]
for i in 0..0 do
   System.Console.WriteLine(lines.[i])
for i in 0..0 do
   System.Console.WriteLine(lines.[i])
for i in 0..0 do
   System.Console.WriteLine(lines.[i])

We declare some data:

We also set up three consecutive print loops that don’t yet do anything. The plan is to put some content into lines, and then update the ranges in the loops appropriately.

Aside: I will use the term “list” as a generic term when talking about the lines data structure. It is a list in the Python and F# implementations, but lines is an array in the Java implementation.

Step 2

let q = string(char 34)
let semicol = string(char 59)
let blank = string(char 32)
let lines = 
 [
 ]
for i in 0..0 do
   System.Console.WriteLine(lines.[i])
for i in 0..0 do
   System.Console.WriteLine(blank + q + lines.[i] + q + semicol)
for i in 0..0 do
   System.Console.WriteLine(lines.[i])

public class quine {
    public static void main(String[] args) {
        char q = (char) 34;
        String[] lines = {
        };
        for (int i = 0; i < 0; i++) {
            System.out.println(lines[i]);
        }
        for (int i = 0; i < 0; i++) {
            System.out.println(q + lines[i] + q + ',');
        }
        for (int i = 0; i < 0; i++) {
            System.out.println(lines[i]);
        }
    }
}
q = chr(34)
lines = [
]
for k in range(0,0):
    print(lines[k])
for k in range(0,0):
    print(q + lines[k] + q + ',')
for k in range(0,0):
    print(lines[k])

The plan is to use q to wrap quotes around anything printed via the middle print loop. We also want to append some punctuation to whatever is printed. The punctuation is whichever list item separator is used in the implementation language.

Note that we’re still not printing anything.

Step 3

let q = string(char 34)
let semicol = string(char 59)
let blank = string(char 32)
let lines = 
 [
 "let q = string(char 34)";
 "let semicol = string(char 59)";
 "let blank = string(char 32)";
 "let lines ="; 
 " [";
 " ]";
 "for i in 0..0 do";
 "   System.Console.WriteLine(lines.[i])";
 "for i in 0..0 do";
 "   System.Console.WriteLine(blank + q + lines.[i] + q + semicol)";
 "for i in 0..0 do"; 
 "   System.Console.WriteLine(lines.[i])";
 ]
for i in 0..0 do
   System.Console.WriteLine(lines.[i])
for i in 0..0 do
   System.Console.WriteLine(blank + q + lines.[i] + q + semicol)
for i in 0..0 do
   System.Console.WriteLine(lines.[i])

public class quine {
    public static void main(String[] args) {
        char q = (char) 34;
        String[] lines = {
"public class quine {",
"    public static void main(String[] args) {",
"        char q = (char) 34;",
"        String[] lines = {",
"        };",
"        for (int i = 0; i < 0; i++) {",
"            System.out.println(lines[i]);",
"        }",
"        for (int i = 0; i < 0; i++) {",
"            System.out.println(q + lines[i] + q + ',');",
"        }",
"        for (int i = 0; i < 0; i++) {",
"            System.out.println(lines[i]);",
"        }",
"    }",
"}",
        };
        for (int i = 0; i < 0; i++) {
            System.out.println(lines[i]);
        }
        for (int i = 0; i < 0; i++) {
            System.out.println(q + lines[i] + q + ',');
        }
        for (int i = 0; i < 0; i++) {
            System.out.println(lines[i]);
        }
    }
}
q = chr(34)
lines = [
"q = chr(34)",
"lines = [",
"]",
"for k in range(0,0):",
"   print(lines[k])",
"for k in range(0,0):",
"   print(q + lines[k] + q + ',')",
"for k in range(0,0):",
"   print(lines[k])",
]
for k in range(0,0):
   print(lines[k])
for k in range(0,0):
   print(q + lines[k] + q + ',')
for k in range(0,0):
   print(lines[k])

Next we populate lines. Here’s how:

Results are on the right; we are still not printing anything.

Notice that all three languages allow you to insert the element separator after the last element in a list. This is convenient. Otherwise we would have to adjust the middle print loop to treat the last element differently from the rest.

Step 4

let q = string(char 34)
let semicol = string(char 59)
let blank = string(char 32)
let lines = 
 [
 "let q = string(char 34)";
 "let semicol = string(char 59)";
 "let blank = string(char 32)";
 "let lines ="; 
 " [";
 " ]";
 "for i in 0..4 do";
 "   System.Console.WriteLine(lines.[i])";
 "for i in 0..11 do";
 "   System.Console.WriteLine(blank + q + lines.[i] + q + semicol)";
 "for i in 5..11 do"; 
 "   System.Console.WriteLine(lines.[i])";
 ]
for i in 0..4 do
   System.Console.WriteLine(lines.[i])
for i in 0..11 do
   System.Console.WriteLine(blank + q + lines.[i] + q + semicol)
for i in 5..11 do
   System.Console.WriteLine(lines.[i])

public class quine {
    public static void main(String[] args) {
        char q = (char) 34;
        String[] lines = {
"public class quine {",
"    public static void main(String[] args) {",
"        char q = (char) 34;",
"        String[] lines = {",
"        };",
"        for (int i = 0; i < 4; i++) {",
"            System.out.println(lines[i]);",
"        }",
"        for (int i = 0; i < 16; i++) {",
"            System.out.println(q + lines[i] + q + ',');",
"        }",
"        for (int i = 4; i < 16; i++) {",
"            System.out.println(lines[i]);",
"        }",
"    }",
"}",
        };
        for (int i = 0; i < 4; i++) {
            System.out.println(lines[i]);
        }
        for (int i = 0; i < 16; i++) {
            System.out.println(q + lines[i] + q + ',');
        }
        for (int i = 4; i < 16; i++) {
            System.out.println(lines[i]);
        }
    }
}
q = chr(34)
lines = [
"q = chr(34)",
"lines = [",
"]",
"for k in range(0,2):",
"   print(lines[k])",
"for k in range(0,9):",
"   print(q + lines[k] + q + ',')",
"for k in range(2,9):",
"   print(lines[k])",
]
for k in range(0,2):
   print(lines[k])
for k in range(0,9):
   print(q + lines[k] + q + ',')
for k in range(2,9):
   print(lines[k])

The only thing left to do is to adjust the loop indices to actually print something. We pick the indices so that

We have to to adjust the indices in two places: in the actual working loops (the code), and in the corresponding quoted strings (the data).

Done. We now have working quines.

Brevity, the soul of wit?

main = (\s -> putStr s >> print s)“main = (\s -> putStr s >> print s)”

If you search the internet you can find many quines. Often they are brief, yet hard to get your head around. The one on the right, written in Haskell, is one of my favorites.

Our quines are bloated by comparison. But our method of building quines has two nice features. The first is that it is easy to understand. With a bit of thought, you understand exactly how the quines work. It’s mechanical. The second nice features is that we can extend our approach to pack additional code into the quine, while retaining the quine property. We’ll see that next.

The first step will be to refactor. We’ll put the loops inside a function, and abstract out the loop indices. The code will get slightly longer, but the payoff will be worth it.

A refactoring

public class quine {
    static String[] lines = {
"public class quine {",
"    static String[] lines = {",
"    };",
"    static String source(String[] lines) {",
"        char q = (char) 34;",
"        char nl = (char) 10;",
"        int edge = 2;",
"        int count = 24;",
"        StringBuffer buff = new StringBuffer();",
"        for (int i = 0; i < edge; i++) {",
"            buff.append(lines[i]).append(nl);",
"        }",
"        for (int i = 0; i < count; i++) {",
"            buff.append(q + lines[i] + q + ',').append(nl);",
"        }",
"        for (int i = edge; i < count; i++) {",
"            buff.append(lines[i]).append(nl);",
"        }",
"        return buff.toString().trim();",
"    }",
"    public static void main(String[] args) {",
"        System.out.println(source(lines));",
"    }",
"}",
    };
    static String source(String[] lines) {
        char q = (char) 34;
        char nl = (char) 10;
        int edge = 2;
        int count = 24;
        StringBuffer buff = new StringBuffer();
        for (int i = 0; i < edge; i++) {
            buff.append(lines[i]).append(nl);
        }
        for (int i = 0; i < count; i++) {
            buff.append(q + lines[i] + q + ',').append(nl);
        }
        for (int i = edge; i < count; i++) {
            buff.append(lines[i]).append(nl);
        }
        return buff.toString().trim();
    }
    public static void main(String[] args) {
        System.out.println(source(lines));
    }
}
lines = [
"lines = [",
"]",
"def source():",
"  q = chr(34)",
"  nl = chr(10)",
"  edge = 1",
"  count = 16",
"  code = ''",
"  for k in range(0,edge):",
"      code += lines[k]+nl",
"  for k in range(0,count):",
"      code += q+lines[k]+q+','+nl",
"  for k in range(edge,count):",
"      code += lines[k]+nl",
"  return(code.strip())",
"print(source())",
]
def source():
  q = chr(34)
  nl = chr(10)
  edge = 1
  count = 16
  code = ''
  for k in range(0,edge):
      code += lines[k]+nl
  for k in range(0,count):
      code += q+lines[k]+q+','+nl
  for k in range(edge,count):
      code += lines[k]+nl
  return(code.strip())
print(source())
let lines =
 [
 "let lines =";
 " [";
 " ]";
 "let source =";
 "    let edge = 2";
 "    let count = 20";
 "    let q = string(char 34)";
 "    let semicol = string(char 59)";
 "    let blank = string(char 32)";
 "    let nl = string(char 10)";
 "    let mutable buff = System.String.Empty";
 "    for i in 0..edge-1 do";
 "        buff <- (buff + lines.[i] + nl)";
 "    for i in 0..count-1 do";
 "        buff <- (buff + blank + q + lines.[i] + q + semicol + nl)";
 "    for i in edge..count-2 do";
 "        buff <- (buff + lines.[i] + nl)";
 "    buff <- (buff + lines.[count-1])";
 "    buff";
 "System.Console.WriteLine(source)";
 ]
let source =
    let edge = 2
    let count = 20
    let q = string(char 34)
    let semicol = string(char 59)
    let blank = string(char 32)
    let nl = string(char 10)
    let mutable buff = System.String.Empty
    for i in 0..edge-1 do
        buff <- (buff + lines.[i] + nl)
    for i in 0..count-1 do
        buff <- (buff + blank + q + lines.[i] + q + semicol + nl)
    for i in edge..count-2 do
        buff <- (buff + lines.[i] + nl)
    buff <- (buff + lines.[count-1])
    buff
System.Console.WriteLine(source)

We introduce some new variables:

The print loops have been replaced by the source function, which does not print the source, but rather returns it as a string.

The programs are still quines, but they are something more. They are programs which can access their own source code by simply calling a function.

What makes this style of quine more useful than the Haskell one-liner is extensibility. We can inject additional code, say another function. By also injecting the new code’s string representation into lines and adjusting count accordingly, the extended program will still have access to its own source code. We can pack arbitrary functionality into a program with access to its own code.

Aside: Quines can be finicky, and there are various accounting details in the refactored code that I don’t want to waste too much time on. For instance, in the F# implementation, count is one more than the length of lines, in the Java and Python code count is the length of lines. I probably did that because F# ranges [1..n] include their endpoints, whereas Python range(1,n) does not include n. Whatever. Once done, I decided to let it slide because making changes to quines is tedious and error prone.

The Halting Problem

// G: a solution to the Goldbach conjecture,
// if you happen to have a halting oracle.
even = 2
while True:
  label(A): even += 2
  primes = primesLessThan(even)
  for p,q in zip(primes, primes):
    if p+q == even: goto(A)
  return even

In 1936, Alan Turing proved that there is no algorithm which can decide whether an arbitrary program terminates. Turing used a diagonalization argument. We’re going to take a different approach, one I believe is easier to understand.

But first let’s get some context. Suppose there were a halting oracle, a program able to successfully decide whether any other program halts. Such a program would be amazingly useful. We could use it to easily solve very hard problems, by setting up potentially infinite searches which never have to be carried out.

Consider the still unresolved Goldbach conjecture that every even number greater than 2 can be expressed as the sum of two primes. Given a halting oracle, we could use something along the lines of G, on the right, to decide whether the Goldbach conjecture is true.

G is constructed so that it will halt if and only if the Goldbach conjecture is false. If G halts, it will return an even number greater than 2 which is not the sum of two primes. If there is no such number, G will search for one in vain.

G might run forever, but if we had a halting oracle we would not bother to run G at all. We would instead feed G to the oracle, which would tell us whether or not it halts, and so determine the truth or falsity of the conjecture. The oracle is magical. It knows the whether a potentially infinite search terminates without having to actually perform the search. A halting oracle would be a knowledge factory; it would be better even than polynomial time solution to an np-complete problem.

By the way, the G program is written in Objective Blub++, a trending language in hypothetical worlds where there are halting oracles. Goto is not considered harmful in those worlds.

We have already constructed all the machinery needed to prove that there are no halting oracles. So let’s wrap it up.

Profit!

q = chr(34)
nl = chr(10)
edge = 5
count = 20 
lines = [
"q = chr(34)",
"nl = chr(10)",
"edge = 5",
"count = 20",
"lines = [",
"]",
"def refuteHaltingOracle():",
"    if haltz(source()):",
"        while True: pass",
"    else: return 'The oracle predicted I would not halt!'",
"def source():",
"  code = ''",
"  for k in range(0,edge):",
"      code += lines[k]+nl",
"  for k in range(0,count):",
"      code += q+lines[k]+q+','+nl",
"  for k in range(edge,count):",
"      code += lines[k]+nl",
"  return(code)",
"refuteHaltingOracle()",
]
def refuteHaltingOracle():
    if haltz(source()):
        while True: pass
    else: return 'The oracle predicted I would not halt!'
def source():
  code = ''
  for k in range(0,edge):
      code += lines[k]+nl
  for k in range(0,count):
      code += q+lines[k]+q+','+nl
  for k in range(edge,count):
      code += lines[k]+nl
  return(code)
refuteHaltingOracle()
let lines =
 [
 "let lines =";
 " [";
 " ]";
 "let source =";
 "    let edge = 2";
 "    let count = 20";
 "    let q = string(char 34)";
 "    let semicol = string(char 59)";
 "    let blank = string(char 32)";
 "    let nl = string(char 10)";
 "    let mutable buff = System.String.Empty";
 "    for i in 0..edge-1 do";
 "        buff <- (buff + lines.[i] + nl)";
 "    for i in 0..count-1 do";
 "        buff <- (buff + blank + q + lines.[i] + q + semicol + nl)";
 "    for i in edge..count-2 do";
 "        buff <- (buff + lines.[i] + nl)";
 "    buff <- (buff + lines.[count-1])";
 "    buff";
 "System.Console.WriteLine(source)";
 ]
let source =
    let edge = 2
    let count = 20
    let q = string(char 34)
    let semicol = string(char 59)
    let blank = string(char 32)
    let nl = string(char 10)
    let mutable buff = System.String.Empty
    for i in 0..edge-1 do
        buff <- (buff + lines.[i] + nl)
    for i in 0..count-1 do
        buff <- (buff + blank + q + lines.[i] + q + semicol + nl)
    for i in edge..count-2 do
        buff <- (buff + lines.[i] + nl)
    buff <- (buff + lines.[count-1])
    buff
System.Console.WriteLine(source)
public class turing {
    static String[] lines = {
            "public class turing {",
            "    static String[] lines = {",
            "    };",
            "static void refuteHaltingOracle(){",
            "     if (haltz(source(lines))) {",
            "          while (true) {System.out.println(1337);}",
            "     }",
            "     else {System.out.println(1337);};",
            "}",
            "    static String source(String[] lines) {",
            "        char q = (char) 34;",
            "        char nl = (char) 10;",
            "        int edge = 2;",
            "        int count = 30;",
            "        StringBuffer buff = new StringBuffer();",
            "        for (int i = 0; i < edge; i++) {",
            "            buff.append(lines[i]).append(nl);",
            "        }",
            "        for (int i = 0; i < count; i++) {",
            "            buff.append(q + lines[i] + q + ',').append(nl);",
            "        }",
            "        for (int i = edge; i < count; i++) {",
            "            buff.append(lines[i]).append(nl);",
            "        }",
            "        return buff.toString().trim();",
            "    }",
            "    public static void main(String[] args) {",
            "        refuteHaltingOracle();",
            "    }",
            "}",
    };
    static void refuteHaltingOracle(){
      if (haltz(source(lines))) {
          while (true) {System.out.println(1337);}
      }
      else {System.out.println(1337);};
    }
    static String source(String[] lines) {
        char q = (char) 34;
        char nl = (char) 10;
        int edge = 2;
        int count = 30;
        StringBuffer buff = new StringBuffer();
        for (int i = 0; i < edge; i++) {
            buff.append(lines[i]).append(nl);
        }
        for (int i = 0; i < count; i++) {
            buff.append(q + lines[i] + q + ',').append(nl);
        }
        for (int i = edge; i < count; i++) {
            buff.append(lines[i]).append(nl);
        }
        return buff.toString().trim();
    }
    public static void main(String[] args) {
        refuteHaltingOracle();
    }
}

Suppose by way of contradiction that we have a halting oracle, haltz. It takes a single string argument, the source code of the program whose termination is to be decided. It returns a boolean, true if the input program is claimed to halt, false otherwise.

We will use our quine machinery to produce a program which haltz cannot handle correctly, and so demonstrate that haltz is not actually a halting oracle.

What we do is construct a program, let’s call it Turing. Turing calls the oracle and asks, “Do I halt?”. If the oracle replies that Turing halts, Turing responds by going into an infinite loop. If the oracle predicts that Turing does not halt, then Turing halts.

Turing is able to stump the oracle because Turing has access to its own source code, so it can call the oracle, see the oracle’s response, and then do the opposite. The counter-example demonstrates that the oracle cannot correctly decide the termination of every program.

Notice how the Turing program was constructed. We took the quine from the refactoring step, and injected one additional function, refuteHaltingOracle. The new code was inserted twice, once as code, and once as strings in lines. Changing lines in turn required that count be updated. Finally, the last line of the program was updated; rather than printing the output of a call to source(), the program executes refuteHaltingOracle().

As a point of fact, the Turing programs are notional. None would compile/execute as written because I treated the haltz program as if it were part of the core language, rather than importing it or some such, and so further complicating the code. I leave it an an exercise for the reader to insert additional code to illustrate the invocation of an external program while preserving the quine property.

A final observation: the illustrated method of quine construction is very flexible. Essentially anything can be packed into a quine shell that gives the resultant program access to its own code. A possible use is writing self-replicating programs. But I think I’ll halt now.

@drcabana

Get the source

You can grab the source from drcabana/build-a-quine.

This post was latent in a presentation I gave at TriClojure some time ago, concerning polyquines. A polyquine is a polyglot higher-order quine, say a Haskell program that emits a Clojure program that emits a Ruby program that … that eventually emits the original Haskell program.

I wrote some Clojure code to generate polyquines, polyq. It worked, but it was difficult to fully wrap my head around, no matter how hard I tried. I found the standard quine much simpler to grasp, and thought it would be fun to share.

The use of a quine to illustrate the impossiblity of deciding the halting problem is something I first read about in Gregory Chiatin’s The Unknowable.