7
$\begingroup$

"Ad-hoc polymorphism is obtained when a function works, or appears to work, on several different types (which may not exhibit a common structure) and may behave in unrelated ways for each type." – Strachey 1967

Subtype polymorphism seems to fit this description, albeit usually with late binding on the type that dictates the function's behavior. In Java, for example, the toString function works on any object at all, but has many wholly distinct implementations which are distinguished from one another based on the runtime type of the object; i.e., any class can override it and create a new ad hoc definition.

But when I poke around online, I usually find people making a sharp distinction between subtype polymorphism and ad hoc polymorphism; they are treated as wholly different beasts. Would it be correct to say that subtype polymorphism is a kind of ad hoc polymorphism? If not, why not?

$\endgroup$
5
  • $\begingroup$ Subtype polymorphism requires a "common structure", namely a common supertype. $\endgroup$ – Derek Elkins left SE Oct 15 '17 at 3:36
  • $\begingroup$ @DerekElkins I don't read Strachey's definition as requiring that a common structure be absent -- he's just clarifying that it may be absent. $\endgroup$ – Malnormalulo Oct 15 '17 at 17:35
  • 1
    $\begingroup$ I'm fairly confident Strachey's intent was to emphasize that any "common structure" the different types may have is purely accidental and irrelevant in the case of ad-hoc polymorphism. These terms were (and are) informal and descriptive of patterns in languages Strachey was familiar with which, at that point, would not have been any OO language. The term "inclusion/subtype polymorphism" was introduced later where it was explicitly distinct from ad-hoc polymorphism. These terms become less useful if we blur the distinctions between them. $\endgroup$ – Derek Elkins left SE Oct 15 '17 at 18:00
  • 1
    $\begingroup$ Again, these terms are not formally defined nor prescriptive nor exhaustive so it's hard to state whether or not they are being used "correctly". It is clear that "inclusion/subtype polymorphism" was specifically meant to contrast to ad-hoc polymorphism. On the other hand, what type of "polymorphism" (if any) a specific programming language feature should be classified under (including multiple types) is not necessarily going to have a clear-cut "correct" answer. For example, Haskell's type class mechanism has aspects of parametric, ad-hoc, and subtyping polymorphism. $\endgroup$ – Derek Elkins left SE Oct 15 '17 at 18:08
  • $\begingroup$ Luke Mathieson’s answer focuses more on the set of implementations (single v. multiple implementations) than on the set of acceptable parameter types, defining ad hoc polymorphism as a function accepting a fixed set of parameter types with corresponding implementations, parametric polymorphism as a function accepting any parameter types with a single implementation, and subtype polymorphism as a function accepting any parameter subtypes of a type with a single implementation. This makes subtype polymorphism a kind of parametric polymorphism (restricted to subtypes of a type). $\endgroup$ – Maggyero Mar 9 '20 at 6:56
4
$\begingroup$

Strachey's paper defines only two main classes of polymorphism. Subtyping is certainly not parametric polymorphism, so either subtyping is a form of the remaining class or Strachey's terms are not as comprehensive as he thought.

Strachey distinguished between parametric polymorphism, where there is no information about the actual type and any type can be passed as an argument, and ad hoc where an arbitrary set of types has been nominated as acceptable. Subtyping is not parametric polymorphism because a specific type (the superclass) is known. So the question is, is it ad-hoc?

The choice of the term ad hoc emphasises that there need be no relationship between the different types in a given abstraction; the only unifying factor is the existence of concrete implementations that make them part of the set. Operator overloading and Haskell's type classes fit that criteria.

In contrast, subtyping requires a relationship between the subtypes and the supertype, one that allows subtypes to be used in place of the supertype. The currently-existing set of subtypes is only arbitrary in the sense that all code is arbitrary - being the set of code developers have chosen to write. While the implementation of each subtype can be entirely distinct and unique, the substitutability requirement means that inclusion in the set of acceptable types is principled and not ad hoc.

There is a significant difference between providing the implementation that makes type A a subtype of type B and providing the implementation that enables it to be used as an instance of type class C or an argument for operator +. That seems to justify considering subtyping to be a distinct class of polymorphism.

$\endgroup$
3
  • 1
    $\begingroup$ G'day, Bruce! I think you'll fit right in. Bruce here answers questions about algorithms, Bruce knows about machine learning and Bruce is a bit of a graph theory expert. $\endgroup$ – David Richerby Aug 18 '18 at 8:57
  • $\begingroup$ I suppose I was a little too implementation-focused in my thinking about subtype polymorphism -- while a language like Java might allow us to ignore the substitutability requirement and write unrelated code in a sub_class_ implementation, this would make it, formally, not a sub_type_. So then we may consider the subclass relation in most languages to be a feature which supports both subtype polymorphism and ad hoc polymorphism. $\endgroup$ – Malnormalulo May 2 '19 at 17:46
  • $\begingroup$ Luke Mathieson’s answer focuses more on the set of implementations (single v. multiple implementations) than on the set of acceptable parameter types, defining ad hoc polymorphism as a function accepting a fixed set of parameter types with corresponding implementations, parametric polymorphism as a function accepting any parameter types with a single implementation, and subtype polymorphism as a function accepting any parameter subtypes of a type with a single implementation. This makes subtype polymorphism a kind of parametric polymorphism (restricted to subtypes of a type). $\endgroup$ – Maggyero Mar 9 '20 at 7:01
4
$\begingroup$

They're definitely different things, which is easier to see with a clearer definition of ad-hoc polymorphism. Quoting from Wikipedia:

...ad hoc polymorphism is a kind of polymorphism in which polymorphic functions can be applied to arguments of different types...

So in the definition you've quoted, they're using "on" to mean "passed as arguments", rather than "called from". Ad-hoc polymorphism is available in Java in the form of method overloading. For example BigDecimal has 5 divide(...) methods, all taking different sets of parameters. Other languages have more obvious examples of ad-hoc polymorphism, where there's only one function/procedure, with a list of parameters, and the programmer has to decide what to do with them inside the function/procedure.

Subtype polymorphism, however, is when you can treat an instance of one type as an instance of another type, so anything available on the second type is also avaialable on the first. This is the toString() example you give. toString() doesn't operate on different arguments, but it can be called from different types (because it's defined on Object which everything in Java is a subtype of).

$\endgroup$
5
  • $\begingroup$ Is the distinction between "passed as arguments" and "called from" really meaningful? Isn't an object's this reference really just the same as an extra parameter passed to each method? If I'm not mistaken, some languages even implement object methods in exactly that way. $\endgroup$ – Malnormalulo Oct 15 '17 at 17:34
  • 1
    $\begingroup$ @Malnormalulo correct, but that's not really the distinction I was failing to make :D. The real point is that subtype polymorphism is about treating different types the same way, rather than offering different ways to handle different types that look the same. So if you don't overload toString() (which would effectively be ad-hoc polymorphism), it looks for it on the parent class, because a child class instance is also an instance of the parent class. So for a moment, the type of that child class is effectively different. $\endgroup$ – Luke Mathieson Oct 16 '17 at 0:37
  • $\begingroup$ I thought it was commonly understood that methods are just functions for which the first argument is the associated object - something that Python makes explicit. In any case, saying that something can't be ad hoc because of "called from" rather than "applied to" is arbitrary. It's just different syntax for the same thing - choosing the implementation that corresponds to a type. $\endgroup$ – itsbruce Aug 18 '18 at 6:08
  • $\begingroup$ If I understood you well, ad hoc polymorphism is a function accepting a fixed set of parameter types with corresponding implementations, while subtype polymorphism is a function accepting any parameter subtypes of a type with a single implementation. And what is parametric polymorphism? A function accepting any parameter types with a single implementation (no subtype relationship is required)? In other words, contrary to what @Malnormalulo believed, subtype polymorphism is not a kind of ad hoc polymorphism but a kind of parametric polymorphism? $\endgroup$ – Maggyero Mar 8 '20 at 14:18
  • $\begingroup$ … And polymorphism (in general) is a function accepting different parameter types? $\endgroup$ – Maggyero Mar 8 '20 at 14:19
4
$\begingroup$

Keep in mind that, in PL lingo, the term "polymorphism" is used for different notions.

In OOP, polymorphism usually means subtype polymorphism. If we have a function foo(x: A) we can call foo with any object having a subtype of A. In this way, the function is defined only once but can operate on "many types" -- which justifies the usage of the word "polymorphism".

In functional programming, we often do not have subtypes. Still functions can have a universally quantified type such as bar : forall a b, a -> b -> a. This function can take two arguments of any types a and b (chosen by the caller), and return a value of type a. Hence, this is called a polymorphic function. In some OOP languages, a similar feature can be found with the name of "generic function", e.g. <A,B> A bar(A a, B b) in Java. We can call also this feature "parametric polymorphism".

There is a terminology mismatch here since OOP decided to use the "polymorphism" term to refer to the subtyping one, hence it needed a new term for "parametric polymorphism".

Anyway, in parametric polymorphism, values of the "unknown" quantified types a,b can not be concretely used (since we do not know what they are), but can be merely passed around. This is why bar above must be the projection of its first argument: the function has no other way to produce a return value of type a except to reuse its first argument. Similarly, baz : forall a, a->a must be the identity function.

In real-world languages, sometimes parametric polymorphism is broken by some specific constructs in the language. Minor offenders are

  • non termination: infinite loops / recursion allows to write a baz : forall a, a->a which never terminates, hence it differs from the identity function.
  • exceptions / runtime errors: similar to non termination.
  • null values: if null is a value of any type a, that can be returned by baz as well, making it differ from the identity.

When these are present, one still obtains a weaker form of parametric polymorphism. Worse offenders are

  • checked type casts / instanceof
  • reflection

Indeed, consider this pseudo-Java code

<A> baz(A x) {
  if (x instanceof Integer)
     return (x+1);    // Some casting omitted to make this work
  else
     return x;
}

This is the identity function on all types, except Integer where it does something arbitrarily different. The function above is ugly: it does not handle the x argument as an argument of an unknown type. It actually checks the type of x at runtime and makes decisions on that. We no longer have parametric polymorphism here, since type A is not handled in a "uniform" way: the A=Integer is now "special".

What we get, instead, is just a function which can act on each type A (so it is still polymorphic) but which on each A can have a completely unrelated behavior. In a sense, it is just an unconstrained family of functions, indexed over a type $A$. This is what we call "ad hoc polymorphism".

$\endgroup$
1
  • $\begingroup$ This example of ad hoc polymorphism seems essentially identical to subtyping in terms of its behavior, if not in terms of where it is defined. If your baz were defined as a method of Object (somehow -- let's imagine that Java supports monkey patching) which operates on this instead of on an argument, and we wrote one class which overrides it return some value other than the default identity, then we would get the same sort of polymorphism. $\endgroup$ – Malnormalulo Oct 15 '17 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.