Quines

Recursion has been one of the most interesting domains in computer science and mathematics. The Wikipedia definition says: Recursion occurs when a thing is defined in terms of itself or of its type. In plain words, what came first, the chicken or the egg ? The debate is endless but exploration is fun.

Last week I came across a programming problem: Write a python program that prints itself. At first it seemed quite easy and I went ahead with the following solution typed into a file named script.py :

with open('script.py', 'r') as f:
    for line in f:
        print line

Thus, patting myself for solving out what looked like child’s play. But now, comes the caveat: no inputs allowed. With a little bit of googling I struck up the Wikipedia article on Quine which describes all the technicalities, history and math that goes behind writing programs that print out themselves. So according to this, my above solution comes under the category of “Cheating” Quines

Now comes the task of writing my own quine, the simplest example that Wikipedia gives for Python is:

s = 's = %r\nprint(s%%s)'
print(s%s)

Wrapping my head around this was a bit cumbersome, but turns out it’s mostly playing with format strings in print statement. In above example, the %r format specifier interprets a given argument using python’s repr method, thus returing a string result that represents a valid python syntax and does NOT actually evaluates the given string s, thus skipping evaluation of \n and %% which we might expect otherwise. So the print statement can be imagined to work in three major steps to create a quine:

1. Prologue: Printing s = , which can’t be replicated any other way
2. Main body: Printing s itself as an argument for %r
3. Epilogue: Mimicking the last print statement via \nprint(s%%s) part of the string s. Notice that when s is passed as an argument for %r it’s not evaluated, hence \n and %% do not seem to be taking expected effect, but now it does and hence this third part prints on the next line with %% evaluated to %, thus creating the final output as print(s%s)

So having attempted to crack the trick behind quines, I next translated the Wikipedia example for a Java quine to a python version as follows:

s = [
    "s = [",
    "    ",
    "]",
    "print s[0]",
    "for line in s:",
    "    print s[1] + chr(34) + line + chr(34) + ','",
    "for i in xrange(2, len(s)):",
    "    print s[i]",
]
print s[0]
for line in s:
    print s[1] + chr(34) + line + chr(34) + ','
for i in xrange(2, len(s)):
    print s[i]

The crux remains the same, this program also works in three parts where print s[0] prints out the first string from list s, followed by printing all the strings from list s and finally mimicking the looped print statements at the end. Notice the use of chr(34) in this, that is done because the ASCII value of double quotes is 34 and thus we use chr(34) to evaluate 34 to " but avoid conflicting with the double quotes used in string literals.

Now that you have had the patience to read so far in this blog and I have tried to explain everything I understand about quines, here is one that I created myself:

s = r'''s = r%s%s%s
print s %% (chr(39)+chr(39)+chr(39), s, chr(39)+chr(39)+chr(39))'''
print s % (chr(39)+chr(39)+chr(39), s, chr(39)+chr(39)+chr(39))

This one makes use of raw strings in python coupled with format specifiers and evaluation of ASCII values. The competition is for creating shortest possible quines, which this clearly is not, so count it as a first step.