From: Dmitry A. Kazakov on
On Wed, 16 Aug 2006 14:53:44 GMT, H. S. Lahman wrote:

> Responding to Kazakov...
>
>>>Not if they are abstracted properly for the problem in hand. I agree
>>>that OO abstraction is limited and, therefore, one cannot exactly match
>>>the underlying entity. That is pretty much in the nature of
>>>abstraction. But one can match reality closely enough in particular
>>>problem contexts to satisfy LSP.
>>>
>>>Better yet, one can ensure robustness in the OO application by
>>>/requiring/ LSP compliance for the particular problem in hand. IOW, one
>>>does not ignore LSP when a particular set of property abstractions don't
>>>support compliance properly for the problem in hand; one finds a
>>>different suite of property abstractions that do support it.
>>
>> Again, it is a heavy conceptual disagreement between us. In my view, a
>> properly functioning program is not equivalent to LSP satisfied. You are
>> mixing domains and languages here. Basically, it is a fly and aerodynamics,
>> once more.
>
> OBviously a functioning program is going to depend on a lot more than
> just LSP being being satisfied. But LSP compliance is still a good way
> to ensure proper functioning.

It cannot. You are still mixing things. A trivial counter example would be
an x86 program executed on a 68k processor. CPU does not know OO!

> I don't like the fly and aerodynamics analogy. LSP in an OO context is
> about defining the /intrinsic/ properties of a fly.

I disagree. LSP is about properties of flying things, insects, species. It
is not about a fly. It is about flies. More generally, it is about
interaction of sets of things with their elements and other sets (sounds
much like OOA/D to me, but never mind). When you reduce it to individual
entities, then all substitutability problems automatically disappear. But
it would be absolutely unrealistic agenda.

> To that end one
> needs to abstract -- at most -- a very restricted view of aerodynamics
> that is needed to describe how the fly itself works in the problem
> context. One is not interested in how aerodynamics applies to airplanes
> or Frisbees.

It is not required, but you never know upfront what are the consequences of
something not required. This problem to solve is actually
"substitutability" of models.

> Yes and no. My issue was around individual members of the set. Sure,
> one can deal with larger integers in a variety of ways, with or without
> objects. But when you do so you are artificially subdividing the
> mathematician's notion of 'integer' and modifying it, which was my
> point. Thus when the 3GL defines "int" as a fundamental type, it ain't
> your mathematician's 'integer' any more that your Silver Ghost object is
> your rare car dealer's notion of 'Silver Ghost'.

Yes, it is not integer. Further the actual problem is not infiniteness of
the integer set, or squares, for they are infinite as well and even
individual squares have properties you will never be able to model. The
problem is that any abstraction, any move you make in the solution space
inherently violates something. Surely you can get rid of this by descending
abstraction levels down to treating each memory bit individually, but this
cure is worse than the disease.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de
From: Frans Bouma on
H. S. Lahman wrote:

> Responding to Ulf...
> > Their observation applies equally in object-oriented modelling to
> > what you call "class systems:" We need a behavioral notion of
> > generalization/specialization. A simple example:
> >
> > Class A has a protected attribute x set in the constructor, and a
> > message m1 computing a value F(x) based on x (and returing it or
> > sending it to some other object).
> >
> > Hence a modeller of clients of A objects can expect that their x
> > attribute can never change after construction. But then the A-client
> > part of the model may be broken if the A-part of the model is
> > extended by specializing A to a class B with an additional message
> > m2 whose behavior includes changing the inherited x attribute, and
> > if instances of B are created and brought into an A-client context.
> >
> > Liskov and Wing proposed a behavioral subtyping rule, which they
> > proved to enforce the LSP. Let me try to translate it, AFAIKR, into
> > OOM-talk to obtain a modelling rule. It should be sth like:
> >
> > In a generalization relationship between two classes, the subclass's
> > modeled behavior on receiving an inherited message must be
> > consistent with the superclass's behavior on that message
> > - after the same history of message exchange
> > - but also after histories containing additionally the exchange of
> > the *new messages* introduced in the subclass (like m2 above).
>
> Here we disagree somewhat. What you are describing here is
> implementation inheritance (i.e., the subclass overrides a defined
> property implementation that already exists in a superclass). This
> was one of those ideas in early OO development that seemed like a
> good idea at the time but in practice led to more problems than it
> cured. However, in modern practice one tries to avoid implementation
> inheritance for a variety of reasons, of which fragile
> maintainability is even more important that the potential for LSP
> problems. So in a well-formed OO application responsibilities are
> only implemented at the leaf subclass level, which creates an
> environment of pure substitution between subclass implementations of
> a superclass responsibility.

