Bounded parametric polymorphism vs ad-hoc polymorphism

Question

A similar question has already answered here - Parametric polymorphism vs Ad-hoc polymorphism. The difference in this question is with the term bounded. It seems that there are two distinct flavors of ad-hoc polymorphism -

1. For example, in C++ you can write

   int foo(int x) { return x; }
   int foo(string x) { return x.size(); }
   

   In this case, it doesn't make sense to speak of the type of foo as an overload set (in the sense that it is not a user-definable type, or something for which you can create an alias), but it does make sense to speak of the types of the individual overloads themselves.

2. In Haskell, you can write

   class Foo a where
     foo :: a -> Int
   instance Foo Int where
     foo x = x
   instance Foo String where
     foo xs = length xs
   

   Here, it makes sense to speak about the type of foo by itself as a proper type Foo a => a -> Int which can be used like an ordinary user defined type.

Is it appropriate to say:

1. C++'s flavor of ad-hoc polymorphism via function overloading cannot be classified as bounded parametric polymorphism.

2. Haskell's flavor of ad-hoc polymorphism via type classes can be classified as bounded parametric polymorphism (as a different example, Pierce's Types and Programming Languages talks about System-F_<: in a similar context).

Is bounded parametric polymorphism a strict "subset" of ad-hoc polymorphism, in the sense that any type system that can be said to have the first can also be said to have the second?

Answer 1

It's uncontroversial that 'ad-hoc polymorphism' is a fundamentally different sort of thing than 'parametric polymorphism'. But the relevance of 'bounds' depends on what definition of 'ad-hoc' you use, and therefore so does the answer to whether 'bounded parametric polymorphism' can be considered a type of 'ad-hoc polymorphism'.

In Fundamental Concepts in Programming Languages (FCPL) (Strachey 1967) (which is the only source for the Wikipedia article on ad-hoc polymorphism), it says this:

In ad hoc polymorphism there is no single systematic way of determining the type of the result from the type of the arguments. There may be several rules of limited extent which reduce the number of cases, but these are themselves ad hoc both in scope and content. All the ordinary arithmetic operators and functions come into this category. It seems, moreover, that the automatic insertion of transfer functions by the compiling system is limited to this class.

Whereas the linked answer cites Types and Programming Languages (TAPL) (Pierce 2002):

Ad-hoc polymorphism, by contrast, allows a polymorphic value to exhibit different behaviors when “viewed” at different types. The most common example of ad-hoc polymorphism is overloading, which associates a single function symbol with many implementations; the compiler (or the runtime system, depending on whether overloading resolution is static or dynamic) chooses an appropriate implementation for each application of the function, based on the types of the arguments.

For your question:

Is bounded parametric polymorphism a strict "subset" of ad-hoc polymorphism, in the sense that any type system that can be said to have the first can also be said to have the second?

If we take the FCPL definition, then I would say 'no'. If we take the TAPL definition, then I would say 'yes'.

---

I would argue that the difference in these characterizations is as follows:

• FCPL claims that there are no explicit 'bounds' for the type in question, and that ad-hoc polymorphism is an informal quality of the type system rules.
  • This limits the definition to cases like function overloading, but not bounded parametric polymorphism.
  • In some cases, the ad-hoc polymorphism may only be available to the compiler author for specific built-in symbols, and not to the language user.
• TAPL claims that there is a 'bound': namely, the union of all different types that it could be 'viewed' as.
  • The characteristic of 'ad-hoc type system rules' is no longer a defining feature.
  • 'Bounded parametric polymorphism' as a language feature allows you to establish a bound in a more principled way than ad-hoc type system rules. Under the FCPL definition, the type system rules for 'bounded parametric polymorphism' would not be ad-hoc, and therefore not constitute ad-hoc polymorphism.

After 35 years, it's likely that the prevailing definition of 'ad-hoc polymorphism' has shifted more towards the TAPL definition. But I think the TAPL definition is specific to the pedagogical presentation of type systems, rather than a fully-general definition. Based on my experience in the field:

• I believe that 'ad-hoc polymorphism' is mainly considered in terms of whether you can write finite concrete implementations.
• I believe that 'ad-hoc polymorphism' may involve explicit 'bounds', or it may institute implicit 'bounds' (for function overloading, by simply considering the union of all of the concrete implementations to be the valid 'bounds', as vaguely suggested by TAPL), but some idea of 'bounds' is necessary, as opposed to making the FCPL claim about the characteristics of the type system rules.

