引言

这是上周我在 Gophercon 2019 大会演讲的博客版本。

本文将讨论将泛型添加到 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 方法，该方法返回一个元素。但实际上使用该方法必须返回一个空接口类型，然后我们就失去了静态类型的所有好处。更微妙的是，将无法定义一个接受两个具有相同元素类型的不同切片，或者接受一个类型为 A 的映射并返回一个相同类型 A 的切片的泛型函数。Go 是一种静态类型语言，因为它更容易编写大型程序；我们不想为了获得泛型的好处而失去静态类型的好处。

另一种方法是使用 reflect 包编写一个通用的 Reverse 函数，但这非常麻烦且运行缓慢，因此很少有人这样做。这种方法还需要显式类型断言，并且没有静态类型检查。

或者，您可以编写一个代码生成器，它接受一个类型并为该类型的切片生成一个 Reverse 函数。市面上有一些代码生成器就是这样做的。但这会给每个需要 Reverse 的包增加一个额外的步骤，它会使构建复杂化，因为所有不同的副本都必须进行编译，并且修复主源代码中的 bug 需要重新生成所有实例，其中一些可能完全位于不同的项目中。

所有这些方法都足够麻烦，以至于我认为大多数需要在 Go 中反转切片的人只是为他们需要的特定切片类型编写函数。然后他们需要为该函数编写测试用例，以确保他们没有犯像我最初那样简单的错误。他们还需要定期运行这些测试。

无论我们如何处理，这都意味着大量的额外工作，仅仅是为了一个除了元素类型不同而其他方面完全相同的函数。并不是说它做不到。它显然可以做到，而且 Go 程序员也正在这样做。只是应该有更好的方法。

对于像 Go 这样的静态类型语言，更好的方法就是泛型。我之前写过，泛型编程能够以通用的形式表示函数和数据结构，并将类型分离出来。这正是我们在这里想要的。

泛型能为 Go 带来什么

我们在 Go 中从泛型中获得的第一件也是最重要的事情是能够编写像 Reverse 这样的函数，而不必关心切片的元素类型。我们希望将元素类型分离出来。然后，我们可以编写一次函数，编写一次测试，将它们放在一个 go-gettable 的包中，并随时调用它们。

更好的是，由于这是一个开源世界，其他人可以编写一次 Reverse，然后我们可以使用他们的实现。

这时我应该说，“泛型”可以有很多不同的含义。在本文中，我所说的“泛型”就是我刚才描述的。特别是，我不是指 C++ 语言中的模板，它支持比我在这里写的内容更多。

我详细分析了 Reverse，但还有许多其他函数可以通用地编写，例如

• 查找切片中的最小/最大元素
• 计算切片的平均值/标准差
• 计算映射的并集/交集
• 查找节点/边图中的最短路径
• 将转换函数应用于切片/映射，返回新的切片/映射

这些示例在大多数其他语言中都有。事实上，我是在浏览 C++ 标准模板库时写下这个列表的。

还有一些示例是 Go 特有的，因为它对并发有强大的支持。

• 带超时的通道读取
• 将两个通道合并为一个通道
• 并行调用一系列函数，返回结果切片
• 调用一系列函数，使用 Context，返回第一个完成的函数的结果，取消并清理额外的 goroutine

我见过所有这些函数都用不同的类型写了很多遍。在 Go 中编写它们并不难。但能够重用一个高效且经过调试的、适用于任何值类型的实现将是很棒的。

需要明确的是，这些只是示例。还有许多其他通用函数可以使用泛型更轻松、更安全地编写。

此外，正如我之前写的，这不仅仅是函数。它也是数据结构。

Go 在语言层面内置了两个通用的泛型数据结构：切片和映射。切片和映射可以存储任何数据类型的元素，并且对存储和检索的值进行静态类型检查。值是按原样存储的，而不是作为接口类型。也就是说，当我有一个 []int 时，切片直接存储 int，而不是转换为接口类型的 int。

切片和映射是最有用的泛型数据结构，但它们并非唯一。以下是一些其他示例。

