(Continued from Part 2)
This is the third part of a six-part series. In Part 1 and
Part 2 I
took a look at a couple of tutorial descriptions of the Liskov Substitution
Principle (LSP) and found much fault with them. Now I want to turn my attention
to the paper that appears to have been the origin of the LSP concept: A
Behavioral Notion of Subtyping, by Barbara Liskov and Jeannette Wing (ACM
Transactions on Programming Languages and Systems 16, No. 6, November
1994). Here is how I finished up Part 2:
“It was with a certain sense of relief and anticipation that
I turned to the original Liskov/Wing paper. Surely here, I thought, I would
find much greater precision and clarity of thinking and expression. Nor was I
disappointed. Indeed, the paper was so clear that its errors were clear, too!
In fact, it was precisely because I found I wanted to make so many comments on
that paper that I decided to split the present article into three parts. In
particular, it seemed best to defer my detailed commentary on the Liskov/Wing
paper to Parts 4, 5 and 6, and that's what I'm going to
do.”
Without further ado, let me start that commentary.
Background Assumptions
The Liskov/Wing paper includes a section entitled "Model
of Computation," in which the authors spell out some -- but unfortunately
not all -- of their background assumptions. The present section represents my
own attempt to distill out the essence of those assumptions. To be more
specific, the work reported in the Liskov/Wing paper is explicitly cast in an
object-oriented framework, and I believe the salient features of that framework
are as indicated here:
·
Objects have values -- different values at different
times, in general, unless the object in question is "immutable" (see
below).
·
Objects are accessed via program variables containing
pointers (i.e., object IDs). Program variables are subject to assignment, but
objects apparently aren't (?).
·
Objects are generally "encapsulated," meaning
they have behavior but no user-visible structure -- unless such structure is an
intrinsic feature of the object type in question, as would be the case if,
e.g., the object type in question were some array type (The paper doesn't
actually say objects are encapsulated -- indeed, encapsulation as such isn't
mentioned at all -- but I think it's at least implied.)
·
Every object is of some type. In fact, a given object
is of exactly one type, except in the case where the object in question
is of type S and type S is a proper subtype of type T, in which case the object
is additionally of type T. (I believe the second sentence here is true,
although the point is nowhere spelled out explicitly in the paper. Also, the
term "proper subtype" doesn't appear, so I'd better define it: Type S
is a proper subtype of type T if (a) it is a subtype of T and (b) S and T are
distinct. (Note, therefore, that any given type T is a subtype of itself but
not a proper one.))
·
Objects cannot change their type. (Again, this is my
assumption--the paper doesn't say as much explicitly, but it does include
numerous remarks that make sense only if what I've just said is correct.)
·
Objects are never destroyed. (I think this assumption
-- which is stated explicitly -- is made purely to simplify other
portions of the paper, but I can't be sure.)
·
Methods are bundled with types. As a consequence, every
method has a distinguished parameter, called in the paper (rather loosely)
"the method's object." Mutators are methods that update "the
method's object," while observers are methods that don't (instead they
return results -- i.e., values, not objects, I presume -- "of other
types" (?)). However, the paper explicitly states that "an observer
can also be a mutator," which I take to mean that a mutator can also return
a result; also, I find it hard to imagine a mutator that doesn't
"observe" as well. So the distinction between observers and mutators
isn't very clear to me. However, the distinction, perhaps fortunately, isn't
very important for present purposes.
·
Following on from the previous point, the paper
explicitly defines any given type to consist, in part, of some specific set of
methods. Note the (presumably intended) implication: Adding a new method to
a given type changes the type! This fact would seem to have some rather
important consequences, some of which I'll discuss in Parts 5 and 6 of this
article.
·
An object is "immutable" if its value can
never change (presumably such an object, unlike other objects, must be
initialized when it first comes into existence). An object is
"mutable" if it isn't immutable.
·
A type is immutable "if its objects are"
(i.e., if and only if all of its objects are, presumably). A type is
mutable if it isn't immutable. (This notion of types per se, as opposed
to objects, being mutable or immutable seems rather strange to me. At the very
least, there seems to be something wrong with the terminology; types per se are,
among other things, sets of values, and such sets don't change -- in fact, sets
of values are themselves values, and values cannot change, by
definition. Also (quite apart from the terminology), I don't really understand
what an "immutable type" would be (unless it's one you can't add
methods to?) However, the rest of the paper has little to say regarding
"mutable vs. immutable types," so perhaps the issue isn't very
important.)
Objectives
As I see it, the primary aim of the Liskov/Wing paper is not
to propose an abstract model (as such) of subtyping and inheritance. Rather,
its aim is to provide certain definitional constructs that allow assertions of
the form "S is a subtype of T" to be formally verified,in the
sense that:
a.
Methods associated with type S can be shown to "behave
the same as" the corresponding methods associated with type T.
b.
"Constraints" associated with type S can be shown to
imply those associated with type T.
Note: The paper makes these two
statements much more precise. I can't do the same here, because I haven't
explained enough of the background--and I don't want to explain more of
the background just yet, because there are significant parts of it I don't
agree with, as I'll make clear soon.
The paper's main contribution is thus that it provides a way
of checking whether an assertion on the part of the type definer to the effect
that S is a subtype of T is valid, or at least plausible. By way of motivation
for their work, the authors offer the following remarks among others:
"[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."
Interestingly, this sentence (which as we saw in Part 1
was repeated in the Tockey article) seems to be as close as the paper comes to
actually providing a statement of the Liskov Substitution Principle. Certainly
there is no formal statement of LSP, as such, anywhere in the paper.
"Subtype Requirement: Let f(x) be a property
provable about objects x of type T. Then f(y) should be true for
objects y of type S where S is a subtype of T."
This statement is highlighted in the paper (in the introduction,
in fact), and it constitutes clear evidence in support of what I said at the
beginning of this section: namely, that the aim of the paper is to provide a
mechanism that supports formal verification of claims to the effect that some
given type S is a subtype of some other type T. (In case it's not obvious, I
should stress the fact that I think this aim is a perfectly valid and
interesting one. However, it's rather different from the one Hugh Darwen and I
had in mind when we developed our own inheritance model, as I'll explain later.
And I think the word "true" in the second sentence would better be
replaced by the word "provable," but perhaps it's not
important.
"[We] were motivated primarily by pragmatics. Our intention
[was] to capture the intuition programmers apply when designing type
hierarchies in object-oriented languages. However, intuition in the absence of
precision can often go astray or lead to confusion. This is why [in the past]
it has been unclear how to organize certain type hierarchies such as
integers."
[Sic! Presumably the authors mean "type
hierarchies such as one involving different kinds of integers".]
I find these remarks about pragmatics and intuition very
revealing. I could be quite wrong, but it seems to me that what Liskov and Wing
are trying to do in their paper is retroactively to formalize and impose
some discipline on a bunch of disparate preexisting notions that are all
somehow related to some concept of "subtyping" and "type
inheritance." The trouble is, there has never been--there still
isn't!--any consensus on what these latter terms mean. Instead, what there
definitely has been is much confusion... To quote from THE THIRD
MANIFESTO once again: "In The Object-Oriented Database
System Manifesto (Proc. 1st International Conference on Deductive and
Object-Oriented Databases, Elsevier Science, 1990), Malcolm Atkinson et
al. state that "[there] are at least four types of inheritance: substitution
inheritance, inclusion inheritance, constraint inheritance,
and specialization inheritance... Various degrees of these four types of
inheritance are provided by existing systems and prototypes, and we do not
prescribe a specific style of inheritance."
J. Craig Cleaveland, in his book AN INTRODUCTION TO DATA
TYPES (Addison-Wesley, 1986) states that "[inheritance can be] based
on [a variety of] different criteria and there is no commonly accepted standard
definition" -- and proceeds to give eight (!) possible
interpretations. (Bertrand Meyer, in his article The Many Faces of
Inheritance: A Taxonomy of Taxonomy, IEEE Computer 29, No. 5, May
1996, gives twelve.)
In a Technical Correspondence item in Communications
of the ACM 37, No. 9 (September 1994), Kenneth Baclawski and Bipin
Indurkhya state that "a programming language [merely] provides a set of
[inheritance] mechanisms. While these mechanisms certainly restrict what one
can do in that language and what views of inheritance can be implemented [in that
language], they do not by themselves validate some view of inheritance or
other. [Types,] specializations, generalizations, and inheritance are only
concepts, and... they do not have a universal objective meaning... This [fact]
implies that how inheritance is to be incorporated into a specific system is up
to the designers of [that] system, and it constitutes a policy decision that
must be implemented with the available mechanisms." In other words, there
simply is no model. "
Thus, it seems to me that most if not all of those earlier
notions of subtyping and inheritance were confused and muddled at best. And it
also seems to me that at least some of that muddle has, regrettably, carried
over to the Liskov/Wing paper. I'll get more specific on this point below, as
well as later in this series.
Anyway, regardless of whether I'm right about that business
of "formalizing and imposing discipline on a bunch of preexisting
notions," I would like to emphasize how different our own objectives were
when we (i.e., Hugh Darwen and I) developed our own inheritance model.
Basically, we worked from first principles; we very deliberately paid very
little attention to existing work in the field (After a period of initial
study, that is. Of course, we did recognize that our decision to work from
first principles meant we might be duplicating work already done by somebody
else, but there seemed to be so much confusion in the field--not least the
confusion over whether a circle was an ellipse!--that we decided we would be
better off going it alone, as it were. And so we did, and I think we were). We
certainly didn't feel constrained by "existing programmer intuition,"
and very definitely not by "object-oriented languages." Rather, we
were concerned with getting the concepts of the model right first--
i.e., finding a good answer to the question "What does it mean to
assert that S is a subtype of T?"--before possibly turning our attention
to the question of making such assertions formally verifiable in some way.
Thus, we started by developing a formal theory of types as such (and
considering the impact of such a theory on the relational model of data in
particular). Then we extended that theory to incorporate what seemed to us to
be logically sound and useful concepts of subtyping and inheritance. In
particular -- since we were familiar with at least the general idea and aims of
LSP, albeit not by that name -- we took pains to ensure that our theory did
indeed support that notion in what seemed to us to be a logically sound, correct,
and useful fashion.
In this connection, the Liskov/Wing paper contains another
interesting remark: "Our work is most similar to that of America [P.
America: Designing an Object-Oriented Programming Language with Behavioural
Subtyping, in J. W. de Bakker, W. P. de Roever, and G. Rozenberg (eds.), FOUNDATIONS
OF OBJECT-ORIENTED LANGUAGES (Springer Verlag, 1991)]… who has proposed
rules for determining based on type specifications whether one type is a
subtype of another." In other words, the idea seems to be: Given two type
specifications, what conditions must those specifications satisfy for one of
the two types to be regarded as a subtype of the other? In our own work, by
contrast, we took the diametrically opposite approach: We assumed that
type S was a subtype of type T, then we spelled out in detail what the
properties of type S must logically be, and went on to explore the logical
implications of those properties (especially the substitutability
implications). I'll come back to this difference in approach later in this
series, when I discuss the "bags-and-stacks" example.
Next, the Liskov/Wing Inheritance Model.
(Continued in Part 4)
Posted
07/21/02
[ABOUT]
[QUOTES]
[LINKS]
