Polymorphism in C++ – A Type Compatibility View

Polymorphism is the provision of a single interface to entities of different types [Stroustrup]. While there is a single interface, there can be many possible implementations of the interface and the appropriate implementation is selected (either explicitly by the programmer, or by the compiler) based on the types of the arguments. C++ supports multiple kinds of polymorphism and classifying them based on certain common characteristics makes it easier for us to reason about design choices. One way to classify them is in terms of when the implementation is selected i.e. compile-time vs. runtime. In this article, we will look at the relationship between type compatibility and polymorphism, and see that the different kinds of polymorphism can also be classified based on whether they require nominative or structural compatibility between the types of arguments (actual parameters) and parameters (formal parameters). This gives us a framework for arguing about design choices in two dimensions.

Type compatibility and polymorphism

An important characteristic of type systems concerns the notion of type compatibility i.e. whether the type of an expression is consistent with the type expected in the context that the expression appears in [Wikipedia-1]. To understand the importance of type compatibility to polymorphism, consider the following definition of polymorphism from On Understanding Types, Data Abstraction and Polymorphism by Luca Cardelli and Peter Wegner:

Similarity relations among type expressions that permit a type expression to denote more than one type, or to be compatible with many types, are referred to as polymorphism [Cardelli85].

Basically, the notion of type compatibility is at the heart of polymorphism. The strongest similarity relation between types is equivalence (under some rules for equivalence). Types that are equivalent are compatible with each other. In languages with subtyping, such as C++, a subtype is compatible with its super types. The forms of type compatibility that are of interest to us are nominative and structural.

Nominative typing is the one that is immediately familiar to C++ programmers. In nominative typing, two variables are type-compatible if and only if their declarations name the same type [Wikipedia-2]. Basically, types are not equivalent unless they have the same name and are in the same scope. In C++, aliases defined using typedef are equivalent to the original type. In nominative subtyping, such as inheritance in C++, super type – subtype relationships are explicitly declared. The C++ type system is primarily nominative.

In a structural type system, on the other hand, type equivalence is determined by the type’s actual structure or definition, and not by other characteristics such as its name or place of declaration [Wikipedia-3]. Super type – subtype relationships are also determined based on the structures of the types. One type is a subtype of another if and only if it contains all the properties of that type. Conversely, any type whose properties are a subset of those of another type is a structural super type of that type. In contrast to nominative subtyping, we can define a structural super type of an existing type without modifying the definition of that type. Thus, structural typing thus allows us to treat concrete types that are otherwise unrelated by inheritance in a polymorphic manner. Duck typing is a special form of structural typing where type compatibility is only based on the subset of a structure used within a particular context. Two types that are considered compatible in one context might not be compatible in another context. C++ exhibits structural typing with respect to type template parameters. In this article, I use structure to mean a type’s public interface, and property to mean a type’s public method or data.

In Listing 1, while both the Cat and the Dog classes have the same structure, they are not considered equivalent in a nominative type system such as C++. For instance, you cannot pass an object of type Dog to a function that expects a Cat. However, they are structurally equivalent. Also, in a structural type system, ThingWithName would be a super type of both the Cat and the Dog classes. Now, let’s see the forms of type compatibility required by the different kinds of polymorphism in C++.

class Dog {
public:
  const std::string& name() const;
  void moveTo(const Point& point);
};

class Cat {
public:
  const std::string& name() const;
  void moveTo(const Point& point);
};

class ThingWithName {
public:
  const std::string& name() const;
};
			

Polymorphism at compile-time

C++ is a statically typed language, which means that variables have a type (whether declared or deduced) at compile-time and they retain that type throughout their life. Compile-time polymorphism, also known as static polymorphism, involves selecting an implementation based on static types of the arguments. C++ allows two kinds of compile-time polymorphism – ad hoc and parametric.

Ad hoc polymorphism [Strachey67] in C++ is implemented using overloaded functions. Function overloading allows us to define two or more functions with the same name in the same scope [Wikipedia-4]. Overloaded functions are distinct and potentially heterogeneous implementations over a range of specific types. The compiler selects the most appropriate overload based on the number and types of the arguments [cpp-reference]. Overload resolution requires either nominative compatibility or implicit convertibility between the types of the arguments and the parameters. Consider the overloaded functions in Listing 2.

void printName(const Dog& v)
{
  std::cout << v.name() << std::endl;
}

void printName(const Cat& v)
{
  std::cout << v.name() << std::endl;
}

int main()
{
  Dog d;
  printName(d);
  
  Cat c;
  printName(c);
  return 0;
}
			