• 集合（Sets）
• 自平衡树，具有高效的插入和按排序顺序遍历
• 多重映射（Multimaps），具有键的多个实例
• 并发哈希映射，支持并行插入和查找，没有单一锁

如果我们能够编写泛型类型，我们就可以定义新的数据结构，如这些，它们具有与切片和映射相同的类型检查优势：编译器可以静态类型检查它们所包含的值的类型，并且值可以按原样存储，而不是作为接口类型。

还应该可以采用前面提到的算法并将其应用于泛型数据结构。

这些示例都应该与 Reverse 类似：泛型函数和数据结构编写一次，放在一个包中，并在需要时重用。它们应该像切片和映射一样工作，即它们不应存储空接口类型的值，而应存储特定类型的值，并且这些类型应在编译时进行检查。

这就是 Go 通过泛型可以获得的好处。泛型可以提供强大的构建块，使我们能够共享代码并更轻松地构建程序。

我希望我已经解释了为什么值得深入研究这一点。

优点和成本

但是泛型并非来自 糖果山乐园，那个太阳每天都照耀在 柠檬水泉 上的地方。每一次语言更改都有其成本。毫无疑问，将泛型添加到 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，并成为我们所说的类型参数。它不再是切片参数类型的一部分，而是现在一个独立的、额外的类型参数。

要调用带类型参数的函数，在一般情况下，您需要传递一个类型参数，它与其他参数一样，只是它是一个类型。

func ReverseAndPrint(s []int) {
    Reverse(int)(s)
    fmt.Println(s)
}

这就是此示例中 Reverse 后面的 (int)。

幸运的是，在大多数情况下，包括本例，编译器可以从常规参数的类型推断出类型参数，而您无需提及类型参数。

调用泛型函数看起来就像调用任何其他函数一样。

func ReverseAndPrint(s []int) {
    Reverse(s)
    fmt.Println(s)
}

换句话说，虽然泛型 Reverse 函数比 ReverseInts 和 ReverseStrings 稍微复杂一些，但这种复杂性由函数编写者承担，而不是调用者。

契约（Contracts）

由于 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 函数。此函数返回 s 序列中 b 的索引，其中 s 是 string 或 []byte。我们可以使用这个单一的泛型函数来替换 bytes 和 strings 包中的两个函数。实际上，我们可能不会费心这样做，但这只是一个有用的简单示例。

这里我们需要知道类型参数 T 的行为类似于 string 或 []byte。我们可以对其调用 len，可以对其进行索引，并且可以将索引操作的结果与字节值进行比较。

为了让它编译，类型参数 T 本身需要一个类型。它是一个元类型，但由于我们有时需要描述多个相关类型，并且它描述了泛型函数的实现与其调用者之间的关系，因此我们实际上称 T 的类型为契约。在这里，契约的名称是 Sequence。它出现在类型参数列表之后。

这是此示例中 Sequence 契约的定义方式。

contract Sequence(T) {
    T string, []byte
}

它非常简单，因为这是一个简单的示例：类型参数 T 可以是 string 或 []byte。这里的 contract 可能是一个新关键字，或者是一个在包作用域中识别的特殊标识符；请参阅设计草案了解详情。

任何记得 我们在 2018 年 Gophercon 上提出的设计 的人会发现，这种编写契约的方式要简单得多。我们从早期设计中获得了大量关于契约过于复杂的反馈，并已尽力将其考虑在内。新的契约写起来、读起来和理解起来都简单得多。

它们允许您指定类型参数的基础类型，以及/或列出类型参数的方法。它们还允许您描述不同类型参数之间的关系。

带有方法的契约

这是另一个简单的示例，一个使用 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 {
    ...
}

这里我们描述了一个图，由节点和边组成。我们不要求图采用特定的数据结构。相反，我们说 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 函数（可能也会在标准库的某个地方）看起来会是这样。这里我们只是引用了 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 的槽的指针，或者指向树中应该放置它的位置的指针。

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 未来版本的方案。