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

Ruby quines [metaspring.com]

Tags:

15 Comments to “How to write a self-printing program”

  1. lorenzo says:

    Hello I am tring to write number program,Which I thing that it may give a edge on picking number

    This is my theory I pick 10 and no more than 5 set(only) have for here 4
    however I WOULD LIKE TO CREATE SEVERAL DIFFERENT SET. JUST USING THE NUMBER I DICTATE TO A PROGRAM

    1 2 3 4 5 76 77 78 79 80
    08 09 10 19 28 71 72 73 7475
    41 42 43 44 45 51 52 58 59 62
    08 09 10 18 20 29 30 38 39 49

  2. Anonymous says:

    This post is awesome! I’m deeply fascinated by quines. I linked to your post (above) when I put together a post of my own on MetaSpring.com. My co-workers kept asking me…”Are quines useless?” As you pointed out, the answer is NO! Check out my post and let me know your thoughts.

  3. Eylon Yogev says:

    I have loved this riddle for many years. I thought maybe it is the time to update it to the world we live in today, the world of web. I have made an . I used the exact same method you use here in your post.
    I hope you enjoy it!
    http://yogil.com/yogi/slef-printing-html-page.htm

  4. Eylon Yogev says:

    My last comment got corrupted someway. This is it again:
    I have loved this riddle for many years. I thought maybe it is the time to update it to the world we live in today, the world of web. I have made an HTML page that shows it source. I used the exact same method you use here in your post.
    I hope you enjoy it!
    http://yogil.com/yogi/slef-printing-html-page.htm

  5. Eylon: Cool, thanks for sharing!

  6. […] How to write a self-printing program Says: September 22nd, 2009 at 3:48 pm […]

  7. uma says:

    how to execute it and in which platform

  8. […] fact that it’s short and I have limited time), is because I have recently bumped into another blog post about this issue. That post actually presents a generic recipe for creating such a “Self […]

  9. Johnny says:

    I like your approach, though it is not a quine. Your program doesn’t print its own source code (it’s not printing the escape charactes you’re using in S).

  10. Johnny says:

    Sorry my bad, I overlooked a line myself lol.

  11. python says:

    import sys;f=sys.argv[0];print open(f).read()

  12. ruby says:

    puts File.read(__FILE__)

  13. Trivial Tom says:

    Here is a program that works in many languages that prints itself:

  14. alt coins says:

    Hi, all the time i used to check webpage posts here in the early hours in the break
    of day, since i enjoy to gain knowledge of more and more.

Leave a Reply

You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>