Subtype

Subtype #

As we saw in the previous sections, the purpose of generic programming is to write abstract code while enforcing type constraints. As a result, when we write a program that uses a generic type (e.g. a native Java Collection), we need to make sure that our code complies with these type constraints.

In some situations, this requires reasoning about types and their hierarchy (notably for programs that use callback methods).

In this section, we briefly illustrate how the notion of a subtype extends to functions (and more generally, methods). This will allow us to understand (in the dedicated section) some type constraints expressed via generics in languages like Java or C#.

The subtype relation #

Intuitively, $A$ is a subtype of $B$ if “every $A$ is a $B$”.

Examples.

  • Integer is a subtype of Number,
  • String is a subtype of Object.

In object-oriented programming, subtyping generalizes hierarchical relations between classes, interfaces, etc.

Example. In Java, $A$ is a subtype of $B$ if:

  • $A$ and $B$ are classes and $A$ extends $B$ (directly or transitively), or
  • $A$ and $B$ are interfaces and $A$ extends $B$ (directly or transitively), or
  • $A$ is a class, $B$ is an interface and $A$ implements $B$ (directly or transitively), or
  • etc.

Observation. “Subtype” is a binary relation. This relation is both:

  • reflexive: every type $A$ is a subtype of itself,

  • transitive: if $A$ is a subtype of $B$ and $B$ is a subtype of $C$, then $A$ is a subtype of $C$.

Observation. If an object $o$ has type $A$ and $A$ is a subtype of $B$, then $o$ also has type $B$.

Examples. In Java:

  • if an object has type Integer, then it also has type Number,
  • if an object has type String, then it also has type Object.

Question. How do these observations generalize to functions (or methods) and the type of their arguments and return value?

Function type #

Definition. A function has type

$\qquad X \to Y$

if it maps every element of $X$ to some element of $Y$.

Examples #

Glossary (reminder).

  • $\mathbb{R}$ : real numbers
  • $\mathbb{Z}$ : integers
  • $\mathbb{N}$ : natural numbers (a.k.a. positive integers, including 0)

Observe that:

  • $\mathbb{N}$ is a subtype of $\mathbb{Z}$
  • $\mathbb{Z}$ is a subtype of $\mathbb{R}$
  • $\mathbb{N}$ is a subtype of $\mathbb{R}$

Example. Consider a function getLength that:

  • takes as argument a string, and
  • returns the length of this string.

This function has type

$\qquad$ String $\to \mathbb{N}$

because it maps every string to a natural number.

It also has type

$\qquad$ String $\to \mathbb{Z}$

because it maps every string to an integer (since natural numbers are integers).

For the same reason, it also has type

$\qquad$ String $\to \mathbb{R}$

However, it does not have type

$\qquad$ Object $\to \mathbb{N}$

because it does not map every object to an integer (only strings).

Consider the function $f\colon \mathbb{R} \to \mathbb{R}$ defined by $f(x) = x^2$.

Which of the following types are also valid for $f$ ?

  1. $\qquad \mathbb{R} \to \mathbb{Z}$
  2. $\qquad \mathbb{R} \to \mathbb{N}$
  3. $\qquad \mathbb{Z} \to \mathbb{R}$
  4. $\qquad \mathbb{Z} \to \mathbb{Z}$
  5. $\qquad \mathbb{Z} \to \mathbb{N}$
  6. $\qquad \mathbb{N} \to \mathbb{R}$
  7. $\qquad \mathbb{N} \to \mathbb{Z}$
  8. $\qquad \mathbb{N} \to \mathbb{N}$

3, 4, 5, 6, 7, 8

Function subtyping #

Which of the 8 proposals below are (always) correct?

If a function has type

$\qquad \mathbb{Z} \to \mathbb{Z}$

then it also has type:

  1. $\qquad \mathbb{N} \to \mathbb{N}$
  2. $\qquad \mathbb{N} \to \mathbb{Z}$
  3. $\qquad \mathbb{N} \to \mathbb{R}$
  4. $\qquad \mathbb{Z} \to \mathbb{N}$
  5. $\qquad \mathbb{Z} \to \mathbb{R}$
  6. $\qquad \mathbb{R} \to \mathbb{N}$
  7. $\qquad \mathbb{R} \to \mathbb{Z}$
  8. $\qquad \mathbb{R} \to \mathbb{R}$

2, 3, 5

We can now generalize these observations:

Property. If $X_1$ is a subtype of $X_2$ and $Y_1$ is a subtype of $Y_2$, then

$\qquad X_2 \to Y_1$

is a subtype of

$\qquad X_1 \to Y_2$

Example. A function from Unit to Integer is also a function:

  • from Butterfly to Integer,
  • from Unit to Number, and
  • from Butterfly to Number.