引言
这是我上周在 2019 年 Gophercon 大会上演讲的博客文章版本。
本文讨论的是在 Go 语言中添加泛型意味着什么，以及我认为我们应该这样做的原因。我还会简要介绍一下为 Go 语言添加泛型的一种可能设计的最新情况。
Go 于 2009 年 11 月 10 日发布。不到 24 小时后，我们就看到了关于泛型的第一条评论。（该评论还提到了异常，我们在 2010 年初以 panic 和 recover 的形式将其加入到这门语言中。）
在三年的 Go 语言调查中，缺乏泛型一直被列为该语言需要解决的三大问题之一。
为什么需要泛型？
但是，添加泛型意味着什么，我们为什么要这么做呢？
套用 Jazayeri 等人的话来说：泛型编程允许以泛型形式表示函数和数据结构，同时将类型提取出来。
那是什么意思？
举个简单的例子，假设我们想要反转一个切片中的元素。这并不是很多程序都需要做的事情，但也并非特别罕见。
假设它是一个整数切片。
func ReverseInts(s []int) {
first := 0
last := len(s)
for first < last {
s[first], s[last] = s[last], s[first]
first++
last--
}
}这相当简单，但即便是这样一个简单的函数，你也会想要编写几个测试用例。事实上，我在编写测试用例时就发现了一个漏洞。我相信很多读者已经发现了这个问题。
func ReverseInts(s []int) {
first := 0
last := len(s) - 1
for first < last {
s[first], s[last] = s[last], s[first]
first++
last--
}
}设置变量 last 时，我们需要减去 1。
现在让我们反转字符串的一个切片。
func ReverseStrings(s []string) {
first := 0
last := len(s) - 1
for first < last {
s[first], s[last] = s[last], s[first]
first++
last--
}
}如果你比较 ReverseInts 和 ReverseStrings，就会发现这两个函数完全相同，只是参数类型不同。我认为任何读者对此都不会感到惊讶。
一些刚接触 Go 语言的人会感到惊讶的是，没有办法编写一个简单的 Reverse 函数来处理任何类型的切片。
大多数其他语言确实允许你编写那种函数。
在像 Python 或 JavaScript 这样的动态类型语言中，你可以直接编写函数，无需费心指定元素类型。但这在 Go 语言中行不通，因为 Go 是静态类型的，它要求你写下切片的确切类型以及切片元素的类型。
大多数其他静态类型语言，如 C++、Java、Rust 或 Swift，都支持泛型来恰好解决这类问题。
如今的 Go 泛型编程
那么人们是如何用 Go 编写这类代码的呢？
在 Go 语言中，你可以通过使用接口类型，并在想要传入的切片类型上定义方法，来编写一个适用于不同切片类型的函数。标准库中的 sort.Sort 函数就是这样工作的。
换句话说，Go 语言中的接口类型是泛型编程的一种形式。它们让我们能够捕捉不同类型的共同特征，并将这些特征表示为方法。然后，我们可以编写使用这些接口类型的函数，而这些函数将适用于任何实现了这些方法的类型。
但这种方法并未达到我们的期望。使用接口时，你必须自己编写方法。仅仅为了反转一个切片，就要定义一个带有几个方法的命名类型，这很不方便。而且你为每种切片类型编写的方法完全相同，所以从某种意义上说，我们只是移动并压缩了重复代码，并没有消除它。尽管接口是泛型的一种形式，但它们并没有提供我们期望从泛型中获得的所有功能。
另一种使用接口实现泛型的方式可能无需自行编写方法，即由语言为某些类型定义方法。目前语言尚不支持这一功能，但举例来说，语言可以规定每个切片类型都有一个返回元素的 Index 方法。然而，在实际使用中，该方法必须返回空接口类型，这样我们就会失去静态类型带来的所有优势。更微妙的是，将无法定义一个接收两个元素类型相同的不同切片的泛型函数，也无法定义一个接收某种元素类型的映射并返回相同元素类型的切片的泛型函数。Go 是一种静态类型语言，因为这使得编写大型程序更为容易；我们不希望为了获得泛型的优势而失去静态类型的好处。
另一种方法是使用反射包编写一个通用的 Reverse 函数，但这种方法编写起来非常麻烦，运行速度也很慢，因此很少有人会这样做。这种方法还需要显式的类型断言，并且没有静态类型检查。
或者，你可以编写一个代码生成器，它接收一个类型并为该类型的切片生成一个 Reverse 函数。市面上有几个代码生成器就是这么做的。但这会给每个需要 Reverse 的包增加额外的步骤，这会使构建变得复杂，因为所有不同的副本都必须编译，而且修复主源代码中的错误需要重新生成所有实例，其中一些实例可能完全位于不同的项目中。
所有这些方法都足够麻烦，以至于我认为大多数在 Go 语言中需要反转切片的人，都会针对他们所需的特定切片类型编写函数。然后他们需要为该函数编写测试用例，以确保没有犯我最初犯过的那种简单错误。而且他们需要定期运行这些测试。
然而，无论我们怎么做，这都意味着大量额外的工作，而这么做只是为了实现一个除了元素类型外看起来完全相同的功能。这并不是说做不到。显然，这是可以做到的，而且 Go 程序员们也正在这么做。只是，理应存在一种更好的方法。
对于像 Go 这样的静态类型语言来说，更好的方法是泛型。我之前提到过，泛型编程能够以通用形式表示函数和数据结构，同时将类型抽象出来。这正是我们这里所需要的。
泛型能为 Go 带来什么
在 Go 语言中，我们对泛型的首要且最重要的需求是，能够编写像 Reverse 这样的函数，而不必关心切片的元素类型。我们希望将元素类型抽象出来。这样，我们就可以只编写一次函数，只进行一次测试，将它们放入一个可通过 go-get 获取的包中，然后在需要的时候调用它们。
更妙的是，由于这是一个开源世界，其他人可以编写一次 Reverse，我们就可以使用他们的实现。
这里我需要说明的是，“泛型”可能有很多不同的含义。在本文中，我所说的“泛型”指的就是我刚刚描述的内容。具体来说，我指的不是 C++语言中的模板，后者所支持的功能比我在这里所写的要多得多。
我详细研究了 Reverse，但还有许多其他函数我们可以通用地编写，例如：
- 在切片中查找最小/最大元素
- 求切片的平均值/标准差
- 计算映射的并集/交集
- 在节点/边图中寻找最短路径
- 对切片/映射应用转换函数，返回新的切片/映射
这些示例在大多数其他语言中都能找到。事实上，我是通过浏览 C++标准模板库才写出这个列表的。
Go 对并发有强大的支持，也有一些专门针对它的示例
- 带超时的通道读取
- 将两个通道合并为一个通道
- 并行调用函数列表，返回结果切片
- 使用上下文调用一系列函数，返回第一个完成的函数的结果，并取消和清理额外的协程。
我见过这些函数以不同类型被多次编写出来。用 Go 语言编写它们并不难。但如果能复用一个高效且经过调试、适用于任何值类型的实现，那就再好不过了。
需要明确的是，这些仅仅是示例。还有更多通用功能可以使用泛型更轻松、更安全地编写出来。
而且，正如我之前所写，这不仅仅是函数的问题，还涉及数据结构。
Go 语言内置了两种通用的泛型数据结构：切片和映射。切片和映射可以存储任何数据类型的值，并对存储和检索的值进行静态类型检查。这些值以其自身的形式存储，而非接口类型。也就是说，当我有一个[]int 时，该切片直接存储整数，而不是转换为接口类型的整数。
切片和映射是最有用的泛型数据结构，但它们并非唯一的。以下是其他一些例子。
- 集合
- 自平衡树，具有高效的插入操作和按排序顺序遍历的功能
- 多重映射，具有一个键的多个实例
- 并发哈希映射，支持并行插入和查找，且无需单一锁
如果我们能编写泛型类型，就能定义诸如此类的新数据结构，它们具有与切片和映射相同的类型检查优势：编译器可以对它们所存储的值的类型进行静态类型检查，而且这些值可以按其自身类型存储，而不是作为接口类型存储。
也应该可以采用前面提到的那些算法，并将它们应用于通用数据结构。
这些示例都应该和 Reverse 一样：通用函数和数据结构在一个包中编写一次，然后在需要时重复使用。它们的工作方式应该类似于切片和映射，即不存储空接口类型的值，而是存储特定类型，并且这些类型应该在编译时进行检查。
这就是 Go 语言能从泛型中获得的好处。泛型能为我们提供强大的构建模块，让我们可以共享代码，更轻松地编写程序。
希望我已经解释了为什么这件事值得研究。
收益与成本
但泛型并非来自《大块冰糖山》 —— 那片阳光每日照耀着柠檬水泉的土地。每种语言的变更都需要付出代价。毫无疑问，在 Go 语言中添加泛型会使这门语言变得更加复杂。与对该语言的任何变更一样，我们需要考虑如何最大化收益并最小化成本。
在 Go 语言中，我们致力于通过独立、正交的语言特性来降低复杂性，这些特性可以自由组合。我们通过让各个特性保持简单来降低复杂性，并通过允许它们自由组合来最大化这些特性的价值。对于泛型，我们也希望采取同样的做法。
为了让这一点更具体，我将列出一些我们应该遵循的指导原则。
尽量减少新概念
我们应该尽可能少地向这门语言中添加新概念。这意味着要将新语法、新关键字及其他新名称的数量降至最低。
复杂度由泛型代码的编写者承担，而非用户
尽可能地，复杂性应该由编写泛型包的程序员来承担。我们不希望包的用户需要担心泛型问题。这意味着应该能够以自然的方式调用泛型函数，也意味着使用泛型包时出现的任何错误都应该以易于理解和修复的方式进行报告。此外，调试对泛型代码的调用也应该很容易。
作者和用户可以独立工作
同样地，我们应当让泛型代码的编写者和使用者能够轻松分离关注点，以便他们可以独立开发各自的代码。他们不必担心对方在做什么，就像不同包中普通函数的编写者和调用者不必担心彼此一样。这听起来显而易见，但并非其他所有编程语言中的泛型都是如此。
构建时间短，执行速度快
当然，我们希望尽可能保留 Go 语言如今所带来的短暂构建时间和快速执行速度。泛型往往会在快速构建和快速执行之间引入一种权衡。我们希望尽可能两者兼得。
保持 Go 语言的清晰性和简洁性
最重要的是，Go 语言如今是一门简洁的语言。Go 程序通常清晰易懂。在我们长期探索这一领域的过程中，很大一部分工作是尝试理解如何在添加泛型的同时保持这种清晰性和简洁性。我们需要找到能够很好地融入现有语言的机制，而不是将其变成一种完全不同的语言。
这些指导原则应适用于 Go 语言中的任何泛型实现。这是我今天想给大家留下的最重要的信息：泛型能为这门语言带来显著益处，但只有在 Go 语言仍保持其本色的情况下，引入泛型才是值得的。
草案设计
幸运的是，我认为这是可以做到的。在本文的结尾部分，我将不再讨论我们为什么需要泛型以及对泛型的要求，而是简要探讨一种我们认为可以将泛型添加到这门语言中的设计方案。
2022 年 1 月补充说明：本博客文章撰写于 2019 年，并未描述最终采用的泛型版本。有关更新信息，请参阅语言规范和泛型设计文档中对类型参数的说明。
在今年的 Gophercon 上，罗伯特·格里瑟默和我发布了一份为 Go 语言添加泛型的设计草案。详情请参见该草案。我将在这里介绍一些主要内容。
以下是该设计中的通用 Reverse 函数。
func Reverse (type Element) (s []Element) {
first := 0
last := len(s) - 1
for first < last {
s[first], s[last] = s[last], s[first]
first++
last--
}
}你会注意到函数体完全相同，只有签名发生了变化。
切片的元素类型已被提取出来。它现在被命名为 Element，并成为了我们所说的类型参数。它不再是切片参数类型的一部分，而是一个单独的、额外的类型参数。
要调用带有类型参数的函数，一般情况下需要传递一个类型实参，它与其他实参类似，只是它是一个类型。
func ReverseAndPrint(s []int) {
Reverse(int)(s)
fmt.Println(s)
}这就是本示例中 Reverse 后面看到的(int)。
幸运的是，在大多数情况下，包括这种情况，编译器可以从常规参数的类型中推断出类型参数，因此你根本不需要提及类型参数。
调用泛型函数看起来就和调用其他任何函数一样。
func ReverseAndPrint(s []int) {
Reverse(s)
fmt.Println(s)
}换句话说，尽管通用的 Reverse 函数比 ReverseInts 和 ReverseStrings 稍微复杂一些，但这种复杂性由函数的编写者承担，而非调用者。
契约
由于 Go 是一种静态类型语言，我们必须讨论类型参数的类型。这种元类型告诉编译器，在调用泛型函数时允许哪些类型的实参，以及泛型函数可以对类型参数的值执行哪些操作。
Reverse 函数可以处理任何类型的切片。它对 Element 类型的值所做的唯一操作就是赋值，这在 Go 语言中对任何类型都适用。对于这种通用函数（这是一种非常常见的情况），我们不需要对类型参数做任何特殊说明。
让我们快速看一下另一个函数。
func IndexByte (type T Sequence) (s T, b byte) int {
for i := 0; i < len(s); i++ {
if s[i] == b {
return i
}
}
return -1
}目前，标准库中的 bytes 包和 strings 包都有一个 IndexByte 函数。该函数返回 b 在序列 s 中的索引，其中 s 可以是 string 或[]byte。我们可以使用这个单一的泛型函数来替代 bytes 包和 strings 包中的这两个函数。实际上我们可能不会费心去做这件事，但这是一个有用的简单示例。
这里我们需要知道，类型参数 T 的作用类似于 string 或[]byte。我们可以对它调用 len 函数，可以对它进行索引，还可以将索引操作的结果与一个字节值进行比较。
为了让其能够编译，类型参数
这就是本示例中 Sequence 契约的定义方式。
contract Sequence(T) {
T string, []byte
}这相当简单，因为这是一个简单的示例：类型参数 T 可以是 string 或[]byte。这里的 contract 可能是一个新的关键字，或者是在包作用域中可识别的特殊标识符；详情请参见设计草案。
任何记得我们在2018 年 Gophercon 大会上展示的设计的人都会发现，这种编写契约的方式要简单得多。我们从早期的设计中收到了很多反馈，说契约太复杂了，我们也努力考虑了这些反馈。新的契约在编写、阅读和理解方面都简单得多。
它们允许你指定类型参数的基础类型，和/或列出类型参数的方法。它们还允许你描述不同类型参数之间的关系。
带方法的契约
这是另一个简单的示例，展示了一个使用 Stringmethod 的函数，该函数返回一个[]string，其中包含 s 中所有元素的字符串表示形式。
func ToStrings (type E Stringer) (s []E) []string {
r := make([]string, len(s))
for i, v := range s {
r[i] = v.String()
}
return r
}这非常简单：遍历切片，对每个元素调用 String 方法，然后返回结果字符串的切片。
此函数要求元素类型实现 String 方法。Stringer 契约可确保这一点。
contract Stringer(T) {
T String() string
}这份契约简单规定，T 必须实现 String 方法。
你可能会注意到，这个契约看起来像 fmt.Stringer 接口，因此值得指出的是，ToStrings 函数的参数并非 fmt.Stringer 的切片，而是某种元素类型的切片，其中该元素类型实现了 fmt.Stringer。该元素类型的切片与 fmt.Stringer 的切片在内存表示上通常是不同的，并且 Go 不支持它们之间的直接转换。因此，即便 fmt.Stringer 已经存在，编写这段代码也是有价值的。
具有多种类型的合约
这是一个带有多个类型参数的契约示例。
type Graph (type Node, Edge G) struct { ... }
contract G(Node, Edge) {
Node Edges() []Edge
Edge Nodes() (from Node, to Node)
}
func New (type Node, Edge G) (nodes []Node) *Graph(Node, Edge) {
...
}
func (g *Graph(Node, Edge)) ShortestPath(from, to Node) []Edge {
...
}这里我们描述的是一个由节点和边构建的图。我们不要求该图采用特定的数据结构。相反，我们是说 Node 类型必须有一个 Edges 方法，该方法返回连接到 Node 的边的列表。而 Edge 类型必须有一个 Nodes 方法，该方法返回 Edge 所连接的两个 Nodes。
我略过了实现过程，但这里展示了一个返回 Graph 的 New 函数的签名，以及 Graph 上的 ShortestPath 方法的签名。
这里的重要启示是，契约不仅仅与单一类型有关。它可以描述两种或多种类型之间的关系。
有序类型
关于 Go 语言，一个出人意料的常见抱怨是它没有 Min 函数。就此而言，也没有 Max 函数。这是因为一个有用的 Min 函数应该适用于任何有序类型，这意味着它必须是泛型的。
虽然自己编写 Min 相当简单，但任何有用的泛型实现都应该允许我们将其添加到标准库中。这就是我们设计的样子。
func Min (type T Ordered) (a, b T) T {
if a < b {
return a
}
return b
}Ordered 契约规定类型 T 必须是有序类型，这意味着它支持小于、大于等运算符。
contract Ordered(T) {
T int, int8, int16, int32, int64,
uint, uint8, uint16, uint32, uint64, uintptr,
float32, float64,
string
}“Ordered”契约只是该语言定义的所有有序类型的列表。此契约接受任何列出的类型，或任何基础类型为其中一种类型的命名类型。基本上，是任何可以使用小于运算符的类型。
事实证明，简单枚举支持小于运算符的类型，要比发明一种适用于所有运算符的新符号容易得多。毕竟，在 Go 语言中，只有内置类型才支持运算符。
这种相同的方法可用于任何运算符，或者更广泛地说，可用于为任何旨在与内置类型配合使用的泛型函数编写契约。它让泛型函数的编写者能够清晰地指定该函数预期适用的类型集合。它也让泛型函数的调用者能够清楚地了解该函数是否适用于所使用的类型。
实际上，这份合约可能会被纳入标准库，因此，Min 函数（它可能也会在标准库的某个地方）实际上会是这个样子。这里我们只是引用了合约包中定义的 Ordered 合约。
func Min (type T contracts.Ordered) (a, b T) T {
if a < b {
return a
}
return b
}通用数据结构
最后，让我们来看一个简单的通用数据结构——二叉树。在这个示例中，该树有一个比较函数，因此对元素类型没有要求。
type Tree (type E) struct {
root *node(E)
compare func(E, E) int
}
type node (type E) struct {
val E
left, right *node(E)
}以下是创建新二叉树的方法。比较函数会被传递给 New 函数。
func New (type E) (cmp func(E, E) int) *Tree(E) {
return &Tree(E){compare: cmp}
}一个未导出的方法会返回一个指针，该指针要么指向存储 v 的槽位，要么指向它在树中应处的位置。
func (t *Tree(E)) find(v E) **node(E) {
pn := &t.root
for *pn != nil {
switch cmp := t.compare(v, (*pn).val); {
case cmp < 0:
pn = &(*pn).left
case cmp > 0:
pn = &(*pn).right
default:
return pn
}
}
return pn
}这里的细节其实并不重要，尤其是因为我还没有测试过这段代码。我只是想展示一下编写一个简单的通用数据结构是什么样子的。
这是用于测试树是否包含某个值的代码。
func (t *Tree(E)) Contains(v E) bool {
return *t.find(e) != nil
}这是插入新值的代码。
func (t *Tree(E)) Insert(v E) bool {
pn := t.find(v)
if *pn != nil {
return false
}
*pn = &node(E){val: v}
return true
}注意，node 类型有一个类型参数 E。这就是编写泛型数据结构的样子。如你所见，它看起来像编写普通的 Go 代码，只是到处穿插了一些类型参数。
使用这棵树非常简单。
var intTree = tree.New(func(a, b int) int { return a - b })
func InsertAndCheck(v int) {
intTree.Insert(v)
if !intTree.Contains(v) {
log.Fatalf("%d not found after insertion", v)
}
}情况本应如此。编写通用数据结构要稍难一些，因为你常常必须为支持类型明确写出类型参数，但尽可能地使用通用数据结构与使用普通的非通用数据结构并无不同。
后续步骤
我们正在进行实际的实现工作，以便能够对这一设计进行试验。能够在实践中试用该设计很重要，这是为了确保我们能够编写出我们想要的那种程序。进展没有我们希望的那么快，但一旦这些实现有了更多消息，我们会发布更多细节。
罗伯特·格里瑟默（Robert Griesemer）编写了一份初步的 CL，对 go/types 包进行了修改。这使得我们能够测试使用泛型和契约的代码是否可以进行类型检查。目前它还不完整，但对于单个包来说基本可以正常工作，我们会继续对其进行完善。
我们希望人们在使用这个以及未来的实现时，尝试编写和使用通用代码，看看会发生什么。我们希望确保人们能够编写出他们需要的代码，并且能够如预期般使用这些代码。当然，并非所有事情一开始都能顺利运行，随着我们对这个领域的探索，可能需要对一些内容进行调整。而且，需要明确的是，相比语法细节，我们对这些语义方面的反馈更感兴趣。
我要感谢所有对早期设计发表评论的人，以及所有讨论过 Go 语言中泛型可能呈现何种形态的人。我们阅读了所有的评论，非常感谢大家为此付出的努力。没有这些努力，我们就不会有今天的成果。
我们的目标是设计出一种方案，使得编写我今天讨论的这类泛型代码成为可能，同时又不会让这门语言变得过于复杂而难以使用，也不会使其失去 Go 语言原有的风格。我们希望这个设计能朝着这个目标迈进一步，并且预计会根据我们自己以及你们的经验，不断调整该设计，了解哪些部分可行，哪些不可行。如果我们真的实现了这个目标，那么我们就会有可以为 Go 语言未来版本提出的内容了。