The works of Liskov and Wing [LONG] (Was: Class hierarchy design question)
S Perryman
>Actually, the Liskov Substitution Principle says that "*Functions*
>that use pointers or references to base classes must be able to use
>objects of derived classes without knowing it."
>It seems to me that, by this definition, the only requirement is that
>if you have a function that takes, as an argument, an instance of
>FruitList, the function should only operate on generic FruitList
>instances, and not be concerned with the specific type of fruit
>contained therein. I'm assuming that AppleList and OrangeList exist
>because there is a need for some strongly-typed FruitList
>functionality. Perhaps, for instance, the FruitList class has an
>Item(int index) operation that returns a Fruit object, but does not
>implement an Add() operation. The strongly-typed AppleList class
>implements Add(anApple), to force a client to add the correct type of
>Fruit (the same would be true for OrangeList).
>In the case I've described, perhaps a function exists that does not
>need to add fruits to the list, but simply access them for some
>purpose, without concern for the specific kind of fruit. To that end,
>the function takes as an argument a FruitList class. With my
>understanding of the Liskov principle, it seems that a violation
>would only occur if that function had to cast the list argument to
>a specific kind of FruitList, as this would mean that the function
>had to know which kind of FruitList was passed in as an argument.
>Is this a correct understanding of the principle, or am I missing
>something?
1. There is a boolean predicate : substitutable-for(T2,T1,C)
that is true if in a (program) context C, an instance of type T2
is substitutable for an instance of T1.
2. A definition of this predicate for *OO* was given by Simula many
yrs ago (and is still the predominate usage) :
substitutable-for(T2,T1,C) = inheritance-lineage(T2,T1)
If T2 (directly or indirectly) inherits properties from T1, then T2
is substitutable for T1. Note that the context C is redundant.
3. Liskov and Wing effectively define the predicate thus :
substitutable-for(T2,T1,C) =
- T2 always satisfies the type invariant of T1.
- For any operation OP invoked on T1 in C, T2::OP :
-- Satisfies the preconditions for itself or those of T1::OP.
-- Satisfies the postconditions for itself and those of T1::OP.
-- Raises the same set of exceptions as T1::OP.
-- Accepts as argument parameters the same set of values as for T1::OP.
-- Yields as results, values whose types are substitutable with those
types assigned to the result parameters for T1::OP.
4. Liskov and Wing then move to their definition of a *subtype* ,
which can be formally defined as :
LW-Subtype(T2,T1) =
FORALL C IN SYSTEM.CONTEXTS(T1) : substitutable-for(T2,T1,C)
What this all means is that this term "Liskov Substitution Principle"
(which notably neither Liskov nor Wing formally used in any of their
papers on type substitutability) is an incorrect statement of their
work.
They tell us what they want type substitutability to mean.
They then define what they want a subtype to be.
So for your example :
AppleList/OrangeList are substitutable for FruitList. In fact,
substitutability probably holds in many different contexts for the
former and latter.
As you have correctly noted, adding any fruit to an AppleList/
OrangeList instance is incorrect. You have found a context in which
substitutability fails the Liskov/Wing definition. Consequently,
AppleList/OrangeList are *NOT Liskov/Wing SUBTYPES* of FruitList.
What people who actually understand the work of Liskov/Wing know, is
that :
- Type substitutability is a more universal concept than OO inheritance.
- OO provides weaker type substitutability than desired by Liskov and
Wing.
- Type substitutability conflicts have nothing to do with inheritance.
- The organisation of programs into a set of Liskov/Wing subtypes,
although desirable, can often have a lower ROI for developer effort
than having an easily defined set of types that provide a very large
(but incomplete) set of program contexts having no conflicts (because
the set of potential contexts for any type is theoretically infinite) .
Regards,
Steven Perryman
Dmitry A. Kazakov
Nicely put.
The only thing I would slightly disagree upon is that the idea to tie
substitutability and inheritance is not all that bad. If we
appropriately relax one generalizing another, they probably will meet
somewhere.
--
Regards,
Dmitry Kazakov
http://www.dmitry-kazakov.de
Universe
> The only thing I would slightly disagree upon is that the idea to tie
> substitutability and inheritance is not all that bad. If we
> appropriately relax one generalizing another, they probably will meet
> somewhere.
Sure. For a given swapping context, one typically finds that swapping
based upon type concinnity - polymorphism - is a subset of
substitutability in general. Substitutability is necessary but not
sufficient for swapping based upon type - polymorphism.
Substitutability is more about the code units being swapped in having
commonality with the swapping socket - the point where code units are
being substituted. Once we know code units can be swapped into a
socket, polymorphism is more about commonality across the units being
swapped in and out.
I discussed this in "Beauty & Power of C++", that apart from detailing
the OO polymorphic aspects of C++, explains how commonality is the root
power of substitutability.
Elliott
--
"Object-oriented [OO] programming. A program execution is regarded as
a physical model, simulating the behavior of either a real or
imaginary part of the world...The notion of a physical model should be
taken literally." ~ Computerized physical models
Madsen, Moeller-Pederson, Nygaard (co-founder of OO)
S Perryman
> On 9 Dec 2003 03:27:26 -0800, ggr...@bigfoot.com (S Perryman) wrote:
> [ snip ]
> Nicely put.
Thank you.
> The only thing I would slightly disagree upon is that the idea to tie
> substitutability and inheritance is not all that bad. If we
> appropriately relax one generalizing another, they probably will meet
> somewhere.
Not quite.
What we need to state is that OO type substitutability and Liskov/Wing
type substitutability become the same thing when an inheritance
relationship meets one of two conditions.
One of those conditions is already covered by the Liskov/Wing definition.
Specifically, using inheritance to *extend* the properties of an existing
type will by definition be LW conformant.
The other condition is met by using inheritance for "mixins" etc.
Regards,
Steven Perryman
Universe
> Dmitry A. Kazakov <mai...@dmitry-kazakov.de> wrote in message
> > The only thing I would slightly disagree upon is that the idea to
tie
> > substitutability and inheritance is not all that bad. If we
> > appropriately relax one generalizing another, they probably will
meet
> > somewhere.
> Not quite.
>
> What we need to state is that OO type substitutability and Liskov/Wing
> type substitutability become the same thing when an inheritance
> relationship meets one of two conditions.
Kazakov states:
"... the idea to tie substitutability and inheritance is not all that
bad."
Kazakov is not, at least explicitly, identifying "substitutability" as
"OO type substitutability", though Perryman does.
"Substitutability" does in fact exist apart from OO. And not all
"substitutability" in OO is associated with types.
In C pointers of static type 'void', support substitutability. In
OOPLs, a class may be substituted into a location (socket) while *not*
having any methods defined to support the type operations normally
expected of all other, or most types being substituted into the location
(socket).
OO substitutability based upon type correspondence at least nowadays is
understood to mean meeting the specification for how Liskov defines type
correspondence.
> One of those conditions is already covered by the Liskov/Wing
definition.
> Specifically, using inheritance to *extend* the properties of an
existing
> type will by definition be LW conformant.
As I indicate above, using just *any* inheritance does *not* necessarily
make a class type compliant in terms of what normally is expected of
types being substituted at some location.
> The other condition is met by using inheritance for "mixins" etc.
The types that a Mixin comprises may be Liskov type compliant at a
location, for anywhere from 1 to All of the types.
Elliott
--
Be bold, be artistically imaginative, yet scientifically grounded -- DO
GREAT OO MODELLING WITH OBJECTS OF ALL TYPES!!