The Fundamental Difference Between C++ Templates and Parametric Polymorphism

❖C++ Templates and Parametric Polymorphism

Templates are a feature of the C++ language, similar to:

1template <class T>
2T id(T x) {
3    return x;
4}

Here, T can be any type. Many people have noticed its similarity to parametric polymorphism, and some even directly regard the template mechanism as a kind of parametric polymorphism. Such as this ppt and this webpage.

However, in this blog post, I will explain that regardless of whether C++ templates are a good language feature, they are fundamentally different from parametric polymorphism.

❖What is Parametric Polymorphism

The history of parametric polymorphism can be traced back to a lecture note (Fundamental Concepts in Programming Languages). Although the lecture note mainly describes the CPL language, in fact, this section should describe the MAP function of LISP:

Parametric polymorphism is more regular and may be illustrated by an example. Suppose f is a function whose argument is of type α and whose results is of β (so that the type of f might be written α ⇒ β), and that L is a list whose elements are all of type α (so that the type of L is α list). We can imagine a function, say Map, which applies f in turn to each member of L and makes a list of the results. Thus Map[f,L] will produce a β list. We would like Map to work on all types of list provided f was a suitable function, so that Map would have to be polymorphic. However its polymorphism is of a particularly simple parametric type which could be written

The ML language in 1975 implemented this kind of polymorphism at the level of the type system. In ML-like languages, a function’s type can contain type variables, such as the id function below:

1let id (x:'a) = x

The type of the id function is 'a -> 'a, where 'a is a type variable that can match any type, so we get

1id 1
2id "ssdfs"
3id 1.23

All are legal expressions. The type system of ML-like languages can be seen as a system that restricts and extends System F. System F can be seen as an extension of λ expressions. In System F, each bound variable of a λ expression must be given a type, and this type is introduced by $Λ$ (uppercase λ).

Specifically, the most basic λ expression $λx.x$ in System F should be written as:

And the type of this expression is

This large $Λ$ introduces a type variable that needs to be explicitly applied when used (just like the apply for small $λ$). In System F, similar to λ expressions, there is nothing other than $λ$, $Λ$ and $∀$. If you temporarily add an integer type (for example, $1: \text{Int}$), then you can give such an evaluation instance:

Due to the existence of the Hindley-Milner type inference algorithm, there is no need to manually give such $\text{Int}$ in ML-like languages, and the type of the function will also be automatically inferred to the form with a universal quantifier. Although in order to make inferences, some legal expressions in System F cannot be constructed in ML, but it is very beneficial to understand the type rules of System F for the following discussion.

The type rules of System F are divided into four rules:

1. $${\frac{Γ , (x:t_1) ⊢ y:t_2}{Γ ⊢ (λ(x:t_1).y):t_1 → t_2}}_{}$$
2. $$\frac{Γ , A:\bold{type} ⊢ x:t_1 }{ Γ ⊢ (Λ A.x): ∀ A. t_1}$$
3. $$\frac{Γ ⊢ x:(t_1 → t_2), y:t_1}{Γ ⊢ (x\ y): t_2}$$
4. $$\frac{Γ ⊢ x:(∀A.t_1)\ \ \ \ (B:\bold{type})}{ Γ ⊢ (x\ B):[B/A]t_1}$$

From Rule 2, we can see that $A$ here is an arbitrary type, and the condition for introducing this $Λ$ is that no matter what type $A$ is, it can be inferred that $x$ is of type $t₁$. In this way, in Rule 4, $B$ is also an arbitrary type. It can be obtained without proof:

Proposition 1. If $(ΛA.x)$ is a closed term in System F, then for any type $t$, $((ΛA.x)\ t)$ is a closed term in System F.

Proposition 1 is a proposition that any system claiming to have implemented parametric polymorphism must satisfy. In ML-like languages, it is manifested as, a function f of type 'a -> b (here b is not quoted, representing any possible type, such as 'a, so it is 'a -> 'a), for any legal ML expression x of type t, the type of f x is [t/'a]b.

For example, the previous id function, the type of id 10 is [int/'a]'a, that is, int.

In fact, parametric polymorphism satisfies a stronger condition–parametricity, which is quite complicated, so its meaning is not explained here.

❖Does C++ template satisfy Proposition 1?

The answer is obviously: No. This is also a reason why C++ templates are not parametric polymorphism.

For example, the id function can be written as:

1template <class T>
2T id(T x) {
3    return 10;
4}

If you haven’t written it before, you may be surprised to find that this is not an error! In fact, no matter how you write it, it won’t be an error:

1template <class T>
2int id(T x) {
3    return x;
4}

The real error occurs when using the id function:

1auto x = id("sdfsdf");
2
3------------------------
4.\test.cpp:5:10: error: cannot initialize return object of type 'const char *'
5      with an rvalue of type 'int'
6  return 10;
7         ^~
8.\test.cpp:9:14: note: in instantiation of function template specialization       
9      'id<const char *>' requested here
10    auto y = id("s");
11             ^
121 error generated.

This tells a ruthless truth: The C++ compiler does not perform type checking on template functions, but only performs type checking when specializing. This makes Proposition 1 impossible, because we have no guarantee that when T is a type and x is of type T, the type of the id function body (that is, return x) can be inferred to be T.

On the contrary, ocaml will ignore generic parameters:

1# let id (x: 'a) : int = x ;;
2val id : int -> int = <fun>

1# let id (x: 'a) : 'a = 10 ;;
2val id : int -> int = <fun>

Haskell will throw an error:

1Prelude> :{
2Prelude| id :: a -> a
3Prelude| id x = 10
4Prelude| :}
5
6<interactive>:6:8: error:
7    • No instance for (Num a) arising from the literal ‘10’
8      Possible fix:
9        add (Num a) to the context of
10          the type signature for:
11            id :: forall a. a -> a
12    • In the expression: 10
13      In an equation for ‘id’: id x = 10

1Prelude> :{
2Prelude| id :: a -> Int
3Prelude| id x = x
4Prelude| :}
5
6<interactive>:12:8: error:
7    • Couldn't match expected type ‘Int’ with actual type ‘a’
8      ‘a’ is a rigid type variable bound by
9        the type signature for:
10          id :: forall a. a -> Int
11        at <interactive>:11:1-14
12    • In the expression: x
13      In an equation for ‘id’: id x = x
14    • Relevant bindings include
15        x :: a (bound at <interactive>:12:4)
16        id :: a -> Int (bound at <interactive>:12:1)

As you can see, C++ is not parameter polymorphic, its template system and the generic system in ML-like languages are not on the same level.

❖Does the type class affect the problem?

Some people might say, doesn’t Haskell’s type class also have the phenomenon of only reporting errors when used? For example

1max :: Ord p => p -> p -> p
2max x y = if y > x then y else x
3
4data X = I | J
5
6max I J -- 这里报错
7-- error:
8--    • No instance for (Ord X) arising from a use of ‘max’
9--    • In the expression: max I J
10--      In an equation for ‘it’: it = max I J

This error, simply put, is that the custom type X does not implement the Ord type class, and the type signature of max requires the Ord type class, so it throws an error. This is still very different from C++ templates. The fundamental difference is that when type checking max I J, only max :: Ord p => p -> p -> p this information is enough, there is no need to know what the function body of max is, let alone specialize this function, this is still a deduction in the type system.

❖True or false generics? Better performance?

Although I don’t particularly like the Java language, the generic system of the Java language (in general cases) satisfies Proposition 1., it is true parameter polymorphism. This is because the predecessor of Java generics–Generic Java (GJ) was designed by real programming language experts such as Philip Wadler.

Some people say that Java generics use type erasure, which is fake generics, which is obviously influenced by the design of c++ templates. In fact, it is clear that the parameter type corresponding to parameter polymorphism is more qualified to call itself generic. c++ is an example of fake generics.

The design of c++ templates makes the module system a difficult problem. By 2021, 99.9% of c++ programs are still using ancient header files–this complete garbage–to simulate the module system.

As for performance, the so-called specialization has two stronger concepts in programming languages that can replace it.

• Partial Evaluation
• Inlining

Specialization can be seen as an example of partial evaluation. F# can be decompiled back to C# through bytecode, in sharplab, you can find

1let select x y = x
2
3let select2 (x:int) (y:int) = select x y

Such an example will yield:

1using System.Reflection;
2using Microsoft.FSharp.Core;
3
4[assembly: FSharpInterfaceDataVersion(2, 0, 0)]
5[assembly: AssemblyVersion("0.0.0.0")]
6[CompilationMapping(SourceConstructFlags.Module)]
7public static class @_
8{
9    [CompilationArgumentCounts(new int[] {
10        1,
11        1
12    })]
13    public static a select<a, b>(a x, b y)
14    {
15        return x;
16    }
17
18    [CompilationArgumentCounts(new int[] {
19        1,
20        1
21    })]
22    public static int select2(int x, int y)
23    {
24        return x;
25    }
26}
27namespace <StartupCode$_>
28{
29    internal static class $_
30    {
31    }
32}

Isn’t select2 a specialization of select? From this point of view, it’s hard to say whether C++ templates are better performing.

❖Concept: Can it solve the problem?

Whether it is parametric polymorphism seems to be an academic question. Non-parametric polymorphism mainly leads to potential errors when using a parametric type (i.e., a type containing ∀). If parametricity does not hold, some theorems (such as map f . map g = map (f . g)) also do not hold.

As mentioned before, Haskell also has problems. Other ML family languages, if not counting extensions like F#’s object system, basically have no problems, but they need to pass more parameters or explicitly use the module system. The type of F#’s List.sortWith is (('a -> 'a -> int) -> 'a list -> 'a list), it won’t go wrong for any 'a, but it needs to explicitly pass a comparer.

So, non-parametric polymorphism may not be a big problem.

But when it comes to C++, non-parametric polymorphism does bring a serious problem, that is, the error messages given by the template system are often baffling.

For example, a program like this:

1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5class A {};
6
7int main() {
8    std::vector<A> v;
9    std::sort(v.begin(), v.end());
10}

Will produce 200 lines, 19kb of errors:

1In file included from .\test.cpp:3:
2C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\VC\Tools\MSVC\14.28.29910\include\algorithm:7361:32: error: no matching function for call to object of type 'std::less<>'
3            if (_DEBUG_LT_PRED(_Pred, _Val, *_First)) { // found new earliest element, move to front
4...

To solve this problem, C++20 introduced the concept, which draws on the design of type classes and Java generics, allowing us to write programs similar to the previous Haskell max:

1#include <iostream>
2#include <algorithm>
3#include <concepts>
4
5template <class T> requires std::equality_comparable<T>
6bool max(T x, T y) {
7    if (x > y) {
8        return x;
9    } else {
10        return y;
11    }
12}

If you write at this time:

1class A{};
2
3int main() {
4    max(A(), A());
5}

The compiler will report an error:

1source>: In function 'int main()':
2<source>:17:8: error: no matching function for call to 'max(A, A)'
3   17 |     max(A(), A());
4      |     ~~~^~~~~~~~~~
5<source>:6:6: note: candidate: 'template<class T>  requires  equality_comparable<T> bool max(T, T)'
6    6 | bool max(T x, T y) {
7      |      ^~~
8<source>:6:6: note:   template argument deduction/substitution failed:
9<source>:6:6: note: constraints not satisfied
10In file included from /opt/compiler-explorer/gcc-11.2.0/include/C++/11.2.0/compare:39,
11                 from /opt/compiler-explorer/gcc-11.2.0/include/C++/11.2.0/bits/stl_pair.h:65,
12                 from /opt/compiler-explorer/gcc-11.2.0/include/C++/11.2.0/bits/stl_algobase.h:64,
13                 from /opt/compiler-explorer/gcc-11.2.0/include/C++/11.2.0/bits/char_traits.h:39,
14                 from /opt/compiler-explorer/gcc-11.2.0/include/C++/11.2.0/ios:40,
15                 from /opt/compiler-explorer/gcc-11.2.0/include/C++/11.2.0/ostream:38,
16                 from /opt/compiler-explorer/gcc-11.2.0/include/C++/11.2.0/iostream:39,
17                 from <source>:1:
18/opt/compiler-explorer/gcc-11.2.0/include/C++/11.2.0/concepts: In substitution of 'template<class T>  requires  equality_comparable<T> bool max(T, T) [with T = A]':
19<source>:17:8:   required from here
20/opt/compiler-explorer/gcc-11.2.0/include/C++/11.2.0/concepts:280:15:   required for the satisfaction of '__weakly_eq_cmp_with<_Tp, _Tp>' [with _Tp = A]
21/opt/compiler-explorer/gcc-11.2.0/include/C++/11.2.0/concepts:290:13:   required for the satisfaction of 'equality_comparable<T>' [with T = A]
22/opt/compiler-explorer/gcc-11.2.0/include/C++/11.2.0/concepts:281:4:   in requirements with 'std::remove_reference_t<_Tp>& __t', 'std::remove_reference_t<_Up>& __u' [with _Up = A; _Tp = A]
23/opt/compiler-explorer/gcc-11.2.0/include/C++/11.2.0/concepts:282:17: note: the required expression '(__t == __u)' is invalid
24  282 |           { __t == __u } -> __boolean_testable;
25      |             ~~~~^~~~~~
26/opt/compiler-explorer/gcc-11.2.0/include/C++/11.2.0/concepts:283:17: note: the required expression '(__t != __u)' is invalid
27  283 |           { __t != __u } -> __boolean_testable;
28      |             ~~~~^~~~~~
29/opt/compiler-explorer/gcc-11.2.0/include/C++/11.2.0/concepts:284:17: note: the required expression '(__u == __t)' is invalid
30  284 |           { __u == __t } -> __boolean_testable;
31      |             ~~~~^~~~~~
32/opt/compiler-explorer/gcc-11.2.0/include/C++/11.2.0/concepts:285:17: note: the required expression '(__u != __t)' is invalid
33  285 |           { __u != __t } -> __boolean_testable;
34      |             ~~~~^~~~~~
35cc1plus: note: set '-fconcepts-diagnostics-depth=' to at least 2 for more detail
36Compiler returned: 1

This will directly indicate that A does not satisfy the std::equality_comparable constraint. Even so, the noise is still very much. More importantly, for library functions–functions we don’t want to study the source code, the effect is still general:

1n file included from /opt/compiler-explorer/gcc-11.2.0/include/c++/11.2.0/bits/stl_algobase.h:71,
2                 from /opt/compiler-explorer/gcc-11.2.0/include/c++/11.2.0/bits/char_traits.h:39,
3                 from /opt/compiler-explorer/gcc-11.2.0/include/c++/11.2.0/ios:40,
4                 from /opt/compiler-explorer/gcc-11.2.0/include/c++/11.2.0/ostream:38,
5                 from /opt/compiler-explorer/gcc-11.2.0/include/c++/11.2.0/iostream:39,
6                 from <source>:1:
7/opt/compiler-explorer/gcc-11.2.0/include/c++/11.2.0/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_less_iter::operator()(_Iterator1, _Iterator2) const [with _Iterator1 = __gnu_cxx::__normal_iterator<A*, std::vector<A> >; _Iterator2 = __gnu_cxx::__normal_iterator<A*, std::vector<A> >]':
8/opt/compiler-explorer/gcc-11.2.0/include/c++/11.2.0/bits/stl_algo.h:1826:14:   required from 'constexpr void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<A*, std::vector<A> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
9/opt/compiler-explorer/gcc-11.2.0/include/c++/11.2.0/bits/stl_algo.h:1866:25:   required from 'constexpr void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<A*, std::vector<A> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
10/opt/compiler-explorer/gcc-11.2.0/include/c++/11.2.0/bits/stl_algo.h:1957:31:   required from 'constexpr void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<A*, std::vector<A> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
11/opt/compiler-explorer/gcc-11.2.0/include/c++/11.2.0/bits/stl_algo.h:4842:18:   required from 'constexpr void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<A*, std::vector<A> >]'
12<source>:10:14:   required from here
13/opt/compiler-explorer/gcc-11.2.0/include/c++/11.2.0/bits/predefined_ops.h:45:23: error: no match for 'operator<' (operand types are 'A' and 'A')
14   45 |       { return *__it1 < *__it2; }
15      |                ~~~~~~~^~~~~~~~
16
17剩下还有80多行

To be fair, the design of C++ templates also brings some benefits. Although theoretically, the compiler has some general methods to get the performance improvement brought by specialization, various practical difficulties¹ make C++ templates indeed have some advantages in performance (here refers to runtime performance, in terms of compilation performance, C++ templates are extremely bad).

Compared with language design itself, what I dislike more is the ignorance of some C++ programmers and the arrogant attitude brought by this ignorance. Some people often call Java’s generics fake generics, thinking that only generics implementations like C++ templates are real generics. I sincerely suggest that these people should read this article carefully.