Puzzling OO design problem

Discussion in 'Python' started by George Sakkis, Apr 9, 2005.

  1. 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
    George Sakkis, Apr 9, 2005
    #1
    1. Advertising

  2. 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
    Jack Diederich, Apr 9, 2005
    #2
    1. Advertising

  3. > 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 worldModelFactory(version):
    if version < 2: return WorldModel()
    else: return WorldModel_v2()

    class WorldModel(object):

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

    class FieldObject(object):
    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(FieldObject):
    def speed(self):
    '''Get or estimate the current speed.'''
    # [implementation snipped]

    class Player(MovableObject):
    def passBall(self,power,teammate):
    '''Pass the ball to the teammate.'''
    # [implementation snipped]


    class WorldModel_v2(WorldModel):

    class FieldObject(WorldModel.FieldObject):
    '''New implementation of FieldObject.'''
    def position(self):
    # [new implementation snipped]
    pass

    class MovableObject(WorldModel.MovableObject, FieldObject):
    '''MovableObject didn't change since the previous version. The
    only reason for this class is to make
    WorldModel_v2.FieldObject
    accessible to WorldModel_v2.Player.
    '''
    pass

    class Player(WorldModel.Player, MovableObject):
    '''New implementation of Player.'''
    def passBall(self,power,teammate):
    # WorldModel_v2.FieldObject.position() should be called
    myPosition = self.position()
    # [new implementation snipped]

    #=============================
    George Sakkis, Apr 9, 2005
    #3
  4. 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 worldModelFactory(version):
    > if version < 2: return WorldModel()
    > else: return WorldModel_v2()
    >
    > class WorldModel_v1(object):
    > class Player(object):
    > def foo(self): pass # v1 implementation of foo()
    >
    > class WorldModel_v2(object):
    > class Player(WorldModel_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, PlayerAggressive
    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=PlayerAggressive,
    )
    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
    Jack Diederich, Apr 9, 2005
    #4
  5. > <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.MovableObject 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.MovableObject 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
    George Sakkis, Apr 9, 2005
    #5
  6. George Sakkis <> 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 "inheritance 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
    Dirk Thierbach, Apr 9, 2005
    #6
  7. 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.MovableObject 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(type):
    """WorldVersion 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(baseworld,cls)
    target = clsdict.setdefault(cls, base)
    if base is target:
    continue
    oldbases = list(target.__bases__)
    if base in target.__bases__:
    continue
    try:
    oldbases[oldbases.index(object)] = base
    except ValueError:
    oldbases.append(base)
    target = type(target.__name__, tuple(oldbases),
    dict(target.__dict__))
    clsdict[cls] = target



    return type.__new__(self,name, bases, clsdict)

    class World1(object):
    __metaclass__ = WorldVersion
    class Field(object):
    def position(self):
    print "Positioning 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 "Positioning 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
    Michael Spencer, Apr 9, 2005
    #7
  8. "Michael Spencer" <> 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(PreviousNamespace.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 PreviousNamespace
    class Namespace(PreviousNamespace):
    class A(PreviousNamespace.A):
    def foo(self): return "version_2.foo()"
    class B(PreviousNamespace.B, A):
    pass
    class C(PreviousNamespace.C, B):
    pass
    #======================================================
    # version_3.py

    from version_2 import Namespace as PreviousNamespace
    class Namespace(PreviousNamespace):
    class A(PreviousNamespace.A):
    pass
    class B(PreviousNamespace.B, A):
    def bar(self): return "version_3.bar()"
    class C(PreviousNamespace.C, B):
    pass

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

    def NamespaceFactory(version):
    return __import__("version_%d" % version).Namespace

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

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

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

    George
    George Sakkis, Apr 9, 2005
    #8
  9. Dirk Thierbach <> 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/linearization-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
    Dirk Thierbach, Apr 9, 2005
    #9
  10. 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
    Michael Spencer, Apr 9, 2005
    #10
  11. George Sakkis

    El Pitonero Guest

    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(cls, version))

    def versionize(w, cls, version):
    import inspect
    methods = inspect.getmembers(version, inspect.ismethod)
    methods = [m[1] for m in methods if m[0].split('_')[0] ==
    cls.__name__]
    for m in methods:
    m_name = '_'.join(m.__name__.split('_')[1:])
    import new
    im = new.instancemethod(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(Version1):
    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'
    El Pitonero, Apr 9, 2005
    #11
  12. > 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/linearization-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, Apr 9, 2005
    #12
  13. > 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
    George Sakkis, Apr 9, 2005
    #13
  14. George Sakkis

    Kay Schluehr Guest

    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(object):
    def __init__(self):
    self.class_names = [] # 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_names.append(names)

    def add_arrow(self,arrow):
    self.arrows.append(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[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_names[k][j]
    if name:
    break
    k-=1
    if not name:
    raise ClassGridError,"Wrong arrow matrix"
    bases.append(self.classes[name])
    if arrow%l == 0: # search leftmost
    k = j-1
    while k>=0:
    name = self.class_names[k]
    if name:
    break
    k-=1
    if not name:
    raise ClassGridError,"Wrong arrow matrix"
    bases.append(self.classes[name])
    self.classes[cls_name] =
    type(cls_name,tuple(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_classes()

    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
    Kay Schluehr, Apr 9, 2005
    #14
  15. 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/comp.lang.python/msg/77ef889e9f99696c
    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(baseworld, 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
    Michael Spencer, Apr 9, 2005
    #15
  16. 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/linearization-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>
    Michele Simionato, Apr 10, 2005
    #16
  17. On 9 Apr 2005 03:49:19 -0700, "George Sakkis" <> wrote:

    >"Michael Spencer" <> 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(PreviousNamespace.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 PreviousNamespace
    >class Namespace(PreviousNamespace):
    > class A(PreviousNamespace.A):
    > def foo(self): return "version_2.foo()"
    > class B(PreviousNamespace.B, A):
    > pass
    > class C(PreviousNamespace.C, B):
    > pass
    >#======================================================
    ># version_3.py
    >
    >from version_2 import Namespace as PreviousNamespace
    >class Namespace(PreviousNamespace):
    > class A(PreviousNamespace.A):
    > pass
    > class B(PreviousNamespace.B, A):
    > def bar(self): return "version_3.bar()"
    > class C(PreviousNamespace.C, B):
    > pass
    >
    >#======================================================
    ># test.py
    ># command: python test.py <#version>
    >
    >def NamespaceFactory(version):
    > return __import__("version_%d" % version).Namespace
    >
    >print NamespaceFactory(2).B().foo() # "version_2.foo()"
    >print NamespaceFactory(3).C().bar() # "version_3.bar()"
    >
    >import sys, inspect
    >namespace = NamespaceFactory(int(sys.argv[1]))
    ># print the __mro__ of each 'inner' class
    >for name,cls in inspect.getmembers(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 PreviousNamespace
    class Namespace(PreviousNamespace):
    __metaclass__ = vars(PreviousNamespace)['__metaclass__']

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

    and

    ----< version_3.py >-----------
    from version_2 import Namespace as PreviousNamespace
    class Namespace(PreviousNamespace):
    __metaclass__ = vars(PreviousNamespace)['__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_CLASSNAMES = ['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(nsdict).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(NAMESPACE_CLASSNAMES):
    cbases = (vars(nsbases[0])[cname],) + (i and (nsdict[NAMESPACE_CLASSNAMES[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.metadeco)'}
    cdict['__module__'] = nsdict['__module__']
    nsdict[cname] = type(cname, cbases, cdict)
    return type(nsname, nsbases, nsdict)

    class Namespace(object):
    __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 PreviousNamespace
    class Namespace(PreviousNamespace):
    __metaclass__ = vars(PreviousNamespace)['__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 PreviousNamespace
    class Namespace(PreviousNamespace):
    __metaclass__ = vars(PreviousNamespace)['__metaclass__']

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

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

    def NamespaceFactory(version):
    return __import__("version_%d" % version).Namespace

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

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

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

    Run:

    [ 5:33] C:\pywk\clp\sakkis\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
    Bengt Richter, Apr 10, 2005
    #17
  18. George Sakkis <> 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
    Dirk Thierbach, Apr 10, 2005
    #18
  19. "Bengt Richter" <> wrote in message
    news:...
    >
    > 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.GameUnit.move()"
    class CombatUnit(GameUnit):
    def fight(self): return "MedievalAge.CombatUnit.fight()"
    class RangedUnit(CombatUnit):
    def aim(self): return "MedievalAge.RangedUnit.aim()"

    class ColonialAge(Era):
    __metaclass__ = Namespace(MedievalAge)
    class CombatUnit:
    def fight(self): return "ColonialAge.CombatUnit.fight()"

    class IndustrialAge(Era):
    __metaclass__ = Namespace(ColonialAge)
    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).__name__,
    type(player).__name__,
    action, result)
    George Sakkis, Apr 11, 2005
    #19
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. GaryM
    Replies:
    0
    Views:
    299
    GaryM
    Dec 21, 2003
  2. Richard

    puzzling <div> problem

    Richard, Sep 12, 2003, in forum: HTML
    Replies:
    2
    Views:
    341
  3. Dfenestr8

    Puzzling form/cgi problem

    Dfenestr8, Nov 2, 2003, in forum: Python
    Replies:
    2
    Views:
    496
    Bengt Richter
    Nov 3, 2003
  4. CS ADNT

    Puzzling xsl problem

    CS ADNT, Feb 19, 2010, in forum: ASP .Net
    Replies:
    3
    Views:
    457
    Alexey Smirnov
    Feb 23, 2010
  5. richard

    Puzzling problem with code

    richard, Feb 18, 2013, in forum: HTML
    Replies:
    5
    Views:
    451
    Mike Duffy
    Feb 19, 2013
Loading...

Share This Page