Puzzling OO design problem

[George Sakkis]

I'm looking for a design to a problem I came across, which goes like
this (no, it's not homework):

1. There is a (single inheritance) hierarchy of domain classes, say
A<-B<-..<-Z (arrows point to the parent in the inheritance tree).
2. This hierarchy evolved over time to different versions for each
class. So for example, version's 1 hierarchy would be A_v1 <-B_v1
<-..<-Z_v1.
3. At runtime, only one version is selected by a factory function.

Up to this point, the inheritance graph would be the following:

A <- A_V1 ... <- A_Vn
^ ^ ^
| | |
B <- B_V1 ... <- B_Vn
.. . .
.. . .
.. . .
^ ^ ^
| | |
Z <- Z_V1 ... <- Z_Vn
This could be implemented either with multiple inheritance (e.g.
B_V1(B,A_V1)) or using the bridge design pattern |Z| times, one per
each row. Both solutions would be acceptable; there are no ambiguities
caused by the multiple inheritance (or they are resolved properly
whenever they occur).

Now the problem is that there are 'holes' in this inheritance lattice:
Not all versions introduced new variations of all types; for instance
B_V5 could be missing, meaning that the most recent earlier version of
B would be used in version 5 (say B_V2). My first thought was to create
all the missing classes dynamically, but it's somewhat obscure and it
may not be that simple. Is there a more elegant solution, either a
general design pattern or some clever python metaprogramming hack ?

George

[El Pitonero]

It may be useful to separate the code into version-independent part and
version-dependent part. Also, one can try to implement the higher-level
logic directly in the class definition of A, B, etc., and then use the
version objects only as patches for the details. That is, one can use
place-holder calls. The place-holder calls do nothing if a feature is
not really implemented (either in a parent class, or in an older
version).

class World(object):

def __init__(w, version):

class A(object):
def ff(): pass # place holder for version-dependent code
def f(self): # version-independent code
return self.ff()

class B(A):
def gg(): pass
def g(self):
return self.gg()

for cls in (A, B):
setattr(w, cls.__name__, w.versionize(cl s, version))

def versionize(w, cls, version):
import inspect
methods = inspect.getmemb ers(version, inspect.ismetho d)
methods = [m[1] for m in methods if m[0].split('_')[0] ==
cls.__name__]
for m in methods:
m_name = '_'.join(m.__na me__.split('_')[1:])
import new
im = new.instancemet hod(m.im_func, None, cls)
setattr(cls, m_name, im)
return cls

class Version1(object ):
def A_ff(self):
return 'A.ff: version 1'
def B_gg(self):
return 'B.gg: version 1'

class Version2(Versio n1):
def A_ff(self):
return 'A.ff: version 2'
def B_ff(self):
return 'B.ff: version 2'

w1, w2 = World(Version1) , World(Version2)
a1, b1 = w1.A(), w1.B()
a2, b2 = w2.A(), w2.B()

print a1.f() # prints 'A.ff: version 1'
print b1.f() # prints 'A.ff: version 1'
print b1.g() # prints 'B.gg: version 1'
print '------------'
print a2.f() # prints 'A.ff: version 2'
print b2.f() # prints 'B.ff: version 2'
print b2.g() # prints 'B.gg: version 1'

[George Sakkis]

> On second thought, I had doubts. Consider the following scenario:

A2 | f <- A3
^ ^
| |
B2 | f <- B3
^ ^
| |
C2 <- C3 | g

Assume g calls f. Since f is defined in B version 2, it should taken
over unchanged into B version 3, and that should be the version g
calls. However, with multiple inheritance doing depth-first search,
giving the "upper" class priority over the "left", the first path
searched is B3 - A3 - A2, and hence it finds f at A2. A quick test
confirms this for old-style classes, which failed in exactly that
way. But with new-style classes, it works, and finds f at B2 instead.

So I dug through the documentation and found that new-style classes
compute a monotonic linearization of the inheritance graph, observing
local precedence order, using the algorithm also used in Dylan
described here:

http://www.webcom.com/haahr/dylan/li...-oopsla96.html
That's right; you can actually access this linearization for new-style
classes by the '__mro__' class atrribute. See my example in the main
subthread of this thread that uses __mro__ to illustrate the need for
the dummy intermediate classes.
And this algorithm will even work correctly if one leaves out B3
in the example above, inheriting directly as in C3(A3,C2), because
the ordering constraint that A2 comes before B2 will still be
valid in the linearization for C3.

However, in the following case (shortening the notation even more)
it will fail, if a method defined at C3 is looked up at D4:

A1 - A2 - A3 - A4 - ...
| | | |
B1 - B2 - + - B4 - ...
| | | |
C1 - + - C3 - + - ...
| | | |
D1 - D2 - + - D4 - ...
| | | |

The solution is simply to include C3 in the list of parents of D4, as
in D4(C3,B4,D2). So for every hole in a column, you have to include
the first class (or classes, if the hole spans multiple rows) to the
left of the hole as parents if the class just below the hole, in order from bottom to top. This adds the missing constraints, and should
solve the problem without any need to write __metaclass__ stuff.
Nice. I had taken for granted that you need to fill in the holes
(D3,B3,C2), either manually or automa[tg]ically, but if you allow a
class to inherit from more than two bases, you can pick a set of
parents that does the job, without any boilerplate code or
__metaclass__ magic. The downside of this approach is that it's even
harder to see the big picture, as in the schematic notation above;
remember that each column is a different version that resides in a
separate module, so it's not obvious which classes should be the
parents of each variation. Another drawback in the general case is ease
of maintenance: if a new hole appears in the future or an old hole is
filled, you have to go back and change the parents of the affected
classes. In my case this is not an issue though; old versions are
'frozen', so the only expected change in the lattice is the addition of
new columns (versions).
Interesting question. I learned a lot while thinking about that.

- Dirk

I learned too, and I'm glad for this learning side-effect :-) Thanks !

George

[George Sakkis]

> Have you considered a 'macro' solution composing source? If I were
handling so

many versions, I would want a complete class definition for each version rather than having to scan many sources for each implementation.

Can you elaborate on this a little ? You mean something like a
template-based code generating script that creates all the boilerplate
code for each version before you start customising it ? This could be
an option, though you'd better be pretty sure that the template is
frozen; you don't want to go back and fill in the template more than
once !

George

[Kay Schluehr]

Hi George,

it's a nice little puzzle and it is more fun to solve it if one is not
a student anymore :)

