Polymorphism: A Comparative Analysis

Hello! Welcome back to our course on programming theory.

In the last few lessons, we've built a solid foundation by examining the three main types of polymorphism individually:

• Parametric Polymorphism: Writing generic code that works for any type (e.g., C++ templates, Rust generics).
• Ad-hoc Polymorphism: Defining functions that have different implementations for different types (e.g., function overloading, Haskell/Rust traits).
• Subtype Polymorphism: Using a value of a subtype where a value of a supertype is expected (e.g., OO inheritance).

Today, we will synthesize this knowledge. Our goal is to analyze the trade-offs between parametric, ad-hoc, and subtype polymorphism by comparing their use cases and implementations across language families. We'll move beyond definitions to the practical questions of why and when a programmer or language designer would choose one form over another.

This is a crucial topic that touches on language design philosophy, performance, and software architecture. Given your background, we can explore not just the "what" but the deep implementation details that drive these trade-offs.

1. A Concrete Problem: Sorting

To make our comparison tangible, we'll use a single, universal problem: sorting a collection of items. A generic sorting algorithm needs to be polymorphic because the core logic (like quicksort or mergesort) is the same, but the specific operations—comparing and moving elements—depend on the type of item being sorted.

The following article provides an excellent tour of how different languages solve this exact problem, giving us a perfect framework for our analysis.

2. Comparing the Approaches

Let's dissect the three main approaches, using the languages from the article as case studies. We'll start with the most familiar OO approach.

2.1. Subtype Polymorphism: The Dynamic, Object-Oriented Way

This is the classic approach seen in languages like Java and Python. It relies on inheritance and dynamic dispatch.

As the article explains, Java's Collections.sort method can sort a List<T> where T is constrained to be a Comparable.

