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.

Python code analysis tools

1. Use pep8 to check if your Python code matches the style guide.

http://pypi.python.org/pypi/pep8


2. Use pyflakes to analyze your python code and detect errors.

http://pypi.python.org/pypi/pyflakes

The Philosophy of PyPy...roughly

This has been gleaned from the excellent PyPy site, just so I could understand why PyPy exists and the goals for it.

This is how Python currently runs programs.




Suppose the interpreter is in Python instead of C. Ignoring performance, this would be a great setup since we could work in Python rather than C. But we cant ignore performance! This setup would be slow.




So if we have to get back to the speed levels of the existing CPython setup, we would have run an interpreter based in C rather than in Python. How about we keep the source file of the interpreter in Python but use a translator to convert the code to C? Then we can still write the interpreter in Python and also get a functioning interpreter that’s fast as C.




But are we sure that a translated interpreter will always be as fast as or faster than the original C interpreter? Are there other ways we can increase the speed of this setup? Yes! Instead of just a translator, use the JIT (just-in-time) compiler-generator to generate a JIT compiler out of the Python interpreter.

Points to note:

• The interpreter written in Python in PyPy is actually written in RPython, a restricted version of Python that is statically-typed. This is to enable generation of a more-efficient program for the target platform.
• The JIT Compiler generated uses a different approach than the JIT compiler that can be generated for the CPython version (Psyco) and according to the PyPy site has demonstrated superior performance, even though its still a work in progress.

Python introspection

This is a handy article on python introspection. The article is old (Dec 2002) and uses Python 2.2 but you can work through the article with the current Python version which is 2.7. There are a few differences, for eg. two new keywords "as" and "with" will be displayed in the exercise which lists keywords, but most of the exercises are useful to get an understanding of Python's introspection abilities.

http://www.ibm.com/developerworks/library/l-pyint.html

One thing to note: in listing 29 (Types), its worth mentioning that if you use the 'type' function on modules , it only works for modules that are loaded. For modules that are not, you get an error. Calling type on built-ins will not give an error since built-ins like int are always loaded on initialization. Here's an example:


Python 2.6.3 (r263rc1:75186, Oct 2 2009, 20:40:30) [MSC v.1500 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> type(int)
< type 'type' >
>>> type(sys)
Traceback (most recent call last):
File "", line 1, in
NameError: name 'sys' is not defined
>>> import sys
>>> type(sys)
< type 'module' >
>>>