Filling the gaps in the lattice is somehow necessary but it is not
necessary to create all the classes.

Ansatz:

We can consider two matrices: one is filled with nodes ( class names )
the other is filled with arrows between the nodes representing the
inheritance relationships.

In symbolic notatation:

| A B C |
Nodes = | D 0 F |
| G H I |

| 0 l l |
Arrows = | u 0 u*l |
| u u*l u*l |
Remarks:
1 ) if a node or an arrow is empty a 0 is inserted into the matrix.

2 ) u is for uppermost, l is for leftmost. A multiplication between
arrows should read as a logical AND: u*l ~ upper AND left.

With this interpretation the above matrizes contains the same
information than the lattice:

A <- B <- C
^ ^ ^
| | |
D <- 0 <- F
^ ^ ^
| | |
G <- H <- I

Now we need an algorithm to create all the classes from the matrix
information using multiple inheritance when needed:
# arrows symbolized as primes. Only u and l are used in the impl.
# d and r are somewhat more complicated to implement

l = 2
r = 3
u = 5
d = 7

class ClassGridError( Exception):pass

class ClassGrid(objec t):
def __init__(self):
self.class_name s = [] # rows of the class-name matrix
self.arrows = [] # rows of the arrow matrix
self.classes = {} # store the resulting classes

def add_names(self, names):
self.class_name s.append(names)

def add_arrow(self, arrow):
self.arrows.app end(arrow)

def __repr__(self):
if self.classes:
return self.classes.__ repr__()
return object.__repr__ (self)

def create_classes( self):
for i,class_row in enumerate(self. class_names):
for j,cls_name in enumerate(class _row):
if cls_name == 0:
continue
arrow = self.arrows[i][j]
if arrow == 0:
self.classes[cls_name] = type(cls_name,( ),{})
else:
bases = []
name = 0
if arrow%u == 0: # search uppermost
k = i-1
while k>=0:
name = self.class_name s[k][j]
if name:
break
k-=1
if not name:
raise ClassGridError, "Wrong arrow matrix"
bases.append(se lf.classes[name])
if arrow%l == 0: # search leftmost
k = j-1
while k>=0:
name = self.class_name s[i][k]
if name:
break
k-=1
if not name:
raise ClassGridError, "Wrong arrow matrix"
bases.append(se lf.classes[name])
self.classes[cls_name] =
type(cls_name,t uple(bases),{})

cg = ClassGrid()

cg.add_names((" A","B","C"))
cg.add_names((" D", 0, "F"))
cg.add_names((" G","H","I"))

cg.add_arrow(( 0, l, l ))
cg.add_arrow(( u, 0, u*l))
cg.add_arrow(( u, u*l, u*l))

cg.create_class es()

Now You can checkout Your solution:

