wiki.secretGeekWhat Links Here?
Outbound Links
- Willard Van Orman Quine
- unbounded recursion
- try it online here
- Wikipedia: Quine (computing)
- The Little Schemer
- Esolang, the esoteric programming languages wiki
- Esolang: Quine
- Esolang: Iterating Quine
- Quine Relay
- Esolang Muriel
- Codegolf: Quines
- QuineDB is a quine that is also a key/value store.
- ⭐ unbounded-recursion
- ⭐ how-to-become-a-programmer
- ⭐ esoteric-programming-concepts
- ⭐ quine-programming-language
Quine
A Quine is a program that produces, as output, its own source code.
More formally: A Quine is a non-empty program, that takes no input, and produces, as its only output, a copy of its own source code.
The name was coined by Douglas Hoftstader, and named after Willard Van Orman Quine.
But here is the thing about Quines: reading about them is not where the fun lies. Reading examples of Quines is also not very fun. The real fun of Quines is only revealed when you attempt to produce one for yourself.
And it's best if you don't read too much about it first.
Just attempt it.
Watch what happens as the problems increase, and you eventually get stuck. Then see if you can think your way out of the problem. It's a fun and possibly mind-bending exercise, but readily accessible to any beginning programmer.
Now go and write a Quine. I can wait. I'll be here making a jelly sandwich.
This space reserved for Jelly Stains.
How did you go? Did you build a Quine?
Or did you get stuck?
Assuming you either did not build a Quine, or you got stuck, let's step through the process of learning to build a Quine.
My examples are going to be in C# because it's the main language I use.
First we need to look at an "empty" C# program. Here is what it looks like:
using System;
namespace Quine
{
class Program
{
static void Main()
{
// Program goes here.
}
}
}
This code, the starting code, is what is commonly referred to as "boilerplate". It's the chaff that is always included in every program. Different languages have different amounts of boilerplate.
You'll see in the code that follows that the boilerplate code has a big impact on the length of the Quine. Most of the Quine is dedicated to reproducing the boilerplate.
This leads to an interesting paradox.
The more "boilerplate" a language has, the lengthier a Quine will be in that language. Yet, a language with more boilerplate will make it easier to demonstrate the core issues of writing a Quine.
So the real reason I chose C# is because it has a lot of boilerplate chaff. Thus the difficulties and challenges of writing a Quine will become very obvious as we move forward. Well, that's the theory, let's see how we go.
One more thing to mention before we get started. It's against the rules to write a program that simply reads the source code off the disk. For example, this would not be a valid solution:
using System;
namespace CheatingQuine
{
class Program
{
static void Main()
{
System.Console.WriteLine(System.IO.File.ReadAllText(@"..\..\Program.cs"));
}
}
}
So if you used any technique along those lines, please go back and try again.
Okay. Now we can begin by writing a program that writes the empty program above.
After a bit of tappity-tap on the keyboard you should end up with something like this:
using System;
namespace Quine
{
class Program
{
static void Main()
{
Console.WriteLine("using System;");
Console.WriteLine("namespace Quine");
Console.WriteLine("{");
Console.WriteLine(" class Program");
Console.WriteLine(" {");
Console.WriteLine(" static void Main()");
Console.WriteLine(" {");
Console.WriteLine(" // Program goes here.");
Console.WriteLine(" }");
Console.WriteLine(" }");
Console.WriteLine("}");
}
}
}
Very good. We compile and run our program, and it produces the empty program from the first code example above.
That's good. Now we need to enhance our program so that instead of writing "// Program goes here" it writes out all of those Console.WriteLine statements.
And here is where it first begins to get tricky.
First you write something like this:
using System;
namespace Quine
{
class Program
{
static void Main()
{
Console.WriteLine("using System;");
Console.WriteLine("namespace Quine");
Console.WriteLine("{");
Console.WriteLine(" class Program");
Console.WriteLine(" {");
Console.WriteLine(" static void Main()");
Console.WriteLine(" {");
Console.WriteLine(" Console.WriteLine("using System;");");
Console.WriteLine(" Console.WriteLine("namespace Quine");");
Console.WriteLine(" Console.WriteLine("{");");
Console.WriteLine(" Console.WriteLine(" class Program");");
Console.WriteLine(" Console.WriteLine(" {");");
Console.WriteLine(" Console.WriteLine(" static void Main()");");
Console.WriteLine(" Console.WriteLine(" {");");
Console.WriteLine(" Console.WriteLine(" // Program goes here.");");
Console.WriteLine(" Console.WriteLine(" }");");
Console.WriteLine(" Console.WriteLine(" }");");
Console.WriteLine(" Console.WriteLine("}");");
Console.WriteLine(" }");
Console.WriteLine(" }");
Console.WriteLine("}");
}
}
}
...but you find it won't compile, because the double quotes inside double quotes are confusing to the compiler.
You need to "escape" the double quotes. This is a common issue in all programming languages.
In C# you do this by putting a slash before the quote symbol.
So you update your program to be like this:
using System;
namespace Quine
{
class Program
{
static void Main()
{
Console.WriteLine("using System;");
Console.WriteLine("namespace Quine");
Console.WriteLine("{");
Console.WriteLine(" class Program");
Console.WriteLine(" {");
Console.WriteLine(" static void Main()");
Console.WriteLine(" {");
Console.WriteLine(" Console.WriteLine(\"using System;\");");
Console.WriteLine(" Console.WriteLine(\"namespace Quine\");");
Console.WriteLine(" Console.WriteLine(\"{\");");
Console.WriteLine(" Console.WriteLine(\" class Program\");");
Console.WriteLine(" Console.WriteLine(\" {\");");
Console.WriteLine(" Console.WriteLine(\" static void Main()\");");
Console.WriteLine(" Console.WriteLine(\" {\");");
Console.WriteLine(" Console.WriteLine(\" // Program goes here.\");");
Console.WriteLine(" Console.WriteLine(\" }\");");
Console.WriteLine(" Console.WriteLine(\" }\");");
Console.WriteLine(" Console.WriteLine(\"}\");");
Console.WriteLine(" }");
Console.WriteLine(" }");
Console.WriteLine("}");
}
}
}
And now the program will compile at least.
But when you run it, it doesn't output the current program. It outputs the earlier version of the program.
It outputs a pesky "// Program goes here." comment where it is supposed to output a whole bunch of Console.WriteLines.
Now you're coming close to the real heart of the problem.
Let's press on, as if we haven't noticed the impending crisis.
We replace this line:
Console.WriteLine(" Console.WriteLine(\" // Program goes here.\");");
...with another series of Console.WriteLines, this time to write all of the Console.WriteLines we added during the previous step.
After much typing we eventually produce a program like this:
using System;
namespace Quine
{
class Program
{
static void Main()
{
Console.WriteLine("using System;");
Console.WriteLine("namespace Quine");
Console.WriteLine("{");
Console.WriteLine(" class Program");
Console.WriteLine(" {");
Console.WriteLine(" static void Main()");
Console.WriteLine(" {");
Console.WriteLine(" Console.WriteLine(\"using System;\");");
Console.WriteLine(" Console.WriteLine(\"namespace Quine\");");
Console.WriteLine(" Console.WriteLine(\"{\");");
Console.WriteLine(" Console.WriteLine(\" class Program\");");
Console.WriteLine(" Console.WriteLine(\" {\");");
Console.WriteLine(" Console.WriteLine(\" static void Main()\");");
Console.WriteLine(" Console.WriteLine(\" {\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\"using System;\\");\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\"namespace Quine\\");\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\"{\\");\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\" class Program\\");\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\" {\\");\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\" static void Main()\\");\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\" {\\");\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\" // Program goes here.\\");\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\" }\\");\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\" }\\");\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\"}\\");\");");
Console.WriteLine(" Console.WriteLine(\" }\");");
Console.WriteLine(" Console.WriteLine(\" }\");");
Console.WriteLine(" Console.WriteLine(\"}\");");
Console.WriteLine(" }");
Console.WriteLine(" }");
Console.WriteLine("}");
}
}
}
By this stage, the crisis is beginning to be obvious.
But let's ignore that for a moment longer.
The program above does not compile, because we have not correctly escaped our strings.
We now learn that not only do we need to escape embedded double quotes, we also need to escape embedded back-slash characters. So we place an extra back-slash before every back-slash in our innermost strings, and we place extra back-slash characters before every double quote as well.
All of this string-escaping business is beginning to get very tedious. But finally we've got something that will compile and run. But what a monster!
using System;
namespace Quine
{
class Program
{
static void Main()
{
Console.WriteLine("using System;");
Console.WriteLine("namespace Quine");
Console.WriteLine("{");
Console.WriteLine(" class Program");
Console.WriteLine(" {");
Console.WriteLine(" static void Main()");
Console.WriteLine(" {");
Console.WriteLine(" Console.WriteLine(\"using System;\");");
Console.WriteLine(" Console.WriteLine(\"namespace Quine\");");
Console.WriteLine(" Console.WriteLine(\"{\");");
Console.WriteLine(" Console.WriteLine(\" class Program\");");
Console.WriteLine(" Console.WriteLine(\" {\");");
Console.WriteLine(" Console.WriteLine(\" static void Main()\");");
Console.WriteLine(" Console.WriteLine(\" {\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\\\\"using System;\\\\\");\\\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\\\\"namespace Quine\\\\\");\\\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\\\\"{\\\\\");\\\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\\\\" class Program\\\\\");\\\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\\\\" {\\\\\");\\\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\\\\" static void Main()\\\\\");\\\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\\\\" {\\\\\");\\\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\\\\" // Program goes here.\\\\\");\\\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\\\\" }\\\\\");\\\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\\\\" }\\\\\");\\\");");
Console.WriteLine(" Console.WriteLine(\" Console.WriteLine(\\\\\"}\\\\\");\\\");");
Console.WriteLine(" Console.WriteLine(\" }\");");
Console.WriteLine(" Console.WriteLine(\" }\");");
Console.WriteLine(" Console.WriteLine(\"}\");");
Console.WriteLine(" }");
Console.WriteLine(" }");
Console.WriteLine("}");
}
}
}
The crisis can no longer be avoided. This monsterous program now contains four versions of itself, nested 3 levels deep.
If we keep going in this direction we'll end up with infinitely nested code and we'll still only be outputing the code from our last iteration.
The thinking that got us into this mess is not going to be sufficient to get us out of the mess!
What is the magic trick at the heart of a Quine?
We need to re-think our whole approach.
We stand back and look at the code and start to wonder what can be done.
We observe that there's a lot of repetition. Now we know that the way programmers deal with repetition is by using loops. So let's think about putting a loop in there.
We want a loop something like this pseudo code:
for each line of code: Console.WriteLine(code);
Let's head back to the drawing board, starting over from the beginning, but using this loop idea.
First we'll write a program that outputs the empty program (from step 1).
using System;
namespace Quine
{
class Program
{
static string[] program = new string[] {
"using System;",
"namespace Quine",
"{",
" class Program",
" {",
" static void Main()",
" {",
" // Program goes here.",
" }",
" }",
"}",
};
static void Main()
{
for (int i = 0; i < program.Length; i++)
{
Console.WriteLine(program[i]);
}
}
}
}
Already our Quine is looking a lot healthier!
For the next iteration we need to update the array of strings, so that it will output this bit:
for (int i = 0; i < program.Length; i++)
{
Console.WriteLine(program[i]);
}
And now we're a lot closer to done (although the final and trickiest part remains)
using System;
namespace Quine
{
class Program
{
static string[] program = new string[] {
"using System;",
"namespace Quine",
"{",
" class Program",
" {",
" static void Main()",
" {",
" for (int i = 0; i < program.Length; i++)",
" {",
" Console.WriteLine(program[i]);",
" }",
" }",
" }",
"}",
};
static void Main()
{
for (int i = 0; i < program.Length; i++)
{
Console.WriteLine(program[i]);
}
}
}
}
That program compiles and runs, but there's still one crucial thing missing!
It doesn't output the internal array of strings (the 'program' variable).
Now we're heading to the really interesting bit.
Can we produce that output -- the program within a program -- without ending up in an unbounded recursion, like last time?
Let's not run head-first into the problem. Let's sidle up to it slowly, as we have been doing throughout this exercise.
First let's output just the outside part of the variable declaration. Let's add this bit in:
static string[] program = new string[] {
};
Here we go:
using System;
namespace Quine
{
class Program
{
static string[] program = new string[] {
"using System;",
"namespace Quine",
"{",
" class Program",
" {",
" static string[] program = new string[] {",
" };",
" static void Main()",
" {",
" for (int i = 0; i < program.Length; i++)",
" {",
" Console.WriteLine(program[i]);",
" }",
" }",
" }",
"}",
};
static void Main()
{
for (int i = 0; i < program.Length; i++)
{
Console.WriteLine(program[i]);
}
}
}
}
Now we're approaching a kind of barrier or limit. But is the barrier able to be pierced?
You probably know that of course it is.
What we need to do is to create an "inner" loop.
As we start to create our inner loop, you might have a fear in the back of your mind: "Will one inner loop be enough?" Or will we end up back in the same problem we were in before: will we need an infinite number of inner loops?
In our inner loop we want to print the code again, but this time as a "quoted" piece of code.
For example, where we previously output:
using System;
This time we want to output:
"using System;",
In other words there's some spaces, and a double quote at the front, and then a double-quote and a comma at the end.
using System;
namespace Quine
{
class Program
{
static string[] program = new string[] {
"using System;",
"namespace Quine",
"{",
" class Program",
" {",
" static string[] program = new string[] {",
" };",
" static void Main()",
" {",
" for (int i = 0; i < program.Length; i++)",
" {",
" Console.WriteLine(program[i]);",
" }",
" }",
" }",
"}",
};
static void Main()
{
for (int i = 0; i < program.Length; i++)
{
Console.WriteLine(program[i]);
if (i == 5)
{
for (int j = 0; j < program.Length; j++)
{
Console.WriteLine(" \"" + program[j] + "\",");
}
}
}
}
}
}
That now does an adequate job of producing the program as it stood only 5 minutes ago, including all of the quoted code. But it doesn't produce the program as it now stands, because the new piece of code needs to be written into the array.
But look at the (familiar) compilation errors we get into when we naively add the new code to the array...
using System;
namespace Quine
{
class Program
{
static string[] program = new string[] {
"using System;",
"namespace Quine",
"{",
" class Program",
" {",
" static string[] program = new string[] {",
" };",
" static void Main()",
" {",
" for (int i = 0; i < program.Length; i++)",
" {",
" Console.WriteLine(program[i]);",
" if (i == 5)",
" {",
" for (int j = 0; j < program.Length; j++)",
" {",
" Console.WriteLine(" \"" + program[j] + "\",");", ← Compile error here!
" }",
" }",
" }",
" }",
" }",
"}",
};
static void Main()
{
for (int i = 0; i < program.Length; i++)
{
Console.WriteLine(program[i]);
if (i == 5)
{
for (int j = 0; j < program.Length; j++)
{
Console.WriteLine(" \"" + program[j] + "\",");
}
}
}
}
}
}
Now we know from our initial experience exactly what is going wrong. We need to double our backslashes, and add backslashes before our double quotes. So we quickly change this:
" Console.WriteLine(" \"" + program[j] + "\",");",
into this:
" Console.WriteLine(\" \\\"\" + program[j] + \"\\\",\");",
Now we're tantalizingly close.
The only remaining problem is that our inner loop doesn't quite perform all of the escaping it needs to perform.
We update this line:
Console.WriteLine(" \"" + program[j] + "\",");
To this:
Console.WriteLine(" \"" + program[j].Replace("\\", "\\\\").Replace("\"", "\\\"") + "\", ");
Then update the quoted code from:
" Console.WriteLine(\" \\\"\" + program[j] + \"\\\",\");",
To:
" Console.WriteLine(\" \\\"\" + program[j].Replace(\"\\\\\", \"\\\\\\\\\").Replace(\"\\\"\", \"\\\\\\\"\") + \"\\\", \");",
(Yes that's up to 9 backslashes in a row!)
...producing a final working Quine that looks like (and produces) this:
using System;
namespace Quine
{
class Program
{
static string[] program = new string[] {
"using System;",
"namespace Quine",
"{",
" class Program",
" {",
" static string[] program = new string[] {",
" };",
" static void Main(string[] args)",
" {",
" for (int i = 0; i < program.Length; i++)",
" {",
" Console.WriteLine(program[i]);",
" if (i == 5)",
" {",
" for (int j = 0; j < program.Length; j++)",
" {",
" Console.WriteLine(\" \\\"\" + program[j].Replace(\"\\\\\", \"\\\\\\\\\").Replace(\"\\\"\", \"\\\\\\\"\") + \"\\\", \");",
" }",
" }",
" }",
" }",
" }",
"}",
};
static void Main(string[] args)
{
for (int i = 0; i < program.Length; i++)
{
Console.WriteLine(program[i]);
if (i == 5)
{
for (int j = 0; j < program.Length; j++)
{
Console.WriteLine(" \"" + program[j].Replace("\\", "\\\\").Replace("\"", "\\\"") + "\", ");
}
}
}
}
}
}
And we're done.
You can try it online here.
For extra credit...
Now that we're done, there's three other things worth mentioning.
As if Quines aren't fun enough, people often play the game of "Code Golf" with Quines. How short (in bytes) can you make a Quine?
In the comments of this page I've hidden my own best attempt at writing the shortest C# quine. It's 157 bytes.
Another popular trick is the Quine relay loop. A program (A) that produces a program (B) that produces the initial program A. (There can be any number of intermediate steps)
And finally: the polyglot quine relay loop: a program in one language that produces a program in another language that produces... and so on until we eventually produce the original program again. The most extreme known version of this passes through 100 different languages.
External Links
- Wikipedia: Quine (computing)
- The Little Schemer
- Esolang, the esoteric programming languages wiki
- Esolang: Quine
- Esolang: Iterating Quine
- Quine Relay (an interating quine with 100 languages)
- Esolang Muriel A language built upon Quining.
- Codegolf: Quines
- QuineDB is a quine that is also a key/value store.
See Also
- Unbounded recursion
- How to become a programmer
- Esoteric Programming Concepts
- Quine Programming Language