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

[Jack Diederich]

On Fri, Apr 08, 2005 at 04:42:52PM -0700, George Sakkis wrote:

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 ?

Err, you might want to explain what these things do instead of an
abstract description of how you are doing it. It looks like you are
using inheritance in the normal way _and_ you are using it to handle
versioning of some kind (maybe stable interface releases? I don't know).

Let us know what parts need inheritance for, and what you have
just been using a side effect of inheritance for as a convenience
(versioning, I think).

A more concrete example would be easier to comment on, if possible
do a simple one (maybe just two classes with two versions each).

-jackdied

[George Sakkis]

> Err, you might want to explain what these things do instead of an

abstract description of how you are doing it. It looks like you are
using inheritance in the normal way _and_ you are using it to handle
versioning of some kind (maybe stable interface releases? I don't know).
Let us know what parts need inheritance for, and what you have
just been using a side effect of inheritance for as a convenience
(versioning, I think).

A more concrete example would be easier to comment on, if possible
do a simple one (maybe just two classes with two versions each).

-jackdied

I intentionally abstracted the problem to remove the irrelevant
details, but here's a more concrete (though still simplified) example.
I hope it is more clear now.

George

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

def worldModelFacto ry(version):
if version < 2: return WorldModel()
else: return WorldModel_v2()

class WorldModel(obje ct):

def __init__(self):
self.ourGoal = self.FieldObjec t(x=-50, y=0)
self.theirGoal = self.FieldObjec t(x=+50, y=0)
self.ball = self.MovableObj ect()
self.teammates = [self.Player(i) for i in xrange(1,12)]
self.opponents = [self.Player(i) for i in xrange(1,12)]

class FieldObject(obj ect):
def __init__(self, id=None, x=0, y=0):
self.id = id
self._pos = (x,y)
def position(self):
'''Get or estimate the current position.'''
return self._pos

class MovableObject(F ieldObject):
def speed(self):
'''Get or estimate the current speed.'''
# [implementation snipped]

class Player(MovableO bject):
def passBall(self,p ower,teammate):
'''Pass the ball to the teammate.'''
# [implementation snipped]
class WorldModel_v2(W orldModel):

class FieldObject(Wor ldModel.FieldOb ject):
'''New implementation of FieldObject.'''
def position(self):
# [new implementation snipped]
pass

class MovableObject(W orldModel.Movab leObject, FieldObject):
'''MovableObjec t didn't change since the previous version. The
only reason for this class is to make
WorldModel_v2.F ieldObject
accessible to WorldModel_v2.P layer.
'''
pass

class Player(WorldMod el.Player, MovableObject):
'''New implementation of Player.'''
def passBall(self,p ower,teammate):
# WorldModel_v2.F ieldObject.posi tion() should be called
myPosition = self.position()
# [new implementation snipped]

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

[Jack Diederich]

On Fri, Apr 08, 2005 at 06:40:54PM -0700, George Sakkis wrote:

Err, you might want to explain what these things do instead of an
abstract description of how you are doing it. It looks like you are
using inheritance in the normal way _and_ you are using it to handle
versioning of some kind (maybe stable interface releases? I don't know).

Let us know what parts need inheritance for, and what you have
just been using a side effect of inheritance for as a convenience
(versioning, I think).

A more concrete example would be easier to comment on, if possible
do a simple one (maybe just two classes with two versions each).

-jackdied

I intentionally abstracted the problem to remove the irrelevant
details, but here's a more concrete (though still simplified) example.
I hope it is more clear now.

<boiled down version of George's exmaple>
def worldModelFacto ry(version):
if version < 2: return WorldModel()
else: return WorldModel_v2()

class WorldModel_v1(o bject):
class Player(object):
def foo(self): pass # v1 implementation of foo()

class WorldModel_v2(o bject):
class Player(WorldMod el_v2.Player):
def foo(self): pass # v2 implementation of foo()
So you are using the WorldModel_* classes as a namespace to hold a
set of classes that might inherit and extend or redefine the previous
classes in a WorldModel_* namespace. This seems to do what you wanted
in your original post, namely if a class is defined in v1 but not in v2
that v2 would just use v1's implementation. WorldModel_v2 will inherit
Player from _v1 by default, so that should work OK out of the box.

So you should be fine there, but I think your question is more practical
than "what is the proper OO way to do it?" which is a bit of a shibboleth
in python. We like "what is easiest and readable?" So here are some
practical recommendations (well, at least that's my intention).

Are you using the *_v1 naming convention for backwards compatibility?
Backwards compatibility is a giant pain in the ass, I notice you are
posting from a .edu address so if this is just something you are working
on by yourself or in a small group drop the versioning aspects from the
code. Talking to the other people in the group is easier.
From your example (which I over-pruned) it looks like you are using

the WorldModel namespace to define parameters for running an iteration
of a game. The classes under "WorldModel " are something like
the rules/physics definition (MovableObject) , coordinates of the team-A
goalpost, coordinates of the team-B goalpost, team-A strategy (Player),
and team-B strategy (also Player). WorldModel would be the gameboard.

If so, make WorldModel just a board - drop putting Player etc under it
as a namespace, and give it a run() function that takes parameters.
Name the Player derivatives as PlayerDumb, PlayerSmart, PlayerAggressiv e
etc, you'll probably have a lot more of those than goals or physics rules.
The actual main routine would look something like

ob = WorldModel() # standard 100x100 board
winner = ob.run(physics= MovableObject, # defines friction and gravity
team_a_goal=(50 ,25),
team_b_goal=(5, 5),
team_a_strategy =PlayerDumb,
team_b_strategy =PlayerAggressi ve,
)
print "Winner is ", winner

I wrote more than I meant to, but the basic idea is don't use classes
when you don't need to - it just makes things more complex. That
should give you more time to tackle the interesting parts (player
strategies, I'd imagine).

-jackdied

[George Sakkis]

> <boiled down version of George's exmaple>

I'm not sure if it was clear to you, but my problem is the dummy
WorldModel_v1.M ovableObject class. It doesn't do anything by itself,
but it has to be in the inheritance chain to make its descendants work
properly.

Are you using the *_v1 naming convention for backwards compatibility?
Backwards compatibility is a giant pain in the ass, I notice you are
posting from a .edu address so if this is just something you are working on by yourself or in a small group drop the versioning aspects from the code.

Sure, if there was a single version there would be no need for this
post, but that's not the point; backwards compatibilty is part of the
sad reality. I'm trying to write a client for a framework that has gone
through 9 protocol version changes so far and now goes for the 10th.
There are 5-7 different game object classes, so this makes 50-70
classes overall for the ten versions. Most of them would be dummy like
the WorldModel_v1.M ovableObject in the example. So the candidate
solutions so far are:
1. Write the dummy classes by hand.
2. Generate them on the fly using some metaprogramming technique
(introspection/metaclass/?)
3. Find an appropriate design pattern that avoids the need for the
dummy classes.

Any ideas for (2) or (3) ?

George

[Dirk Thierbach]

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

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
Interesting problem.
This could be implemented either with multiple inheritance (e.g.
B_V1(B,A_V1))
To help myself thinking about that, let's make a somewhat complicated
example, somewhere in the middle of the graph, with the possibility of
introducing a hole at B3. I also shorten A_Vn to An etc. Consider the
subgraph (with nonstandard annotations of method definition after the bar
(to save space) as explained below):

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

Assume a method g that is present in C2 but not changed in C3. Now g
calls a method f, which is inherited unchanged in C2 from A2 (and not
changed in B2, B3 or C3, either), but changed in A3. Finally, let h
call g in C3. As here the "inheritanc e columns" have "priority", one
would expect then g to call f in A3, and not in A2, for example.

So what you need is that every method, even if not originating from
the "real" class, is looked up first in the column above the "real"
class, then in the column left to that, and so on.

Ok. Multiple inheritance can often select priority for conflicting
methods. If you can specify yhat tou want "column priority" for
each class, you're fine.
or using the bridge design pattern |Z| times, one per each row.
When I read your description above, I also thought immediately
"bridge pattern", but then I tried to write down details,
and got stuck. How would you do it?
Now the problem is that there are 'holes' in this
inheritance lattice: Not all versions introduced new variations of
all types; [...] 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 ?

In the most general case, you need to access time the whole "upper
left" subgraph at class creation, collect all methods defined in this
subgraph with "column priority", and overwrite or add to that any
methods defined in the newly defined class.

I don't know enough about the intricacies of Python's class creation
to make a concrete suggestion, but I'd think that would be possible
with the help of __metaclass__. You would need some sort of
repository for the complete inheritance. One way to do that would
be to create the chain A ... Z first, letting A inherit from some
special class with __metaclass__ set, and then store an array
of all versions somewhere inside the class namespace.

You'd also need some special syntax to create a new version of a class
(say, again inheriting from some special class with __metaclass__
set). You could set the version inside the class definition, and then
let the __metaclass__ routine disable the normal inheritance
mechanism, and add missing methods as appropriate.

This could for example look like

class A(Versioning):
...

class B(A):
...

class C(B):
def h ...
...

class A2(NewVersion,A ):
__version__ = 2
def f(): ...

class B2(NewVersion,B ):
__version__ = 2

class C2(NewVersion,C ):
__version__ = 2
def g(): ... f() ...

class A3(NewVersion,A ):
__version__ = 3
def f(): ...

class C3(NewVersion,C ):
__version__ = 3
def h(): ... g() ...

with a hole at B3, as in the example. C3 will get g from C2 and f from
A3, and hence the call chain will work correctly. Also, C3 will have no
base classes (or maybe only the __metaclass__ ones), the inherited
class A, B, C are just used by the class creation process to find
out where to look for the inheritance matrix.

Others who know more about the class creation mechanism will no doubt
improve this suggestion, point out my errors, and tell you how to
implement it :-) Note that you're basically completely changing the
normal inheritance mechanism, and the class objects will be larger,
because they'll have to copy all the necessary methods.

I cannot think of any pattern that would give similar flexibility.

- Dirk

[Michael Spencer]

George Sakkis wrote:

<boiled down version of George's exmaple>

I'm not sure if it was clear to you, but my problem is the dummy
WorldModel_v1.M ovableObject class. It doesn't do anything by itself,
but it has to be in the inheritance chain to make its descendants work
properly.

George,

since you explicit allowed metaprogramming hacks :-), how about something like
this (not tested beyond what you see):

class WorldVersion(ty pe):
"""WorldVer sion instances are World classes
If a World inherits from another World: Field, Movable, Player
automatically inherit from their corresponding superclasses"""

def __new__(self, name, bases, clsdict):
clslist = set(["Field", "Movable", "Player"])
baseworld = bases[0]
if type(baseworld) is self:
for cls in clslist:
base = getattr(basewor ld,cls)
target = clsdict.setdefa ult(cls, base)
if base is target:
continue
oldbases = list(target.__b ases__)
if base in target.__bases_ _:
continue
try:
oldbases[oldbases.index( object)] = base
except ValueError:
oldbases.append (base)
target = type(target.__n ame__, tuple(oldbases) ,
dict(target.__d ict__))
clsdict[cls] = target

return type.__new__(se lf,name, bases, clsdict)

class World1(object):
__metaclass__ = WorldVersion
class Field(object):
def position(self):
print "Positionin g in World1"
class Movable(Field):
def move(self):
print "Moving in World1"
class Player(Movable) :
def passBall(self):
print "Passing in World1"

class World2(World1):
__metaclass__ = WorldVersion
class Field(object):
def position(self):
print "Positionin g in World2"
class Movable(Field): # You still need placeholder classes
# but they are trivial
pass
class Player(Movable) :
def passBall(self):
print "Passing in World2"

class World3(World2):
__metaclass__ = WorldVersion
class Player(object):
def passBall(self):
print "Passing in World3"

p3 = World3.Player()
p3.move() Moving in World1 p3.position() Positioning in World2 p3.passBall() Passing in World2

Michael

[George Sakkis]

"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

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

George

[Michael Spencer]

George Sakkis wrote:

Nice try, but ideally all boilerplate classes would rather be avoided
(at least being written explicitly).
It depends on how much magic you are prepared to accept; this goal is somewhat
in conflict with the next one...

Also, it is not obvious in your solution why and which placeholder classes have to be written (like
World2.Movable) and which do not.
It is systematic, if not obvious. You need place holder classes only if you
need to propagate new methods within a given world. More magic would make this
even less obvious.

By the way, my current working solution involves copying and pasting verbatim these classes :-)

It appears to be basically the same as mine except you spell out the previous
version explicitly (not that that's bad!)

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.

Michael

[Dirk Thierbach]

Dirk Thierbach <dt********@use net.arcornews.d e> wrote:

Ok. Multiple inheritance can often select priority for conflicting
methods. If you can specify yhat tou want "column priority" for
each class, you're fine.

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

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.

Interesting question. I learned a lot while thinking about that.

- Dirk