• Mechanism: Dynamic Dispatch. Each object in the list contains metadata (in Java's case, pointing to its class information, which includes a v-table). When compareTo is called, the Java Virtual Machine performs a lookup at runtime to find the correct implementation for that specific object's type.
• Use Case: Its strength lies in handling heterogeneous collections. You can have a List<Shape> containing Circle and Square objects, and calling draw() on each element will correctly invoke the specific drawing method for each shape.
• Trade-offs:
  • Pro: Extremely flexible for systems where types are not known at compile time or where you need to mix related but different types. This is the bedrock of most GUI frameworks and entity-component systems in games.
  • Con (Overhead): The flexibility comes at a cost. Dynamic dispatch involves a pointer indirection and prevents compiler optimizations like inlining. This is often called the "v-table overhead".
  • Con (Intrusiveness & Semantics): It often requires objects to inherit from a base class or interface. More subtly, it pushes the program towards reference semantics (pointers/references to objects on the heap) rather than value semantics (stack-allocated values), which can introduce complexities around memory allocation, ownership, and nullability.

This last point is a major topic of discussion in the C++ community. The following video provides an expert-level breakdown of the problems with traditional inheritance-based polymorphism and motivates the search for better solutions.

2.2. Parametric Polymorphism: The Static, Zero-Cost Way

C++ templates and Go generics are prime examples of this approach. The polymorphism exists at compile time and is "erased" before runtime.

• Mechanism: Monomorphization. The compiler generates a specialized, non-polymorphic version of the code for each concrete type it's used with. sort<int> and sort<string> become two entirely separate functions in the final binary.
• Use Case: Ideal for writing generic algorithms that operate on homogeneous collections, where performance is critical. Think of standard library containers and algorithms.
• Trade-offs:
  • Pro (Performance): It's a "zero-cost abstraction." The generated code is just as fast as if you had written the specialized version by hand. The compiler can inline and optimize aggressively.
  • Pro (Flexibility): It works with any type that happens to have the right syntax (e.g., an operator<), a concept sometimes called "duck typing at compile time."
  • Con (Code Bloat): Generating many specialized versions can lead to larger binary sizes.
  • Con (Compile Time): The process of instantiation can increase compilation times, sometimes significantly in large C++ projects.
  • Con (Error Messages): Errors can be verbose, as they occur deep inside the template instantiation process (though C++ Concepts have improved this).

The design philosophy behind this is to provide maximum performance and static safety, at the cost of runtime flexibility for heterogeneous types.

2.3. Ad-hoc Polymorphism: The Flexible, Trait-Based Way

Haskell and Rust offer a powerful middle ground with typeclasses and traits. This system unifies the way polymorphism is expressed, while allowing for both static and dynamic dispatch.

• Mechanism: Traits/Typeclasses. This is a system of bounded parametric polymorphism. A function is generic over a type T, but T is constrained to implement a certain trait (e.g., fn sort<T: Ord>(slice: &mut [T])). The dispatch can be:
  1. Static (Default in Rust): The compiler uses monomorphization, just like C++ templates, for zero-cost performance.
  2. Dynamic (Explicit in Rust): The programmer can opt into dynamic dispatch using "trait objects" (e.g., &dyn Draw). This creates a "fat pointer" (a pointer to the data and a pointer to a v-table of trait methods), achieving a result similar to Java interfaces but with explicit intent.
• Use Case: Extremely versatile. It can be used for high-performance generic algorithms (static dispatch) and for traditional OO-style dynamic polymorphism (dynamic dispatch), using a single, unified feature.
• Trade-offs:
  • Pro (Best of Both Worlds): You get the performance of static dispatch when you need it and the flexibility of dynamic dispatch when you choose it.
  • Pro (Non-intrusive): You can implement a trait for a type you didn't define, even for built-in types (subject to certain rules), which is impossible with inheritance.
  • Pro (Clarity): The constraints are explicit in the function signature, leading to clearer intent and better error messages than unconstrained C++ templates.
  • Con (Complexity): The system is more complex than simple inheritance. Concepts like trait objects and object safety in Rust have their own learning curve.

3. Summary of Trade-offs

Here is a table summarizing the core trade-offs between the canonical implementations of each polymorphism type.

Feature	Subtype Polymorphism (Java interface)	Parametric Polymorphism (C++ template)	Ad-hoc Polymorphism (Rust trait)
Dispatch	Dynamic (Runtime)	Static (Compile-time)	Static by default, Dynamic when opted-in (dyn Trait)
Primary Use Case	Heterogeneous collections	Homogeneous collections, generic algorithms	Both; a unified system
Performance	Slower (v-table lookup, no inlining)	Fastest (zero-cost, full optimization)	Fastest by default; slower when using dynamic dispatch
Binary Size	Compact	Larger (code bloat from monomorphization)	Larger for static dispatch, compact for dynamic
Intrusiveness	High (must implement or extend)	Low ("duck typing")	Low (can implement traits for external types)
Flexibility	Easy to add new types, hard to add new operations	Hard to add new types to a heterogeneous collection	Easy to add types and operations (via new traits)
Key Idea	Objects carry their own behavior	Compiler creates specialized code	Code is generic over types that are proven to have a behavior

4. Advanced Topic: Rethinking Runtime Polymorphism

We've seen that the classic OO approach has performance and semantic drawbacks. But what if we could get the benefits of dynamic dispatch without the costs of inheritance? This is where modern C++ techniques, which use parametric polymorphism (templates) to implement runtime polymorphism, become fascinating.

This is a perfect example of how the lines between these categories can blur. We use a compile-time mechanism to build a more efficient runtime one.

The key takeaway here is that even within a single category like "runtime polymorphism," there is a rich spectrum of implementation choices. Techniques like type erasure (which is what the video demonstrates) allow you to create non-intrusive, value-semantic wrappers that can hold any type satisfying an interface, giving you the power of subtype polymorphism with the feel of parametric polymorphism.

Conclusion

We have now compared the three major forms of polymorphism, not just by their definitions, but by their core mechanisms, design philosophies, and practical trade-offs.

Key Takeaways:

• There is no single "best" form of polymorphism. The choice is a fundamental design decision that reflects the language's priorities (e.g., C++'s "zero-cost abstraction" vs. Java's "everything is an object").
• Subtype polymorphism is best for open-ended object hierarchies where behavior is tied to identity and runtime flexibility is paramount (e.g., GUI widgets). Its cost is runtime overhead and a push towards reference semantics.
• Parametric polymorphism is the champion of performance for generic algorithms on homogeneous data, providing static safety and optimal machine code at the cost of binary size and a lack of runtime flexibility.
• Ad-hoc polymorphism via traits/typeclasses (as in Rust/Haskell) offers a powerful, unified synthesis. It provides the vocabulary to demand certain behaviors and allows the programmer to choose between static and dynamic dispatch, offering an excellent balance of performance, safety, and flexibility.

Next Lesson Preview:

This discussion has touched upon a classic problem in program design: is it easier to add new data types or new operations to your system? This is known as the Expression Problem. In our next module, we will begin exploring Algebraic Data Types (ADTs) and Pattern Matching, a core feature of functional languages that provides a powerful alternative to class hierarchies for modeling data and offers a different solution to the Expression Problem.