Subtype Polymorphism and Inheritance

Hello! Welcome back to our exploration of programming language theory.

In our last two lessons, we investigated parametric polymorphism (generic functions that work on any type) and ad-hoc polymorphism (functions that have different implementations for different types, via overloading or type classes).

Today, we will explore the third and final major category of polymorphism: subtype polymorphism. This is the form of polymorphism most closely associated with object-oriented programming. Our goal is to describe subtype polymorphism and its relationship to inheritance in object-oriented languages like Java or Python.

We will unpack the core principle of substitutability, see how inheritance is used to achieve it in practice, and, most importantly, draw a sharp distinction between the concepts of subtyping (an interface relationship) and inheritance (an implementation relationship).

1. The Essence of Subtype Polymorphism: Substitutability

At its heart, subtype polymorphism is about creating flexible code that can operate on a family of related types. The central idea is that of substitutability.

To get a formal definition, let's turn to the lecture slides based on John C. Mitchell's book, which you expressed an interest in.

As the slides state, the principle is: if S is a subtype of T, then any expression of type S may be used without type error in any context that requires an expression of type T.

This allows for powerful patterns, like creating heterogeneous data structures (e.g., a list of Animals containing Dogs, Cats, and Birds) and writing functions that operate uniformly over them.

A helpful mental model is to think of subtypes as subsets. If the set of all Student objects is a subset of all Person objects, then any Student is also a Person.

2. Inheritance: A Mechanism for Subtyping and Code Reuse

So, how do we create these subtype relationships in a language? In most mainstream object-oriented languages like Python, Java, or C++, the primary mechanism is inheritance.

When a class Dog inherits from a class Animal, two things happen:

1. Code Reuse: Dog automatically gains the fields and methods defined in Animal. This is a mechanism for sharing implementation.
2. Subtype Creation: Dog becomes a subtype of Animal, allowing Dog objects to be used where Animal objects are expected.

Let's watch a practical demonstration of how inheritance and polymorphism work together. Although the video uses Java, the concepts are directly applicable to Python and other OO languages.

The video clearly shows substitutability: an array of Animals can hold Lions, Reptiles, and Bats. A function like veterinarian.diagnose() can accept any object whose type is a subtype of Animal.

Here is the equivalent concept demonstrated in Python, which you are more familiar with:

class Shape:
    def area(self) -> float:
        # A generic shape might not have a defined area
        raise NotImplementedError("Subclasses must implement this method")

class Square(Shape):
    def __init__(self, side: float):
        self.side = side

    def area(self) -> float:
        # Override the area method with a specific implementation
        return self.side * self.side

class Circle(Shape):
    def __init__(self, radius: float):
        self.radius = radius

    def area(self) -> float:
        # Override with another specific implementation
        import math
        return math.pi * self.radius ** 2

def print_area(shape: Shape):
    # This function accepts any object that is a subtype of Shape
    print(f"The area is: {shape.area()}")

# Create instances of the subtypes
my_square = Square(5)
my_circle = Circle(3)

# Demonstrate polymorphism
print_area(my_square)  # Correctly calls Square.area() -> "The area is: 25.0"
print_area(my_circle)  # Correctly calls Circle.area() -> "The area is: 28.27..."

In this example, because Square and Circle inherit from Shape, they are its subtypes. This allows us to pass instances of Square and Circle to the print_area function, which expects a Shape. The Python runtime performs dynamic dispatch to call the correct area method.

3. The Crucial Distinction: Inheritance vs. Subtyping

We've seen that inheritance is a way to create subtypes. This leads many programmers to equate the two concepts. However, from a programming language theory perspective, they are distinct. This is a critical point.

Let's go back to the Mitchell slides for the definitive statement.

This distinction is fundamental:

• Subtyping is a relation on interfaces (the "what"). It's about compatibility of behavior. Type S is a subtype of T if S provides all the public functionality of T. This is a semantic and logical relationship.
• Inheritance is a relation on implementations (the "how"). It's about code reuse. Class S inherits from T to avoid re-writing the code that is already in T. This is a syntactic and implementation-level relationship.

While languages like Java and Python bundle them together (inheritance automatically confers subtyping), they don't have to be.

• Inheritance without subtyping: Imagine a language where a subclass could remove a method from its superclass. The subclass would still inherit the other methods (implementation reuse), but it would no longer be a valid subtype because it couldn't be safely substituted for the superclass (it broke the interface contract). The Mitchell slides note this was possible in Smalltalk (slide 156).
• Subtyping without inheritance: Two classes, A and B, could be written completely independently. But if class A happens to have all the public methods that class B has, with compatible signatures, then A could be considered a subtype of B. This is the basis of structural typing, used in languages like Go (with its interfaces) and TypeScript.

The Cornell notes formalize the subtyping rules for records (which are like simple objects). The "width subtyping" rule captures exactly what inheritance usually provides: a subtype can have more fields/methods than its supertype.

4. A Principle for Using Subtype Polymorphism

Finally, just because a language provides a mechanism doesn't mean it should be used indiscriminately. A key design principle separates good uses of subtype polymorphism from poor ones.

The principle is to use class hierarchies and subtype polymorphism when your subtypes represent genuinely different behaviors. If the only difference is in data values (like the damage amount in his first example), a single class with different instances is often a simpler and more flexible design. This aligns with the goal of replacing complex conditional logic (if/else or switch statements) with polymorphic dispatch.

Conclusion

In this lesson, we have explored subtype polymorphism, the third pillar of polymorphism in programming languages.

Key Takeaways:

• Subtype Polymorphism is based on the principle of substitutability: a value of a subtype can be used wherever a value of its supertype is expected.
• This is enabled by dynamic dispatch, where the specific method to execute is determined at runtime based on the object's actual type.
• In languages like Python and Java, inheritance is the primary mechanism used to create subtype relationships and reuse code.
• Theoretically, subtyping and inheritance are distinct concepts. Subtyping is a relationship between interfaces (what an object can do), while inheritance is a relationship between implementations (how an object is built).
• A good design heuristic is to use subtype polymorphism to model variations in behavior, not just data.

Next Lesson Preview:

We have now covered parametric, ad-hoc, and subtype polymorphism. In the next lesson, we will synthesize this knowledge by analyzing the trade-offs between these three approaches. We'll compare their typical use cases and implementations across different language families to understand when and why a language designer or a programmer might choose one over the others.