Introduction
This is the first part of a six-part investigation into the
subject of type inheritance--in particular, into the crucial notion of substitutability. As you might know, I published another article on this subject earlier this year entitled Is a Circle an Ellipse?. In that article, I argued that circles are
ellipses in the real world, and hence that any model of type inheritance that
failed to regard a circle as an ellipse could hardly be claimed to be "a
good model of reality." I also
stated that Hugh Darwen and I had defined an inheritance model in which a
circle certainly was an ellipse, and further that we thought we knew how to
implement that model efficiently (see FOUNDATION FOR FUTURE
DATABASE SYSTEMS: THE THIRD MANIFESTO, 2nd edition, hereafter referred
to simply as THE THIRD MANIFESTO).
I published that previous article in July 2001. Then I ducked ... Perhaps it's an
exaggeration to say that people threw things at me from all directions, but I
certainly received an unusually large amount of correspondence, most of it
unfavorable. It isn't worth giving a
blow-by-blow response here to all of the criticisms I received, but I do want
to respond to one particular claim that ran like a common thread through many
of them: namely, that I seemed not to be aware of the Liskov Substitution
Principle--or (worse!) if I was aware of it, then I didn't understand
it.
Well, I freely admit that I wasn't familiar with the term
"Liskov Substitution Principle" (hereinafter abbreviated to LSP) when
I wrote my original article. However, I
was certainly familiar--I venture to say, extremely familiar--with the concept,
which I had been taught to refer to as substitutability.* Here's a loose definition (I'll refine this
definition at the very end of Chapter 16):
If S is a subtype of T, then wherever the system expects
a value of type T, a value of type S can be substituted.
For example, if AREA is an operator that can be invoked on an
ellipse e, then we can always substitute a circle c for e
in such an invocation, because circles are ellipses (at least, such is my
claim).
* So perhaps I owe Barbara Liskov an apology, if
the concept truly is due to her and I haven't acknowledged that fact in my
previous writings.
As I recall, it was Nelson Mattos of IBM who introduced me to
the idea of substitutability, way back in 1993; certainly I was already writing
about it no later than May of that year, when I was working on the 6th edition
of my book AN INTRODUCTION TO DATABASE SYSTEMS (published by
Addison-Wesley in 1994, though with a copyright date of 1995). And I have subsequently studied it in
considerable depth in connection with my work with Hugh Darwen on the
inheritance model mentioned above (the one described in THE THIRD MANIFESTO).
What Is LSP?
Given all of the foregoing, I naturally wanted to see if
there were any significant differences between substitutability as I understood
it and LSP. I began my attempt to
answer this question by taking a look at a short article by Stephen R. Tockey
entitled What is LSP? That
article starts by asserting that LSP is described in detail in a paper entitled
A Behavioral Notion of Subtyping, by Barbara Liskov and Jeannette Wing (ACM
Transactions on Programming Languages and Systems 16, No. 6, November
1994), and it goes on to quote from the abstract to that paper as follows. (Note: In fact, the extract quoted consists of the first half of the
abstract in its entirety.)
The use of hierarchy is an important component of
object-oriented design. Hierarchy
allows the use of type families, in which higher level supertypes capture the
behavior that all of their subtypes have in common. For this methodology to be effective, it is necessary to have a
clear understanding of how subtypes and supertypes are related. This paper takes the position that the
relationship should ensure that any property proved about supertype objects
also holds for subtype objects.
The wording of this extract put me on my guard right
away. I believe strongly--and I've said
as much, in many places and on many occasions--that if you want to make precise
and formal statements about data and data management in general, then it's a
bad idea to try and do so in terms of "objects." Object terminology almost always seems to be
fuzzy. There are several reasons for
this state of affairs, but one of the biggest is that it (object terminology,
that is) seems never to make the absolutely crucial distinction between values
and variables. (In fact, in our
own work on type inheritance, Hugh Darwen and I found it necessary to
distinguish two kinds of substitutability, one based on values and the other
based on variables; what's more, we showed that if you fail to make that
distinction, then at least one, and arguably as many as four, extremely
undesirable consequences follow. I'll
elaborate on this point in the subsequent parts of this article.
Anyway (I said to myself as I was reading), perhaps the
Liskov/Wing paper does deal with the substitutability issue properly and does
avoid the many "value vs. variable" traps and confusions. We'll see.
Meanwhile, I was still studying the Tockey article. The very next thing it said was this:
Very simply put, the LSP states that "objects of the
subtype ought to behave the same as those of the supertype as far as anyone or
any program using supertype objects can tell." In other words, I ought to be able to substitute any subtype of
class X in a program that expects a member of class X and the program should
still behave reasonably.
As I expected: Fuzziness! Let's examine the two sentences in this
quote one at a time. The first one is not too bad*--I
mean, you can make a pretty good guess at what the author is trying to say,
even if, like me, you feel the phrase "ought to behave" would be
better shortened to just "behave"--but surely it could be better
expressed? For example:
If S is a subtype of T, then wherever the system expects an
object of type T, an object of type S can be substituted.
Much more precise, and--at least to me--much easier to
understand, too. (Mind you, I don't
necessarily agree with the sentiment the revised sentence expresses!--it
depends, of course, on what the term object means. But let that pass for now.)
* I subsequently discovered that this first
sentence was a direct quote from the Liskov/Wing paper.
Now let's look at the second sentence: "In other words, I ought to be able to
substitute any subtype of class X in a program that expects a member of class X
and the program should still behave reasonably." I have many reactions to this sentence!
Ø First
of all, where did that stuff about classes come from? It wasn't mentioned in the first sentence, and it wasn't
mentioned in the Liskov/Wing abstract either.
Am I to understand that class is just another word for type? If so, why introduce the term? If not, how do the concepts differ? And if they do differ, what are we supposed
to make of the phrase "any subtype of class X"?
By the way, in my original article
(Is a Circle an Ellipse?) I did say that class and type
were synonyms--and I got a lot of flak on that one, too. The truth is, however,
that there's an amazing amount of confusion over this particular
issue. In support of this claim, let me
quote some material from Appendix K of THE THIRD MANIFESTO. Appendix
K is the References and Bibliography appendix, and it includes a
reference to a book by Elisa Bertino and Lorenzo Martino entitled OBJECT-ORIENTED
DATABASE SYSTEMS: CONCEPTS AND ARCHITECTURES (Addison-Wesley, 1993). Here's the annotation to that reference from
Appendix K (edited just slightly here):*
* I quoted from this
annotation in my original article, too.
Many publications from the object world try to draw a
distinction (as we do not) between type and class, and Bertino
and Martino's book is one such: "Object-oriented systems can be classified into two main
categories--systems supporting the notion of class and those supporting
the notion of type ... [Although] there are no clear lines of
demarcation between them, the two concepts are fundamentally different [sic!]
... Often the concepts type and class are used interchangeably. However, when both are present in the same
language, the type is used to indicate the specification of the
interface of a set of objects, while class is an implementation notion [so
why is it "present in the language" at all?]. Therefore ... a type is a set of objects
which share the same behavior ... [and] a class is a set of objects which have
exactly the same internal structure and therefore the same attributes and the
same methods. [But if all objects in
a class have the same attributes and the same methods,*
is not that class a type, by the authors' own definition?] The class defines the implementation of a
set of objects, while a type describes how such objects can be used." (Contrast the ODMG specification,
incidentally--see R. G. G. Cattell and Douglas K. Barry (eds.), THE OBJECT
DATA STANDARD: ODMG 3.0, Morgan Kaufmann, 2000--which uses the terms type
and class in almost exactly the opposite way.)
* I prefer the term operator,
but method is much more common in the object world, and so I'll use it
here.
The authors [i.e., Bertino and Martino] then go on to
say: "With inheritance, a class
called a subclass can be defined on the basis of the definition of
another class called a superclass." Surely--in accordance with their own earlier definitions--they
should be talking in terms of types here, not classes? And then they add: "The specification hierarchy (often called subtype
hierarchy) expresses ... subtyping relationships which mean that an
instance of the subtype can be used in every context in which an instance of
the supertype can correctly appear (substitutability)." Observe that they do now speak of types, not
classes ... [Also,] observe the failure to distinguish properly between values
and variables (note the fuzzy talk of "instances"), and the
consequent failure to distinguish between value substitutability and variable
substitutability.
Of course, it is precisely because of confusions,
terminological and otherwise, such as those just illustrated that we felt
free--or compelled, rather--to introduce our own terms in THE THIRD
MANIFESTO and to define them as carefully as we could.
Ø Back
to the sentence from the Tockey article.
My next complaint is sloppiness, as evidenced by the phrasing
"substitute any subtype of class [= type?] X." To be specific, the author is talking about
substituting a subtype as such, when presumably what he should be
talking about is substituting an object of the subtype in question. This is not just a quibble! As I wrote in my original article, our own
model of types and inheritance is based on the four classical--and, we hope,
widely understood--concepts type, value, variable, and operator.* There are HUGE logical differences between
any two of these concepts, and any article or other writing that confuses them
is likely to manifest other confusions as well.
* I also said we found no
need to drag in any kind of "object" concept at all, and I stand by
this claim.
Ø By
now you've probably forgotten the sentence from Tockey's article that I'm
complaining about (I nearly have myself), so let me repeat it again, but with a
different emphasis this time:
In other words, I ought to be able to substitute [an object
of?] any subtype of class [= type?] X in a program that expects a member
of class [= type?] X and the program should still behave
reasonably.
Am I to understand that member
is just another word for object?
If so, why introduce the term?
If not, how do the concepts differ?
I could say quite a bit more about this sentence of
Tockey's--in particular, I'd love to see a definition of what it means for a
program to "behave reasonably"--but let's move on. A couple of paragraphs further on, I found
this:
In order for class X' to be a subtype [sic!] of class X,
the pre-conditions of the methods of the supertype [presumably "the
supertype" is class X?] must be at least as restrictive (but possibly
more) than the pre-conditions of the corresponding methods of the subtype(s)
AND/OR the post-conditions of the methods of the subtype must be at least as
restrictive (but possibly more) than the post-conditions of the corresponding
methods on the supertype.
Well, the syntax here is pretty wobbly, but let's focus on
the two central claims the author appears to be making. I'll take them one at a time. The first is as follows:
·
Let M be a method that applies to objects of type X and
therefore--let's assume--to objects of type X' as well.* Then the preconditions that apply to M when
it's invoked on an object of type X must be "at least as restrictive"
as those that apply to M when it's invoked on an object of type X'.
* Actually this assumption needs to be carefully
examined too, but this isn't the place for that examination. Suffice it to say that the distinction
between values and variables rears its (very nonugly) head here once
again.
To me, this claim
seems to be nonsense. For
consider:
§
First of all, by definition, there are more values of
type X than there are of type X'. After
all, to say that X' is a subtype of X is to say that every value of type X' is
a value of type X, so there can't be MORE values of type X' than there are of
type X; and if the two types have the same number of values, then they're the
same type. Note: I'm aware that not everyone agrees with the
points I'm making here. I'll revisit
them in the next chapter.
§
The precondition that applies to M when it's invoked on
an object O of type X is basically that O must have a value that's a value of
type X. The precondition that applies
to M when it's invoked on an object O' of type X' is basically that O' must
have a value that's a value of type X'.
This latter precondition is OBVIOUSLY more restrictive than the former,
thereby directly contradicting the claim that the former is supposed to be more
restrictive than the latter. Note: Of course, I'm aware that preconditions
might be more complicated in practice than the simple ones I'm describing here,
but it's sufficient to consider just the simple case in order to make the point
I want to make.*
* As an aside, I feel bound to say that I'm not
very happy with the terminology of "preconditions," anyway. Given a method M, the preconditions, as
such, for M are surely always the same, no matter what types the arguments
might happen to have. Thus, the real
question is, rather, "Do the arguments satisfy the
preconditions?" (Perhaps the
reason I'm having difficulties here is that Tockey and I are basing our
statements on different unspoken assumptions.
Be that as it may, I'll revisit the whole business of preconditions--and
postconditions--in Chapter 16.)
Now here's the second claim:
·
Again, let M be a method that applies to objects of
type X and therefore to objects of type X' as well. Then the postconditions that apply to M when it's invoked on an
object of type X' must be "at least as restrictive" as those that
apply to M when it's invoked on an object of type X.
This claim, by contrast, does seem reasonable. Assume first that M produces a result R when
it's invoked. Then--given the
preconditions stated earlier--it's obvious that every possible result
that can be produced when invoking M on some object O' of type X' can also be
produced when invoking M on some object O of type X (because O' is an object of
type X, by definition). Thus, the
postcondition that applies to M when it's invoked on an object of type X' is obviously
"at least as restrictive" as the one that applies to M when it's
invoked on an object of type X.
Onward. Tockey
subsequently gives an example of two methods both called Draw, one of which
applies to objects of type GeometricShape and the other to objects of type
WildWestGunfighter, and observes, correctly, that there's no subtyping, and
therefore no substitutability, in that example. (His actual words are as follows: "[According] to LSP, WildWestGunfighter is not a subtype of
GeometricShape and I should not expect a program to be well behaved if I
substitute a member of WildWestGunfighter in a place where the program expected
a GeometricShape.") Well, I agree,
but I think the point would have been much clearer if the writer had explicitly
introduced the terms inclusion polymorphism and overloading
polymorphism (and explained the difference between them, of course). Let me elaborate.
First of all, an operator (or "method") is said to
be polymorphic if it's defined in terms of some parameter P and
the arguments corresponding to P can be of different types on different
invocations. The equality operator
"=" is an obvious example: We
can test any two values for equality (just so long as the two values are
of the same type), and so "=" is polymorphic--it applies to integers,
and to character strings, and to ellipses, and to polygons, and in fact to
values of every type. Analogous
remarks apply to the assignment operator ":=" also. Further examples include the well-known aggregate
operators (MAX, COUNT, etc.), the operators of the relational algebra (UNION,
JOIN, etc.), and others.
Next, polymorphism comes in (at least) two distinct flavors,
known as inclusion polymorphism and overloading polymorphism,
respectively.* To
paraphrase some remarks from THE THIRD MANIFESTO, a helpful way of
characterizing the difference between these two concepts is as follows:
* The kind of polymorphism displayed by the
operators of the relational algebra is called generic polymorphism, on
the grounds that--loosely speaking--those operators apply to all possible
relations, generically.
Ø Inclusion
polymorphism means we have one operator with several distinct implementation
versions under the covers (but the user does not need to know that the versions
in question are in fact distinct--to the user, there is just the one
operator). Inclusion polymorphism is
what we get with subtyping, and it implies substitutability. For example, the fact that the operator AREA
applies to values of type POLYGON implies that the same operator AREA can be
invoked on a value of type RECTANGLE (i.e., rectangles can be substituted for
polygons), even if there are indeed--as there probably will be, for efficiency
reasons--two distinct implementation versions of AREA under the covers. Note: The term "inclusion polymorphism" derives from the fact
that, e.g., the set of all rectangles is included in the set of all
polygons (just as the set of all circles is included in the set of all
ellipses).
Ø Overloading
polymorphism means we have several distinct operators with the same name (and
the user does need to know that the operators in question are in fact distinct,
with distinct--though preferably similar--semantics). Overloading polymorphism has nothing to do with subtyping, and it
doesn't imply substitutability. It shouldn't
really even be mentioned in connection with subtyping, except to make it
clear (as I'm trying to do here) that it has nothing to do with the subject
under discussion. Tockey's
"Draw" example is an example of overloading.*
* What's more, that example violates the suggested
principle that the "several distinct operators" in question should
have similar semantics. Indeed, the
kind of polymorphism displayed in that example might better be called punning
polymorphism.
Note: The
foregoing definitions notwithstanding, I should now warn you that some
writers--very unfortunately, in my opinion--use the term overloading to
mean inclusion polymorphism. Caveat
lector!
(Continued in Part 2)
Posted
05/31/02
