Ad-Hoc Polymorphism: Type-Specific Implementations

Hello! Welcome back to our course on programming theory.

In our last lesson, we explored parametric polymorphism, where a single function behaves uniformly across all types, like the generic identity function id :: a -> a. This is a powerful tool for abstraction, allowing us to write code that is completely agnostic to the data it operates on.

Today, we shift our focus to a different, yet equally important, kind of polymorphism: ad-hoc polymorphism. This lesson addresses the learning outcome: Describe ad-hoc polymorphism as a mechanism for providing type-specific implementations of a common interface.

We will see how ad-hoc polymorphism allows a single function name or operator to have different, specialized implementations for different types. Think of the + operator: it performs integer addition for numbers but string concatenation for text. This is ad-hoc polymorphism in action.

1. Mapping the Terrain of Polymorphism

To start, let's visualize where ad-hoc polymorphism fits into the bigger picture. The following diagram, based on a famous 1985 paper by Cardelli and Wegner, provides a classic taxonomy.

As you can see, parametric and ad-hoc polymorphism represent two fundamentally different approaches to writing code that works with multiple types.

2. What is Ad-Hoc Polymorphism?

The term "ad hoc" means "for a specific purpose or case." Ad-hoc polymorphism allows a single interface (like a function name or an operator symbol) to be associated with multiple, distinct implementations. The compiler or runtime system then chooses the correct implementation based on the types of the arguments involved.

This contrasts sharply with parametric polymorphism, where a single implementation works for all types.

To get a precise definition and a clear example, please watch the following segment from a talk by George Wilson.

As the video explains, the way you check if two integers are equal (a single CPU instruction) is fundamentally different from checking if two strings are equal (a character-by-character loop). Ad-hoc polymorphism provides a way to bundle these different implementations under a single name, like == or .equals().

3. Mechanisms for Ad-Hoc Polymorphism

Languages provide several mechanisms to achieve ad-hoc polymorphism. We'll explore three prominent approaches to see how the concept is realized in practice.

a) Function Overloading

The most direct form of ad-hoc polymorphism is function overloading. This allows you to define multiple functions with the same name, as long as their parameter lists differ in type or number. The compiler resolves which function to call based on the arguments provided at the call site.

As you saw in the reading, a single add function name can be used for integers, floats, and strings, with each version having a completely different implementation. This is resolved at compile-time.

b) Interfaces and Type Classes

A more structured approach involves defining an explicit contract that types can choose to fulfill. This is common in both object-oriented and functional languages.

• In OO languages like Java or C#, this is done with interfaces. A class can implement an interface, promising to provide concrete methods for the abstract operations defined in that interface.
• In functional languages like Haskell (and with traits in Rust), this is done with type classes. You can define an instance of a type class for a data type, providing the required function implementations.

The following video segments demonstrate both approaches, using the Equal interface/type class as the running example.

Both interfaces and type classes are powerful mechanisms for ad-hoc polymorphism. They formalize the "common interface" and allow different types to provide their own "type-specific implementations."

c) Tagged Unions and Visitors

A third approach, rooted in functional programming but now prominent in modern C++, uses a combination of tagged unions and the visitor pattern.

A tagged union (like std::variant in C++) is a type that can hold a value from a closed set of other types. To perform an operation, you "visit" the variant with a function object that provides an implementation for each possible type the variant could hold.

This achieves ad-hoc polymorphism without relying on inheritance or a shared interface. The "common interface" is the visitor's function call operator, and the "type-specific implementations" are the different overloads or branches within the visitor.

This variant/visit pattern is powerful because it offers value semantics and can be more performant than traditional virtual function calls, but it requires the set of types to be known upfront.

Conclusion

Today we've defined ad-hoc polymorphism and explored its role as a mechanism for providing type-specific implementations for a common interface.

Key Takeaways:

• Ad-Hoc vs. Parametric: Unlike parametric polymorphism, which involves a single, uniform implementation, ad-hoc polymorphism involves multiple, specialized implementations for a single interface.
• Core Idea: It allows a single name (e.g., +, equals, draw) to invoke different behavior depending on the types of the operands.
• Mechanisms: We saw three common ways to achieve this:
  1. Function Overloading: Simple, direct, and resolved at compile-time.
  2. Interfaces/Type Classes: A more structured approach that defines an explicit contract for types to implement.
  3. Tagged Unions/Visitors: A pattern that works on a closed set of types, often providing performance and safety benefits.

Your background in various programming paradigms, including functional languages, should give you a good perspective on how these different mechanisms manifest across language families.

Next Lesson Preview:

We have now seen what ad-hoc polymorphism is and some ways it's implemented. In the next lesson, we will dive deeper into the trade-offs between two of these mechanisms. We will directly compare function overloading, as seen in C++, with type classes, as seen in Haskell, to analyze their impact on extensibility, type safety, and overall program design.