An even shorter quine

While on the topic of self-reproducing programs or "quines" as they are called, I was watching Hilary Mason's keynote at Pycon 2011. It was very interesting to hear her talk about data science - how its gaining ground, and how Python provides great tools to dig into it.
One interesting thing was she showed a quine in one of her slides, and it was much shorter than the one I came up with. I think she said the source of it was Godel, Escher, Bach.
Here it is:

a = 'print "a=", repr(a);print "exec(a)"'
exec(a)

To me this is a shorter, elegant quine. Still have to figure out how to arrive at it, though.

Process for deriving the self-reproducing program

This is more like a note to myself since I do not want to forget the process of how I laid out the self-reproducing program in python. As I mentioned, it was this blog post that started it. I mostly just followed the logic outlined there.

There should be 2 methods, A and B. The basic logic would be:
1. A is the entry point of the program.
2. A would compute the description of B and then call B passing the description.
3. B prints description of A and then prints the passed description of B.

We will start with Python-like pseudo-code and arrive at pure Python code. So we lay out the logic above as the pseudocode below. and are placeholders since we dont know what they will hold for now.

def A():
   descB = [description of B]
   B(descB)   
def B(descB):
   descA = [description of A]
   print descA
   print desc

Since indentation and whitespace will complicate matters for this purpose, we can write the program without them. This is perfectly valid python syntax.

def A(): descB = [description of B]; B(descB)
def B(descB): descA = [description of A]; print descA; print desc

We can replace [description of A] placeholder in method B like this:

def A(): descB = [description of B]; B(descB)
def B(desc): descA = "def A(): descB = [description of B]; B(descB)"; print descA; print desc

Now in method B, [description of B] is the passed in variable desc. So we can substitute that for the placeholder.

def A(): descB = [description of B]; B(descB)
def B(desc): descA = "def A(): descB = " + desc + "; B(descB)"; print descA; print desc

And now, the only remaining variable is [description of B]. This can be a just a copy and paste of method B as a string.

def A(): descB = "def B(desc): descA = "def A(): descB = " + desc + "; B(descB)"; print descA; print desc"; B(descB)
def B(desc): descA = "def A(): descB = " + desc + "; B(descB)"; print descA; print desc

Notice that the double-quotes appearing in method B mess things up when constructing the string variable descB. In python, this can be easily taken care of since double and single quotes escape each other in a string. So we can change descA in method B to be a string with single quotes instead of double and change descB in method A accordingly.

def A(): descB = "def B(desc): descA = 'def A(): descB = ' + desc + '; B(descB)'; print descA; print desc"; B(descB)
def B(desc): descA = 'def A(): descB = ' + desc + '; B(descB)'; print descA; print desc

Seems like this should work. Except we missed one thing. In method B when we are constructing the description of method A, the passed in "desc" variable is used to construct the description of the method. But desc will not have the double quotes coming along with it, because the double quotes is what is used to construct the desc (or descB) variable.
The solution is pretty easy though. in descA, just add a double quote, since we need to print the double quotes, add it as a function that returns double quotes. That function is chr(34), since an ascii value of 34 represents a double-quote.
Of course, we also have to update the descB variable string inside method A appropriately.

def A(): descB = "def B(desc): descA = 'def A(): descB = ' + chr(34) + desc + chr(34) + '; B(descB)'; print descA; print desc"; B(descB)
def B(desc): descA = 'def A(): descB = ' + chr(34) + desc + chr(34) + '; B(descB)'; print descA; print desc

We can make a few more adjustments by removing the variables descA and descB to arrive at the final version of the program.

def A(): B("def B(desc): print 'def A(): B(' + chr(34) + desc + chr(34) + ')'; print desc")
def B(desc): print 'def A(): B(' + chr(34) + desc + chr(34) + ')'; print desc

Self-reproducing program in python

I came across this blog post that details how to write a self-reproducing program, and implements the same in Java. So I set out to write a python version:


def A(): B("def B(desc): print 'def A(): B(' + chr(34) + desc + chr(34) + ')'; print desc")
def B(desc): print 'def A(): B(' + chr(34) + desc + chr(34) + ')'; print desc


So to test this this, save the above code in a file selfrep.py. Then fire up the interpreter and type the following:


Python 2.6 (r26:66721, Oct 2 2008, 11:35:03) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> import selfrep
>>> selfrep.A()
def A(): B("def B(desc): print 'def A(): B(' + chr(34) + desc + chr(34) + ')'; print desc")
def B(desc): print 'def A(): B(' + chr(34) + desc + chr(34) + ')'; print desc
>>>

Voila! The output of the program is exactly the same as its source code. Note though, that this is not a complete program that can be run via the interpreter but a module that needs to be imported and then called.