Re: LSP and subtype

Responding to Huber...

H. S. Lahman wrote:

Um, why is the "happiness" of some *particular* client code
important? As long as all foo overrides respect the invariants, pre-
&
postconditions that Base documents/relies on then *any* imaginable
client code will run just fine with *any* subclass object of Base,
won't it? IOW, the client just needs to be happy with the documented
behavior (again invariants, pre- & postconditions) of Base and never
needs to know that there are in fact subclasses and overrides.



The relationship between the Client and the member of the tree needs
to be defined for each client.  When evaluating the collaboration the
developer must determine where in the tree the Client will access
objects.  That decision must be made on a client-by-client basis.

For the tree above it is entirely possible that for a given class of
Client objects the only behavior that is acceptable is Sub2.foo().  If
that is the case the developer must establish a relationship between
the Client class and only the Sub1 class.  That is the only way ot
capture the constraint on the collaboration that the Base.foo()
behavior is not acceptable to the Client.


Do you have a real-world example for such a case? 

               [Missile]
               + assignTarget()
                   A
                   | R1
         +---------+------------+
         |                      |
    [Ballistic]              [Cruise]
         | *                    | *
         | launches             | launches
         |                      |
         | R2                   | R3
         |                      |
         | 1                    | 1
     [NORADSilo]        [AegisCruiser]

Assume assignTarget is essentially a device driver that initializes the missile hardware. The hardware addressed by assignTarget will be quite different for the two subclasses so it would be an error for the NORADSilo to invoke the implementation for a cruise missile. One captures that with the constraint that a NORAD silo only deals with ballistic missiles and an Aegis cruiser only deals with cruise missiles. The missile taxonomy has many members but the particular clients are very picky about which members they collaborate with.

We could add a third client, TridentSubmarine, which is capable of launching both and is, therefore, indifferent to the implementation of the subclass so long as it works for the Missile in hand. In that case on has:

                         * launches         1
               [Missile] -------------------- [TridentSubmarine]
               + assignTarget()
                   A
                   | R1
         +---------+------------+
         |                      |
    [Ballistic]              [Cruise]
         | *                    | *
         | launches             | launches
         |                      |
         | R2                   | R3
         |                      |
         | 1                    | 1
     [NORADSilo]        [AegisCruiser]

Note that the issue here is really inseparable from the relationships with the clients. One defines the level in the tree where collaboration takes place based upon what implementations are valid for the client. If a NORAD silo only has ballistic missiles it makes no sense to define the collaboration at the [Missile] level since that says the NORAD silo would be happy with a cruise missile.

While that seems to be a distinction at the level of what-kind-of-missile-do-you-have, it really isn't in OOA/D. That's because the set of ballistic missiles is defined by their membership in the [Ballistic] class. That class, in turn, is defined by the properties that its set members share, one of which is the behavior assignTarget that is different enough to warrant subclassing. So where one instantiates the R2 relationship really depends upon what implementation of assignTarget is satisfactory to the client.

Bottom line: in the end the assignment of the R2 relationship requires that the notion of 'ballistic missile' is consistent in both the notion of [Missile] subclassing properties needed by the client and the problem space notion of a NORAD silo only having one "type" of missile available. IOW, both views have to play together properly (which can make software construction something of an art).

That was pretty much my point.  The pitfall from an LSP perspective
is that one cannot arbitrarily add new subclass implementations
without validating them against the existing client access contexts.




Same disagreement as above, I think you can leave client access
contexts out of the discussion.



If Base.foo() and Sub1.foo() are acceptable to the existing clients
one still has to make sure that Sub3.foo() is also acceptable.  This
is a really basic maintenance issue anytime one updates a subclassing
tree. If there are overrides it is possible to break the existing
clients when an instance of the new subclass is presented to them. To
put it another way, validating the clients' access is the only
/practical/ way to ensure one is not creating an LSP problem when
adding the new behavior to the tree.