To recharacterize:

• Parametric polymorphism involves universal quantification.
  • 'Bounds' apply to the universal quantification of parametric polymorphism, changing the type from forall a. a to forall a : X. a for some bound X.
  • Note: You can view subtyping polymorphism as also involving bounded parametric polymorphism (see example below). The main question in such a type system is the decision problem of whether a type satisfies a bound given the subtyping rules.
  • Note: Typically, a 'bound' is satisfied with some concrete implementation, but it's also possible to satisfy a bound for a universally-quantified type with another universally-quantified implementation instead; see below for an example.
• Ad-hoc polymorphism involves concrete implementations for some interface.
  • It ought to eventually involve manually writing out a finite number of implementations adhering to some interface. Therefore, it cannot rely on universal quantification, unless you can write an infinite number of implementations by hand 🙂.
  • The interface/bounds in question could be implicit or explicit.
  • In some sense, it relates more to existentially-quantified types than universally-quantified types.

---

Therefore, 'bounded parametric polymorphism' is an instance of 'ad-hoc polymorphism' so long as it involves writing concrete implementations. So the language design matrix looks like this:

	Can write concrete implementations	Can write universal implementations
Bounded parametric polymorphism	✅1	✅2
Function overloading	✅	❌

And the claim is merely that having a ✅ in the "can write concrete implementations" column means that the language supports ad-hoc polymorphism, so all bounded parametric polymorphism systems are instances of ad-hoc polymorphism as well¹.

¹ I don't immediately see any cases where it would be useful for a language to support bounded universal quantification but not make it possible to write a concrete type that satisfies the bound. Therefore, I would argue that 'bounded parametric polymorphism' is a case of 'ad-hoc polymorphism' in all languages that I'm aware of.

² Note that there are interesting cases where specific type bounds are implemented in a universally-quantified manner rather than an ad-hoc manner. For example, in Rust, you can write this (and there is surely an equivalent Haskell implementation):

use std::fmt;
struct Foo<T> {
    inner: T,
}
impl<T: fmt::Display> fmt::Display for Foo<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "Foo({})", self.inner)
    }
}
pub fn main() {
    let foo = Foo { inner: 3 };
    println!("foo is: {foo}"); // foo is: Foo(3)
}

But ultimately, for this program to be useful at runtime, there needs to be some concrete (ad-hoc and non-universally-quantified) implementation of Display for some concrete type (in this case, the implementation of Display for the numeric type corresponding to 3).

---

For your questions about the categorization of C++ vs Haskell specifically:

C++'s flavor of ad-hoc polymorphism via function overloading cannot be classified as bounded parametric polymorphism.

I would argue yes, but mainly because function overloading doesn't really involve parametric polymorphism.

For completeness, note that C++ offers bounded parametric polymorphism by other means:

• Implicitly via templates generally. The 'bound' is not statically-annotated, but only determined by whether typechecking succeeds.
• Explicitly via templates combined with concepts (since C++20).
• Explicitly via subtyping polymorphism, i.e. int foo(const Sized& sized) const { return sized.size(); }.
  • Note: The polymorphism here is limited to a per-argument basis. You can't directly express int foo(const Sized& sized1, const Sized& sized2) but also requiring that the two arguments have the same concrete subtype of Sized.
  • In contrast: With more-general bounded parametric polymorphism, you can express constraints between parameter types/return type. With C++ concepts, you could say template <Sized T> int foo(Sized sized1, Sized sized2) to add a bound to T, and ensure that both arguments have the same concrete type.

However: In the same way that we're interpreting subtyping polymorphism as involving a restricted form of bounded parametric polymorphism, you can imagine an interpretation of function overloading where there's an implicit bound that all calls to an overloaded function need to satisfy. But I don't think this interpretation is particularly useful from a theoretical standpoint.

Haskell's flavor of ad-hoc polymorphism via type classes can be classified as bounded parametric polymorphism (as a different example, Pierce's Types and Programming Languages talks about System-F_<: in a similar context).

Yes, I believe that it's a form of bounded parametric polymorphism. I don't recall TAPL's specific formulation of bounded parametric polymorphism or of System-F_<:, but:

• To formulate Haskell's typeclasses as a subtyping problem, you can interpret it as checking the subtyping relationship between a concrete type and a typeclass as its bound, as discussed previously.
• I don't recall, but TAPL might formulate bounded parametric polymorphism more as existential types (like OCaml modules) where subtyping is not inferred, but only explicitly annotated and checked.