NOTES ON TYPE SYSTEMS --- Note: in the following, I mostly stick with the usual object-oriented terminology of subclasses, superclasses, messages, and methods, but when speaking specifically about C++ I often use the (roughly corresponding) terminology of derived classes, base classes, virtual functions, and member functions. --- TWO (or three) PURPOSES Type systems serve two distinct purposes: to tell the language implementation how to construct and operate on program objects, and to restrict the possible ways programs can be put together. (Actually, a third function is documentation---the way the types are defined often conveys a lot of information that humans use in deciding how to test and modify programs, even if that information can't be checked by the compiler.) Roughly, type DECLARATIONS say what types there are and how they can be used. Type DEFINITIONS tell how objects of a given type are constructed and operated on. In a language like C++, both declarative and definitive stuff is going on in a single class declaration. You should always be aware that you are doing both things when you define classes---you are telling the compiler how different kinds of objects are put together, and you are also telling the compiler rules about how those objects can be used in a legal program. Implementations Variable types in a statically-typed language are often there largely for the convenience of the compiler---if a Pascal compiler knows that a variable is of type integer, it can always compile fast code to add that value to another integer, or assign it to another integer, or convert it to a floating point if necessary, etc. The compiler does not have to compile in extra tests that will be done at runtime to decide how to do the operations, as a Scheme compiler must do. Notice the trick that a Pascal compiler uses---static typing makes it possible to do *local* checking to ensure that types match, rather than analyzing all possible paths of program execution to tell what kinds of values might end up in what places. Restrictions on program construction Consider the numeric types of a language like Pascal. You can assign an integer value to a float, because the type system encodes the fact that a floating point variable is compatible with an integer value. You can assign an integer value into a float variable and you won't lose any information. (Well, as long as your integers aren't bigger than the floats can encode, anyway.) Pascal will NOT let you assign a float value into an integer variable, however. The compiler will complain and make you clarify your intentions. Why is this? Because you will lose information if the floating point value happens not to be an integral value---Pascal is keeping you from ACCIDENTALLY doing an assignment that will lose precision. If you DO want to do the assignment, you can truncate the floating point number explicitly to convert it to an integer. In this case, the compiler assumes you know what you're doing and will assing the result into the integer variable. In effect, the compiler says "hey, are you sure you want to do that?" in cases that are likely errors, but doesn't complain if you say "I really mean to do this" by explictily truncating the value. C, on the other hand, will not complain if you assign a floating point value into an integer variable. It will always assume you know what you're doing, and any errors due to truncation are your fault. It is a matter of some controversy when a language should require you to calm its fears that you're screwing up, and when it should go ahead and compile seemingly dangerous code without question. --- In languages like Pascal and C, certain built-in types are well understood by the compiler, but user-defined types are not. The compiler understands that floating point numbers and integer numbers have a lot in common, and it has rules for constructing numerical expressions that apply to all kinds of numbers, as well as more specialized rules for special kinds of numbers. User-defined types such as records (or structs) are all seen pretty much the same way, however---each is separate, and the compiler doesn't really take any notice of whether one user-defined type is "enough like" another one. So in Pascal, for example, built-in types are handled reasonably well. For example, an integer value is enough like a floating-point value that you can use one in the same place in an arithmetic expression---but an array or file object is clearly not similar enough. The compiler will complain if you attempt to add a file or an array to a floating point value. User-defined types aren't handled so well. The compiler won't let you substitute one user-defined type for another based on any rules about their similarities, because there aren't any rules like that. The programmer probably has such rules in mind, but can't express them in the language. That's one of the things strongly-typed object-oriented programming languages are for---to make it possible to express the similarities between different kinds of objects, and under what circumstances it is okay to substitute one kind of object for another and still have the computation make sense. --- Notice the difference between the type-checking philosophies of Scheme and of Pascal: * a Pascal compiler attempts to ensure that there is no possible way a type error could result from any possible execution of the program. Since the compiler is not very smart, certainly not as smart as a good programmer, it can't know things that the programmer knows---e.g., that certain paths of execution can't happen because of invariants the programmer is careful to preserve. (E.g., "I know the search procedure will never go down the leftmost path because the cutoff value will always be higher than the leftmost key at that node...") The Pascal compiler assumes that the programmer is wrong if it detects what looks (statically) like a possible type mismatch. More precisely, it restricts the language of possible programs so that most subtle type mismatches aren't even possible---types are either obviously compatible at compile time, or obviously not compatible, because there's no real subtlety in the type system. For these reasons, Pascal and related languages have been called "bondage and discipline" languages: they severely restrict the ways that programs can be composed, because they don't trust the programmer not to screw up. In a sense, this is ludicrous, because there are only a few trivial things the compiler can check in this way: most programming errors are never caught by the type system. * Scheme compilers are much more libertarian---they'll let you do things that the compiler can't tell are reasonable at compile time. They trust you to ensure that the right kinds of values show up in the right places, so that all of the operations in the program make sense. This lets programmers write programs in more flexible ways, but gives them tremendous latitute to make mistakes that will not be caught by the compiler. In practice, most languages fall in between these extremes. For example, in most languages the type system can't tell you that an array reference won't fail at runtime---you may use an integer whose value could exceed the size of the array, and the compiler can't tell that. In this case, the compiler assumes the programmer DOES know what he/she is doing. (The compiler may compile in array-bounds checks and gracefully signal an error at runtime if you index past the end of an array, or it may be an uncaught error as in C, which can crash the program with a segmentation fault.) More recent programming languages attempt to beat the tradeoff between Pascal's compile-time restrictiveness and Scheme's runtime foot-shooting by having more expressive type systems. This lets the programmer express more subtle constraints on the way programs can be composed and what the legal runtime execution paths are. Strongly-typed object-oriented languages allow the programmer to specify what types of arguments are legal for different operations in a much more flexible way than Pascal does. It is possible to declare that a large variety of objects types are acceptable in a particular context, rather than an exact match to a particular concrete type. This is an extension of the traditional notion of abstract data types in three ways: * rather than picking one implementation for an abstract data type at compile time, the programmer may use multiple implementations in a single program, and the same piece of code may operate on different types of objects at different points in a single run of a program. * the type system can express similarities between types in subtle ways---not only may multiple concrete types implement a single abstract type, but different abstract types can be defined by their differences in functionality. An ADT can be defined as an extended version (supporting more operations, or more general operations) of another. * the type system an also express similarities between the implementions of concrete types, whether or not they implement the same abstract types. The goal of such a type system is to allow programmers to express more flexible rules for the composition of sensible programs, while still letting the compiler reject programs that clearly don't make sense. The hope is that the type system is expressive enough that it doesn't keep the programmer from concisely describing reasonable ways of putting programs together, but precise enough that it does rule out most other ways of putting them together. --- In much of the following, I'll use C++ as an example strongly-typed object-oriented language. In reality, C++ is not the best example, because its type system has annoying warts and holes. But it'll do for most of this discussion, and it actually has a couple of nice features that most strongly-typed OO languages don't. --- When you define a subclass in C++ in the usual way, using public inheritance, you are doing TWO things: You are telling the compiler that instances of the subclass (derived class) are implemented just like instances of the superclass (base class), except for the particular differences you specify by adding new instance variables and defining or redefining methods. This is called SUBCLASSING FOR CODE REUSE. You are telling the compiler that instances of the subclass implement the same abstract data type as instances of the superclass. If you define a public subclass of a given class, the compiler assumes you intend for the subclass to support ALL of the operations that the superclass supports. (It will not complain if people compile code where an instance of the subclass might pop up where an instance of the superclass is expected.) This is called SUBCLASSING FOR SUBTYPING. --- There are circumstances where you do not intend to do both of the above things, and you should do something special in those cases. If you only want to make the new class a subclass so that it can share *implementation* aspects with the superclass (e.g., if you want it to inherit some instance variables and code), you should make it a PRIVATE subclass. Using the keyword private in the class definition tells the compiler NOT to let the instances of the subclass be used in every context where the superclass can be used. (Note that here I'm talking about using the keyword private when you declare the base class list, NOT when you declare instance variables (members).) If you want to make the new class a subclass and you DON'T want it to share implementation with its superclass, you usually want to make the superclass an *abstract* class, i.e., one which cannot be instantiated. Abstract classes are used primarily to define interfaces which can be shared by subclasses. (Sometimes abstract classes also specify partial implementations which may be inherited as well.) A well-designed class hierarchy uses abstract classes to define interfaces if the subclasses don't all share part of their implementations. --- Privately derived classes Suppose we want to implement arbitrary-precision integers, or "bignums," and we want them to be usable like built-in integers, i.e., for addition, multiplication, and so on. They will be implemented quite differently from integers, however, since they may require arbitrarily many bits. Arbitrary precision integers might therefore be represented as lists, and it may be a good idea to make BigNum a subclass of List. We would like to tell the compiler that it is NOT legal to USE a bignum as a list, however. Client code should not be able to tell how they're are implemented, only what they're usable for. In C++ we can use private inheritance for this: class BigNum : private List; { ... } This lets BigNum inherit list-manipulation primitives, and BigNum can use those inherited instance variables and methods in implementing its (public) interface. Client code will NOT be able to see those inherited features, however, only the public methods of class BigNum. If C++ were a pure object oriented language, we would probably also be able to make BigNum a public subclass of Number, and in that way advertise its numeric interface: class BigNum : public Number, private List; ... The built-in C-style numeric types of C++ aren't part of the class hierarchy, however, so we can't do that. (There are kludges involving operator overloading that can give a similar effect, but I won't go into that right now.) --- Abstract classes An abstract class is a class that isn't supposed to actually be instantiated---you never make objects of that particular class---but which can be subclassed. This lets you put the common characteristics of several classes in one class, and then define those other classes by inheriting from the abstract class and specifying the details of each subclass in its class definition. For example, in a graphics program, we might have an abstract class "shape", which is a superclass of all classes that represent shapes that can be drawn on the screen. It might have subclasses like triangle, square, and circle. The inheritance hierarchy might look like this: shape / | \ / | \ square circle triangle Class shape might have instance variables x and y, giving its position on the screen, and methods like change_position, which update the position of an object, and move(), which erases an object, changes its position, and redraws it on the screen. Class shape would NOT have an erase() method or a draw() method, because each kind of shape needs to be drawn and erased in a different way. Each subclass has to provide its own method, saying how to draw that particular kind of shape. In C++ish syntax, class shape might look like this: class shape { private: int x; int y; public: void virtual erase(); void virtual draw(); void virtual change_position(int, int); void virtual move(int, int); } Here we've defined one private instance variable. The keyword private means that the variable can only be operated on by methods defined on shapes. We've also declared several virtual functions---abstract operations---that are public, meaning that you can invoke those virtual operations freely from other code. Shape's change_position method might look like this: /* take integers giving deltas in x and y directions, and update position instance variable accordingly */ void shape::change_position(int dx, int dy) { this->x += dx; this->y += dy; } (In C++, "this" is a pseudo-variable that refers to the object we're invoking the virtual function on---the particular instance of some kind of shape. "this->x" is the x field of the object pointed to by "this", i.e., the one whose position we're changing.) Its move method would look like this: void virtual shape::move(int dx, int dy) { this->erase(); this->update_position(dx, dy); this->draw(); } (Note that late binding is important here. A class may inherit the move method, but when we move an object, it invokes the erase and draw _virtual_ functions on itself, so that it invokes the appropriate erase method for the particular kind of object being operated on.) Each subclass of shape would define more instance variables. For example, a square might have a size instance variable, which gives the length of its sides. A circle might have a radius instance variable. A triangle might have three instance variables A, B, and C, which represent the distances of the vertices from the center of the triangle. Each subclass would have draw and erase methods to draw itself on the screen, and erase it later. Class square might look like this: class square : public shape { private: int size; } Its draw method might like like this, using a draw_line routine provided by a graphics libary: void square::draw() { int half_size = (this->size)/2; int top = this->x - half_size; int bottom = this->x + half_size; int left = this->y - half_size; int right = this->y + half_size; draw_line(top,left,top,right); /* draw top side */ draw_line(top,left,bottom,left); /* draw left side */ draw_line(bottom,left,bottom,right); /* draw bottom side */ draw_line(top,right,bottom,right); /* draw right side */ } --- Abstract classes specify interfaces and partial implementations, so that subclasses can share their interfaces---and perhaps _some_ implementation characteristics. --- For example, suppose we have a class Point, whose instances have (private) instance variables x and y, and a class Polar_Point, whose instances have (private) instance variables direction and magnitute. We may want both representations of (2D) points, because each has performance characteristics that are desirable for particular kinds of computations. We would like them to share a common interface and semantics, so that in most circumstances they can be freely interchanged without affecting the correctness of the code using them. (This might just be for flexibility in how programs are written, or specifically to support sharing of data between modules which use different representations by default.) If we have the ability to restructure the class hierarchy, it's probably best to call the (cartesian) Point class described above Cartesian_Point, and make both Polar_Point and Cartesian_Point subclasses of an abstract class Point. Point may define an interface that allows clients to access the data of an instance in either cartesian or polar format. Each concrete class would implement the access methods in a different way appropriate to its own instance variable formats. For example, Point may define get_x_coordinate and set_x_coordinate virtual functions; in class Cartesian_Point, these would simply fetch and update the values of the x instance variable, but in class Polar_Point, the corresponding methods (member functions) would use trigonometric functions to derive and update the effective x coordinate using the direction and magnitude. --- Conceptual types and language-level types There are really two notions of "types" and "subtyping," and it's important to know when you're talking about which. The most important notion of types and subtyping is the CONCEPTUAL relationships between the abstract data types used by the programmer. This includes everything the programmer knows and thinks is important about what kinds of objects can be used in what ways. This kind of conceptualization is essential to proper program design, but it's not always expressed directly in the programming language. The second sense of types is what you can actually tell the language implementation about abstract data types and their concrete implementations. This is usually only a subset of the things the programmer knows and cares about. In particular, it's generally only things that are commonly specified in many programs, and only the ones that a language implementation can check very easily. Typically, the type system only allows the programmer to express simple constraints such as: how objects of a particular concrete type (e.g., a C++ class) are structured what kinds of values it might *ever* make sense to have assigned to a particular variable (e.g., the value of x is always a number) what operations are legal on particular kinds of objects, and how to perform them (e.g., C++ "member functions" (methods)). Notice that all of these involve constraints that can be enforced at compile time. The compiler ensures that certain invariants are maintained for all time, by refusing to compile code that could ever violate those invariants. So, for example, if a variable is of type Stack, and Stack only supports put_first() and get_first() operations, the compiler will not allow you to compile a program that uses the double-ended queue operations put_last() and and get_last() on a variable of type stack. Often the programmer has many other constraints on program construction in mind, when designing modules, but most of those are not expressible in the type system. For example, it may be an error to attempt to pop more values off of a stack than have been pushed onto it. There is no way to specify this declaratively in conventional languages, because it is not possible to write a compiler that can infer whether this error could happen in an arbitrary program. When programmers think about the types of objects in their programs, they may be very much concerned with such "history sensitive" constraints, but the type system does not help very much in that respect. For another example, you can imagine a type system where you could declare a type of "nonzero integer," so that you could declare that a variable could take on any integer value except zero. This could be useful for avoiding divison-by-zero errors, for example. Unfortunately, it would be impossible for the compiler to guarantee that an arbitrary program would not ever generate zero values that might be assigned into a "nonzero" integer variable. To do so would require drastic limitations on the kinds of arithmetic allowed in programs using "nonzero" integers, making them much less valuable. --- The Principle of Substitutability A very important concept in understanding subtyping is the Principle of Substitutability. The basic notion of a type is that objects of a given type are usable in the same kinds of circumstances. Notice that this is a SEMANTIC notion that goes well beyond what the type system of a language is able to check or enforce. The type system of the language can only flag certain obvious kinds of errors. You can still make subtle mistakes and shoot yourself in the foot. An example: Given some reasonable semantics for stacks and double-ended queues, it may be correct to say that a double-ended queue is usable wherever a stack is---if you just use the stack operations put and get, and avoid the other double-ended queue operations, putlast and getlast, a double-ended queue will work fine as a stack. It may therefore be reasonable to make double-ended queue a public subclass of stack. In that case, a compiler will not complain if you write code where a double-ended queue may appear where a stack is expected. (E.g., you can assign a pointer to a dequeue to a variable that's typed as a pointer to a stack, and then use the put and get operations on the object at the end of that pointer.) Notice, however, that the compiler really only checks the interfaces involved, not the implementations or the semantics they implement. The compiler will ensure that the stack interface (put and get) is inherited by double-ended-queue, and that's about it. It is up to the programmer to ensure that what a double-ended queue actually *does* when told to put and get is consistent with what a stack does---for example, the history-sensitive LIFO property that if you push items onto a stack you can pop them off in the opposite order. A negative example: Now consider the classes Set and Bag (where bag means multiset---an unordered collection that allows duplicates). It is a very common error to make Set a public subclass of Bag, or vice versa. After all, they support the same interface (e.g., put and get and maybe a few other things like size), so at first glance it seems natural that one should be a subclass of the other. On closer inspection, however, it's obvious that it's not generally safe to substitute a bag for a set, or vice versa---some code uses sets precisely to eliminate duplicates, and other code relies on bags' allowing duplicates. If either is declared to be a subtype of the other, the compiler will allow substitutions that make no sense semantically. This should make it obvious that one of the functions of a type system like C++'s is to provide some important information in a form that's checkable by the compiler---if you declare something that isn't really a subtype to be a public subclass, the compiler will quietly sit by while you shoot yourself in the foot. Another important function of the class hierarchy is DOCUMENTATION of the programmers' intentions. If a programmer makes something a public subclass of something else, that SHOULD signify that the subclass is a true subtype, i.e., that it implements not only the interface of the supertype, but the same SEMANTICS as well. So, for example, if d-e-queue is declared to be a public subclass of stack, it can be inferred to be a subtype of stack, and that should make anyone who modifies class d-e-queue aware that they should preserve the stack property. A well-designed class hierarchy therefore encodes considerable information about the possible ways reasonable programs can be constructed, and only part of that information can be checked by the compiler. ----------------------------------------------------------------------------- SUBTYPING and MUTABLE STATE In pure functional languages, there are no side effects. This makes certain kinds of things easier to reason about, because if a property is true of an object when it's created, it will always be true after that. In imperative languages like Pascal, C, C++, and Scheme, the possibility of side effects means that you can't count on things staying true unless you reasonable possible paths of execution. This has a profound impact on the idea of subtyping. A lot of things that seem at first glance to be subtypes of other things ARE NOT, because something may change and some property of the (supposed) supertype will not hold in an instance of the subtype. Suppose you're trying to define a class hierarchy for geometric shapes including polygons, rectangles, squares, ellipses, and circles. If there are no side effects, this might be a reasonable way to organize them into subtype relationships: Shape / \ Polygon Ellipse | | Rectangle Circle | Square After all, every polygon is a shape, every rectangle is a polygon, and every square is a rectangle. Similarly, every ellipse is a shape, and every circle is an ellipse whose to foci happen to coincide. But now consider what happens if we try this in a language with side effects, and we want to make our shapes mutable in the obvious convenient ways. For example, we may define a method on class rectangle that changes the width of the rectangle independent of its height, and a similar one that changes the height independent of its width. In order for square to be a subtype of rectangle, we need to supply similar methods for class Square, but that makes no sense---if we change the width of a square without changing its height, it stops being square! We could define the height- and width-changing methods on class square to change both the height and width, so that squares are always square, but then the behavior of squares would be deeply inconsistent with the behavior of plain rectangles---if you're operating on a plain rectangle, you can change its width and expect its height not to change as a result. If you have a pointer to something that you know is some kind of rectangle, but don't know if it's a square, you don't know what to expect. (Similar things happen if you define a method on class ellipse that allows you to adjust its proportions, or a method on class polygon that lets you add a new vertex to the polygon. An ellipse might in fact be circular at some times, but it wouldn't be circular in general.) The point of declaring subtypes is to allow people to reason about properties that DON'T CHANGE---i.e., you're declaring invariants that people can count on in writing code that uses those types. You should only make things properties of a type if they're ALWAYS true. Unfortunately, this means that a lot of the time things simply aren't subtypes, even if you might expect them to be at first glance. So for our shape hierarchy, it turns out that we may only want two levels: a Shape superclass which has subclasses Polygon, Rectangle, Square, Ellipse, and Circle. Another alternative is to declare some intermediate subtypes, and be careful where we define methods: Shape / \ / \ Polyhedron Curve / | \ / \ / | \ / \ Polygon Rectangle Square Ellipse Circle Notice that none of the methods we mentioned above would be defined on Polyhedron or Curve, because none of them applies to all subtypes of those types. We might have these intermediate types so that we could define methods like that (if we think of some), or just to make the conceptual organization clearer. Notice also that this means that the information encoded in the type hierarchy is POSITIVE INFORMATION, not negative information. If you're interested in whether a shape is actually square, you can't just check to see if it's an instance of class square. An instance of class rectangle or class polygon might be square at some particular point in time, without be an instance of class square. If you're going to need to check whether particular instances are square at particular times, you'll have to define a generic function (e.g., square-now?) with appopriate methods for each class. The moral of this is that designing type hierarchies is often not simple; you have to think things through. Sometimes you'll get it wrong and have to go back and restructure your code; that's life. Usually, the exercise of having to design the type hierarchy (and maybe redesign it several times) makes a lot of issues clearer to you---and more explicit, so that it's clearer to other people who use your code. If you don't do it right, though, you class hierarchy will be cumbersone and misleading. So if you're not pretty sure that things are subtypes, it's usually best not to declare them to be. If you use subclassing for code reuse where the subclasses are not subtypes, you should either declare that fact (if your language supports it, as with C++ private inheritance) or document that very clearly so that it's not confusing. --- SUBTYPING, NUMBERS, and VALUE semantics vs. POINTER semantics In Scheme, numeric values are immutable, and numbers are referred to via pointers (conceptually, anyway). This means that some of the obvious properties of subtypes DO work the way they should. E.g., you should be able to use an integer wherever a real value is expected, because an integer IS a real number. In languages like Pascal, C, and C++, however, integer variables are mutable, so weird things can happen. (Remember that by default, those languages pass copies of integer values around, rather than references to unique integer values.) ------------------------------------------------------------------------ Notes on Type Signatures, Conformance, and and Contravariance --- TYPE SIGNATURES The type of a function is specified by the number and types of its arguments, plus the type(s) of its return value(s). So for example, a simple integer arithmetic function might take two integer arguments and return an integer value. Its signature is written: integer * integer --> integer The first part (integer * integer), says that its arguments may be any two integers; the * signifies the cross product---i.e., any combination of the values each can take on independently. The arrow (-->) can be read as "yields". Type signatures are used to tell whether functions provided by one module match the needs of client modules. (We use the term ``module'' very loosely here. It includes not only modules as in Modula, or Ada packages, or separately-compiled C files, but as we will see later, classes and code that uses them.) ---- CONFORMANCE When a module implements a function required by another module, there must be agreement between the types of arguments passed (and return values expected) at the call site and the types of arguments expected (and return value passed) by the actual function. In some languages with separately-compiled modules, it is up to the linker to ensure that the arguments match; in other languages (such as C++) other mechanisms (such as C++'s function prototypes) may be used in order to get around limitations of existing linkers. Unfortunately, C++ does not behave exactly as described below, due to language warts caused by the need for compatibility with C++ and old linkers, as well as to problems caused by its hybrid type system and the fact that arguments are passed by value. The following should be taken as a discussion of an idealized strongly-typed, pure object-oriented language, more similar to Eiffel than C++. When the matching is done, it is not necessary for the match to be exact: it is necessary that the function be able to handle the kinds of arguments that are passed to it, but it is quite acceptable if the function can also handle other types. Similarly, the caller may be able to handle more than one kind of return value, and it is only necessary that the actual return type be among those that are acceptable. So, for example, a function may be able to multiply two numbers, and it may be okay that the actual argument types are integers, or floats, or any type of number. If the caller passes it two integers, it will be able to compute a result. More generally, the caller should pass to the procedure an instance of the type expected. This may not be a direct instance of that type, but an instance of any subtype of that type. As long as it is an instance of the expected type---or any subtype of that type---the procedure should be able to operate on it correctly. Similarly, when the called procedure returns a value, it should return an instance of the type the caller expects, or some subtype thereof. The general principle here is that (in a well-designed strongly-typed object-oriented language), the value passed as an argument or a return value should always implement AT LEAST the functionality that the receiver expects. When looking at type signatures of procedure call sites and of called procedures, and attempting to match them in this way, it must be remembered that argument values are being passed one way, and return values are being passed the other. Therefore, the following signatures are compatible caller: integer * integer --> number callee: number * number --> number because the callee expects any kind of numbers as arguments, and integers are numbers. The caller gets exactly the type of return value it expects, so that's fine too. The following is also acceptable: caller: number * number --> number callee: number * number --> integer The callee gets exactly the types of arguments it expects, and returns a subtype of what the caller expects. Notice that when looking at the arguments, the types at the call site must be NO HIGHER in the subtyping graph than the types declared in the callee---but when looking at the return types, the types at the call site must be NO LOWER in the subtype graph than the types declared in the callee. This apparent asymmetry is due to the fact that arguments are being passed one direction, and return values are being passed the other. In both cases, the values passed must be of the expected type (or some subtype thereof). That's all there is to it: don't pass anything to a routine that it can't handle, whether you're passing arguments in or returning return values out to the caller. --- CONTRAVARIANCE Recall that if subclassing is used for subtyping, superclasses declare INTERFACES that must be supported by (public) subclasses (subtypes). In order to be able to substitute an instance of a subclass for an instance of a superclass, the methods of the subclass must CONFORM to the interfaces defined by the superclass. This means that within the inheritance hierarchy, there are conformance issues similar to those between other code modules. The superclasses can be regarded as declaring module interfaces, while the subclasses define (possibly multiple) implementations that support those interfaces. Intuitively, if the caller of a generic function sees an object as an instance of type T, but it's really an instance of a subtype S of T, then the caller should not have anything surprising happen---it should be able to pass the same kinds of arguments and expect the same kinds of return values. The type signatures of methods defined in subclasses must preserve the two basic conformance properties: * they MUST be able to handle any kinds of arguments that can be legally passed to the corresponding method in the superclass. This means that the subclass method's argument types must be the same as the superclass method's, or any SUPERTYPE thereof (i.e., it's okay if the subclass can handle MORE kinds of things than the superclass). * they MUST NOT return any values that couldn't legally be returned by the corresponding method of the superclass. This means that the return value type of the subclass method must be the same as the superclass method's, or some SUBTYPE thereof. These two properties are known as CONTRAVARIANCE. As with other kinds of conformance, the apparent asymmetry between argument types and return types is really just an artifact of the fact that arguments are passed one direction, and return values are passed another. In either case, the receiver of a value must be able to handle at least the type that's being sent---i.e., exactly that type or some supertype of it. --- LOTS OF SUBCLASSES AREN'T SUBTYPES---DON'T OVERUSE INHERITANCE. The above rules for contravariance mean that a lot of classes that might appear to be subtypes really aren't---if you can't define a method of a subclass to take the SAME kinds of arguments as the superclass method, it's simply not a subtype. This is just a fact of life. Get used to it. In such cases, you may want to use private inheritance so that one class can use code and instance structure defined in another class. In some other cases, you may find that you need a separate abstract class to define shared characteristics between several classes, rather than trying to make one a subclass of another. In many cases, however, a failure of conformance indicates that inheritance is entirely the wrong mechanism to be using. Often, parameterized types turn out to be the right mechanism in such cases---parameterized types allow you to express the fact that classes are very similar, WITHOUT trying to shoehorn them into superclass/subclass relationships. --- Problems with the C++ type system C++'s type system differers from the idealized system we've been discussing, for several reasons. First, C++ treats builtin types like int, float, and and char * differently than "user-defined" types built using structures or classes. There is a type hierarchy for the builtin types, but it's entirely separate from the class hierarchy. You can't define a subclass of integer, for example, because integer isn't a class in the class system. Secondly, C++ often requires stricter matching of types than the simple conformance relationship. (Conformance is really the most flexible way of matching types that makes sense when you're trying to define subtype relationships with classes---it's the most general way of doing things that preserves substitutability.) For builtin types, an exact match is typically required---you can't write a procedure that operates on "numbers" and can accept either ints or floats. Even when using user-defined classes, you can get into deep trouble because conformance may not be enough to make things work in C++. This is especially true when passing arguments BY VALUE, due to the way pass-by-value is implemented in C++ implementations. (Limitations of implementations show through in the language definition.) The slicing problem The big problem with pass-by-value occurs when the caller of a procedure attempts to pass (by value) an argument that is an instance of a subtype of the declared argument type in the callee. (The same kind of problem can occur with return types, but I'll leave that to your imagination...) So, for example, suppose we have a procedure that expects an argument of type T, and we pass it an argument of some subtype S of T. In principle, this should work fine. But not in C++. The problem is that argument passing in C++ works by reserving space for the whole value to be passed, either in argument-passing registers, or on an evaluation stack. The code for the procedure assumes that its argument is of the type T, and reserves space in registers (or on a stack) for an argument of that size. If an argument of a larger size is passed, part of the object will not be copied into the argument passing register(s) ---only the first (T-sized) part of the object will be copied. Naturally, this is a disaster if the value is later operated on in a way that depends on the presence of the missing field(s). This is an enormous hole in the C++ type system---and the moral is DON'T EXPECT SUBTYPING TO WORK IF YOU PASS OBJECTS BY VALUE! Instead, if you want to avoid worrying about this kind of thing, you should generally pass POINTERS to objects, not (copies of) the objects themselves. The nice thing about pointers is that the size of the pointer is independent of the size of the thing it points at---you neatly avoid the slicing problem by passing uniform-sized values. --- PURE OO LANGUAGES AGAIN: The slicing problem is one reason why Eiffel uses pointers by default, like Scheme and Smalltalk---everything's a pointer, at least conceptually. (As with Scheme, small immutable values like integers and characters may be stored directly in a word, but conceptually everything's a pointer, and in implementation, every value fits in a pointer-sized space.) This uniformity lets you skip the pointer-creation and pointer-dereferencing syntax, because they're implicit in the way you operate on all values. (Note: I'm not absolutely sure about this characterization of Eiffel. It too may have warts with respect to small built-in types like ints and floats. I know Java does.) Similarly, in Eiffel, Self, and other pure O-O languages, every operation on an object is a message send (or virtual function call, or whatever you want to call object-oriented function dispatch): you can't accidentally bypass the type system by invoking a non-virtual function on a value that's a subtype of the one that was expected. If the compiler can't be sure what code should be executed, it compiles in a dynamic dispatch that will ensure that the right code is found at runtime. --- Virtual vs. non-virtual functions Notice that in C++'s (impure) type system, problems arise because of the ambiguity in pointers---does a pointer-to-T really point to a T, or perhaps to an S? C++ was designed to avoid virtual function dispatch when it's not expressly asked for (by declaring functions virtual), and that causes problems when it's ambiguous what the actual type of an object is. An alternative approach would have been to make the class of pointers unambiguous---have different kinds of pointer declarations, saying that certain pointers are polymorphic and others are not. So, instead of pointer-to-T, we could have two varieties of pointers: pointer-to-exactly-a-T, and pointer-to-T-or-any-subtype-thereof. For the former, virtual function dispatch could trivially be avoided, and for the latter, the full flexibility contravariance could be supported using virtual function dispatch. The type system could then be made safer, by disallowing the unchecked assignment of the latter kind of pointer to the former kind of pointer variable. (Presumably, there would be some runtime checking mechanism so that the conversion could be done explicitly, and the programmer could specify code to be executed in the case of a runtime type error.) (Would this work better than the approach taken in C++ in terms of safety? What about efficiency? What about compatibility with C? I don't really know.)