Isn't that somewhat like bending reality to meet a certain definition
D of said reality? Because I find the requirement to implement type
definitions only at the leaf level too restrictive, and to me it seems
this requirement is invented not to be practical but to be able to meet
a given principle's demands.

Because what about the situation where the developer has to work with
a library where a given class C has a processing method M and this
method M can be replaced by your own if you want to, but you don't have
to. In effect, doing implementation inheritance. Is this then 'bad
practise' ? If so, why? I don't see it, especially because the library
has to supply a functional M, however also wants to be flexible so that
a developer could replace the method with an override in a derived
class.

FB


--
------------------------------------------------------------------------
Lead developer of LLBLGen Pro, the productive O/R mapper for .NET
LLBLGen Pro website: http://www.llblgen.com
My .NET blog: http://weblogs.asp.net/fbouma
Microsoft MVP (C#)
------------------------------------------------------------------------
From: S Perryman on
"Mark Nicholls" <Nicholls.Mark(a)mtvne.com> wrote in message
news:1155818667.712103.216720(a)m73g2000cwd.googlegroups.com...

> S Perryman wrote:

>> "Mark Nicholls" <Nicholls.Mark(a)mtvne.com> wrote in message
>> news:1155807673.140835.86680(a)b28g2000cwb.googlegroups.com...

>> See the Circle/Ellipse problem.

> I don't believe it looses semantic correctness!....it's just the
> abstraction does not match 'reality'.....

If the "abstraction" deviates from the "reality" , is the abstraction a
correct representation of the reality ??


>>> Dmitry claims to need a mathematical foundation to OO....I believe it
>>> either exists or is trivial for a competent mathematician (which I am
>>> not)....does it exist for Liskov/Wing types?

>> A mathematical definition of Liskov/Wing subtypes can be derived from
>> the source papers. In my Usenet posting of old, I did a semi-formal def
>> of the Liskov/Wing subtype. It should be trivial to convert the english
>> into
>> proper propositional/predicate logic.

> ahhh OK....thats what I thought....i.e. a full formal def doesn't exist
> but is trivial.

I believe so (could be wrong though) .


>>> Don't really understand this.....how do the entity relationships cause
>>> conflict?

>> Wegner and Zdonik reason that for two types T1 and T2, when a *subset*
>> relationship exists between them, it is likely that a type
>> substitutability
>> conflict will occur in the software realisation. They have covered the
>> big three problems :

>> 1. Some property P in T2 is a subset of P as defined for T1.

>> This is the Circle/Ellipse problem.

>> If ellipse is defined : E = { (focus-a,focus-b) : focus-a > 0, focus-b >
>> 0 }
>> and circle is defined :
>> C = { (focus-a,focus-b) : focus-a > 0, focus-a =focus-b }

>> C is a subset of E.
>> And it is these properties (focus-a and focus-b) that are the
>> Circle/Ellipse
>> problem.

>> This form of the subset relationship is the mass offender in type
>> substitutability conflicts (it is the one that I have continually
>> encountered over the years) .

> OK you've defined the members of each model but not any methods....thus
> I cannot discern a substitutability problem....trivially with no
> methods there is no problem.

Ellipse::focusA(f)
// post : focusA() = f, focusB() = OLD.focusB()

Circle::focusA(f)
// post : focusA() = f
// invariant : focusA() = focus(B)

This is the classic form of the problem.
Which is, the software realisation of the relationship between Ellipse and
Circle (which is not a problem in the subject domain) causes a conflict.

Which properties of ellipse and circle have caused the conflict ??
The foci.

For ellipse and circle, what is the relationship between the foci ??
The set of values that a circle can define is a *subset* of the values that
an ellipse can.

Subset relationship ??
Problem suggested in advance by Wegner and Zdonik. QED. :-)