cg.classes["A"].__subclasses__ () [<class '__main__.B'>, <class '__main__.D'>]
cg.classes["B"].__subclasses__ () [<class '__main__.C'>, <class '__main__.H'>]
cg.classes["C"].__subclasses__ () [<class '__main__.F'>]
cg.classes["D"].__subclasses__ () [<class '__main__.F'>, <class '__main__.G'>]
cg.classes["F"].__subclasses__ () [<class '__main__.I'>]
cg.classes["G"].__subclasses__ () [<class '__main__.H'>]
cg.classes["H"].__subclasses__ () [<class '__main__.I'>]
cg.classes["I"].__subclasses__ ()

[]

Ciao,
Kay

[Michael Spencer]

George Sakkis wrote:

Have you considered a 'macro' solution composing source?

Can you elaborate on this a little ? You mean something like a
template-based code generating script that creates all the boilerplate
code for each version before you start customising it ?

I was thinking more along the lines of repeatable code generation.
I started from this idea:
http://groups-beta.google.com/group/...ef889e9f99696c
which is a straightforward wrapping case, but illustrates source code
composition/generation.

Now given that you have:
#World1.py

class Field:
...
class Movable
...
etc...
#Then in World2Delta.py

class FieldDelta:
"""just the classes that have changed"""
def somemethod(self ):
"""just the methods that are added or changed
you could even have nomenclature for method deletion, (a lack which
sometimes bugs me in OO schemes)"""
etc...
then you have a 'makefile' that generates a new module for each of your worlds

#makefile.py

def generateWorld(b aseworld, delta, newworld):
"""reads two modules:
baseworld defines the 'superclasses'
delta defines any changes to these
writes module newworld, that contains complete
source for all the classes in the model, with no
external dependencies
"""

I haven't tried it, but I'm sure it is fairly straightforward to implement (and
very easy to test).
This could be an option, though you'd better be pretty sure that the template is
frozen; you don't want to go back and fill in the template more than
once !

I envisage something that could be regenerated at will, simply by re-running the
makefile.

The thing that would need to be frozen is the inheritance graph within each
world. If you want to change that between versions, that would make
generateWorld much more complex.

The general advantage that I see with this approach is that whatever the hoops
you have to jump through to get the makefile process working right - the result
is extremely simple to verify. You would also probably get better performance,
by avoiding so much subclassing (not that you mentioned that as factor, but...)

Michael

[Michele Simionato]

Dirk wrote:

So I dug through the documentation and found that new-style classes
compute a monotonic linearization of the inheritance graph, observing
local precedence order, using the algorithm also used in Dylan
described here: http://www.webcom.com/haahr/dylan/li...-oopsla96.html

<nitpick mode>
Actually Dylan authors invented the C3 algorithm but Dylan does not use
it:
for compatibility with Lisp, Dylan uses the CLOS algorithm. Languages
that
I know that use C3 are Python and Goo. Playing with the MOP you can get
lispy languages to follow C3 too.
</nitpick mode>

[Bengt Richter]

On 9 Apr 2005 03:49:19 -0700, "George Sakkis" <gs*****@rutger s.edu> wrote:

"Michael Spencer" <ma**@telcopart ners.com> wrote:

George,

since you explicit allowed metaprogramming hacks :-), how about

something like

this (not tested beyond what you see):

[snipped]

Nice try, but ideally all boilerplate classes would rather be avoided
(at least being written explicitly). Also, it is not obvious in your
solution why and which placeholder classes have to be written (like
World2.Movable ) and which do not. By the way, my current working
solution involves copying and pasting verbatim these classes :-) Below
is an abstracted example; note that the 'declaration string' of each
original class is exactly the same across all different versions after
the first (e.g. "class B(PreviousNames pace.B, A)").
#============= =============== =============== ===========
# version_1.py

class Namespace:
class A(object):
def foo(self): return "version_1.foo( )"
class B(A):
def bar(self): return "version_1.bar( )"
class C(B):
def zen(self): return "version_1.zen( )"
#============= =============== =============== ===========
# version_2.py

from version_1 import Namespace as PreviousNamespa ce
class Namespace(Previ ousNamespace):
class A(PreviousNames pace.A):
def foo(self): return "version_2.foo( )"
class B(PreviousNames pace.B, A):
pass
class C(PreviousNames pace.C, B):
pass
#============= =============== =============== ===========
# version_3.py

from version_2 import Namespace as PreviousNamespa ce
class Namespace(Previ ousNamespace):
class A(PreviousNames pace.A):
pass
class B(PreviousNames pace.B, A):
def bar(self): return "version_3.bar( )"
class C(PreviousNames pace.C, B):
pass

