Igor Ostrovsky Blogging

As promised at the end of my recent post, I am going to explain how to implement a program that prints itself, in addition to doing other things (like playing Game of Life).

A self-printing program - also called a quine - is a program that prints out its own source code. I will describe one simple way to implement a quine that can be adapted to just about any programming language. The technique does not depend on any unusual language features, but also does not necessarily yield the shortest possible quine in a particular language.

The main idea behind this quine implementation is simple. The quine will consist of two parts: a definition of a string and the program core. The string will contain the source code of the program core. And, what will the program core do? It will print the string twice: once to print the string definition, and again to print the program core.

That’s pretty much all we need to do, except for some details. When printing the string the first time, we need to escape special characters and surround each line with quotes. Also, some code may need to come before the string definition (the “header”), and some may need to come after the program core (the “footer”). Fortunately, we can stuff all the code we need into the program core, so handling these details is not a big problem.

Let’s walk through a quine construction in C#. The quine will look like this:

    using System;
    class P {
        static void Main() {
            string[] S = {
                // the program core, as a string array
            };

            // the program core, as source code:            //     1. Print the program header
            //     2. Print S, formatted as the definition of S
            //     3. Print S, formatted as source code            //     4. Print the program footer
        }
    }

Let’s implement the program core. That’s easy:

    using System;
    class P {
        static void Main() {
            string[] S = {
                // the program core, represented as a string array 
            };
            // 1. Print the program header
            Console.WriteLine(“using System;”);
            Console.WriteLine(“class P {”);
            Console.WriteLine(”    static void Main() {”);

            // 2. Print S, formatted as the definition of S
            Console.WriteLine(”        string[] S = {”);
            foreach (string line in S)
            {
                string escapedLine = line.Replace(@”\”, @”\\”).Replace(“\”", “\\\”");
                Console.WriteLine(“\”{0}\”,”, escapedLine);
            }
            Console.WriteLine(”        };”);

            // 3. Print S, formatted as source code
            foreach (string line in S) Console.WriteLine(line);

            // 4. Print the program footer
            Console.WriteLine(”    }”);
            Console.WriteLine(“}”);
        }
    }

We also need to initialize string S. To do that, simply copy & paste the program core source code into the definition of S, add a backslash before each occurrence of ” or \, and surround each line with quotes.

Here is the final quine:

using System;
class P
{
    static void Main()
    {
        string[] S = {
”        Console.WriteLine(\”using System;\”);”,
”        Console.WriteLine(\”class P {\”);”,
”        Console.WriteLine(\”    static void Main() {\”);”,
“”,
”        Console.WriteLine(\”        string[] S = {\”);”,
”        foreach (string line in S) {”,
”            string escapedLine = line.Replace(@\”\\\”, @\”\\\\\”)”,
”                .Replace(\”\\\”\”, \”\\\\\\\”\”);”,
”            Console.WriteLine(\”\\\”{0}\\\”,\”, escapedLine);”,
”        }”,
”        Console.WriteLine(\”        };\”);”,
“”,
”        foreach (string line in S) Console.WriteLine(line);”,
“”,
”        Console.WriteLine(\”    }\”);”,
”        Console.WriteLine(\”}\”);”,
        };
        Console.WriteLine(“using System;”);
        Console.WriteLine(“class P {”);
        Console.WriteLine(”    static void Main() {”);

        Console.WriteLine(”        string[] S = {”);
        foreach (string line in S)
        {
            string escapedLine = line.Replace(@”\”, @”\\”)
                .Replace(“\”", “\\\”");
            Console.WriteLine(“\”{0}\”,”, escapedLine);
        }
        Console.WriteLine(”        };”);

        foreach (string line in S) Console.WriteLine(line);

        Console.WriteLine(”    }”);
        Console.WriteLine(“}”);
    }
}

Pretty simple, isn’t it?

One interesting point is that if we add extra code into the program core, and add the same code into the definition of string S, we will still have a quine. For example, here is how you can extend to quine to print an arbitrary string to standard error, after printing its own source code to standard output:

using System;
class P
{
    static void Main()
    {
        string[] S = {
”        Console.WriteLine(\”using System;\”);”,
”        Console.WriteLine(\”class P {\”);”,
”        Console.WriteLine(\”    static void Main() {\”);”,
“”,
”        Console.WriteLine(\”        string[] S = {\”);”,
”        foreach (string line in S) {”,
”            string escapedLine = line.Replace(@\”\\\”, @\”\\\\\”)”,
”                .Replace(\”\\\”\”, \”\\\\\\\”\”);”,
”            Console.WriteLine(\”\\\”{0}\\\”,\”, escapedLine);”,
”        }”,
”        Console.WriteLine(\”        };\”);”,
“”,
”        foreach (string line in S) Console.WriteLine(line);”,
“”,
”        Console.WriteLine(\”    }\”);”,
”        Console.WriteLine(\”}\”);”,
“”,
”        Console.Error.WriteLine(\”This quine can do other things too!\”);”,
        };
        Console.WriteLine(“using System;”);
        Console.WriteLine(“class P {”);
        Console.WriteLine(”    static void Main() {”);

        Console.WriteLine(”        string[] S = {”);
        foreach (string line in S)
        {
            string escapedLine = line.Replace(@”\”, @”\\”)
                .Replace(“\”", “\\\”");
            Console.WriteLine(“\”{0}\”,”, escapedLine);
        }
        Console.WriteLine(”        };”);

        foreach (string line in S) Console.WriteLine(line);

        Console.WriteLine(”    }”);
        Console.WriteLine(“}”);

        Console.Error.WriteLine(“This quine can do other things too!”);
    }
}

So, we can write a program that knows how to print its source code, but also does other things. This is interesting for three reasons:

1. It is an important result in theoretical computer science, known as the recursion theorem. Recursion theorem can be used to prove a variety of interesting results. For example, using the recursion theorem is one way to prove that the halting problem is undecidable.
2. Virus writers write programs that know how to replicate themselves, but also do other things, such as messing up your computer.
3. You can write pointless but cool little programs, like my self-printing Game of Life.

By the way, the quine that I described in this article is by no means the shortest possible one in C#. Joey Wescott came up with a C# quine that is only 166 characters long. I suggested two improvements, and we got it down to 149 characters (all one line):

class P{static void Main(){var S=“class P{{static void Main(){{var S={1}{0}{1};System.Console

.Write(S,S,’{1}’);}}}}”;System.Console.Write(S,S,‘”‘);}}

And there you have it - that’s how you write quines. In my next article, I will talk about an interesting little problem, and seven very different algorithms that can be used to solve it.

Other articles you may like:

Numbers that cannot be computed

Skip list are fascinating!

Quicksort killer