So what Wegner and Zdonik are stating is that if you look at the details,
you may pre-empt the grief. If you have a proof tool, or perhaps DBC, you
may find the problem quickly.

But we work in the real world. And more often than not, the conflict
reveals itself in all its gory glory at the exact time that it causes the
most
grief.


>> 3. The set of properties for T2 is changed to a subset of those of T1.

>> A classic example of this : birds that cannot fly.

>> T1 : Bird = type { Weight weight() ; fly() ; }
>> T2 = Emu = Bird subtype { exclude fly() ; }

>> Bird b = new Emu() ;
>> b.fly() ;

> hmmmmmm OK.....this one seems a no hoper to me....to talk about Emu "is
> a" bird is clearly not true.

But an Emu clearly is a bird. Just one that cannot fly.
Specifically Emu instances can be used in all contexts that a Bird instance
can,
except that one.

Should a type system reject the substitution for all those other contexts
because
of this one exception ... ??


Regards,
Steven Perryman


From: Mark Nicholls on

S Perryman wrote:
> "Mark Nicholls" <Nicholls.Mark(a)mtvne.com> wrote in message
> news:1155818667.712103.216720(a)m73g2000cwd.googlegroups.com...
>
> > S Perryman wrote:
>
> >> "Mark Nicholls" <Nicholls.Mark(a)mtvne.com> wrote in message
> >> news:1155807673.140835.86680(a)b28g2000cwb.googlegroups.com...
>
> >> See the Circle/Ellipse problem.
>
> > I don't believe it looses semantic correctness!....it's just the
> > abstraction does not match 'reality'.....
>
> If the "abstraction" deviates from the "reality" , is the abstraction a
> correct representation of the reality ??
>

no

that is not to say there aren't abstractions that do match the reality.

have I missed your point or you missed mine?

>
> >>> Dmitry claims to need a mathematical foundation to OO....I believe it
> >>> either exists or is trivial for a competent mathematician (which I am
> >>> not)....does it exist for Liskov/Wing types?
>
> >> A mathematical definition of Liskov/Wing subtypes can be derived from
> >> the source papers. In my Usenet posting of old, I did a semi-formal def
> >> of the Liskov/Wing subtype. It should be trivial to convert the english
> >> into
> >> proper propositional/predicate logic.
>
> > ahhh OK....thats what I thought....i.e. a full formal def doesn't exist
> > but is trivial.
>
> I believe so (could be wrong though) .

OK..so do I....I've tried to do it...but it is beyond me....but
seemingly only just.

>
>
> >>> Don't really understand this.....how do the entity relationships cause
> >>> conflict?
>
> >> Wegner and Zdonik reason that for two types T1 and T2, when a *subset*
> >> relationship exists between them, it is likely that a type
> >> substitutability
> >> conflict will occur in the software realisation. They have covered the
> >> big three problems :
>
> >> 1. Some property P in T2 is a subset of P as defined for T1.
>
> >> This is the Circle/Ellipse problem.
>
> >> If ellipse is defined : E = { (focus-a,focus-b) : focus-a > 0, focus-b >
> >> 0 }
> >> and circle is defined :
> >> C = { (focus-a,focus-b) : focus-a > 0, focus-a =focus-b }
>
> >> C is a subset of E.
> >> And it is these properties (focus-a and focus-b) that are the
> >> Circle/Ellipse
> >> problem.
>
> >> This form of the subset relationship is the mass offender in type
> >> substitutability conflicts (it is the one that I have continually
> >> encountered over the years) .
>
> > OK you've defined the members of each model but not any methods....thus
> > I cannot discern a substitutability problem....trivially with no
> > methods there is no problem.
>
> Ellipse::focusA(f)
> // post : focusA() = f, focusB() = OLD.focusB()
>
> Circle::focusA(f)
> // post : focusA() = f
> // invariant : focusA() = focus(B)
>
> This is the classic form of the problem.
> Which is, the software realisation of the relationship between Ellipse and
> Circle (which is not a problem in the subject domain) causes a conflict.