#============= =============== =============== ===========
# test.py
# command: python test.py <#version>

def NamespaceFactor y(version):
return __import__("ver sion_%d" % version).Namesp ace

print NamespaceFactor y(2).B().foo() # "version_2.foo( )"
print NamespaceFactor y(3).C().bar() # "version_3.bar( )"

import sys, inspect
namespace = NamespaceFactor y(int(sys.argv[1]))
# print the __mro__ of each 'inner' class
for name,cls in inspect.getmemb ers(namespace,
inspect.isclass ):
print cls
for ancestor in cls.__mro__:
print "\t", ancestor

#============= =============== =============== ===========

See if this does what you want:
(Note that vermeta.py preliminarily writes out the three version_?.py files, so
you can just go to a temp directory and run python24 vermeta.py)

It makes the version files look a little more cluttered with the
open(..).write( '''\ ... ''') wrapping. E.g., 2 & 3 are just
----< version_2.py >-----------
from version_1 import Namespace as PreviousNamespa ce
class Namespace(Previ ousNamespace):
__metaclass__ = vars(PreviousNa mespace)['__metaclass__']

class A:
def foo(self): return "version_2.foo( )"
-------------------------------

and

----< version_3.py >-----------
from version_2 import Namespace as PreviousNamespa ce
class Namespace(Previ ousNamespace):
__metaclass__ = vars(PreviousNa mespace)['__metaclass__']

class B:
def bar(self): return "version_3.bar( )"
-------------------------------

And you only have to change one digit in the 3-line boilerplate
and your class definitions don't have to specify inheritance,
but it could test for type classobj (classic class) and only
redefine if so ;-)

There are some limitations I think (;-) but the idea is you just have to
specify three lines of boilerplate for a new version, and then just
the classes and methods you are interested in overriding in the new
version, and you don't have to specify the class inheritance in the new versions,
as the lazystyle metaclass function takes care of that. I hope ;-)
Version_1 has to be hand made, but after that, see what you think.

----< vermeta.py >---------------------------------------------------------------
#============== =============== =============== ==========
# version_1.py
open('version_1 .py','w').write ('''\
NAMESPACE_CLASS NAMES = ['A', 'B', 'C']
def metadeco(nsname , nsbases, nsdict):
# print '--- metadeco ---', nsbases, nsdict['__module__'], __name__
# print 'nsname = %r\\nnsbases = %r\\nnsdict = %s' %(
# nsname, nsbases, ',\\n '.join(str(nsdi ct).split(', ')))
if nsdict['__module__'] != __name__: # exclude this first-version module
# print '--- doing meta stuff for namespace of module %s ---'% nsdict['__module__']
for i, cname in enumerate(NAMES PACE_CLASSNAMES ):
cbases = (vars(nsbases[0])[cname],) + (i and (nsdict[NAMESPACE_CLASS NAMES[i-1]],) or ())
if object not in cbases: cbases += (object,)
if cname in nsdict:
cdict = nsdict[cname].__dict__.copy( )
#cdict['__module__'] = __name__
else:
cdict = {'__doc__': '(Generated by version_1.metad eco)'}
cdict['__module__'] = nsdict['__module__']
nsdict[cname] = type(cname, cbases, cdict)
return type(nsname, nsbases, nsdict)

class Namespace(objec t):
__metaclass__ = metadeco
class A(object):
def foo(self): return "version_1.foo( )"
class B(A):
def bar(self): return "version_1.bar( )"
class C(B):
def zen(self): return "version_1.zen( )"
''')

#============== =============== =============== ==========
# version_2.py
open('version_2 .py','w').write ('''\
from version_1 import Namespace as PreviousNamespa ce
class Namespace(Previ ousNamespace):
__metaclass__ = vars(PreviousNa mespace)['__metaclass__']

class A:
def foo(self): return "version_2.foo( )"
''')
#============== =============== =============== ==========
# version_3.py
open('version_3 .py','w').write ('''\
from version_2 import Namespace as PreviousNamespa ce
class Namespace(Previ ousNamespace):
__metaclass__ = vars(PreviousNa mespace)['__metaclass__']

class B:
def bar(self): return "version_3.bar( )"
''')

#============== =============== =============== ==========
# test.py
# command: python test.py <#version>

def NamespaceFactor y(version):
return __import__("ver sion_%d" % version).Namesp ace

print NamespaceFactor y(2).B().foo() # "version_2.foo( )"
print NamespaceFactor y(3).C().bar() # "version_3.bar( )"

