C++ 模板与参数多态的根本区别

14/09/2021

C++ 模板与参数多态
到底什么是参数多态
C++模板满足命题1.吗？
类型类影响问题吗？
真假泛型？性能更好？
Concept: 能解决问题吗？

❖C++ 模板与参数多态

模板(template)是一种 C++ 语言特性，类似于：

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

这里的 T 可以是任意类型。很多人都注意到了这与参数多态(parametric polymorphism)的相似性，更有甚者直接把模板机制看作是一种参数多态。比如这份ppt和这个网页。

然而这篇博客中，我将会说明，无论 C++ 模板到底是不是一个好的语言特性，它都和参数多态有根本性的区别。

❖到底什么是参数多态

参数多态的历史要追溯一份讲义(Fundamental Concepts in Programming Languages)，讲义虽然主要描述的是 CPL 语言，但是实际上这一段应该描述的是 LISP 的 MAP 函数：

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

(α → β , α\ \text{list}) → β \ \text{list}

1975 年的 ML 语言在类型系统的层面上实现了这种多态。在 ML 类语言中，一个函数的类型中可以含有类型变量，例如如下的id函数：

1let id (x:'a) = x

id函数的类型是'a -> 'a，其中'a就是一个类型变量，它可以与任意类型相匹配，所以得到

1id 1
2id "ssdfs"
3id 1.23

都是合法的表达式。ML 类语言的类型系统可以看作是对 System F 进行限制和扩展后的系统。System F 可以看作对 λ 表达式的扩展，在 System F 中，λ 表达式的每个绑定变量都必须给定一个类型，而这个类型则是通过 $Λ$ （大写的λ）引入的。

具体来说，最基本的λ表达式 $λx.x$ 在 System F 中应该写作：

Λt.λ (x:t).x

而这个表达式的类型是

∀t.t → t

这个大 $Λ$ 引入的类型变量在使用时需要得到显式 apply（就像对小 $λ$ 的 apply 一样）。在 System F 中，类似于 λ 表达式，没有除了 $λ$ 、 $Λ$ 和 $∀$ 以外的东西，如果给它暂时加入整数类型（例如 $1: \text{Int}$ ），那么就可以给出这样的求值实例:

\begin{aligned} ((Λ t. λ (x:t). x) \text{Int})1 & \Rightarrow \\ (λ (x:\text{Int}). x) 1 & \Rightarrow 1 \end{aligned}

由于Hindey-Milner类型推理算法的存在，ML类语言中无须手动给出这样的 $\text{Int}$ ，函数的类型也会自动推导为带有全称量词的形式。虽然为了进行推理，某些在 System F 中合法的式子不能在 ML 中被构造，但搞清楚 System F 的类型规则对接下来的讨论是大有裨益的。

System F的类型规则分为四个规则：

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

从规则2.中可以看到，这里的 $A$ 是任意的类型，引入这个 $Λ$ 的条件是无论 $A$ 到底是什么类型，它都可以推出 $x$ 是 $t₁$ 类型。这样一来，在规则4.中， $B$ 也是一个任意的类型。可以不加证明地得到：

命题1. 如果 $(ΛA.x)$ 是一个系统F中的封闭项，那么对于任意的类型 $t$ ， $((ΛA.x)\ t)$ 是一个系统F中的封闭项。

命题1.是任何声称自己实现了参数多态的系统所必须满足的命题。在ML类语言中，它表现为，一个类型为'a -> b（这里的b没有加引号，表示任何可能的类型，比如'a，这样一来就是'a -> 'a）的函数f，对于任何类型为t的合法ML表达式x，f x的类型都是[t/'a]b.

例如之前的id函数，id 10的类型就是[int/'a]'a，即int.

事实上，参数多态满足更强的条件–parametricity，鉴于比较复杂，这里暂不解释其含义。

❖C++模板满足命题1.吗？

答案是很显然的：不满足。这也就是为什么C++模板不是参数多态的一个原因。

例如说，id函数可以写成：

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

如果之前没有写过，你可能会惊讶地发现，这竟然是不会报错的！事实上，无论怎么写，它都不会报错：

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

它真正报错的位置，是在对id函数进行使用的时候：

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.

这诉说了一个无情的真相：C++ 编译器不会对模板函数进行类型检查，只会在特化的时候进行类型检查。而这使得命题1.无法成立，因为我们根本没有保证在T是一个类型，x是T类型的情况下，可以推出id函数体（也就是return x）的类型是T.

相反，ocaml 会无视泛型参数：

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 会报错：

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)

可见，C++ 并不是参数多态，它的模板系统和 ML 类语言中的泛型系统完全不在一个层次上。

❖类型类影响问题吗？

有人可能会说了，Haskell 的类型类不是也会出现“在使用的时候才报错”这一现象吗？比如说

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

这个错误简单来说，就是自定义类型X没有实现Ord类型类，而max的类型签名中需要类型类Ord，所以报错。这和 C++ 模板仍然很不一样。根本性的区别是，在对max I J进行类型检查的时候，只需要max :: Ord p => p -> p -> p这一个信息就够了，不需要知道max的函数体是什么，更不需要“特化”这个函数，这仍是在类型系统中的推导。

❖真假泛型？性能更好？

虽然我并不是很喜欢 Java 语言，但是 Java 语言的泛型系统（在一般情况下）满足命题1.，它是真正的参数多态。这是因为 Java 泛型的前身–Generic Java（GJ）是由 Philip Wadler 等真正的编程语言专家设计的。

有人说 Java 泛型采用了类型擦除，是“假泛型”，这显然是被c++模板的设计影响了。事实上显然参数多态对应的参数类型更有资格把自己叫做“泛型”。c++才是“假泛型”的例子。

c++模板的设计使得 module 系统变成了一个困难的问题，到了 2021 年，99.9% 的c++程序仍然在使用上古时代的头文件–这一彻头彻尾的垃圾–模拟 module 系统。

至于性能，所谓的“特化”在编程语言中有两个更强的概念可以替代。

部分求值(partial evaluation)
内联(inlining)

特化可以看作是一个部分求值的例子。F# 则可以通过字节码反编译回 C#，在sharplab中，可以发现

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

这样的例子会得到：

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}

select2难道不是对select的“特化”吗？由此看来，C++ 模板的“性能更好”也是很难说清楚的问题。

❖Concept: 能解决问题吗？

是否是参数多态，似乎只是一个学术问题。不是参数多态，主要导致的是使用一个参数化类型（parametric type，也就是含有∀的类型）时的潜在错误，pararmetricity 不成立，某些定理（比如map f . map g = map (f . g)）也不成立。

之前已经提到了，Haskell 也有会出错的问题。其他 ML 家族的语言，如果不算上类似 F# 的 object 系统的扩展，则基本没有出错的问题，但是需要传递更多参数或显式使用模块（module）系统。F# 的 List.sortWith 的类型就是 (('a -> 'a -> int) -> 'a list -> 'a list)，对于任何 'a 都不会出错，但是需要显式地传递一个 comparer.

所以，不是参数多态，也许也不是特别大的问题。

但说到 C++，不是参数多态确实带来了一个相当严重的问题，那就是模板系统给出的报错信息常常令人无从下手。

例如这样的程序：

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}

会产生 200 行，19kb 的报错：

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...

为了解决这个问题，C++20 引入了 concept，concept 借鉴了类型类和 Java 泛型的设计，可以使得我们能写出类似于之前 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}

如果这时写出：

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

编译器会报错：

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

这里会直接表明A不满足std::equality_comparable的约束。虽然如此，噪音还是非常的多。更重要的是，对于库函数–这种我们不想研究源码的函数，效果还是一般：

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多行

公允地说，C++ 的模板设计也带来了一些好处。虽然从理论上来说，编译器有一些通用的方法能够得到“特化”所带来的性能提升，但实践上的各种困难¹使得 C++ 模板在性能上确实有一些优势（这里指的是运行时性能，在编译性能上，C++ 模板是极其糟糕的）。

相比语言设计本身，我更不喜欢的是某些 C++ 程序员的无知，以及这种无知带来的傲慢态度。某些人动辄把 Java 的泛型叫做“假泛型”，认为只有像 C++ 模板一样的泛型实现才是“真泛型”。我真诚地建议，这些人应该认真阅读一下本文。