OK I'm only just with the syntax....your abstraction is mutable?

That is the problem, this is not true of a mathematical definition of
circles and ellipses.

Mathematical objects are all immutable.....always.

>
> Which properties of ellipse and circle have caused the conflict ??
> The foci.

The mutability of the foci.

mutability is evil (well at least a signicant constraint on either
state or the strength of the type).

>
> For ellipse and circle, what is the relationship between the foci ??
> The set of values that a circle can define is a *subset* of the values that
> an ellipse can.
>
> Subset relationship ??
> Problem suggested in advance by Wegner and Zdonik. QED. :-)
>
> So what Wegner and Zdonik are stating is that if you look at the details,
> you may pre-empt the grief. If you have a proof tool, or perhaps DBC, you
> may find the problem quickly.

if you drop the mutability then you do not have the closure of your
object states obey the type definition....(well you do, it just doesn't
change).....then you export the new state.....(I've been here before
talking about the problems of the state pattern and how it inhibits
strong type definitions....I was largely poo pood...if you say
"externalise state" people start hopping up and down....as breaking
encapsulation...yes I am choosing to expose more than I have to in
order to strengthen my type definitions).

so if we change the language to do it as it would be in mathematics
i.e.

interface IEllipse
{
IEllipse SetFocusA(x);
IEllipse SetFocusB(x);
}