In ad hoc polymorphism, we need to provide a separate implementation for each type. This, however, leads to code duplication if we want to uniformly apply an algorithm to values of different types. Parametric polymorphism, on the other hand, allows us to write generic functions and generic data types that can handle values identically without depending on their type [Strachey67]. In C++, parametric polymorphism is implemented using templates – generic functions are defined using function templates, and generic data types are defined using class templates. For each type parameter, a template implicitly specifies the minimum set of properties that the corresponding type argument must have. We can use SFINAE [Vandevoorde02] and Concepts (which have recently been merged into the C++20 draft) to explicitly add additional requirements on the type arguments. Consider the example in Listing 3.

template<typename T>
void printName(const T& v)
{
  std::cout << v.name() << std::endl;
}

int main()
{
  Dog d;
  printName(d);
  
  Cat c;
  printName(c);
  return 0;
}
			

The printName template has one type parameter and can be instantiated with Dog, Cat, or any type that has a name() method, irrespective of any other methods they might have. In other words, a template can be instantiated with any types that are structurally equivalent to, or are structural subtypes of its type parameters. Note that this is also true of generic lambdas. After all, the call operator of a generic lambda’s compiler-generated type is a template.

Curiously Recurring Template Pattern [Coplien95] is a technique that uses templates and inheritance to simulate subtype polymorphism at compile-time. In CRTP, the base class template is implemented in terms of the derived class’s structural properties. Consider the example in Listing 4.

template<typename T>
class Animal {

protected:
  Animal() { }

public:
  const std::string& getName() const
  {
    return static_cast<const T *>(this)->name();
  }
};

class Dog : public Animal<Dog> {
public:
  const std::string& name() const;
  void moveTo(const Point& point);
};

class Cat : public Animal<Cat> {
public:
  const std::string& name() const;
  void moveTo(const Point& point);
};

template<typename T>
void printName(const Animal<T>& v)
{
  std::cout << v.getName() << std::endl;
}

int main()
{
  Dog d;
  printName(d);
  
  Cat c;
  printName(c);
}
			

Compile-time polymorphism in C++ is quite powerful and expressive, but because implementations are selected at compile-time, it cannot depend on information that is available only at runtime. In fact, often we only know the type of objects to create at runtime. Let us now see how polymorphism works at runtime.

Polymorphism at runtime

Runtime polymorphism, also known as dynamic polymorphism, involves selecting an implementation based on the runtime type of one or more arguments (dynamic dispatch). In C++, it is implemented using subtyping and the most common form of subtyping for dynamic dispatch is inheritance with virtual functions. Overrides of a virtual function essentially overload it on the type of the implicit this argument. Virtual function calls are resolved based on the runtime type of this (which must be nominatively compatible with the base class) and the static types of the rest of the arguments. Consider the example in Listing 5.

class Animal {
public:
  virtual ~Animal() {}
  virtual const std::string& name() const = 0;
};

class Dog : public Animal {
public:
  const std::string& name() const override;
  void moveTo(const std::string& std::string);
};

class Cat : public Animal {
public:
  const std::string& name() const override;
  void moveTo(const std::string& std::string);
};

void printName(const Animal& v)
{
  std::cout << v.name() << std::endl;
}

int main()
{
  Dog d;
  printName(d);
  
  Cat c;
  printName(c);
}
			

Inheritance is a form of nominative subtyping, and the printName() method can be called with any object whose type is a nominative subtype of Animal. However, because inheritance requires explicit declaration of super type – subtype relationships, is not always a viable solution for runtime polymorphism. Some of the types we need to abstract over might be in a third-party library that we cannot modify, and thus cannot be made to derive from a common base class. The types might not even be related – forcing a set of unrelated types to derive from a common base class is intrusive and does not necessarily express an is-a relationship. Inheritance also implies a tight coupling between the base and the derived classes, which might cause scalability issues. For more details about the various types of inheritance and their implications, please refer to John Lakos’s presentation on inheritance [Lakos16a]. The video of his presentation is available on the ACCU YouTube channel [Lakos16b].

The ability to select implementations based on structural compatibility of runtime types would help overcome some of the drawbacks of using inheritance, but how do we do that? The answer is type erasure. Type erasure is used to create non-intrusive adapters that are implemented in terms of the structural properties of the adapted object’s type, and some of those adapters behave just like structural super types. Consider the example in Listing 6.

class ThingWithName {
public:
  template<typename T>
  ThingWithName(const T& obj)
  : inner_(std::make_unique<Holder<T> >(obj))
  {

  }
  const std::string& name() const
  {
    return inner_->name();
  }
    
private:
  struct HolderBase {
    virtual ~HolderBase() { }
    virtual const std::string& name() const = 0;
  };
    
