Go 博客
为什么要泛型？
引言
本文是我在上周 Gophercon 2019 大会上演讲的博客版本。
本文旨在探讨将泛型添加到 Go 语言的意义，以及我认为我们应该这样做的原因。我还会提及关于在 Go 中添加泛型的一种可能设计方案的最新进展。
Go 于 2009 年 11 月 10 日发布。不到 24 小时后，我们看到了关于泛型的第一个评论。(该评论也提到了异常，我们在 2010 年初以 panic 和 recover 的形式将其添加到了语言中。)
在三年的 Go 语言调查中，缺乏泛型一直被列为语言中需要解决的前三大问题之一。
为什么要泛型？
但添加泛型意味着什么？我们为什么想要它？
引用 Jazayeri 等人的话来说：泛型编程使得函数和数据结构能够以泛型形式表示，并将类型参数化。
这是什么意思？
举个简单的例子，假设我们想反转一个切片中的元素。这并非许多程序都需要的操作，但也并非完全不常见。
假设这是一个 int 类型的切片。
func ReverseInts(s []int) {
first := 0
last := len(s)
for first < last {
s[first], s[last] = s[last], s[first]
first++
last--
}
}
相当简单，但即使对于这样一个简单的函数，你也会想写几个测试用例。实际上，当我写的时候，我发现了一个 bug。我相信很多读者已经发现了。
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。
现在我们来反转一个 string 类型的切片。
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 方法。但要在实践中使用该方法，它必须返回空接口类型，这样我们就会失去静态类型的所有好处。更微妙的是，将无法定义一个泛型函数，该函数接受两个具有相同元素类型的不同切片，或者接受一种元素类型的 map 并返回相同元素类型的切片。Go 是一种静态类型语言，因为这使得编写大型程序更容易；我们不希望为了获得泛型的好处而失去静态类型的好处。
另一种方法是使用 reflect 包编写一个泛型的 Reverse 函数，但这非常笨拙且运行缓慢，以至于很少有人这样做。这种方法还需要显式的类型断言，并且没有静态类型检查。
或者，你可以编写一个代码生成器，它接受一个类型并为该类型的切片生成一个 Reverse 函数。市面上有好几个这样的代码生成器。但这会给需要 Reverse 的每个包增加一个额外的步骤，使构建复杂化，因为所有不同的副本都必须编译，并且修复主源中的 bug 需要重新生成所有实例，其中一些实例可能完全位于不同的项目中。
所有这些方法都足够笨拙，以至于我认为大多数需要在 Go 中反转切片的人只是为他们需要的特定切片类型编写函数。然后他们需要为该函数编写测试用例，以确保没有犯像我最初犯的简单错误。而且他们需要定期运行这些测试。
无论我们怎么做，仅仅为了一个除了元素类型外看起来完全相同的函数，这意味着大量额外的工作。这并非说它做不到。显然它可以做到，而且 Go 程序员正在这样做。只是应该有更好的方法。
对于像 Go 这样的静态类型语言，更好的方法就是泛型。我前面写过，泛型编程使得函数和数据结构能够以泛型形式表示，并将类型参数化。这正是我们在这里想要的。
泛型能为 Go 带来什么
在 Go 中，我们期望从泛型获得的首要且最重要的事情是能够编写像 Reverse 这样的函数，而无需关心切片的元素类型。我们希望将该元素类型参数化。然后我们可以只写一次函数，只写一次测试，将其放入一个可通过 go get 获取的包中，并在需要时随时调用。
更好的是，既然这是一个开源世界，其他人可以编写一次 Reverse，而我们可以使用他们的实现。
此时我应该说明的是，“泛型”可以意味着许多不同的事物。在本文中，我所说的“泛型”就是我刚刚描述的。特别地，我指的不是 C++ 语言中的模板，C++ 模板支持的内容远超我在此所述。
我详细解释了 Reverse 函数，但还有许多其他我们可以泛型地编写的函数，例如：
- 查找切片中的最小/最大元素
- 计算切片的平均值/标准差
- 计算 map 的并集/交集
- 查找节点/边图中的最短路径
- 对切片/map 应用转换函数，返回新的切片/map
这些例子在大多数其他语言中都有。实际上，我是通过浏览 C++ 标准模板库来写下这个列表的。
还有一些例子是 Go 特有的，因为它对并发有强大的支持。
- 带超时的 channel 读取
- 将两个 channel 合并成一个 channel
- 并行调用一系列函数，返回结果切片
- 使用 Context 调用一系列函数，返回第一个完成函数的결과，并取消和清理多余的 goroutine
我见过所有这些函数被用不同的类型重复编写多次。在 Go 中编写它们并不难。但如果能够复用一个适用于任何值类型的高效且已调试的实现，那就太好了。
需要说明的是，这些只是例子。还有许多更通用的函数可以使用泛型更轻松、更安全地编写。
此外，正如我前面写到的，不只是函数。还有数据结构。
Go 语言内置了两种通用的泛型数据结构：切片（slices）和 map。切片和 map 可以容纳任何数据类型的值，并对存储和检索的值进行静态类型检查。值以其本身的形式存储，而不是以接口类型存储。也就是说，当我有一个 []int 时，切片直接存储 int 值，而不是转换为接口类型的 int 值。
切片和 map 是最有用的泛型数据结构，但它们并非唯一。这里还有一些其他例子。
- 集合
- 自平衡树，支持高效插入和按排序顺序遍历
- 多重 map（Multimap），一个键可以对应多个值实例
- 并发哈希 map，支持并行插入和查找且无需单一锁
如果我们能编写泛型类型，我们就可以定义新的数据结构，就像这些例子一样，它们拥有与切片和 map 相同的类型检查优势：编译器可以静态检查它们所持有值的类型，并且这些值可以以其本身的形式存储，而不是以接口类型存储。
也应该可以将前面提到的算法应用于泛型数据结构。
所有这些例子都应该像 Reverse 一样：作为泛型函数和数据结构，它们只需编写一次，放在一个包中，并在需要时重复使用。它们应该像切片和 map 那样工作，不应存储空接口类型的值，而应存储特定类型的值，并且这些类型应在编译时进行检查。
这就是 Go 可以从泛型中获得的。泛型可以提供强大的构建块，使我们能够共享代码并更轻松地构建程序。
我希望我已经解释了为什么这值得深入研究。
好处与成本
但泛型并非来自糖果山（Big Rock Candy Mountain），那个每天阳光照耀在柠檬水泉水之上的土地。任何语言的改变都有代价。毫无疑问，将泛型添加到 Go 会使语言变得更复杂。与任何语言改变一样，我们需要讨论如何最大化收益并最小化成本。
在 Go 语言中，我们的目标是通过独立、正交且可以自由组合的语言特性来降低复杂性。我们通过简化单个特性来降低复杂性，并通过允许它们自由组合来最大化这些特性的益处。我们希望在泛型方面也能做到这一点。
为了使这一点更具体，我将列出我们应该遵循的一些准则。
最小化新概念
我们应该尽量少地向语言中添加新概念。这意味着最少的新语法和最少的新关键字及其他名称。
复杂性应落在泛型代码的编写者身上，而非使用者
应尽可能地将复杂性交给编写泛型包的程序员。我们不希望包的使用者不得不担心泛型。这意味着调用泛型函数应该以自然的方式进行，并且使用泛型包时出现的任何错误都应该以易于理解和修复的方式报告。调试泛型代码的调用也应该很容易。
编写者和使用者可以独立工作
同样，我们应该使泛型代码的编写者和使用者能够轻松地将各自的关注点分开，以便他们可以独立开发代码。他们不应该像不同包中的普通函数编写者和调用者那样互相担心对方在做什么。这听起来很显而易见，但这并非适用于所有其他编程语言中的泛型。
短构建时间，快执行时间
当然，我们希望尽可能地保持 Go 目前提供的短构建时间和快执行时间。泛型往往会在快速构建和快速执行之间引入权衡。我们希望尽可能兼得。
保持 Go 的清晰度和简洁性
最重要的是，Go 目前是一门简单的语言。Go 程序通常清晰易懂。我们长期探索此领域的一个主要部分是试图理解如何在保持这种清晰度和简洁性的同时添加泛型。我们需要找到能很好地融入现有语言的机制，而不是将其变成完全不同的东西。
这些准则应适用于 Go 中的任何泛型实现。这是我今天想留给大家的最重要的信息：泛型能为语言带来显著益处，但只有在 Go 语言依然像 Go 的前提下，泛型才值得去实现。
设计草案
幸运的是，我认为这是可以做到的。为了结束本文，我将从讨论我们为什么想要泛型及其要求，转向简要讨论我们认为如何将它们添加到语言中的设计方案。
2022 年 1 月补充说明：此博客文章写于 2019 年，其中描述的泛型版本并非最终采用的版本。有关最新信息，请参阅语言规范中关于类型参数的描述和泛型设计文档。
在今年的 Gophercon 大会上，Robert Griesemer 和我发布了一份关于如何在 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，并成为了我们所说的类型参数。它不再是切片参数类型的一部分，而是一个独立的、额外的类型参数。
要调用带类型参数的函数，在一般情况下，你需要传递一个类型实参（type argument），它就像任何其他实参一样，只不过它是一个类型。
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 是一种静态类型语言，我们必须讨论类型参数的类型。这种元类型（meta-type）告诉编译器在调用泛型函数时允许使用哪些类型的实参，以及泛型函数可以用该类型参数的值执行哪些操作。
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 函数。这个函数返回序列 s 中 b 的索引，其中 s 可以是 string 或 []byte。我们可以使用这个单一的泛型函数来替代 bytes 和 strings 包中的这两个函数。实际上我们可能不会去这样做，但这一个有用的简单例子。
这里我们需要知道类型参数 T 的行为类似于 string 或 []byte。我们可以对它调用 len，可以对其进行索引，并且可以将索引操作的结果与字节值进行比较。
为了让它能够编译，类型参数 T 本身需要一个类型。它是一个元类型，但因为有时我们需要描述多个相关类型，并且它描述了泛型函数的实现与其调用者之间的关系，所以我们实际上将 T 的类型称为契约（contract）。在这里，该契约被命名为 Sequence。它出现在类型参数列表之后。
这就是本例中 Sequence 契约的定义方式。
contract Sequence(T) {
T string, []byte
}
这非常简单，因为这是一个简单的例子：类型参数 T 可以是 string 或 []byte。这里的 contract 可能是一个新关键字，或者是在包范围内识别的特殊标识符；详情请参阅设计草案。
任何记得我们在 Gophercon 2018 大会上提出的设计的人都会看到，这种编写契约的方式要简单得多。我们收到了很多关于早期设计的反馈，认为契约过于复杂，我们已努力将这些反馈考虑在内。新的契约更易于编写、阅读和理解。
它们允许你指定类型参数的基础类型，和/或列出类型参数的方法。它们还允许你描述不同类型参数之间的关系。
带方法的契约
这是另一个简单的例子，一个函数使用 String 方法返回 s 中所有元素的字符串表示形式的 []string 切片。
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 {
...
}
这里我们描述了一个由节点（nodes）和边（edges）构成的图。我们不要求图使用特定的数据结构。相反，我们说 Node 类型必须有一个 Edges 方法，返回连接到该 Node 的边列表。而 Edge 类型必须有一个 Nodes 方法，返回该 Edge 连接的两个 Node。
我跳过了实现部分，但这展示了一个返回 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 函数（很可能也将在标准库的某个地方）会是这样的。这里我们只是引用 contracts 包中定义的 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 的位置，或指向 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 版本提出的方案。
下一篇文章：实验、简化、发布
上一篇文章：宣布新的 Go 商店上线
博客索引