A Behavioral Notion of Subtyping
Authors: Barbara H. Liskov (MIT) and Jeannette M. Wing (CMU)
ACM TOPLAS.
The full text of this paper is here (in
PostScript).
Abstract
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 its subtype
objects. It presents two ways of defining the subtype relation, each
of which meets this criterion, and each of which is easy for
programmers to use. The subtype relation is based on the
specifications of the sub- and supertypes; the paper presents a way of
specifying types that makes it convenient to define the subtype
relation. The paper also discusses the ramifications of this notion
of subtyping on the design of type families.