Type systems are the most interesting aspect of modern programming languages. Subtyping is an important notion that is helpful for describing and reasoning about type systems. This document describes much of what you need to know about subtyping. Some of the definitions, notation, and presentation ideas in this document have been taken from Kim Bruce's text "Fundamental Concepts of Object-Oriented Languages" which is a great book and the one that I use in my CSCI 5535 course. Some of the presentational ideas have also been taken from Cardelli and Wegner.
Sebesta says: "A compatible type is one that is either legal for the operator or is allowed under language rules to be implicitly converted by compiler-generated code to a legal type"
There are two aspects to type compatibility:
The discussion of name and structural compatibility (which by the way are more commonly called name and structural equality) in the text takes care of the first aspect. In other words, a type is compatible with any type that is equal to itself (the language defines whether "equals" uses structure or name).
What about the second aspect? When can a type be safely converted to another type? Let us think of a type as a set of values. For example, an INTEGER type is the set of values from -minint to maxint, inclusive. A subrange type [1 TO 100] is the set of values from 1 to 100, inclusive. A boolean type is the set of values TRUE and FALSE. Now, when we declare an entity (such as a variable) to be of a particular type, essentially we are saying that the entity can evaluate to any value in the set for its type.
For example,
VAR x: [10 TO 20];
PROCEDURE p(): [10 TO 20] = ...
A reference to the variable x can evaluate to a value between 10 and 20 (and nothing else). A call to p can evaluate to a value between 10 and 20 and nothing else. Note that in this document I assume a strongly typed language; i.e., all programs in the language respect the type system.
Once we consider types as set of values, we realize immediately one set may be a subset of another set.
[0 TO 10] is a subset of [0 TO 100]
[0 TO 100] is a subset of INTEGER
[0 TO 10] has a non-empty intersection with [5 TO 20] but is not a subset of [5 TO 20]
When the set of values in one type, T, is a subset of the set of values in another type, U, we say that T is a subtype of U. Or that U is a supertype of T. This is often written as T <: U. What are the implications of T being a subtype of U?
"... a value of type T can be used in any context in which a value of type U is expected" [Bruce 2002, pg 24] (my italics)
In other words, if a program expects a value of type U, one can substitute a value of type T in its place and the program will still be correct with respect to types. For example, consider the following code fragment in MYSTERY:
VAR x: INTEGER;
BEGIN
x := ?;
END;
Disregarding any kinds of conversions, MYSTERY expects the right-hand-side of the assignment to be the same type as the left-hand-side. In the example above, the expression substituted for "?" must evaluate to INTEGER. However, since [10 TO 20] is a subtype of INTEGER, one could substitute a value in the type [10 TO 20] and still expect the above program to be safe with respect to types.
VAR x: INTEGER;
BEGIN
x := An expression that evaluates to [10 TO 20] (e.g., a call to p, where p returns [10 TO 20])
END;
The above program will always respect the types since any value of type [10 TO 20] is also a legal INTEGER. Or to put it another way, any value in the set [10 TO 20] is a legal value in the set [-minint TO maxint]. The program above automatically converts the value of type [10 TO 20] to INTEGER and then assigns it to x. A conversion from a subtype to a supertype is called a widening conversion. It is called a widening conversion because it goes from a smaller type (the subtype) to a bigger type (the supertype). Note that by "smaller" or "bigger" I do not mean the size of the representation in memory; I mean the size of the sets associated with the type. Since a widening conversion goes from a subtype to a supertype it is always safe (though it may be the case that with computer representations one may lose some precision). A conversion from a supertype to a subtype is called a narrowing conversion. It is called a narrowing conversion because it goes from a bigger type (supertype) to a smaller type (subtype). A narrowing conversion may or may not be safe.
For example:
VAR x: INTEGER;
VAR y: [0 TO 10];
BEGIN
y := some expression evaluating to an integer
END;
The assignment to y needs a narrowing conversion. If one is lucky and integer expression happens to evaluate to a value between 0 and 10, then the program will work successfully. If on the other hand it evaluates to a value outside the range 0 to 10, then the above program will do a "bad" assignment. Since narrowing conversions may fail but widening conversions do not fail, many programming languages, such as Java, automatically apply the widening conversions but require explicit casts to apply the narrowing conversions.
If a narrowing conversion fails then one of two things happen (depends on the language): (i) The language flags it as a run-time error and the program halts, perhaps throwing an exception; (ii) The supertype value is somehow converted to a subtype value, for example by throwing away some of the bits in the supertype value's representation. Java does a combination of the two (uses the first option for reference types and the second option for primitive types). The first option has the advantage that it is safe. The second option has the advantage that it is fast (doesn't require as much checking).
So far we have used simple types such as subranges and integers to demonstrate subtyping. (BTW, MYSTERY has subrange types to allow me to demonstrate subtyping issues in the language). What about more interesting types?
Let's start with SET types (using Modula-3-like syntax):
TYPE Set1 = SET OF [3 TO 7];
TYPE Set2 = SET OF [1 TO 10];
Set1 includes all sets that have zero or more of the values in the range 3 to 7 (e.g., {3, 4, 7}). Set2 includes all sets that have zero or more of the values in the range 1 to 10 (e.g., {1, 4, 6, 7}). Thus, it must be the case that Set1 <: Set2. More generally, one might say:
SET OF T <: SET OF U iff T <: U
It turns out that while the above reasoning makes perfect sense mathematically, languages that support sets (such as Modula-3) often do not support the above rule for pragmatic reasons. To see why, consider how a set is implemented. Set1 may be represented by 5 bits, with the first bit representing the value 3, the second representing the value 4, and so on. A value in Set1 will have zero or more of the bits set to 1 (e.g., 11001 would represent the set {3,4,7}). Set2 may be represented by 10 bits, with the first bit representing 1, the second representing 2, and so on. Now, if we allow the above subtyping rule, we will allow this assignment:
VAR s2: Set2;
BEGIN
...
s2 := An expression evaluating to a value in Set1
END;
In order to implement the widening conversion required by this assignment, the compiler will have to generate code to convert a representation for Set1 into a representation for Set2. For example, the compiler will need to convert 11001 to 001100100. In the worst case the compiler will have to generate code to look at the value of type Set1 one bit at a time and based on its value of the bit set the corresponding bit in s2. While doable this will be slow and add complexity to the compiler. Thus, languages do not generally support subtyping of sets. (Historic note: The original definition of Modula-3 actually did support subtyping of sets but they decided to remove it from the language after a year for the above reasons).
Classes in object-oriented languages also generally support subtyping via subclassing. For example, in C++ syntax:
class C1 { int x; public void m() {...} };
class C2: public C1 {int y; public void n() {...}};
C2 is not just a subclass of C1 but is also a subtype. To see why, let's consider a set-based argument. C1 is a type whose set of values contain all objects that have an instance variable x and a method m. C2 is a type whose set of values contain all objects with instance variables x and y, and methods m and n. Considered this way, since all values in C2 also support x and m, it must be the case that the values in C2 must be a subset of the values in C1. Thus, C2 <: C1. Since we will see a lot more of this as the class progresses, I won't go into any further detail of subtyping of classes.
For languages that treat functions as first-class values, one may want to talk about subtyping of function types. For example:
TYPE P1 = PROCEDURE (x: P1A): P1R;
TYPE P2 = PROCEDURE (x: P2A): P2R;
Where P1A and P1R are defined elsewhere and are the argument and return types for P1. Similarly P2A and P2R are the argument and return types for P2. For P1 to be a subtype of P2, it must be legal (with respect to types) to call P1 instead of P2. There are two parts to this:
The above two requirements define the correct subtyping rule for procedures. The above rule is also sometimes called the "arrow rule" (since in formal notation, function types are written using →, with the argument type on the left-hand-side of the arrow and the return type on the right-hand side of the arrow).
While the above rule for subtyping of procedures is sound, I do not know of any language that uses it. The reason for this is that it requires complexity in the compiler and may be slow at run time (it can lead to a similar kind of a issue as subtyping sets).
So far our definition of subtyping refers to values and not to variables. If one can substitute a value of a subtype where a value of a supertype is expected, can one substitute a variable of a subtype where a variable of a supertype is expected? It turns out that the answer is no.
To see this, consider how a variable differs from a value: A value, such as the number 7, can be read but not modified (i.e., you cannot modify the value 7 to become 8). A variable can not only be read but it can also be modified. Let's consider this example:
VAR x: T;
VAR y: U;
Imagine that we are trying to determine if one can use y in a place where the program expects x. Since x may be read to obtain value, it must be the case that y's value must be a subtype of x's value:
U <: T
In addition, since x may be modified, it must be the case that any value that x can be modified with must be a legal value for y. Since x may be modified with any value in T, it must be the case that
T <: U
The only reasonable solution to these two constraints is that T = U; i.e., a variable may be used in place of another variable only if they have the same type. Let's look at a concrete example that illustrates the issues here:
VAR x: [10 TO 20];
VAR y: [12 TO 18];
BEGIN
x := ?;
? := x;
END;
A legal type for the "?" is [10 TO 20] since it is the same type as x. What if we use y in place of ?:
VAR x: [10 TO 20];
VAR y: [12 TO 18];
BEGIN
x := y;
y := x;
END;
It is obvious that the first assignment (x := y) will always succeed since any value for y is a legal value for x. However, the second assignment (y := x) may or may not succeed if, for example, x holds the value 20. Bottom line: the rule for substituting updateable quantities are different than the rules for substituting values.
Let's now apply what we have learned so far to arrays. We would like to be able to say:
ARRAY I OF T <: ARRAY I OF U, if T <: U
In other words, one array is a subtype of another array if they have the same index type (e.g., [10 TO 20]) and the element type of the first array is a subtype of the element type of the second array. Is this actually true? If we think about it for a moment, we realize that like variables, arrays are updatable in most languages. In other words, one can not only read the values in an array but one can modify values in the array. Can you come up with a correct rule for array subtyping along with an example that demonstrates the need for your rule?
It actually turns out that Java uses the above rule for subtyping of arrays even though it is not correct:
The following conversions are called the narrowing reference conversions:
...
From any array type SC[]to any array type TC[], provided that SC and TC are reference types and there is a narrowing conversion from SC to TC. [Section 5.1.5, Java Language Specification, 2nd Ed]
The price that Java has to pay for this flexibility is lots of extra run time checks. Every assignment to an array element in Java needs to be checked to make sure that the value being stored is legal for the array.