That is contrary to my experience. With the usually flat inheritance
trees I design and use I very rarely run into an LSP problem anyway. In
the few cases when I did in fact run into such a problem it always
turned out to be either:

1. a doc problem in the base class
2. The method granularity wasn't right (one method tried to do too much
or too little), i.e. the base class interface wasn't thought out well to
begin with
3. a violation of the LSP in the newly added derived class

I submit that these are symptoms that when the original access was provided the developer did not properly envision the future Sub3 addition. For (1) the base class needed to be documented to include the future Sub3 description AND the developer had to ignore that. For (2) the original developer simply did not anticipate the later Sub3 addition in documenting Base. And (3) is only an LSP error if (1) was written solely for the original solution context (i.e., did not include the possibility of adding Sub3). IOW, (3) arises because the context changed.

We do OO because we have given up on trying to anticipate every future feature or requirements change. Instead we solve /only/ the problem in hand in the most direct manner that is consistent with the problem space as we understand it. But we do OO because we know things will change and we want to construct the solution in a manner that allows us to modify the solution later with minimal hassle. (Recall that we got started on this because I believe that implementation inheritance with overrides tends to create more maintenance foot-shooting than compensated for by its benefits.)

The corollary, though, is that when maintenance is done the developer must worry about things like LSP violations _of the original solution context_. Such LSP violations will be manifested in breaking existing client collaborations. However, apropos of your (3), if the existing clients are not broken, then there is no LSP violation. B-) Yet. B-)) That is basically what I was trying to get at in this context -- as a practical matter one really can't tell whether a new Sub3 represents and LSP violation until one looks at the existing clients' collaborations.


Apropos of your point above about DbC conditions, there is really no
way to write such conditions in practice to deal with OO inclusion
polymorphism.  That's because one is not really substituting
different implementations of the same semantics; one is
substituting different behavior semantics.  So the post conditions
between subclasses will usually be different.  IOW, adding a new
subclass behavior almost always changes the base class' ORed
postcondition specification. The only way to effectively deal with
that is by raising the level
of abstraction of the base class condition specification.  So if we
have: 1        attacks 1
[Predator] ------------------ [Prey]
                                A
                                |
                    +-----------+
                    |           |
                [Gazelle]  [Impala]
                + run()    + run ()

we can implement a Prey.run behavior for the base class and things
will Just Work from an LSP perspective.  But now suppose we add:

           1        attacks 1
[Predator] ------------------ [Prey]
                                A
                                |
                    +-----------+----------+
                    |           |          |
                [Gazelle]  [Impala]   [Pheasant]
                + run()    + run ()   + takeFlight()

Now Prey.run() doesn't cut it.  We can fix that by abstracting the
postcondition and providing a Prey.flee() behavior.  However, it we
add:
           1        attacks 1
[Predator] ------------------ [Prey]
                                A
                                |
                    +-----------+----------+-----------------+
                    |           |          |                 |
                [Gazelle]  [Impala]   [Pheasant]      [Brontosaurus]
+ run()    + run ()   + takeFlight()
+ stomp() we have a new problem.  We can raise the level of
abstraction again
and upgrade the [Prey] postcondition to Prey.respondToAttack().




This just shows that run() was wrong to begin with. I'm suspicious
whether even respondToAttack is right, because technically a predator
doesn't/shouldn't really tell its prey to respond to its attack. I
think the attack should more adequately be seen as an event to which
Prey subclasses will react. That is, in a real-world design there's
usually one more level of indirection. But I guess that's what
you're hinting at below anyway.



run() is only wrong when one does maintenance and adds new subclasses;
in the first situation it was Just Fine.



I don't think so. If I really ever had to develop a game with predators
and prey I'm sure I personally would never have thought that run() is a
good interface (at least not after going through the minimal experience
you get during CS studies).

I think this is related to the notion of not anticipating the future and only solving the problem in hand. If the only prey in the game are Impalas and Gazelles, then that represents the world one needs to abstract. It just complicates the solution to model things that one doesn't need to solve the problem.