(I don't know how to write the contract but effectively an ellipse is
immutable...if you SetFocusA/B you get a new IEllipse

interface ICircle : IEllipse
{
ICircle SetFocusAAndB(x);
}

now circles "are" ellipses...and are true subtypes.

(yes we do have some ellipses that have "==" Foci...this is more to do
with the nature of static typing...rather than the underlying
mathematics of typing)

>
> But we work in the real world. And more often than not, the conflict
> reveals itself in all its gory glory at the exact time that it causes the
> most
> grief.

The grief is the closure of state obeying the type definition....the
real world (for the usual circle/ellipse example) is not a model of our
abstractions....the abstraction is mathematically incorrect.....all we
need to do is make the abstraction actually describe the mathematics
and it all just works.

>
>
> >> 3. The set of properties for T2 is changed to a subset of those of T1.
>
> >> A classic example of this : birds that cannot fly.
>
> >> T1 : Bird = type { Weight weight() ; fly() ; }
> >> T2 = Emu = Bird subtype { exclude fly() ; }
>
> >> Bird b = new Emu() ;
> >> b.fly() ;
>
> > hmmmmmm OK.....this one seems a no hoper to me....to talk about Emu "is
> > a" bird is clearly not true.
>
> But an Emu clearly is a bird. Just one that cannot fly.
> Specifically Emu instances can be used in all contexts that a Bird instance
> can,
> except that one.
>

OK fair enough...I know what your saying....it is a weaker substitution
relation....but for some contexts substitutability holds.

> Should a type system reject the substitution for all those other contexts
> because
> of this one exception ... ??
>

hmmmmm

ideally no.

":" to me indicates "forall" contexts.....

I think I'd rather juggle the type hierachy...effectively those
contexts that aren't interested i
From: H. S. Lahman on
Responding to Ulf...

>>My position is that type are quite valuable, but only at the level of
>>defining and implementing 3GLs appropriate for OOP. They are simply not
>>relevant to OOA/D when designing an OO application; for OOA/D one only
>>deals with class systems.
>
>
> Here we disagree. I, maybe unconventionally, distinguish between the
> notion of type system
> 1 - as a system of rules assigning static types to type correct program
> terms, and
> 2 - as a system of types related by type constructors and subtype
> relationships.
>
> IMHO, a class system is - on the right level of abstraction - a type
> system in the second sense.

They are obviously unambiguously mappable because they share property
sets, but I don't think they are the same thing. Class systems are
about member identity and classification while type systems are about
interfaces and access. For example, one cannot deal with class systems
without talking explicitly about sets (e.g., a generalization in an
OOA/D Class Model is just a Venn Diagram in tree form) while one can
easily talk about types systems without mentioning sets at all.

Note that in UML the interface to a class, which maps directly to a type
at the 3GL level, is a separate model element from the definition of the
class itself.

>>>Liskov and Wing proposed a behavioral subtyping rule, which they proved
>>>to enforce the LSP. Let me try to translate it, AFAIKR, into OOM-talk
>>>to obtain a modelling rule. ...
>>
>>Here we disagree somewhat. What you are describing here is
>>implementation inheritance (i.e., the subclass overrides a defined
>>property implementation that already exists in a superclass).
>
>
> I intended not to describe implementation inheritance but specification
> inheritance.
>
> The problem is not inherited behavior implementations are overridden.
> The problem is: What the behavior implementation finally is in the
> concrete instance is not compatible to the assumptions under which
> interactions involving superclass instances were modeled. For the
> problem to arise it does no matter whether these assumptions were
> derived from actual behavior implementations in the superclass or from
> specifications of behavior in the superclass or intuitively from the
> superclass's name and informally described purpose.

What I was responding to was the notion of overriding the superclass in
the subclass. If one regards this as specification inheritance rather
than implementation inheritance, then such an override is impossible in
a well-formed OO application. That is because the semantics of the
responsibility is defined in one and only one place: the highest level
in the generalization tree where it is identified. All specializations
in a direct line of descent /must/ honor that semantic definition or the
application is mal-formed.

Note that such compliance does not depend upon client interactions. The
tricky part where LSP comes into to play is defining the semantics of
the superclass responsibility correctly for the client context. In the
classic example:

* attacks 1
[Predator] ----------------------- [Prey]
+ run()
A
|
+------------+--------....
| |
[Impala] [Zebra]

everything is fine until one adds:

* attacks 1
[Predator] ----------------------- [Prey]
+ run()
A
|
+------------+----------+
| | |
[Impala] [Zebra] [Quail]

Now run() is not the correct semantics for what all subclasses do in
response to being attacked. So one might change run() semantics to
flee() semantics. But that get broken when one adds:

* attacks 1
[Predator] ----------------------- [Prey]
+ flee()
A
|
+------------+----------+----------+
| | | |
[Impala] [Zebra] [Quail] [Elephant]

where the appropriate response is to stand and stomp the attacker rather
than fleeing.

The hard part of LSP is not making the subclasses conform to the
semantics of the superclass responsibility. It is providing a proper
level of abstraction for the superclass semantics. So if the only
[Prey] that are relevant are [Impala] and [Zebra], then the first
solution is adequate. It becomes something of an art form to anticipate
future requirements changes and come up with:

* attacks 1
[Predator] ----------------------- [Prey]
+ attacked()
A
|
...

For complex problem space notions like [Prey] that is close to
impossible to do for all possible contexts in a one-size-fits-all
manner, which Kazakov and I agree about. Where we disagree is that I
believe one can do it for particular problem contexts.

>>My second problem here is with the implication that somehow there is s
>>dependence between client messages that affects substitutability.
>
>
> Huh? The existence of such dependencies is a fact: Since messages
> received in the past can influence the state an object is in now, they
> can affect the object's externally visible behavior now, and thus can
> affect its substitutability.

Not in a well-formed OO application. By definition object behavior
responsibilities are intrinsic and self-contained so they cannot depend
on what other objects do (other than through state variables).

This is most obvious when one uses object state machines. The rules of
finite state automata prohibit a state action form knowing the prior or
next state. The action is also dependent solely on the input alphabet
(in an OO context that includes attribute state variables). Thus the
FSA rules explicitly enforce basic OOA/D construction pra