Friday, September 08, 2006

Implementing the Visitor Pattern

The visitor pattern is a very interesting way to go if you have a lot of operations
which need to be applied to one data structure. Especially if this is a recursive data structure such as a tree.

Python provides a very interesting way to implement the visitor patter and get
around some of its inherent problems. Granted when done this way you are really getting something closer to double dispatch then the visitor pattern.

Allow me to take a short deter into CLOS (the common lisp object system). Objects
in CLOS bear more of a resemblance to Structures in C then to Objects in a language Like Java or Python in that a CLOS object has no methods. The methods are defined separately as generic functions. One feature of generic
fumigates is that they can select an implementation based on multiple arguments, where's in most OO languages only the first (the calling object) is considered. This idea is really quite powerful.

back on the python front. Here is an interesting way to implement the visitor
pattern using the available introspection tools.

class Node(object):

def __init__(self):
self.MethodNames = [ cls.__name__ for cls in self.__class__.__mro__]

def accepts(self, visitor, prefix='visit_'):
for name in self.MethodNames:
vName = prefix+name
if hasattr(visitor, vName):
# we could have allowed getattr to raise an exception but this is generally slower
# then an explicit check. In this case we assume that the exception would be
# thrown regularly under normal operation and would hurt performance.
getattr(visitor, vName)(self)
#do any cleanup activity
raise AttributeException("Visitor %s does not contain a suitable method." % visitor)

class Visitor(object):

def visit_Node(self, node):
#do something

The important thing about these code is the use of __class__.__mro__
__mro__ stands for Method Resolution Order and is a list of class objects in the
order they are tried when a definition is needed for a method. In Older versions of python this is a simple (and fundamentally broken) depth first search. The problem with simple depth first search is that it doesn't handle
multiple inheritance corectly. Since Python 2.4 a more sophisticated algorithm is used (incidentally the same Algorithm as used in CLOS).

We have in effect created a Dispatch method which is polymorphic on the type of the current class. And moreover has the same method resolution order as the python language its self. The main advantage of this approach over a more
traditional one is that we are free to extend the Node class hiarchy at any time
without breaking existing visitors. Granted the dynamic dispatch will be slightly
slower than accept methods which explicitly call a particular method.

Thursday, April 27, 2006

Other side of the Coin

There is always a counter example. Having just saying that dynamically typed languages are better then statically typed ones, I find my own counter example in the kind of bug that static typing would have caught easily and simply.

Recently I have been looking at two things, Databases (and especially SQLObject) and cross platform GUI libraries. I seem to have settled on wxPython for this. wxPython comes with a great Python shell called PyCrust, this once was it's own project but the maintainer agreed to fold into the main wxPython distribution.

PyCrust has a namespace browser (which I thought was quite a nifty idea) except every time I tried to brows SQLObject it would hang. And the problem was name collision. The Namespace inspector in PyCrust checks for objects that expose a method called _getMethodNames, which will assist it in displaying the correct attributes. It just so happens that SQLObject has a class which will happily return a callable object for almost any attribute you ask it for. PyCrust is expecting a list of strings and gets an instance of a class it knows nothing about, to make things worse this class overloads the + operator for its own purpus (it is used
to dynamically construct SQL queries from python expressions).

An error is only generated 20 lines of code later when PyCrust attempts to iterate over what a local variable which should contain a list (but dosn't). Has this changed my mind about dynamic typing... Well No. In the end every language feature has benefits and drawbacks. Dynamic typing opens the door for bugs of this type which can be quite hard to locate. It also gives flexibility, a lot of flexibility, this can make the programming effort a lot easier, as it promotes decoupled code.
In python it is relatively easy to create an objects which are interface compatible with other objects without having a dependency on them.

Friday, April 21, 2006

So what's so good about Python

So what's so good about Python? All things being equal I would program in Lisp, because on Language features I think it rules, but there are problems including lack of libraries, lack of portability and difficulty of installation, the fact that I am yet to meet a full implementation of the Common Lisp standard.

A few years back I tried Franz Common Lisp and it was the best tool I have ever used for developing a GUI (you can make changes to the app while it is running, find an error, fix it and try again (and this includes the GUI), the only problem is the cost, I couldn't afford it, even if I managed to convince my employer to use a Language which almost no-one (who isn't a programmer) has ever heard off, they could afford it either.

When I found Python it was really the next best thing (in the interim I had messed about with Haskell and Prolog). Now I'm not the only Lisper who has ended up in Python, the lambda expression was only ever included because so many ex Lisp programmers where asking for it. Strangle I've never really used it (lambda's work great in Lisp but they just don't seem to fit in python, its an element which doesn't fit).

The other good points in my opinion:

  • Interfaces are implicit. Nothing annoyed me more in java that exceptions based on the compiler telling me this is the wrong type of object. I don't care if it implements a next() method I will not call it. With dynamic typing the system will happily call my next method.
  • meaningfully whitespace. Using a return to denote lines of code is an excellent idea for so many reasons:
  1. Lines of Code can have a definite meaning, there is no point in arguing about this, what constitutes one logical line of Python code is defined in the Language reference.
  2. How many times has the average programmer forgotten to press return at the end of a line? How many times has the same programmer forgotten a semicolon ? Most C text books will have a paragraph which goes something like this, because semicolons delimit statements it is possible to put more than one statement on the same line ... But this can make your code harder to read and is considered bad style. These days when I write JavaScript I don't put the semicolons either.
In short the dynamic nature of the language means that you can take shortcuts and avoid the need to write boilerplate code. The SQLObject library
takes this a step further be implicitly creating properties based on the existence of _get_ and -set_ methods this is a very pythonic approach.

what's missing:
There are also a couple of features I would like to see:

Delegation: this is a neat feature of Delphi (I will go out on a limb and say the only neat feature) claim to the world that you have implement interface X and then delegate it to a member variable. In essence this is a tool for avoiding typing which will generate a whole set of stubs for you such as

def method(self, *args, **kwargs):
return self.member.method(*args, **kwargs)

I have some Ideas about how to add something like this to SQLObject, which I'll be talking about in my next post.

Macros: Someone coming from C will have a long list of why macros are bad and dangerous. The problem is that the C macro pre-processor is not a true part of the language and is text based. Comings from Lisp I am familiar with an integrated macro expander which is part of the language and understands the language, hence it can solve all of the problems, associated with macros. And why would you want this... For speed optimization, and writing programs that write programs, if you can predict a head of time that a loop will execute exactly 20 times then why not unwrap it ... Because writhing the same
lines with minor variations is annoying and error prone (even with copy and past), so let the macro expander do it.

The first problem however is one of syntax? In Lisp macros fit, they look don't require any major contortions to express. I'm not the only one who has raised the idea of adding Lisp like macros to Python but so far no-one is come up with a model of what said macros should actually look like.

OK That will do for this post.