import sys, inspect
namespace = NamespaceFactor y(int(sys.argv[1]))
# print the __mro__ of each 'inner' class
for name,cls in inspect.getmemb ers(namespace,
inspect.isclass ):
#for name, cls in (t for t in namespace.__dic t__.items() if isinstance(t[1], type)):
print cls
for ancestor in cls.__mro__:
print "\t", ancestor

#============== =============== =============== ==========
---------------------------------------------------------------------------------

Run:

[ 5:33] C:\pywk\clp\sak kis\meta>py24 vermeta.py 3
version_2.foo()
version_3.bar()
<class 'version_3.A'>
<class 'version_3.A'>
<class 'version_2.A'>
<class 'version_1.A'>
<type 'object'>
<class 'version_3.B'>
<class 'version_3.B'>
<class 'version_2.B'>
<class 'version_1.B'>
<class 'version_3.A'>
<class 'version_2.A'>
<class 'version_1.A'>
<type 'object'>
<class 'version_3.C'>
<class 'version_3.C'>
<class 'version_2.C'>
<class 'version_1.C'>
<class 'version_3.B'>
<class 'version_2.B'>
<class 'version_1.B'>
<class 'version_3.A'>
<class 'version_2.A'>
<class 'version_1.A'>
<type 'object'>
<type 'type'>
<type 'type'>
<type 'object'>

Regards,
Bengt Richter

[Dirk Thierbach]

George Sakkis <gs*****@rutger s.edu> wrote:

A1 - A2 - A3 - A4 - ...
| | | |
B1 - B2 - + - B4 - ...
| | | |
C1 - + - C3 - + - ...
| | | |
D1 - D2 - + - D4 - ...
| | | | The solution is simply to include C3 in the list of parents of D4,
as in D4(C3,B4,D2). So for every hole in a column, you have to
include the first class (or classes, if the hole spans multiple
rows) to the left of the hole as parents if the class just below
the hole, in order from bottom to top.

Nice. I had taken for granted that you need to fill in the holes
(D3,B3,C2), either manually or automa[tg]ically, but if you allow a
class to inherit from more than two bases, you can pick a set of
parents that does the job, without any boilerplate code or
__metaclass__ magic. The downside of this approach is that it's even
harder to see the big picture, as in the schematic notation above;
remember that each column is a different version that resides in a
separate module, so it's not obvious which classes should be the
parents of each variation.

It's obvious if you know which versions are available, and which
aren't. If you don't have this information, and you're only looking at
each module locally, than it's probably even safer (i.e., less likely
to confuse a casual reader of the source) to just generate all the
dummy classes manually. But that sort of makes your original problem
irrelevant :-)

- Dirk

[George Sakkis]

"Bengt Richter" <bo**@oz.net> wrote in message
news:42******** *******@news.oz .net...

See if this does what you want:

[snipped]

Yes, that's pretty much what I had in mind. I particularly liked the
idea of mirroring automagically the nested class inheritance in each
version. So I tried to refine this recipe a little and I pushed down
the boilerplate code from 3 lines to one word; laziness is a virtue :-)
Below is the test only; I posted the main module to
http://rafb.net/paste/results/Hweu3t19.html to avoid messing up the
indentation.

Cheers,
George

#============== =============== =============== =====
# test.py
from namespace import Namespace

class Era(object):
def __init__(self):
self.lumberjack = self.GameUnit()
self.warrior = self.CombatUnit ()
self.shooter = self.RangedUnit ()

class MedievalAge(Era ):
__metaclass__ = Namespace()
class GameUnit(object ):
def move(self): return "MedievalAge.Ga meUnit.move()"
class CombatUnit(Game Unit):
def fight(self): return "MedievalAge.Co mbatUnit.fight( )"
class RangedUnit(Comb atUnit):
def aim(self): return "MedievalAge.Ra ngedUnit.aim()"

class ColonialAge(Era ):
__metaclass__ = Namespace(Medie valAge)
class CombatUnit:
def fight(self): return "ColonialAge.Co mbatUnit.fight( )"

class IndustrialAge(E ra):
__metaclass__ = Namespace(Colon ialAge)
class GameUnit:
def move(self): return "IndustrialAge. GameUnit.move() "
class RangedUnit:
def aim(self): return "IndustrialAge. RangedUnit.aim( )"
if __name__ == '__main__':
for era in MedievalAge(), ColonialAge(), IndustrialAge() :
for player in era.lumberjack, era.warrior, era.shooter:
for action in "move", "fight", "aim":
try: result = getattr(player, action)()
except AttributeError:
result = "N/A"
print "%s:%s.%s:\ t%s" % (type(era).__na me__,
type(player).__ name__,
action, result)