If the game is a text-based RPG (anybody remember Zork?), would you include a complicated articulated skeleton representation suitable for simple graphics for critters? Now that is an extreme, but the problem is locating a place to draw the line in the sand about what future features and possible changes one needs to support in the current solution.

Philosophically the OO approach is to resolve only the requirements in hand and rely on a construction methodology that will allow changes to be made easily later.

[BTW, as I think I mentioned, as the OOA/D level much of this problem goes away because messages and interfaces can be represented separately from behaviors. So behaviors could be named run, takeFlight, and stomp or whatever else the future might bring. So one just has a mapping problem rather than a semantic problem.]

Well, it totally depends on how much the requirements change. If they
really change so much that you can't add a new subclass without breaking
the existing Prey interface then yes there's no way around checking
every client.

Ok, I guess I'm starting to see why you keep saying that one needs to
check existing clients when one adds new subclasses. I agree that you
need to do that in the run --> respondToAttack scenario, because you
have effectively changed the behavior/interface of Prey. There's no
way around that.



I believe that is generally true in OO subclassing because we do
routinely provide different behaviors.  Base behaviors like "sort"
where one can truly just substitute different implementations without
affecting the semantics tend to be quite rare.  [In fact, I have a
hard time thinking of a practical example where such a pure
implementation substitution isn't a response to just nonfunctional
requirements at the OOD/P level.



What about Streams? The location where a byte-stream goes or comes from
is certainly a functional requirement.

First, let me qualify that I am really talking just about problem space abstractions needed to resolve functional requirements. Computing space artifacts like streams only show up at the OOD/P level to resolve nonfunctional requirements. The software structure that ensures decoupling and maintainability is mostly done at OOA/D level and that is where I have a problem with implementation overrides in subclassing.

So I have to disagree with the example. Whether one uses a byte stream, shared memory, or heliograph signals is a pure implementation decision within the computing space. The functional requirements only specify what /information/ must be communicated between A and B. (There may be nonfunctional requirements, such a performance or a need to interface with another piece of software, that would severely limit the choices at the OOP level.)

Similarly the functional requirements only identify A and B in terms of problem space entities so one is free to abstract them any way one wants so long as those requirements are satisfied. (Again nonfunctional requirements may effectively demand very detailed choices at the OOP level.)

In the end any message can be abstracted as {message ID, target address, [data packet]}, which is exactly what one does in an OOA model where one resolves /only/ functional requirements. So any subclassing done by ..NET or whoever for things like streams is not really relevant. (Fortunately LSP problems due to later maintenance is usually not a major problem for computing space abstractions because the underlying semantics doesn't change.)

[BTW, this problem exists in no small part because the OOPLs do not
separate message and method because they are all implemented with
type systems and they all employ procedural message passing.  If
one only needed to define the messages that a [Prey] would accept,
most of the LSP problems evaporate.




I don't think that the problems evaporate just because you define
messages instead of methods. Even in a message scenario "run" is
simply the wrong message. Sending an attackImminent message would
much better convey what is happening. In a more complex scenario one
would probably more adequately send appropriate sound & vision
events, which Prey subclass objects use to establish that an attack
is imminent. As mentioned above, Predator should probably not
interact with Prey directly.
I also think that this has only little to do with procedural vs.
message-oriented. In a procedural language there's "only" more work
to do. I.e. you have to implement a message-oriented system yourself
or use a library.



I think they evaporate because if one truly separates message and
response, then the message is just an announcement of something the
sender did.  That means the sender implementation does not to know
about the response, much less depend in any way on what the responder
does, so LSP becomes academic.



Right, but as I said, you'd never think of sending a "run" message in
such an environment. So "message-basedness" alone doesn't do the job,
the problems evaporate because the prey interface was improved. You no
longer impratively say "run". If you had chosen respondToAttack() as
Prey interface right in the beginning then there wouldn't have been as
many problems with adding additional subclasses.

But why worry about it? We only need to have the imperative in the interface because the OOPLs force us to do so. That raises defining Base methods to an art form where one must consider all possible present and future contexts.

If I separate the message from the method, then I can name the methods run, takeFlight, stomp, or whatever is appropriate as subclasses are added. Then I make the message that Base responds to "chases" or "attacks", which is meaningful as a sender announcement, and I can map that to the relevant behavior. Thus the message and the method have entirely different semantics in the client and service contexts without any LSP problems. The only constraint I am left with is that every subclass must provide /some/ method to respond to any message the Base accepts.

[Of course the problem of LSP has just been moved elsewhere from the client. One still must decide where the client will access the tree and that depends on what behaviors are appropriate for the client collaboration. But collaboration is a solution flow of control and message addressing problem so now one has converted the problem to a more abstract static relationship problem.]


That's because separation of message and
method decouples the contexts so there is no expectation of specific
behavior on the part of the client.  Thus there is no contract with
the client
per se.  The message simply becomes an announcement of something the
client did.  The developer could then map that announcement to the
proper response in the interface.  That does involve contract
enforcement but it is at a quite different level of abstraction
(e.g., a UML Interaction Diagram).]




Right, but that's just an artifact of the rather special relationship
Predator <--> Prey. Procedural interaction is usually just fine
between everyday objects like FileStream and Whatever, because
Whatever can (and must be able to) rely on the documented behavior
of FileStream. Predator and Prey are much more loosely coupled.



I could argue that FileStream is a computing space artifact and it is
unlikely to change significantly because it is really mathematically
defined.  Customer problems spaces aren't though, which is what makes
constructing software interesting.  That is, the OO paradigm is
focused on properly abstracting customer problem spaces in a manner
that is maintainable in the face of volatile requirements.  One
technique for doing that is implementation independence, which is
what drives the conceptual separation of message and method.  One
only gets into trouble at the OOP level where they aren't separated.



You keep saying that. You only get into trouble when you don't see that
the problem at hand requires messages-based interaction instead of
method-based interaction. An architect not seeing that is a bad
architect. Surely, a OOPL makes it easy for newbies to fall into this
trap but an experienced architect won't.

But that's why OOA/D is message-based (and behavior access is assumed to be asynchronous). If they are separated, then one can't write client implementations so that they depend on what the response is. That implementation independence is the real goal and enables maintainability. Once the OOA/D has been structured so that is true, it doesn't matter that the OOPLs use procedural message passing -- the software /structure/ is already decoupled. IOW, in OOA/D the "architect" doesn't have a choice about thinking message-based. (In fact, the translation methodology I use describes /all/ object behavior with state machines so client and service are always decoupled through events.)

To put it another way, in a well-formed OO application Filestream should be just as "loosely coupled" with its clients as Prey. If that is not the case, then the problem lies with the Filestream implementation.


Then it becomes must easier to make caller implementations dependent
on callee responses because of expectations arising from encoding
procedural-style Do This calls.



Which are just fine most of the time. It is only for the rather special
and rare Predator <--> Prey style relationships where you need and
benefit from message-based interaction.
Message-based interaction has problems of its own you only want to deal
with when you must.

On the contrary, one gets the benefit of it for /all/ object collaborations -- provided the OOA/D is done properly.

                  [Base]
                  + foo()
                    A
                    |
          +---------+--------+
          |                  |
        [SubA]            [Sub3]
          A               + foo()
          |
    +-----+------+
    |            |
  [Sub1]       [Sub2]
  + foo()      + foo()

Not only do we have to perform more surgery on the tree, we have
to change the calling context in Client to invoke SubA.foo()
rather than Base.foo().  Thus the Client has to understand the
tree to invoke the correct property implementations





How could this ever fix the problem above? Sub3.foo() is buggy, no
amount of rearranging the inheritance tree will fix that.




It fixes the problem because the Client can unambiguously access the
tree at the [SubA] level so it never gets the unacceptable [Sub3]
behavior.




Right, that fixes the problem by effectively not calling the buggy
code. I'm not sure whether that's very helpful in practice because
someone somewhere implemented Sub3 for a reason.

The OOP implementation can then ensure the relationship 


But it shouldn't be "buggy" code if that is the way the problem space
taxonomy works.  The fact is that different subsets of Base objects
have three different behaviors (four if Base is not abstract) and not
all of those behaviors may be appropriate for particular clients.
Going back to the Prey example, consider:

             [Prey]
                A
                |
      +---------+---------------+
      |                         |
   [Bird]                   [Antelope]
   + takeflight()           + run()
                                A
                                |
                      +---------+-------+---...
                      |                 |
                  [Gazelle]         [Impala]

Now let's say I have two flavors of [Predator], [Hawk] and [Lion] and
assume lions can't catch birds that take flight.  If the goal of the
collaborations is for the predator to satisfy its hunger, then hawks
are not going to attack antelopes and lions are not going to attack
birds. (It's just an example so let's not pick on the exceptions.) In
that case the behavior of takeFlight for [Lion] and run for [Hawk]
are inappropriate and could lead to LSP problems.  So neither predator
should have a direct relationship with [Prey]; instead their
relationships should be with [Bird] or [Antelope].


This is a totally different situation than the original one.

My fault, I should have been more explicit that I was talking about the difference in /behaviors/, which I spelled out as takeFlight and run, rather than the interface. Look at my example assuming a [Prey] interface behavior of respondToAttack that [Bird], [Antelope], et al must implement. When respondToAttack is invoked for a Bird one gets the takeFlight behavior and if it is invoked for the Antelope one gets the run behavior. The point is that when a Hawk invokes respondToAttack the only acceptable behavior is takeFlight and when a Lion invokes respondToAttack the only acceptable behavior is run.

is instantiated only with [SubA] members of [Base].  The downside is
that the Client must understand where to access the tree so if the
tree changes the Client may become broken.




Agreed, but let's be clear that this is not because something is
wrong with subclassing non-abstract classes or overriding methods
per se.


I never said there was anything wrong with subclassing; it is one of 


Note that I said "subclassing *non-abstract* classes", doesn't that
imply implementation inheritance?


Kazakov covered this.

the most important tools in the OO arsenal.  What I do contend is that
implementation inheritance in general and implementation overrides in
particular are not good OO practice (in most situations).  That's
because they open the door to maintainability problems later.


So what's a language that's not poorly formed?


I must have missed that answer...

From a purist OOA/D viewpoint they are all poorly formed; its a matter of degree. Some things, like procedural message passing, are intrinsic to being 3GLs. Some things, like the attribute access mess, they fix after a few decades. Some things, like implementation overrides in inheritance they haven't gotten around to yet.


But OOPLs are crippled by being 3GLS and are
necessarily bound closely to hardware computational models.



Oh, are they? How is the Java language bound to a hardware computational
model? Or would you say Java is 4GL?

Java a 4GL?!? Surely you jest; it's barely a 3GL!. Any language that employs procedural message passing and block structuring is a 3GL. The 3GLs are very closely mapped into the hardware computational models of Turing and von Neumann and that permeates everything from syntax to the graph algorithms used for scoping. For example, the Java execution model is a pure synchronous model. Any support for concurrency is provided by thread library overlays that /emulate/ concurrency through time slicing.

There are various definitions of 4GL but I think the most useful one is that the solution description is independent of the specific computing environment. That is, it can be implemented unambiguously without change on any platform in any language using any computing space technology (e.g., RDBs, OODBs, XML, J2EE, .NET, etc.).


*************
There is nothing wrong with me that could
not be cured by a capful of Drano.

H. S. Lahman
hsl@xxxxxxxxxxxxxxxxx
Pathfinder Solutions  -- Put MDA to Work
http://www.pathfindermda.com
blog: http://pathfinderpeople.blogs.com/hslahman
(888)OOA-PATH



.

Quantcast