  template<typename T>
  struct Holder : public HolderBase {
    Holder(const T& obj)
    : obj_(obj)
    {
    }
    const std::string& name() const override
    {
      return obj_.name();
    }
    T obj_;
  };
  std::unique_ptr<HolderBase> inner_;
};

void printName(const ThingWithName& v)
{
  std::cout << v.name() << std::endl;
}

int main()
{
  ThingWithName d((Dog()));
  printName(d);

  ThingWithName c((Cat()));
  printName(c);
}
			

The container (ThingWithName) can be instantiated with an object of any type as long as it has the name() method, irrespective of any other methods it may have i.e. any type that is structurally equivalent to or is a structural subtype of ThingWithName. Because it is not a class template, clients of ThingWithName do not have to know the underlying type at compile-time. Thus, while there is no language support in C++ for runtime polymorphism based on structural compatibility, it can be simulated using type erasure. Runtime structural subtype polymorphism is widely used in C++, even though we might not have thought of it as such. For example, std::any can be seen as the structural counterpart of an empty base class, and the std::function template can be seen as generating structural super types of callable types (any type with an explicit or an implicit operator()).

Nominative vs. structural typing – the trade-offs

Structural typing enables unanticipated re-use i.e. it frees us from having to anticipate all possible types that we want to apply an algorithm to, and from having to anticipate all possible algorithms that we want to apply to a type. While it is more flexible than nominative typing, there are certain drawbacks. Just because two types are structurally equivalent does not mean they are semantically equivalent. The advantage of a nominative system is that type names convey contracts and invariants that are not necessarily apparent from the structure of type alone. It allows the programmer to explicitly express her design intent, both with respect to contracts and how the various parts of the program are intended to work together. By allowing us to also use the ‘meaning’ of the type to select implementations, nominative typing allows for stronger type-safety than structural typing.

A matrix of polymorphism choices

We have seen that we can classify compile-time and runtime polymorphism in terms the form of type compatibility they require. It is helpful to represent these in a two-dimensional matrix. Bear in mind that these are just building blocks and that real-world design patterns do not neatly fall into one of these categories. For example, in the Curiously Recurring Template Pattern the base class template requires structural compatibility whereas the derived classes are nominative subtypes of the base class.

The matrix shows us that the dichotomy that exists between nominative and structural type compatibility at compile-time also exists at runtime. The choice of the kind of polymorphism to use in C++ is often phrased as a choice between templates and inheritance. However, as we can see from the matrix, the journey from templates to inheritance requires two hops. If we need runtime polymorphism but want to retain the flexibility of structural typing, type erasure is a more natural choice. We should, however, choose inheritance if we also want the stronger type-safety of nominative typing. The matrix provides a framework for understanding the implications and trade-offs of our design choices as they relate to polymorphism.

I should point out that there are exceptions to the type-compatibility view of polymorphism. Type casting, whether implicit or explicit, can make a monomorphic interface appear to be polymorphic. This is sometimes referred to as coercion polymorphism. Also, C++ allows non-type template parameters, meaning templates can be instantiated with values in addition to types.

References

[Cardelli85] L. Cardelli and P. Wegner, On Understanding Types, Data Abstraction and Polymorphism, 1985

[Coplien95] J. Coplien, Curiously Recurring Template Patterns, C++ Report: 24–27, February 1995

[cpp-reference] Overload Resolution http://en.cppreference.com/w/cpp/language/overload_resolution

[Lakos16a] Proper Inheritance, John Lakos (https://raw.githubusercontent.com/boostcon/cppnow_presentations_2016/master/00_tuesday/proper_inheritance.pdf)

[Lakos16b] Proper Inheritance, John Lakos, ACCU 2016 (https://www.youtube.com/watch?v=w1yPw0Wd6jA)

[Strachey67] C. Strachey, Fundamental concepts in programming languages, 1967

[Stroustrup] Bjarne Stroustrup’s C++ Glossary http://www.stroustrup.com/glossary.html#Gpolymorphism

[Vandevoorde02] D. Vandevoorde, N. Josuttis (2002). C++ Templates: The Complete Guide. Addison-Wesley Professional

[Wikipedia-1] Type System (https://en.wikipedia.org/wiki/Type_system)

[Wikipedia-2] Nominal Type System (https://en.wikipedia.org/wiki/Nominal_type_system)

[Wikipedia-3] Structural Type System (https://en.wikipedia.org/wiki/Structural_type_system)

[Wikipedia-4] Overloading (https://en.wikipedia.org/wiki/Function_overloading)